VnutZ Domain
Copyright © 1996 - 2017 [Matthew Vea] - All Rights Reserved

2010-07-07
Featured Article

Brain Teaser - Prisoners and Switches

[index] [1,484 page views]

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; }
}

More VnutZ.com Content You Might Be Interested In Reading:

An historical look at the German roots that formed America's Airborne in WWII.

Or try your hand at fate - use the Pattern Analysis of the MegaMillions Lottery or the Pattern Analysis of the PowerBall Lottery page to pick "smarter" numbers. Remember, you don't have to win the jackpot to win money from the lottery!

coinbase