Fog Creek Software
Discussion Board




switches puzzle

This can be solved in following manner - State 0 means off, State 1 means On. Henceforth
00 - A is Off, B is Off
01 - A is Off, B is On
10 - A is On, B is Off.

Let us have two categories of states :-
1) Valid - 00 & 01
2) Invalid - 10 & 11

Also have a variable "Count" maintained by every prisoner that is local to each prisoner. The "Count" indicates total prisoners that have visited the switch room.

Process :-
1) Now whenever prisoner enters the switch room and encounters "Valid" state he increments his variable "Count" by one.
2) Whenever prisoner enters the switch room and encounters "InValid" state his variable "Count" remains same.
3) If the prisoner visited the switch room for the first time he will change the current state of switch to "Valid".
4) If the prisoner didn't visit the switch room for the first time he will change the current state of switch to "InValid".
5) If at any time a prisoner find his variable "Count" equal to total prisoners +1 i.e. 24 in current problem, he will declare that everyone has visited the Switch Room.

AC
Wednesday, April 20, 2005

I don't think this will work. Say the prisoners are taken to the room in order - then each one will have a personal count of 1, and the switch will always be set to invalid from then on.

Luke
Thursday, April 21, 2005

How about this, building on AC's state categories:

The prisoners decide on one special prisoner.  The special prisoner sets the switches to 'invalid' (as defined above) whenever he's in the room, all the other prisoners will set the switches to 'valid'. The special prisoner can then maintain the count and tell the warden once his count reaches 23.

This would mean that the special prisoner would have to visit the room at least 23 times - although he could make it less by remembering how he left the switches, eg:
- leaves the switches in 10 (invalid) state
- comes back to the switches in 01 (valid) state
- this means that at least 2 other prisoners have been in the room, so he can add 2 to his count.

However, this is still pretty much brute force; there must be a neater solution.

Luke
Thursday, April 21, 2005

Luke,

You solution won't work. Imagine the warden alternate between bringing the special prisoner and an other one. After some time the special prisoner will say  'We have all visited the switch room' and everybody will go visit the alligators.

AlphaBeta

AlphaBeta
Friday, April 22, 2005

A question regarding the problem:
What does "But, given enough time, everyone will eventually visit the switch room as many times as everyone else" exactly mean?

Can we assume it means "there will be an infinite number of occurrences when all prisoners will have visited the room exactly the same number of times"?
Or does it have a weaker meaning?

AlphaBeta

AlphaBeta
Friday, April 22, 2005

It’s important to mention that non special prisoner should not alter the valid state when they get in the room even if it’s the first time they get there.

An easy way of seeing that is to consider A as a flag signaling when set that a prisoner before you went in the room for the first time and that this signal has not yet been collected by the special prisoner. Non special prisoners should wait for the flag to be unset before registering their presence.

As a non special prisoner, when you get in the room, the rule would be
1/ A is set. Leave it that way (switch B).
2/ A is unset, and you have never set it before. Set A.
3/ A is unset but you have already registered you presence by setting A at a previous point in time. Leave it like that (switch B)

Now my rules as the special prisoner would be:
0/ Counter set 1
And each time I get in the room:
1/ A is set. This is a signal from a first time in the room prisoner. Increase the counter and reset A. If the counter is 23, you’re free.
2/ A is unset. No signal. Leave it like that (switch B). The counter is unchanged.

This is almost good but I have an initialization issue: the first time I’m forced in the room and I found A set, I don’t know whether it is the initial state of the system (since the warden wouldn’t describe it to me) or the signal from a co-prisoner. So I run the risk either to get stuck at 22 or that we are all feed to the alligator.

For this reason, I introduce a new non special prisoner rule stipulating that you should not switch A as long as you haven’t seen it in two different states. I’m the only one allowed to change its state as much as I want. I therefore will be the first one to change it.  So the first time I get in the room and A is set I know that this is just the initial conditions not a signal from a co-prisoner. But then, there’s another problem, how much and how often should I set/reset A in order to signal my presence to the other ones ?

Please help us.

Bruno
Friday, April 22, 2005

I think that there is no such problem. The special prisoner will just count to 24 so as to be sure that everyone has already been inside, even if in the beginning switch A is in the count position. Of course this will mean more visits to the shell for everyone, but it will assure no visit to the reptiles...
So, my opinion is that Bruno's solution is correct (must also be the best one) with the alternation of 24, instead of 23 count.

Panagiotis
Monday, April 25, 2005

P.S. without the last paragraph from Bruno's message

Panagiotis
Monday, April 25, 2005

you have sw1 and sw2 leaving the combinaton of 00, 01, 10, 11.

if (sw1 = 1 and not special_prisoner)
sw2 = not sw2;

