… solved last post’s problem. Here’s the C source code.

I verified this by setting it to solve the problem for 2-digit codes and manually checking one of its answers.

It found many solutions, the first of which is here

If you want to verify that, simply do what I did in the previous post, but instead of a 6×6 grid, draw a 10 x 10 x 10 x 10 hypercube and then plot the route described above, checking that you aren’t re-visiting any cells and that you haven’t left any out. Hmm, actually a hypercube is tricky to draw with a regular pen, so you could try a 100 x 100 grid.

I aborted the run when the file of solutions reached 2GB so it’s fair to say there are a few solutions. I set my computer figuring out how many solutions, but as I did that at the same time as trying to open the 2GB file in EditPad, not much happened for a while until I opened taskmanager and clobbered their heads together.

Using this method, you would find my alarm code in about 1/2.3085 the number of keypresses than if you had to press enter after each try. Hmm, that’s possibly enough information for you to figure out my alarm code…

At work, you have to enter four digits and hit the enter key to get in. This means there are 10,000 combinations to try (count them, 0000 to 9999). Locks like this would be very hard to crack without resorting to other means like tricking people into telling you the PIN, or simply ringing the doorbell and blagging your way in. To try all the combinations is ( 4 digits + enter ) x 10000 = 50000 keypresses.

With my home alarm, all you need to do is type the correct four keys in order, no enter key. If my alarm code was 1234, I could type 1261234 and the alarm would disarm. This is handy if I mess up my keying, I can just start again, but it makes it easier to crack. By typing 1261234 I have tried combinations 1261 2612 6123 and 1234. After my first attempt, I need only hit one more key to try another 4-digit combination. This COULD make my alarm 1/5th as hard to crack as my work alarm, with only (3 initial digits) + (1 per combination x 10,000 combinations) 10,003 keypresses needed to try all combinations.

That’s IF I can try a whole combination with every subsequent keypress. If I go 0000,1, 0002, 0003, 0004, 0005, 0006, 0007, 0008, 0009 then I’ve already tried 37 combinations, but I can’t go 0010 next as that’s already been tried (when I hit the first 0 of 0001). What should I choose as my next combination? the lowest that’s not been tried yet? 0011 is next, but that means I’ve not tried 9000. Can I be sure I will get the chance to try that later?

Part of my mind has been trying to formulate a proof or disproof of this for some time. Maybe cutting down the problem will offer some insights. If my alarm only had digits 0 to 5 and a two-digit passcode, could I test all 36 combinations in 37 keypresses? The answer is yes.

( by typing 00102030405112131415222324253343544550)

The first digit of any number but the first has to match the last digit of the previous number. The blue arrow starting at 00 follows a path taking the smallest available number with a permitted first digit. Then it has to avoid 50 because that would force the next number to start with 0 but we have used up all the 0 row. So we pick 51 instead with the first red arrow. As luck would have it, we can complete this and it happens to be a cycle - in a single valid move we can get back to the start. This is a bit of a red herring though, because it does not have to be a cycle to be a solution, so I’ve not drawn that arrow on there.

This is like having a set of dominoes, and setting them all out with matching numbers adjacent. Hooray!

So let’s expand the problem. What about with 3-digit passcodes? Um… we now have a cube instead of a square chart, and it doesn’t behave like dominoes at all…

I *think* I could write a prolog program to figure this out, but I can’t be sure it won’t use up all the memory on my machine before it finds an answer.