# Cracking the safe

The following problem appeared in The Riddler and it’s about finding the right code sequence to crack open a safe.

A safe has three locks, each of which is unlocked by a card, like a hotel room door. Each lock (call them 1, 2 and 3) and can be opened using one of three key cards (A, B or C). To open the safe, each of the cards must be inserted into a lock slot and then someone must press a button labeled “Attempt To Open.”

The locks function independently. If the correct key card is inserted into a lock when the button is pressed, that lock will change state — going from locked to unlocked or unlocked to locked. If an incorrect key card is inserted in a lock when the attempt button is pressed, nothing happens — that lock will either remain locked or remain unlocked. The safe will open when all three locks are unlocked. Other than the safe opening, there is no way to know whether one, two or all three of the locks are locked.

Your job as master safecracker is to open the locked safe as efficiently as possible. What is the minimum number of button-press attempts that will guarantee that the safe opens, and what sequence of attempts should you use?

Here is my solution.
[Show Solution]

## 3 thoughts on “Cracking the safe”

1. @sopanj says:

Huh. You say “I don’t believe there is an efficient way to solve the problem” and “Finding such a winning sequence is challenging to do without a computer.”

But I think I have an elegant solution that avoids a brute force search, both for the way I interpreted the problem (we need to check the initial state) and the way you did.

As you point out, there are eight states of the locks, and six possible key patterns. The key patterns can be divided into two sets, each set containing the circular-shifted versions of its elements. In other words, Set 1 = {ABC, BCA, CAB} and Set 2 = {ACB, CBA, BAC}. Assume without loss of generality that ABC is the correct pattern of keys for the locks. That means that ABC will toggle all three locks. But the other two patterns in Set 1 (BCA and CAB) will not work in any lock, and so using these patterns — both of which are circular-shifted versions of ABC, the correct pattern — will not toggle ANY lock, thereby leaving the state unchanged. Meanwhile, each of the three patterns in Set 2 will toggle EXACTLY one lock: ACB will toggle lock 1, CBA lock 2, and BAC lock 3. (Again, this works w/o loss of generality.)

As for the states: instead of assigning 000 to be all three locks locked and 111 all three unlocked, we can arbitrarily assign 000 to be the initial state of the three locks (whatever it happens to be). Then our task is simply to step through all 8 of the states; we really don’t care which pattern happens to correspond to a fully unlocked state.

It should be obvious that Set 1 can reach ONLY states 000 (initial state) and 111 (all locks toggled). By contrast, each key pattern in Set 2 toggles EXACTLY one lock at a time. That’s useful, and the only way we can get to the other 6 states.

So let’s assume we correctly pick Set 2, i.e., the set of circular-shifted key patterns each of which toggles exactly one lock. A 3-bit Gray Code is the obvious way to traverse the states while toggling exactly one lock at a time. But we don’t actually need or want a true Gray Code, i.e., one in which the final state is also just one toggle away from the initial state. Rather, for reasons that will become clear later, we want to END our pattern on 111 and traverse only 7 states — i.e. we do NOT want to check the initial state, state 000, at this stage. So we modify the last three states of a traditional 3-bit Gray Code to get our traversal pattern: 000, 001, 011, 010, 110, 100, 101, 111.

So here are the steps:
1. BAC (takes us to 001)
2. CBA (takes us to 011)
3. BAC (takes us to 010)
4. ACB (takes us to 110)
5. CBA (takes us to 100)
6. BAC (takes us to 101)
7. CBA (takes us to 111)

Now we’ve gone through 7 states in 7 steps! The only state we have not checked is the initial state, 000. Also note that as long as we’ve picked Set 2 (i.e., the set containing the pattern of keys each of which toggles exactly one lock), this pattern can be generalized:

1. [pick any pattern] — it’ll toggle exactly one lock, call it lock alpha
2. RIGHT circular-shift — it’ll toggle a different one, call it lock beta
3. LEFT circular-shift — it’ll toggle alpha again
4. LEFT circular-shift — toggle lock gamma
5. LEFT circular-shift — toggle beta
6. LEFT circular-shift — toggle alpha
7. RIGHT circular-shift — toggle beta
As you can see, as long as we’ve picked Set 2, we can traverse all 7 states and end with each of the three locks toggled with respect to their initial states; i.e., we will end in state 111.