elsif (sw1 = 0 and not special_prisoner and never_switched_sw1)
sw1 = 1;

elsif (sw1 = 1 and special_prisoner)
sw1 = 0
count += 1;

elsif (sw1 = 0 and not special_prisoner and switched_sw1_before)
sw2 = not sw2

end if

if (count = 23)
then you're free to go.

xnz
Monday, April 25, 2005

delete the 3rd not_special_prisoner from 3rd if.

I also think Bruno's answer is the same as mine, I was just too lazy to read through it. ^^

xnz
Monday, April 25, 2005

err, 3rd elsif

xnz
Monday, April 25, 2005

and the not_special_prisoner from the 1st elsif statement also, that way he'll have to switch it once, getting count to 23 in cases when he's the first to enter.

xnz
Monday, April 25, 2005

Xnz, there’s still something unclear for me.

When the special prisoner is in the room for the first time and sw1 is 1, how can he know whether sw1=1 because this is the initial state of the system and he is the first of all prisoners to be in the room, or because sw1 has been set to 1 by a non special prisoner that was just before in the room ?

To me we need to know. Increasing the counter in the first case would lead to reach 23 before the last non special prisoner has a chance to turn the switch on. In the second case, not increasing the counter would lead the process to be stuck for ever at number 22. 

Increasing or not increasing we’re at risk here.

Bruno
Monday, April 25, 2005

count increases every time he switches the switch down. If he enters the room the first time, and it's at 0, he switches to one and back to zero the next time he enters the room, increasing count by 1. If he enters the room and sw1 = 1, he switches down and it becomes 0, increasing count by one.

xnz
Monday, April 25, 2005

If he enters the room for the first time and it's a 0, he know he's the first person to enter. count += 1. Then he just wait for the next 22 person to turn it.


If it's 1 the first time he enters, 2 possiblities, 1) orignally set at one and no one touched it, turn it down, increase count. 22 people will go through it, and when he's at 23, they are free.

second possility is that some one else had turn it to one. turn it down, 21 people will go through it..... ok i c what you're saying :(

xnz
Monday, April 25, 2005

Let’s say that non special prisoners are requested to switch on the flag exactly two times instead of just a single one.

Now, the special prisoner still increases the counter each time the flag is on. Possibly the first time he is in the room, the flag was set by chance and the initial increase of the counter might not imply the presence of a co-prisoner in the cell. But in any case, when the counter reaches 44, we are sure that the 22 other prisoners have been in the room.

This is because a count of 44 can either mean:
- 1 mistaken initial increase, 21 prisoners increasing two times the counter, 1 prisoner increasing one time the counter
- 22 prisoners increasing two times the counter

The process can be shorten when the flag is not set the first time the special prisoner gets in the room. Under this circumstance,  he can stop counting at 43.

Bruno
Wednesday, April 27, 2005

Yeah I think that does it. I was going along those lines, but just quite can't get to the final hump. GJ bruno.

xnz
Wednesday, April 27, 2005

Here's my solution without the programming jargon (I'm not a computer person).

One prisoner needs to be designated the "answerman." He is the only person permitted to tell the boss "everyone has been in here."

The answerman will have a job and all other prisoners will have a job.

There are two swtiches. Switch A is insignificant...it doesn't matter if it's on or off. Switch B will be the "counter switch."

These are the jobs of the prisoners.

When a prisoner is brought into the room, he will turn Switch B to ON unless it is already on. If it is ON, he changes switch A to fulfill the warden's requirement to change one switch. He will only flips Switch B to ON twice. If he comes in and finds B at OFF for the third time, he does nothing to B and flips switch A instead.

Answerman has a different role. Everytime he comes in he first checks switch B to see if it's ON. If it's on, he turns it off. If it's off, he knows that no prisoner came in since his last visit because he's the only one allowed to turn B to OFF, and in that case he will leave B OFF and switch A.

Everytime Answerman turns switch B to OFF he adds 1 to his tally. When his tally reaches 44, he answers the warden that every prisoner has been in the room.

The reason the answerman has to count to 44 is because he doesn't know the original positon of the switches. If he knew the original positions, he could work a scenario where he only had to count to 22.

I think it would be impossible unless there is the concept of the "answerman." And all prisoners must follow directions perfectly which is unlikely or else they wouldn't be in the slammer in the first place...lol.

Jason
Thursday, April 28, 2005

the way i see this problem is similar to jason, but i think it can be more simple.

switch A is meaningless, so whenever a non-answerman prisoner goes into the room, he will flip this switch to signify nothing.

whenever a non-answerman enters the room for the first time, he turns the switch on. if it's already on, he just flips switch A. if it's off but he's been before, he just flips switch A.

basically, when the answerman goes into the room, if he finds switch B on, he knows that 1 new prisoner has been into the room, because his job is to flip switch B off, and if it's on, he knows that it has been flipped on. if it's off, he knows no one has been and he flips A.

