Fog Creek Software
Discussion Board




Solution to swithches puzzle

Note that the bulbs are labelled so consier this ... take 0 for 'off' and 1 for 'on' and then form a table which looks like
a binary table for all possible values for 'two bits'..
          A    B    Value
        ----------------------
            0    0      0
            0    1      1
            1    0      2
            1    1      3
The following conditions were decided by the three prisoners :
1)They labeled themselves as 1,2 and 3 .... corresponding
    to the above possible combinations of the bulbs.
2)The declaration that all have visited the switch room will
    made by Number 3
3)All have taken note their "signatures" as per the above   
  table.The prisoner 1 for example will leave  "0 1" as his
  signature (on the condition that the available situation of
  the switches is "0 0" or "1  1").
4)Number 2 will leave his signature only when he is sure
    that Number 1 has visited...ie Number 2 sees the 
    signature of Number 1 and remembers...
    Now suppose that Number1 has made his signature
    "0 1" and Number 2 then sees it......so he cannot write
    his signature now..as he is allowed to only switch one
    bulb at a time..so he makes a mental note of the fact
    that number1 had visited and then Number2 puts the
    bulbs in  "0 0" situation.After that when ever Number2
    gets a chance(when "0 0" or "1 1" is available)
    to write his signature he will do it promptly.
5)Everybody will write his own signature or "0 0"( if he 
  cannot write his signature)
6)Nubmer 2 will write his signature only when he is sure
  that Number 1 had written his signature(irrespective of
  the fact that Number 1 had visited immediately before
  or sometime before) and also when he gets an
  opportunity to do so ( ie the situation is "0 0" or "1 1")
  otherwise he will revert to "0 0"... the default one! for
  everybody.
7)Number 3 will write his signature only when he is sure
  that Number 2 had written his signature....
  and Number 2 took care of Number 1's signature
  so Number 3 needs to be only on the look out for
  Number 2's signature.This ensures everybody made it
  into the switching room.Then Number 3 declares....

Take any combination for a start and use the following rules:
1)Prisoner will try to write his signature
2)If he cannot he will try to put "0 0"

One case the combination "1 1" is given and Number 3 walks in for the first time.. he cannot put "0 0" but he wont
even put "0 1" as that would give an impression of Number 1 having walked in .. so he will put "1 0"
Each prisoner knows whether they have put their own sign
or not so if the encounter thier own sign which they
have not put.....Number1 and Number2 will leave "0 0"
as the switches position and Number3 when encounters
"1 1" will leave "1 0"
One needs to recognize the others sign only:
ie Number 2 will only need to recognize "0 1" in order to put his own "1 0" signature (then or in the near future thats it!!)
and Number 3 will only need to recognize "1 0" in order to
put his own "1 1" sign(he doesnt need to observe for "0 1" at all!!
Number 1 is free to put his sign whenver he gets a chance....
he need not observe anything.......

Hope i m right
:)
sorabh

sorabh saxena
Sunday, June 08, 2003

Hi !

I like your approach . However I think it's wrong.

In your algorithm, suppose number 3 eventually finds out that number 2 has put his signature, but how number 3 can know that this is  number 2 from his group, or at least that all number 2's already visited the room. And how number 3, who is going to declare that everybody has visited the room, can know that all other number 3's visited the room?

Gans
Sunday, June 08, 2003

Is there a misprint in the puzzle statement? It says "23" prisoners -- should it actually have said "3"?

If 3,  my proposed solution is:

Prisoner 1 takes the switch on the left.
Prisoner 2 and 3 take the switch on the right.
Both 2 and 3 remember the position of the switches. If, when either of them visits the room, both switches are in different positions from their last visit, they declare.

Of course, if the warden knows the algorithm, he can keep them there indefinitely...

William
Wednesday, June 11, 2003

there is no mistake, i think the number 23 is there to confuse us. any solution should work for 50 or even 100 prisoners as well.

