## Brain Teaser - Prisoners and Switches

It’s been pretty quiet here lately – my posting has been limited by business at work. So I’ve shamelessly ripped a brainteaser from braingle.

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 there 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. Both switches are in their OFF positions now. 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 any one of you may declare to me, ‘We have all visited the switch room.’

“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.”

The remainder of this post will discuss solutions implemented in various programming languages.

### Using C and PThreads

/***** Compile Instructions *****
gcc -o threads threads.c -l pthread
*****/
#include
#include
#include
//global variables for tracking prisoner threads
#define NUM_PRISONERS 23
pthread_t Prisoners[NUM_PRISONERS + 1]; //thread id for each prisoner
unsigned char Visits[NUM_PRISONERS + 1]; //how many times has prisoner been in room
//global variables depicting switch settings
unsigned char Switch1 = 0; //generic Switch
unsigned char Switch2 = 0; //counter Switch
//global variables tracking prisoner status and warden choices
unsigned char SetUsFree = 0; //indicator that all Prisoners have visited
unsigned char InRoom = 0; //current prisoner in room
unsigned char AllFinished = 0; //prisoner is done in room
/***** prisoner thread *****/
void prisoner (void *arg)
{
unsigned int flagged = 0; //has prisoner ever flipped counting Switch
unsigned int unique = 0; //how many unique Prisoners have been in room
unsigned int PrisonID = (int) arg; //associate thread to prisoner id
while (!SetUsFree) //loop until Prisoners are freed
{
if (InRoom == PrisonID && AllFinished == 0) //determine if prisoner is in the room
{
Visits[PrisonID]++; //increment the personal visit count
if (PrisonID == 1) //determine if prisoner is the counter
if (Switch2) //determine if a new prisoner has visited the room
{
unique++; //increment the unique prisoner count
Switch2 = 0; //reset counter Switch
printf("%d determined a new prisoner has visited the room [%d total].\n", PrisonID, unique + 1);
if ((unique + 1) == NUM_PRISONERS)) //test if all Prisoners have visited the room
SetUsFree = 1; //inform the guard
}
else
{
Switch1 = !Switch1; //toggle the generic Switch
printf("%d has determined no change to visitor count.\n", PrisonID);
}
else //prisoner is regular
if (!flagged && !Switch2) //never toggled counter and Switch2 is clear
{
flagged = !flagged; //never flip the counter Switch again
Switch2 = !Switch2; //toggle the counter Switch
printf("%d has toggled the counter for the first time.\n", PrisonID);
}
else //prisoner will not toggle counter
{
Switch1 = !Switch1; //toggle the generic Switch
printf("%d has made a repeat visit.\n", PrisonID);
}
AllFinished = 1; //tell guard we are AllFinished
}
else //prisoner was not in the room
usleep(rand() % NUM_PRISONERS + 1); //wait awhile and check again
}
}
/***** main process *****/
int main (int argc, char *argv[])
{
unsigned int index; //loop counter
//create all of the Prisoners
for (index = 1; index <= NUM_PRISONERS; index++)
pthread_create(&Prisoners[index], NULL, (void *) prisoner, (void *) index);
while (!SetUsFree) //simulate warden
{
InRoom = rand() % NUM_PRISONERS + 1; //pick a prisoner
printf("Warden escorts prisoner %2d to room ... ", InRoom);
while (!AllFinished) //wait until prisoner has finished
usleep(250);
InRoom = 0; //reset prisoner variables
AllFinished = 0; //reset prisoner completion status
}
//show all the prisoner visit counts
for (index = 1; index <= NUM_PRISONERS; index++)
printf("Prisoner %2d visited the room %3d times.\n", index, Visits[index]);
return;
}

### Using Haskell

