Homework 7: Combination Lock
This puzzle was shown to me long ago - I forget the original source.
For this homework assignment, we are going to rob a bank.
Imagine that the bank’s vault has a keypad on which you can enter a 4-digit code. This keypad is fairly insecure because it does not care how many digits there are before the correct code - as soon as the correct code is entered, the vault will open.
For example, if the correct code is “1234” and we enter “981234”, as soon as the “4” is pressed, the vault will open because “1234” was entered, regardless of the “98”.
It is possible to punch in every 4-digit code in order, but there is a more optimal way, since codes can overlap. The 8-digit sequence “12345678” contains 5 different codes: “1234”, “2345”, “3456”, “4567”, and “5678” - if any of those were the correct code, the vault would have opened sometime during the entering of “12345678”.
Your task is to write a program that produces the shortest sequence of digits that, when entered on the keypad, is guaranteed to open the vault. In other words, come up with some sequence of digits that contains every 4-digit code somewhere in it.
For bonus points, generalize your program to take in as an argument the number of digits in the code, N, and produce a sequence of digits that includes all N-digit codes.
Hint: For a given N, the shortest sequence of digits that includes all N-digit codes has length (10^N) + N - 1.
Your program should handle N up to 6.
Examples:
./safecrack 1
0123456789
./safecrack 2
00112233445566778899879768696575859546474849435363738393242526272829213141516171819102030405060708090
Note the solution is not unique. You can test your solution by ensuring its length is correct and every N-digit number exists in the output.
You may do this using the language of your choice. I encourage you to solve it in a language you would like to learn, rather than one you are an expert in, to broaden your horizon.
Bring your solution to our April meeting.
Feel free to discuss the problem or any other topics you are interested in on our mailing list (accessible via our Meetup Group).