|
I solved it! And it is great!! The infamous "two switches" puzzle does have a solution, and it isn't a trick; it is a pure logic puzzle. Actually it is a great logic puzzle, because after you work out the solution, you discover a little teeny crummy thing that makes the solution not the solution, and then you have to figure out a way around it. Excellent.
So, first, here's the puzzle [ courtesy of techInterview ]:
The warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.
"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the 'on' or the 'off' position. I am not telling you their present positions. The switches are not connected to anything.
"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none either. Then he'll be led back to his cell.
"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.
"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'we have all visited the switch room' and be 100% sure.
"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."
What is the strategy they come up with so that they can be free?
I actually think this puzzle is too hard to give in a technical interview. Perhaps many of you are thinking "what's he talking about, that puzzle was trivial" (!) But for me this was a three-bike-ride puzzle, and although some candidates might really enjoy puzzling it out, to expect them to figure it out in fifteen minutes is unrealistic. (As we noted before in Moving Mount Fuji, you want to use puzzles which all good candidates can solve, so as to detect bad candidates.)
Okay, on to the solution. First let me give the "correct except for a little teeny crummy thing" solution:
The Almost Right solution
The prisoners get together and nominate one prisoner as the "leader". All the other prisoners are equivalent. The leader is going to count how many different prisoners have visited the switch room. When the count equals the number of prisoners, he goes to the warden and says "all the prisoners have visited", and everyone goes free. Here's the strategy for the followers and the leader:
Visit by a follower:
- If switch A is on, toggle switch B.
- If switch A is off and you have not previously toggled switch A, toggle it on, otherwise toggle switch B.
- If switch A is off and you have previously toggled switch A, toggle switch B.
Visit by the leader:
- If switch A is off, toggle switch B.
- If switch A is on, toggle it to off. Increment the count of prisoners.
That's it! Each prisoner will toggle switch A on exactly once. Only the leader can toggle switch A off, and he will count each time he does so. Each time switch A is on it means a different prisoner has toggled it. When the count equals the number of prisoners, you're done!
This works because only the leader turns switch A off. Only the followers turn switch A on, and they only do it once each. The key is that each prisoner can remember whether they've previously toggled switch A. Each time the leader turns switch A off, one more new follower has visited.
Note that the switch room basically has one state, held by switch A. The only purpose of switch B is to give each prisoner something to toggle if they don't want to change the state of switch A.
Make sure you understand my convoluted explanation before going on. Hopefully you will have clear that the switch room holds one state, and how the leader and the followers interact.
The problem with the Almost Right solution
A key complication in the puzzle is that the initial state is not known. If the initial state were known - let's say the switches were both off - then there would not be a problem, and we'd be done. But this complication actually means the strategy outlined above won't work exactly right. Here's why. The initial state of switch A can be either off or on. If switch A is off, there is no problem. If a follower visits first, they'll toggle switch A on, and when the leader visits, he'll toggle switch A to off and the count will be one. If the leader visits first he'll do nothing since switch A is already off. All will be cool. But if the initial state of switch A is on, then there's a problem. Nothing will happen until the leader visits, and he'll toggle switch A off and set the count to one. But - his count will be off by one! The leader cannot tell the difference between 'initial state off, one follower visited' and 'initial state on, zero followers visited'. This matters because if the leader is off by one, he'll either wait forever for a last follower who doesn't exist (prisoners remain prisoners), or he'll tell the warden everyone has visited when one prisoner still hasn't (prisoners fed to alligators). So - what to do?
The crux of the complication is that the leader can't know whether the first "switch A on" was created by a follower. So the solution has to be - nobody can do anything until the leader has visited at least once.
The Right solution
The prisoners get together and nominate one prisoner as the "leader". All the other prisoners are equivalent. The leader is going to count how many different prisoners have visited the switch room. When the count equals the number of prisoners, he goes to the warden and says "all the prisoners have visited", and everyone goes free. Here's the strategy for the leader and the followers:
Visit by a follower:
- If switch A is on, toggle switch B.
- If switch A is off and you have not previously toggled switch A, and you have previously seen switch A on, toggle it on, otherwise toggle switch B.
- If switch A is off and you have previously toggled switch A, toggle switch B.
Visit by the leader:
- If switch A is off, toggle it on.
- If switch A is on, toggle it off. If you did not turn switch A on during your previous visit, increment the count of prisoners.
The additions to the strategy are italicized. Each follower must remember two things, 1) whether they've seen switch A on during any previous visit, and 2) whether they've previously toggled switch A. They must have seen switch A on before toggling it on themselves, and they will only toggle it on once. The leader must remember two things also, 1) whether he toggled switch A on during his previous visit, and 2) the current count of followers who have toggled switch A.
To see how this handles the initial state complication, let's consider the possibilities. If the initial state of switch A is off, then nothing will happen until the leader visits, because no follower will have previously seen an on state. If the initial state of switch A is on, then again nothing will happen until the leader visits, because only he can turn switch A off. Since nothing happens until the leader visits, the initial state ambiguity is settled; the leader can be sure that the state of switch A has not been disturbed since the start.
So there you have it - a terrific logic puzzle, with a depth that is belied by the apparent simplicity of the situation. Note that the solution would be the same no matter how many prisoners there were - I don't know if asking the question with 1000 prisoners or n prisoners would have made it easier. (Somehow the number 23 suggests a specific value, doesn't it?)
| 
