Fog Creek Software
Discussion Board




switch puzzle answer (spoiler)


I've looked at it from a bunch of angles and it seems like it's only possible to communicate 1 bit of information per visit to the switch room.  It's actually worse than that, because there is the issue of communicating it to the right person/persons and not just the prisoner following you.

So here's what I think is the best solution.  You choose one person of the 23 to be the counter.  Everyone else takes turns trying to communicate with the counter.  This means, on average, it takes 23/2 turns for the counter to recieve a message that is sent by another prisoner.  Messages are communicated with the first switch.  The second switch simply allows the state of the first switch to remain the same when a prisoner is forced to alter one of the two switches.  Only one prisoner can communicate at a time.  The job of a prisoner who is not communicating is to retain the state of the communicator's message.

Procedure for the normal (non counter) prisoners:
-If you haven't sent a message to the counter and switch a is off, turn it on.  You are now transmitting your message that you have been in the room.
-If switch a is on, someone else is communicating.  You must wait and allow that communication to occur by toggling switch b.
-If you have already sent a message, your job is done.  Toggle switch b and retain the state of communication.  Never send more than one message or risk horrible bloody alligator death.

Procedure for the counter:
-Start counting at 0.  Make sure to count 1 for yourself the first time you go to the room.
-If switch a is on, add one to your count and acknowledge reciept by turning switch a off.  One more prisoner has communicated that he/she has visited the room.
-If switch a is off, you are still waiting for a communication.  Toggle switch b.
-If your counter hits 23, you know for sure everyone has visited the room.  The alligators starve and you can all go home.

Speed:
On average, it takes 11.5 turns for the counter to first visit the room.  That's your first 2 counts.  You have to factor in the time it takes for the next messanger to begin a message.  I think it works out to about 42 more turns (sum n from 22 to 1 of 23/n/2).  Then it takes 11.5 turns after each message is sent for it to be recieved by the counter.  So thats 253 more turns.  So the total is about 307 turns on average (If my lame-o statistics aren't goofed up).

Thoughts:
I keep thinking there must be some reason for 23 to be chosen as the number of prisoners.  It's prime, of course, so I keep thinking there might be some clever way of solving this using some remainder theorem.  What's frustrating is that there problem as stated doesn't allow us to use the passage of time to draw more data from the switches.  None of the prisoners know how many times the room has been visited, since they aren't visited at regular intervals.  Otherwise, you could probably use the switches as some sort of clock, advancing it except when you first go to the room.  The prisoners would then be able to tell how far the clock lagged behind the amount  of times the room was visited.  They could then make a quicker deduction of how many of the prisoners had visited the room at least once.

The impatient and gambling prisoner could also just weigh the probabilities.  I imagine after you have visited the switch room 12 or 13 times you have pretty good chances that everyone else has been there at least once.  Again, I think you could make a better estimate if you knew how many times the room had been visited.  Even so, that still only gets you down to 275-300 turns.  I think I'd wait a little longer and be sure.

Jason Striegel
Wednesday, April 23, 2003

I would have simply guessed all prisoners will refuse to go. Therefore none will ever have gone. All have visited the same amount.

Barny
Thursday, April 24, 2003

You're very close... only problem is that when the 'counter' goes into the room... switch A could have RANDOMLY been in the ON position.  He would count a person, but no one actually switched it on.

Michael H. Pryor
Thursday, April 24, 2003

Yeah you did have the right idea but you should have every prison go through twice so that if the first ON position was random there is a double check. 
If you don't count yourself you have 22 people to check say the first one isn't a dud.  Then you have 44 ons telling you You aren't gator bait.  say it is a dud then you would have 45 ons.  either way you are damn sure that you aren't something's bad breath.
Not double checking has screwed me up enough times to know now that I have to do it with everything.

Michael Lee King II
Thursday, April 24, 2003

The solution to the problem is as follows:
a) one person is assigned the task of counting - he watches switch A and, every time he finds it in the "UP" position, turns it down and adds one to his count.

b)all other prisoners are to do the following two times and two times only: if switch A is down, then turn switch A up. Otherwise toggle switch B.

c) the "counter" declares that all have visited the room when his count goes to 44. For N prisoners, the count at which freedom is declared is (N-1)*2.

A chart (which we imagine is kept by the counter) will illustrate. Assume N=6, so there are 5 other prisoners than the counter:
          1|2|3|4|5|
          ==========
1st Visit  X X X X X
2nd Visit  X X X X

The counter fills out the chart, from left to right, top to bottom, marking an "X" each time he finds the switch in the UP position. For now, we assume that an X indicates that a prisoner(other than the counter) has visited the room. At least one row of X's must be filled out before declaring freedom. But that is not enough because...

it is possible that any X in the first row (e.g., Visit 1 of prisoner 5) was not really a visit, but that the initial setting of the switch was UP when the counter entered the room for the first time. So we cannot trust the first row completely.

In the above chart, adding one more X (Visit 2 of prisoner 5) ensures that both rows are completely filled. Now we can be certain that each prisoner visited at least once.

In summary, if we fill out *both* rows then we are assured that, for each prisoner, at least one "X" was the result of his turning switch A up.

Michael D. Kersey
Thursday, April 24, 2003

Consider the scenario:

1. Switch A is"UP" initially. Switch B position does not matter.

2. Consider, the following sequence of people being taken.

1 2 6 1 6 1 6 1 6 1

where 6 identifies the counter.

Going by the rules which is suggested, it appears that the counter reaching ( 6-1) * 2 would not ensure that all the people have gone at least once.

As suggested, 6 ( counter) would put swich A DOWN and 1 would put switch A UP.

