A prison has 30 prisoners sentenced to be executed and the warden, who has the authority to pardon, decides to give them a chance to escape the punishment. He will stand all the prisoners in a straight line with each prisoner able to see the heads of all prisoners in front of him but not of those behind him. Next, he will put either a white or black hat on each prisoner’s head and ask them to guess the color of their hat one by one (starting with the 1st prisoner in the back of the line who can see all 29 other prisoners’ heads). If he guesses correctly, he’s pardoned. What is the strategy that the prisoners can use to maximize their chances of being pardoned?The answer I came up with was grossly wrong so when these guys gave the answer (link to which I’m not posting here but can be found easily), I was intrigued. When listening to the answer, it sounded very simple but when I actually thought about it some more, I had to listen to it again to understand the strategy. For example, does the current prisoner need to know all the previous guesses or only the most previous guess?
I decided to write a simple program for this. The line of prisoners here is a StringBuffer of predefined size (in this case, 30) that is randomly filled with ‘B’ or ‘W’ chars. The objective is to write a method that will be called for each character in the StringBuffer with all the previous guesses (as a String) and remaining series (as a String). The method has to return the current character and should be implemented in such a way as to maximize the correct answers. Here’s the code:
1: import java.util.Random;
2: public class Test {
3: static int SIZE = 30;
4:
5: public static void main(String[] args){
6: int correctGuesses = 0;
7: StringBuffer pRow = new StringBuffer(SIZE);
8: StringBuffer prevGuesses = new StringBuffer(SIZE-1);
9: char currGuess;
10:
11: Random rnd = new Random(System.currentTimeMillis());
12: //---print the series
13: System.out.print("Series:\t");
14: for (int i=0;i<SIZE;i++){
15: if (rnd.nextInt(2) == 0) //0=black, 1=white
16: pRow.append('B');
17: else pRow.append('W');
18: System.out.print(pRow.charAt(i) + " ");
19: }
20: //---strategy
21: System.out.print("\nStrat:\t");
22:
23: for (int i=0;i<SIZE;i++){
24: currGuess = guessStrategy(prevGuesses.toString(),pRow.substring(i+1));
25: System.out.print(currGuess + " ");
26: if(currGuess == pRow.charAt(i)) correctGuesses++;
27: prevGuesses.append(currGuess);
28: }
29: System.out.print("\nCorrect Guesses=" + correctGuesses);
30: }
31:
32: public static char guessStrategy(String prevGuesses, String remArr){
33: //random
34: Random rnd = new Random(System.currentTimeMillis());
35: if (rnd.nextInt(2) == 0) //0=black, 1=white
36: return 'B';
37: else return 'W';
38: }
39: }
First, I generate the series and print it (lines 13-19). And then I call the guessStrategy method for each character in the series with all the previous guesses and the remaining series. But currently, there is no strategy and each time, it randomly returns ‘B’ or ‘W’. And obviously, result is that correct guesses average around 15. Your job, should you decide to accept this assignment is to provide a better implementation of the guessStrategy method which maximizes the chances of guessing correctly. If you’re stuck, you can look at the Car Talk website or search on internet to find the answer and then try to implement it.
I’ll post my implementation of the method in a few days. Hopefully it provides enough of a challenge to some people to work on this besides their otherwise busy life.
