Cracking The Safe


  • 0

    Click here to see the full article post


  • 0

    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.


  • 0

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


  • 0
    D

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


  • 0

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


  • 0
    N

    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.


  • 0
    D

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


  • 0
    C

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


  • 0
    X

    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) ?


  • 0
    R

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


  • 0
    R

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


  • 0
    J

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


  • 0
    Z

    For the first solution,
    if I change "Set<String> seen;" to "HashSet<String> seen;" I get the following error "
    Exception in thread "main" java.lang.StackOverflowError
    at java.util.HashMap.putVal(HashMap.java:598)
    "
    Anyone knows why?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.