Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @Eniidras,validated by @Snef,@LittleDarkBug and @Westicles.
If you have any issues, feel free to ping them.
In case anyone is interested in some of the math behind this puzzle, Ian Stewart wrote an article for āPour la Scienceā (the French translation of āScientific Americanā, mostly) with the (English) title āThe Autovoracious Ourotorusā. You can find it republished in Stewartās Game, Set and Math (1989) where he talks about an idea that connects:
- A mythical serpent of ancient Egypt.
- An alchemical symbol.
- Kekuleās discovery of the benzene ring.
- An Indian theory of rhythm, a thousand years old.
- The seven bridges of Konigsberg.
- The theory of telephone circuits.
- Radar maps of Venus.
Not bad, for 12 1/2 pages written for nonprofessionals, huh?
6 Likes
Thank you, I already solved it but now I think I can do a better code
Good puzzle. But for existing constraints itās simple to solve by ābrute forceā.
In my opinion, for biggest āxā and ānā (when the list of all combinations is large for creating and keeping it in memory) we should build solution-tree and get answer after pass the tree. It will be more harder.
1 Like
Does it always have to be harder?
PS: I know, I know. āThatās what she saidā 
3 Likes
I generate a list of all possible codes, then using backtracking to generate all possible sequences, then find the min sequence. During backtracking, I cut off the code which add more than 1 to the length.
Appearently, this algo is not performante enough. I got only the 2 first simple cases pass. Do you have any hints on how can I improve. Thank you.
Coincident?
1 Like
Hey!
I donāt know if you have any fundation in graph theory, but this problem can be re-written as finding a euclidian path within a directed graph. I wonāt give you all the answers, so for now, you are going to have to figure what the nodes and edges would be.
Maybe a small hint, though: each node is of the same degree (both in and out) as the number of keys on the keypad.
Finally, what would happen with a greedy algorithm?
If you want to strictly work off of your code, look at the solutions you find. What are their lengths?
You will find that they form circular sequences. This means that you can fix the start of the sequence (To what should you fix them to have the smallest number overall?), and remove a lot of symetry within the problem.
Please keep in mind that the numbers of solutions possible can be prohibitively big.
With a two digit code and 2 possible values, the possible codes are 00, 01, 10 and 11.
The optimal chain is 00110.
By removing the symmetry and forcing to start with 00, you avoid the following sequences: 01100, 11001, 10011.
With a 3 digit code, you have the optimal solution as 0001011100.
Removing the symmetry avoids: 0010111000, 0101110001, 1011100010, 0111000101, 1110001011, 1100010111, 1000101110.
but you also have solutions changing the order in which codes are explored:
0001110010, for example. Can you see it being similar to another one above?
How could you avoid going through it as a potential solution? Could you do that while constructing the solution?
Hope this helps!
9 Likes
Thank you VCO-NSide.
Iām new to graph theory, Iāll do some study on euclidian path.
My issue with the backtracking was that the search space is too big. For d = 2, n = 3 (d: digit code, n: length), there are 8 codes, and the total search space is 8! = 40320.
With elderlybeginnerās hint, I was able to reduce the search space a lot so that the test cases were pass. What I changed is that in my backtracking algo, I just need to find one sequence rather than all possible sequence. And I need to make sure this sequence is the smallest one.
To make the sequence shortest, I suppose that the length of the answer should be (n + d^n - 1) (d: digit code, n: length) which means that every time when I append a new code to sequence, the length should be added only 1.
To make the sequence the smallest, I ordered the codes by its value.
Anyway, Iāll try your proposition about rethink the problem as a graph
Yeah, we could make this problem more difficult, but it was my first contribution, so I just wanted to publish a simple puzzle so I was constrained by an unique answer with 1000 or less characters. For me it was complicated enough to be interesting. And in my opinion, you still need quite a clever ābrute forceā solution to pass all the tests.
Thanks for the feedback !
2 Likes
Bruteforce was way to slow for me.
I donāt see graphs there either.
Itās solvable within a few lines with product and string manipulation. Just find the pattern.
1 Like
In my experience, graphs were what I implemented in Java (with a full explanation of what and how), and what enabled me to get one property based on the algorithm I used for euclidian pathsā¦ to then get the full solution in python within a few lines of code.
If I could submit two java solutions, Iād submit a version of my python one, as it is much simpler and more elegant, however Iām afraid it might be hard for reviewers to see why it works.
Honestly, I might anyways rewrite my java code for a more elegant version, getting rid of the background graphs and only keeping the main part.
Yeah. You are right. It wasnāt a criticism, just some thoughts. Anyway itās interesting medium (not easy!) puzzle. Thanks!
1 Like
Hi!
You donāt have to compute all the possible sequence : there is a simple way for your backtracking to directly generate the smallest one.
You may also assume that a smallest sequence always begin by āā00ā¦0āā.
I would like to share some thoughts. So far I have been like Salanger, obtaining the first two tests using an algorithm that was near bruteforcing.
My intuition is that for the algorithm to run in a decent amount of time, you have to make it pretty simple. And when speaking of a way to eliminate some cases, that would not be a small amount or even half. The algorithm has to eliminates 95% of the bad cases to reach the correct solution in the allowed time.
The requirement to find the lowest possible number is probably the biggest hint if I am correct
Another thing that bugged me was that I could not figure in the simple cases how a human would do using its brain to reach the correct solution. But I think I may have found out what a human would do for the ā2 3ā example.
EDIT: I have found out that my algorithm is wrong (but not too far). I am still hiding it just in case
Summary
- list all combinations: 000 001 010 011 100 101 110 111
- start with the lower one as your solution string: 000
- Notice that the combinations are naturally sorted from lowest to biggest
- go through all combinations and for each
4.a) check if the combination is already in your solution string and if yes, skip to the next
4.b) if the combination is not here yet, add the required digit to make it be there. For example for ā001ā to be in ā000ā you just have to add a ā1ā and it becomes ā0001ā.
with this algorithm, you will reach the result of 000101100111. Which is not correct, but not so far.
My next guess is that the āgreedy algorithmā stuff that VCO-NSide mentioned earlier might finally takes some sense when I think how I could rework the algorithm to make it work
All solutions that I have tested with Python, including mine, fail rapidly, for example if there are 10 different digits and the length of the code is 3 or more. Code error :
"RecursionError: maximum recursion depth exceeded in comparison"
How would it be possible to go round this problem ?
Try sys.setrecursionlimit(100_000), default is 1000.
1 Like
Thank you for the tip! Now, Iām getting this error:
Segmentation fault (core dumped)
1 Like
For a period of time I was unable to understand this puzzle because it mentions āentry codeā.
It assumes if the entry code is 234, and if one presses ā1234ā, the door will unlock.
Where in the world have a security system as foolish as this one?
In real life, people have to press ā234ā and then āEnterā to unlock.
ā12345ā will not unlock.
ā1234ā + āEnterā will not unlock neither.
āFinding a shortest string that contains all possibile combinationsā is good enough to define the problem.
The first paragraph added no value but difficulties in understanding, imho.
I donāt understand. why the length of the sequence for the example with x = 2 & y = 3 is equal to 10?