Friday, February 19, 2016

Prisoners and hats puzzle

According to the story, four prisoners are arrested for a crime, but the jail is full and the jailor has nowhere to put them. He eventually comes up with the solution of giving them a puzzle so if they succeed they can go free but if they fail they are executed.

The jailor puts three of the men sitting in a line. The fourth man is put behind a screen (or in a separate room). He gives all four men party hats. The jailor explains that there are two black hats, and two white hats; that each prisoner is wearing one of the hats; and that each of the prisoners only see the hats in front of him but not on himself or behind him. The fourth man behind the screen can't see or be seen by any other prisoner. No communication among the prisoners is allowed.

If any prisoner can figure out and say to the jailor what color hat he has on his head with 100% certainty (without guessing) all four prisoners go free. If any prisoner suggests an incorrect answer, all four prisoners are executed. The puzzle is to find how the prisoners can escape, regardless of how the jailer distributes the hats.


import java.util.ArrayList;

public class Solution {

 public static void main(String[] args) {
  int members = 10;
  ArrayList<String> list = new ArrayList<String>();
  int blackCount = 0;
  for (int i = 1; i <= members; i++) {
   String val = (getRandom(1, 2) == 1) ? "white" : "black";
   list.add(val);
   if (val.equals("black"))
    blackCount++;
  }
  if (list.get(members - 1).equals("black"))
   blackCount--;
  System.out.println(list);

  int prevC = blackCount;
  String prevB = printStatus(blackCount % 2 != 0);

  for (int i = 8; i >= 0; i--) {
   if (list.get(i).equals("black"))
    blackCount--;
   boolean prevOdd;
   prevOdd = (prevB.equals("white")) ? (prevC == blackCount) ? true
     : false
     : (prevB.equals("black") && prevC == blackCount) ? true
       : false;
   prevB = printStatus(prevOdd);
   prevC = blackCount;
  }
 }

 private static String printStatus(boolean prevOdd) {
  String prevB;
  if (prevOdd) {
   System.out.print("white ");
   prevB = "white";
  } else {
   System.out.print("black ");
   prevB = "black";
  }
  return prevB;
 }

 public static int getRandom(int minimum, int maximum) {
  return minimum + (int) (Math.random() * maximum);
 }

}

Result:
From 1 to N: [white, white, black, black, black, white, white, white, white, white]
Last person to first telling their colors: white white white white white black black black white white 

No comments:

Post a Comment