the reason my solution is different from Jason's is that a non-answerman has to flip switch A just once, not twice. Also, the answerman must just count to 23. not 22, because he doesn't know the initial state of the switches. i just don't see why you would have to double your count, can't you just increase it by 1 for that risk?

it seems like my solution is the simplest. i bet it doesn't work, but i don't know why.

Reuben Moss
Monday, May 30, 2005

The reason counting to 23 does not work is because of the case when switch B is off initially.  Then, the 22 "non-answerman" prisoners will set switch B ON 22 times in total. So, answerman's count will never reach 23 and he would not be able to declare.

Tarkeshwar
Wednesday, June 01, 2005

I don't think this is solvable w/o assuming that everyone will visit a lot.

The warden can lead everyone thru the room on the first day, and he's met his obligations (everyone has visited the same number of times). Then he lets the prisoners rot while they wait...and wait...and wait...for "the counter" to visit another 43 times.

tirespin
Monday, June 06, 2005

I think , Bruno  Friday, April 22, 2005....have the correct solution , only thing left is the problem of initialisation state.......

For this i assume , that NON especial prisoner start to switch A to make the count go up by them , only when they have seen the A counter in set state atleast two times , and ....

the Especial Prisoner when comes the first 3-4 times will do as follows

a) switch A ,
b) when he comes  again ,if he is sure that atleast one have come after him ,again switches A
c) when he comes again , if he is sure that atleast one have come after him , than again switches it.

there could be only 2 cases when he first comes , A may be set or unset. If A was set when he first comes than A will go on to switch this only thrice as shown above to make to reset again .If A may be unset than he have to switch twice as above . In anycase he lefts A to be in unset state finally and now he will start counting.

Now, atleast one prisoner will notice that A is in reset state and had been fluctuated atleast twice by the especial prisoner. He can now set the switch A so as to count him  and the counting thus goes on normally as decribed by bruno.

I hope this solves the problem , if the distribution is random but everyone gets fair chance.

de_tali
Wednesday, June 15, 2005

i have typed wrongly previously the following ,:

For this i assume , that NON especial prisoner start to switch A to make the count go up by them , only when they have seen the A counter in set state atleast two times , and ....

the mistake is that they should swicth A only when they have seen A counter in reset state ( not set state ) twice at two diff times.

de_tali
Wednesday, June 15, 2005

Reuben's solution fits well. Its going to take a lot of visits for the answerman though.

Kumar
Wednesday, June 15, 2005

Reuben's solution is good, but the initialization issue means you may never get to 23! That's why everybody has to signal his entrance twice. Ok, so it's clear that we need a significant bit and an insignificant bit. One person is the counter. The other 22 do the following: During their time they set the significant bit if it is unset exactly two times. If the significant bit is set already they alter the insignificant bit and have to wait for their next chance. The counter adds one to the count (initially zero, obviously) if the significant bit is set and resets it. If is is unset, he alters the insignificant bit. If the couter reaches 43 (2*22 - 1), the counter makes the announcement, everybody will be free.

Andre
Thursday, June 16, 2005

Me and the guys at my workplace wracked our brains over this for a few hours, and we eventually came up with the 44 answer also.

(Which is, the leader's count starts at 0; he adds 1 each time he sees the left switch at 1, and flips it back to 0, else he toggles the right one; everyone else flips it from 0 to 1 the first two times they see it at 0, and toggles the right otherwise. The leader knows at 44, because either everyone has gone twice, or the left was initially set to 1 and someone has only gone once.)

Someone may have already pointed this out, but this answer assumes NOT ONLY that the number of times everyone has flipped will be equal ONCE, but that it will be guaranteed to be equal AT LEAST... What, 103 times maybe? A hojillion times. So I would assume that it will be equal an infinite number of times. If I had to write a proof, I would figure it out. And regardless, the solution will take the prisoners very, very long time; especially if the warden is a bastard.

We have been puzzling over this for a few hours now; you might guess that we don't always "Get things done" around here. So Joel won't hire us, but at least we figured out the answer. :/

Jesse Millikan
Monday, June 20, 2005

Alright, the last detail: This solution is guaranteed to be complete after everyone has flipped an equal number of times on 88 different occasions, not including the first one. This is 89 cycles (from equal to equal again). This is for the worst case scenario where the leader's turns are all at the beginning of even cycles and end of odd cycles. (His count is n/2 - 1 at the end off odd cycle n.)

And the solution can work in as little as 87 flips, for similar reasons.

Where are these poor incarcerated saps, anyway? I hope they had pencils and paper.

Jesse Millikan
Monday, June 20, 2005

*  Recent Topics

*  Fog Creek Home