But what if we picked the “wrong” set, i.e., Set 1? Then instead of having traversed 7 states, we will have simply gone back and forth between 000 and 111, ending in state 111. (We know this because each pattern was used an odd number of times — either 3 times or once.) So then we need to grab the other set and go through the pattern again, although this time we need to check only 6 states, not 7 (because we know, by virtue of having picked the wrong Set the first time, that we’ve already checked 000 and 111). And as it turns out, we can use the same pattern because we’re just toggling (or, as you put it, XORing) the various locks, so the same pattern above that took us from 000 to 111 will take us from 111 to 000. This is one reason we want the pattern to end on 111. Another is that it means the last state to be checked (000) has already been checked by our first go-round using Set 1, so we can truncate this attempt at the 6th step. These 6 steps, plus the initial 7 steps, means 13 steps total.

There is a corner case: What if we picked the right set (Set 2) the first time, but the safe was actually unlocked to begin with (i.e., state 000 was the correct one)? This is another reason it’s important that we end our 7-step pattern on state 111. After we complete the 7 steps, and the safe doesn’t open, we would then pick the other set (Set 1) and repeat the pattern, as described above. But remember Set 1 simply toggles all three locks or none at all. So ending on 111 the first time around (with Set 2) guarantees that we will eventually hit 000 when going through the pattern above using Set 1 (by no later than the fourth step). So if we picked the right set, we will reach a solution in 11 steps.

To summarize, here is the algorithm to solve this in 13 steps, assuming we do need to check the initial state:
1. [pick any pattern]
2. RIGHT circular-shift
3. LEFT circular-shift
4. LEFT circular-shift
5. LEFT circular-shift
6. LEFT circular-shift
7. RIGHT circular-shift
8. [pattern in #1, but with the last two keys swapped. So if #1 was ABC, now use ACB]
9. RIGHT circular-shift
10. LEFT circular-shift
11. LEFT circular-shift
12. LEFT circular-shift
13. LEFT circular-shift

What if we don’t need to check the initial state? Can we modify the algorithm above to do it in 12 steps? Yes!

The key here is that if we know we never need to check 000, then we should exploit the quality of Set 1 — that it can toggle all 3 locks — to test states OTHER than 000 or 111. In other words, we should modify our state-traversal pattern so that it covers only 6 of the 7 states we need to cover and ends on a state that, when all three locks are toggled, results in a state we did NOT already traverse. This one will suffice: 000, 001, 011, 111, 110, 100, 101. The only state we don’t check is 010 — the inverse of the state we end on.

So our pattern for this is:
1. BAC [takes us to 001]
2. CBA [takes us to 011]
3. ACB [takes us to 111]
4. BAC [takes us to 110]
5. CBA [takes us to 100]
6. BAC [takes us to 101]

Then, when we use Set 1, as long as we try each key pattern, we will eventually hit 010, thus covering all the states.

But what if we accidentally picked Set 1 to start? Then we will toggle between states 000 and 111, ending in one of those two states. This time we don’t know which one because one of the key patterns is used an even number of times. (Is there a state-traversal pattern that could solve this? Maybe! But as we’ll see it won’t matter.)

Since we’re in either 000 or 111, and we need to cover the other 6 states, we can actually just reuse the state-traversal pattern we developed in the first version of the problem.

So the full pattern is:
1. [pick arbitrary pattern]
2. RIGHT circular-shift
3. RIGHT circular-shift
4. RIGHT circular-shift
5. RIGHT circular-shift
6. LEFT circular-shift
7. [pattern in #1, but with the last two keys swapped. So if #1 was ABC, now use ACB]
8. RIGHT circular-shift
9. LEFT circular-shift
10. LEFT circular-shift
11. LEFT circular-shift
12. LEFT circular-shift

And that’s how you can get the answer without brute force.

In fact it appears the solutions above will each generate 6 answers (one for each starting condition). If in the step where you switch Sets you swap the first and second keys or the first and third keys (instead of the second and third keys), you get 12 more solutions. And I believe that you can invert all the RIGHT and LEFT circular shifts to get a symmetric set of solutions, and that the RIGHT/LEFT inversion can be applied independently to each Set. So that means there should be a family of 72 solutions.

In fact to generate your solution, we should: start with pattern ABC, invert the RIGHT/LEFT for the first six steps, swap the second and third keys for the pattern in step 7, and maintain the RIGHT/LEFT as I have it for steps 8-12.

1. Diarmuid Early says:

Beautiful solution, sopanj!

2. Jason Weisman says:

Fantastic analysis and very clear presentation! Thank you very much for this!! Regards, Jason