[Community Puzzle] Entry code

Puzzles
#22

Because “0001011100” contains every possible combinations :

  • 000
  • 001
  • 010
  • 011
  • 100
  • 101
  • 110
  • 111
1 Like
#23

And why is it 10 but not 9 or something like 3*n ? Ex : 9, 12, 15, … Here, I still take x = 3.

If it’s just the combination of all possibilities, it must be 3 times something… But I don’t understand, why it’s 10 instead. (for x = 2 and n = 3).

x( x’( x’(

#24

The length of 10 is easy to understand :

  • you try the first combination : 000 (length = y)
  • there are x^y combinations, you tried one so there are x^y-1 missing.
  • every new number test a new combination, so you add x^y-1 numbers
  • the total lenght is y + x^y - 1 => 3 + 2^3 - 1 = 3+8-1 = 10
2 Likes
#25

Ah, thank you… :grin: :grin: I understand now…

#26

I went about solving the problem by creating all the combinations of strings and then creating a graph and creating a relation between entities whose last characters are the same as the fist characters of the other string, thus creating a directed graph (eg. 000 → 001 as “00” is consistent). Then I take the beginning of the graph as “000” and draw a route that make sure to get to each string without creating loops.

I have gone through all the tests and the only one I cannot seem to pass is the one with lots of digits, due to none optimization I believe. How can I make my process faster?

2 Likes
#27

Problem Solved :heart_eyes::fire::sob: 100%

#28

I did not really write it in Graph. I know it is too long and too slow.
But to think it in Graph is interesting.

When you have got to know that 000->001, did you try 002 (or 010?) on each node (both 000 and 001?)

#29

This might help if you’re stuck: de Bruijn sequence - Wikipedia
At least that partially helped me (still not solved, seems some mistake in implementation, but the idea was quite helpful)

3 Likes
#30

I agree. It can be solved with simple algo (complexity O(n)}, if we find the pattern

#31

Tips: Lyndon word

1 Like