import Array
import System.Random
data Decision = FlipA | FlipB | Victory deriving (Show, Eq)
data PrisonerState = Reported | Unreported | Counting Int deriving (Show, Eq)
n :: Int
n = 22
{- an array holding (flag, state) pairs, where the flag indicates to the warden whether the
prisoner has visited the room and the state is the prisoner's memory; prisoner 0 is initially
given state "Counting 21" and the rest "Unreported" -}
prisoners = array (0, n) ((0, (False, Counting (n - 1))):[(i, (False, Unreported)) | i <- [1..n]])
-- an infinite list of random prisoner numbers
visitPlan = randomRs (0,n) (mkStdGen 0)
-- the prisoners' decision function, given their state and the current setting of the switches
decide Reported _ = (Reported, FlipB)
decide Unreported (True, _) = (Unreported, FlipB)
decide Unreported (False, _) = (Reported, FlipA)
decide (Counting 0) (True, _) = (Reported, Victory)
decide (Counting n) (True, _) = (Counting (n-1), FlipA)
decide s _ = (s, FlipB)
-- success means all the prisoners have visited the room
success pr = all fst (elems pr)
isVictory Victory = True
isVictory _ = False
applyDecision FlipA (a,b) = (not a, b)
applyDecision FlipB (a,b) = (a, not b)
-- the warden/guards loop
visit pr switches@(a,b) (p:ps) = if isVictory decision then success pr' else visit pr' switches' ps
where state = pr!p
(p',decision) = decide (snd state) switches
pr' = pr // [(p, (True, p'))]
switches' = applyDecision decision switches
main = putStrLn $ show $ visit prisoners (False,False) visitPlan

### Using Ruby

class Integer #extends the Integer class
def is_on?() self.modulo(2)==0 ? false : true end
def is_off?() !self.is_on? end
end
prisoners = Array.new(23, :uncounted)
prisoners[rand(23)] = :keeping_count #the guy keeping count
counting_switch = dummy_switch = 0 #even=off, odd=on
while counting_switch < 44 do
picked = prisoners[p_index = rand(23)] #randomly picked prisoner
counting_switch += 1 if counting_switch.is_on? && picked == :keeping_count
dummy_switch += 1 if counting_switch.is_off? && picked == :keeping_count
dummy_switch += 1 if counting_switch.is_on? && picked == :uncounted
counting_switch += 1 if counting_switch.is_off? && picked == :uncounted
prisoners[p_index] = :counted if counting_switch.is_off? && picked == :uncounted
dummy_switch += 1 if picked == :counted
end
puts "All have visited in #{dummy_switch+44} total visits (#{dummy_switch} wasted visits)."

### Using Java

package prisoner.problem;
import java.util.Random;
public class Warden {
private static Prisoner[] prisoners = new Prisoner[ 23];
private static SwitchImpl switchA = new SwitchImpl();
private static SwitchImpl switchB = new SwitchImpl();
public static void main( String[] args) {
Random rng = new Random();
int totalVisits = 0;
prisoner.solution.PrisonerLeader.createPlan( prisoners);
try {
while ( true) {
totalVisits++;
prisoners[ rng.nextInt( prisoners.length)].visit( switchA, switchB);
}
} catch ( DeclareWin e) {
}
for ( int i = 0; i < prisoners.length; i++) {
System.out.format( "Prisoner %1$d -- %2$d\n", i, prisoners[ i].visitCount);
}
System.out.format( "Guard visits %1$d\n", totalVisits);
}
}
package prisoner.problem;
public abstract class Prisoner {
public int visitCount = 0;
public void visit( SwitchImpl switchA, SwitchImpl switchB) throws DeclareWin {
visitCount++;
(( SwitchImpl) onVisit( switchA, switchB)).toggle();
}
protected abstract Switch onVisit( Switch switchA, Switch switchB) throws DeclareWin;
}
package prisoner.problem;
public interface Switch {
boolean test();
}
package prisoner.problem;
class SwitchImpl implements Switch {
private boolean state = false;
public boolean test() { return state; }
public void toggle() { state = !state; }
}