Cracking The Safe


In approach #1, the Python code is missing the function name. And this doesn't sound right:
we should expect intuitively that taking any path greedily in some order will probably result in an Euler path. Actually, this intuition is also a theorem: any connected directed graph where all nodes have equal indegree and outdegree has an Euler circuit
The theorem only says that an Euler circuit exists, not that you'll probably walk one by greedily randomly walking around.

@ManuelP Thanks for the corrections. I will think about how to amend the article to discuss the intuition behind Hierholzer's algorithm, with edits coming later.

@dcx9306 Basically we want the cycles of some permutation. The while loop is just finding a cycle and recording the cycle as we proceed. I will explain this better during the rewrite, but basically imagine the permutation is like [0, 3, 1, 2, 4]. We will record the cycles in order: (0) (1 3 2) (4).

@awice Thanks awice! I did write it down. But I don't think it's just simply S'>S mapping as mentioned in the article. I can't figure out why it's a valid Bruijin sequence. Is there any proof for the soundness? I appreciate it!

@chen806
It is a Euler Circuit problem on an (n − 1)dimensional de Bruijn graph.
So we need to cover all edges, not only all nodes.

@awice
In the second approach, why do we need to append zeros at the end of the algorithm?
Thanks.

@ryx for the second solution I think the reason the zeroes are appended is that the de Bruijin sequence allows substrings to wrap around but the safe cracking problem does not.