All About Programming: Crack a Keycode

Crack a Keycode – AlgoBox by dietpepsi

Say you have a keypad that has keys for the numbers 0 through 9 and the correct code is some sequence of 4 digits. This keypad does NOT reset after entering an incorrect sequence of 4 digits. ie. If the correct sequence is 1234, entering 751234 will succeed in opening it because it ends in the correct sequence. If the keypad actually resets after every 4 digits pressed, then it would not succeed b/c it would interpret the above sequence as “7512” then “34”.

Write an algorithm that will try to find the correct code for this keypad. Assume you have an API similar to KeyPad.pressKey(int n) where you pass in a number (0…9) and it returns true if the keypad unlocks and false if it’s still locked.
Generalize your algorithm to work for a keypad where you don’t know the length of the correct sequence in advance.

Note:
You could easily enter all digits of all numbers 0000 through 9999 resulting in 4*10000 key presses, but remember that the panel does not reset after every sequence of 4 digits, so find a way to do this more efficiently.

Think of this keypad as remembering the last 3 keys pressed (and the order pressed); when the next key is pressed, if the last 3 keys + the current key equal the correct code, the keypad will unlock. Assume the keypad does all this internally, so you can just keep feeding it keypresses and it will eventually unlock if the last 4 keys entered is the correct code.

Solution

There are three methods to solve this problem.

Method 1

Consider each three keys combination as one vertex. Then there are 1000 states altogether representing all the possible overlappings between each two consecutive four digit keycode. Then for each vertex, it has 10 directed edges from the vertex to 10 vertices. Such an edge representing a possible keycode combination. In the graph, if we can find a Euler Circuit then that would be our answer. Because it travels each edge once and only once, it goes through all possible keycode combinations with not duplicates.

The method of finding a Euler path is a DFS algorithm called Hierholzer’s algorithm. The idea is following:

Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
As long as there exists a vertex u that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from u, following unvisited edges until returning to u, and join the tour formed in this way to the previous tour.

The time complexity for this $O(E)$ . The problem is it will cause stack overflow error for (10, 4) by default memory settings (-Xss1m).