i'm not going to give any hints, but if you want a solution, google should be able to find one for you. i solved it (almost right) after a while, and it required no thinking outside of the box (aha!). good luck!

rx4ever
Saturday, June 14, 2003

The puzzle does not state *how* the switch must be mounted on the wall. It mentions moving the switch.

Switch A will indicate whether the first 12 prisoners have come through or not.

Switch B acts as an hour hand abd tally.

Since there are 23 positions. Use one switch for AM/PM. The first 12 prisoners use the AM switch as ON. Now as each prisoner comes into the room and move the switch "one hour". He flips the B switch only to statisy the warden.

When the 12th prisoner comes into the room, he switches the first switch OFF to indicate that 12 prisoners have already been though and move the B switch to the "noon position".  Then the rest of the prisoners come in until the last.

If he's been in the room before,  he simply swiches B on or off to statisfy the warden. Prisoner will know he's last when Switch A is OFF and Switch B is tipped to the 11o'clock position.

-V

vrkelley
Monday, June 16, 2003

um, except they are normal lightswitches so you can only flip them 'on' and 'off', not to 11 o'clock.

Michael H. Pryor
Wednesday, June 18, 2003

This was a toughie. Took me a day. 

The solution is to have a leader among the prisoners who will declare when everybody has visited the switch-room. At the allowed meeting between prisoners, they decide on the leader and also decide on a "special switch", which will be used to communicate between the leader and the rest of the prisoners. Lets take it to be A. To denote switch positions, I will use 0 and 1 to denote any one of "on" or "off" positions.

Lets assume that A is 0 initially. I will deal with the problem arising out of this assumption later. If the leader comes in and sees A as 0 he does nothing, he simply flips B. When a prisoner comes in and if the value of A is 0 and if he has never flipped A before, he flips A to a 1 and afterwards everytime he comes in he flips B. The value of B is irrelevant. When a leader comes in and notices that A became 1, he realizes that someone new has come into the room, so increments the count of prisoners who visited the room by one and flips it back to 0. Thus, if we can guarantee that A is initially 0, when the leader notices A becoming 1, 22 times, he can guarantee that everybody has visited the switch-room. But since we cannot guarantee this,so we would need to change the strategy little.  Instead of having the prisoner flip A only if he has not flipped it before, we will let him flip A to a 1, two times i.e if a prisoner has already flipped A to a 1 on a previous visit, we will let him flip it once more on a subsequent visit.

If the leader observes A as 1, 43 times, he cannot yet say if everyone has visited because A could be initially 1 and 21 prisoners could have visited twice. But  if there are 44 flips, we can guarantee that everybody has visited the cell atleast once.

Alex Czarian
Thursday, June 19, 2003

  A similar solution to the one given above by Alex, is:

Let there be a secret code "0 0" for example.
Now,
Every prisoner will make the position of the switches as
"0 0" only once!....so the moment any prisoner sees the  secret code "0 0", 22 times , he would be 100% sure that all the others have visited the room. The number of prisoners does not matter, it can be 2000 also and the key value would be 1999.

Rahul Sachdev
Friday, June 20, 2003

Based on the solution given, I feel the wording of the puzzle was confusing. The warden only guaranteed that each prisoner would eventually visit the switch room the same amount of times, it did not say he would continue choosing prisoners indefinately untiil one declared they had all visited. The solution implies that each prisoner would have to visit the room 22 times.  However, from the wording I thought that each may visit the room 1 time or 6
times or whatever the warden chose not thinking there was no upper limit.

Jeffrey Smith
Tuesday, June 24, 2003

Has anyone actually heard of this puzzle being used in a real interview?  Seems a bit tough for a simple hour-long interview if they're also going to hit you with coding questions.

TwinPapa
Monday, July 07, 2003

The solution to the Switches Puzzle i think is

Initially all the prisoners decide
if they visit the "Swiches room" for the first time they will
alternate between 00 and 01

If they visit swiches room for the second or more times they will alternate between 10 and 11