Could you please explain this scenario by your rule.

Learner
Friday, April 25, 2003

How about each prisoner leaves their left shoe in the switch room.  When someone counts 22 shoes, all prisoners have visited the room... :P

Solid
Friday, April 25, 2003

The switches form 4-state space:

(State 4) <----------> (State 3)
  |                    /|\
  |                      |
  |                      |
  |                      |
  \|/                    |
(State 1) <----------> (State 2)

  Given this set of states it is easy to see that if everyone allowed to make a 2->3 transition only once and only one (the Counter) is allowed to make a 4->1 transition, the Counter will be able to make 22 transitions only after all other 22 prisoners have performend their 2->3 move.
  This would've been great if only the starting state was known - whether it was on the upper (3,4) or lower (1,2) state. The problem is that when the counter first finds the swithes in state 3 or 4 he does not know whether this has been their initial position or someone have flipped them from 2 to 3. So to remedy this - here's what should be done:

  Each prsioner is allowed to move the swiches so that the
transition is made from State2 to State3, but each is allowed to do that ONLY ONCE and ONLY AFTER he has performed a move 4->3 or 3->4 - i.e. he has seen a state
from the upper row of states.
  The transition from State4 to State1 is allowed to be performed only by the Counting prisoner. He and only he is allowed to make the 2->3 transition as many times as he pleases, but whenever he makes a 2->3 transition he does not count the 4->1 transition. If he is not the one that made the 2->3 transition he DOES counts the 4->1 transition. When his count reaches 22 - he declares that everyone has been in the room.
  This way when the counting prisoner first enters the room and finds the switches in one of the states 3 or 4 he knows that either 3 or 4 has been initial state of the swithes so he does not count the 4->1 transition. If the initial state is 1 or 2 no one will be able to go to state 3 since noone will have performed a 3-4 or 4-3 transition and so the state of the switches will remain 1 or 2 until the counter brings it up to the upper row and starts the show.

Peter Radkov
Saturday, April 26, 2003

P.S. The Counter makes the 2-3 transition with non-zero probability.

Peter Radkov
Saturday, April 26, 2003

Nicely done!

I was thinking so much about how the prisoners could communicate that I left out a very critical part of the problem.  Good catch.  In this scenario, there is only a small (1/46) chance that our counter would even know the initial state of the system (if you saw the first switch was off).  It was not safe for me to assume that you would know whether or not you are the first person to be called.

Days or months into the internment, our poor counter would realise his error and would be faced with an incredible dilemma, being forced to make the awful choice of gambling his life for the release of everyone else if his count seemed to halt at 23.  The roulette would be well in his favor, but the potential alligator breath future is pretty sobering regardless.

Can anyone think of a fix that requires less steps than everyone communicating with the counter twice?  It seems logical that any method of initializing the system to a known state would require communication with all the prizoners, so I am a little doubtful that the 44 communications can be improved on.  Alternatively, perhaps there is a more effiecient protocol?  The longer the communication takes, the better the chances that the warden pays you a visit to inform you that one of the other prisoners has died of goulash poinsoning ;)

Jason Striegel
Monday, April 28, 2003

David Neary came up with a good solution

http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=1115&ixReplies=19

which I believe is faster than having every prisoner set the switch twice.

David Clayworth
Tuesday, April 29, 2003

Initially, I had an idea similar to the "leave the left shoe off" idea--upon each prisoner's initial visit to the cell, he makes a mark (e.g. by scuffing his shoe on the wall). When *any* prisoner counts 24 marks on the wall, he can be confident that *all* the prisoners have visited the cell, regardless of the state of the switches.

But what if the guard makes them strip before entering--no shoes, thus no marks. Then we'd have to alter our strategy a little bit and use something that the guards cannnot take away from the prisoners...boogers.

See my solution, implemented in Perl, at http://the.kreft.net/perl/switches

D.Kreft
Wednesday, May 07, 2003

My solution is this.

1. Use only one switch and leave the other one (don't use it). Say only A will be used.

2. When one prisoner goes he will toggle switch A if he is going for the first time and remember the OLD position.

3. If the prisoner is going for the second time, he will see if the switch is in the OLD position, then he will declare that every one has been seen. Otherwise he will toggle again and remember the OLD position.

Thanks


PS: I will explain the logic if this solution is OK.

Thirumal Azhagan V.T
Monday, May 12, 2003

It is not the OLD position, but the NEW position.

Thirumal Azhagan V.T
Monday, May 12, 2003

If we assume that the person who goes there for the first time knows that he is the first person, then there will be no problem with Initial position of switch A. Because, if the first prisoner sees the initial position as on, then he switches B. It is in on position, so the counter gets the message. Otherwise, the first prisoner switches A to on.

nagasatish
Friday, May 16, 2003

This is a terrific puzzle.  Probably too hard to give in an interview (it took me three bike rides to figure out) but really fun.

I just posted my solution at http://w-uh.com/articles/030530-the_two_switches.html .  The fact that the initial state is unknown makes the problem that much more interesting - you derive a solution, notice it almost works but not quite, and then have to derive a more complex solution.

Ole

Ole Eichhorn
Friday, May 30, 2003

If this discussion is still active,then i came across a solution for this problem at this page.

http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/July2002.html

don't click on the solution hyperlink,if you wanna solve the problem by yourself.

Arun Iyer
Sunday, June 01, 2003

Arun -

The IBM research solution is correct, but in my humble opinion not as pretty as mine.  Also, it will likely take the prisoners longer before they are free.

Ole

Ole Eichhorn
Monday, June 02, 2003

*  Recent Topics

*  Fog Creek Home