# 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 in-degree and out-degree 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.

• Could you please clarify the while loop in the second solution? How does it produce a valid Bruijin sequence?

• @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).

• The first solution is really confused. I think it is equal to start from 00..0(k-1) using decrease value(eg. k-1, k-2, ... 0) preorder.

• @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!

• Is this a Euler Circuit problem?
We do not need to cover all edges but only all nodes.

• Hierholzer's Algorithm goes every edge only once and there are kn edges. (K(n-1) nodes and each node has k out edges)

Shouldn't the time/space complexity be O(k**n) ?

• @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.

• For the first solution,
if I change "Set<String> seen;" to "HashSet<String> seen;" I get the following error "