So if the prisoner visits the room 3rd time(or more) and sees some one has put the combination as (10 or 11) he will declare that everyone has visited the room once.
becuase of the clause

" But, given enough time, everyone will eventually visit the switch room as many times as everyone else. "

I think this solution is rite.IF some one thinks its not lemme know

THE RIDDLER
Monday, July 14, 2003

Riddler, you are wrong: remember that in the problem it says: "I may choose the same guy three times in a row"
According to you, the first time he will flip to 01 or 00,
second time to 10 or 11, and the third time he'll
see 10 or 11 and go declare to warden.  While it
may have only been 1st, second and third visits.

I think the solution is posted above - each guy
will leave the code (say 00) exactly once, and
whoever counts 22 of the code declares.

Jeff P
Friday, July 18, 2003

Actually, I think that Alex's second answer is correct;  Leader waits to see A at 1 44 times.

Rahul's secret code won't work, because no one prisoner is likely to see all of the other secret codes.
Prisoner 1: leaves code
Prisoner 2: sees code, but has no choice but to change it
Prisoner 3: leaves code, but will never know about the first one, so he'll never see 22 codes...

Allan Schon
Tuesday, July 22, 2003

On entering the switch room each prisoner will do the following:

Note the current position of the switches A & B, on or off.

They then move one switch to denote either their first or second visit using the folowing table:

o - denotes switch position  off
1 - denotes switch position  on

0, 0 - New
0, 1 - New
1, 0 - Second visit
1, 1 - Second Visit

Note you can set the switches to either new or second entrant using the above table no matter what the current state.

Each prisoner will then simply tally the number of new entrants as and when they make a visit to the switch room.

When a total of 22 or n-1 is reached, the prisoner will know that all have visited the switchroom. n being total number of prisoners.

Since all prisoners keep their own tally there is no need for a single leader (he might escape in the meantime).

Just hope they can all count or else its crocodile time!

Stuart

Stuart
Saturday, July 26, 2003

I think my solution above is incorrect (how sad is that, I'm still thinking about it!).

However I believe the following adaption will work.

A single prisoner will be required to count the number of new entrants using the code below:

Right switch.

0- indicates new to visit
1- already visited

Left switch position not important.

Each time a prisoner visits for the first time and the right switch is in position 1, they must move it to 0 to indicate a new visit.

The counter on their next visit will add this to the tally and then move the right switch to position 1. If already in position 1 they will alternate the position of left switch.

If a prisoner enters on their first visit and right switch is already in position 0, they must alternate the position of the left switch.

Every prisoner must continue to enter the switchroom as if it were their first visit following the rules above until such time that they able to move the right switch from position 1 to 0 indicating their first countable visit.

When the prisoner counting reaches a value of n-1 (n being total number of prisoners) they will know that all prisoners have visited the switch room.

Stuart
Thursday, July 31, 2003

This was a good one with pretty interesting solutions. But Alex's solution posted on June 19th is the right one. If I was forced to select between the alligators and Alex's solution it wouldnt be tough for me to select would it?
:)

Hadi Mohammed
Thursday, August 07, 2003

Alex's solution posted on June 19th is a good attempt but if the number of prisoners = 23
and say the prisoners each vist the switchroom
only 4 times then this solution will not work.

Some one else has already posted this issue.

I propose that each prisoner leave their
left shoe.  When there are 23 left shoes
any prisoner may make the declaration.

John
Tuesday, August 26, 2003

What if they don't wear shoes?
After all they are being threatenend with being fed to alligators. What's to stop the Warden from commiting other Human Rights Violations?

Brian
Wednesday, August 27, 2003

I think Alex's solution is correct. I came up with the solution where the leader counts 22 new ones, but I realized after reading his solution that I was wrong, since the first count could be due to the initial position of the switch. Therefore, to count twice would eliminate that possibility.

Good job Alex !

Anurag Jain
Wednesday, August 27, 2003

*  Recent Topics

*  Fog Creek Home