Back to the puzzler solution. For reference, here is the puzzle statement and the code. My implementation of the guessStrategy method is below.

The strategy is that the 1st person to guess speaks the color of the odd hats ahead. So if the (number of black hats ahead) % 2 == 0, the guess is “Black” (lines 4-8). How does it help that person? It doesn’t, that prisoner is unlucky enough to be the 1st one to guess (end of the line) and has a 50% chance. But the rest of the prisoners can guess the color of their hat correctly now that they know the initial guess, all guesses since then and the color of hats ahead. So for example, if the 1st prisoner guesses black, there must be odd black hats ahead. Now if the 2nd prisoner sees odd black hats ahead, s/he must be wearing a white hat because the previous prisoner also saw odd black hats. And the logic goes on like that…if the nth prisoner sees odd number of black hats, and previously, odd number of people have guessed black, then s/he must be wearing a white hat (lines 13-23).

1: public static char guessStrategy(String prevGuesses, String remArr) {

2: int numB = getNumOfChars(remArr, 'B');

3: int numPrevB;

4: if (prevGuesses.length() == 0) { // initial guess

5: if (numB % 2 == 0)

6: return 'W'; // if B is even, return W

7: else

8: return 'B'; // else return B

9: } else {

10: // strategy: if previously even number of people have said black,

11: // and I see even black hats, I have a white hat, else black

12: numPrevB = getNumOfChars(prevGuesses, 'B');

13: if (numPrevB % 2 == 0) {

14: if (numB % 2 == 0)

15: return 'W';

16: else

17: return 'B';

18: } else {

19: if (numB % 2 == 0)

20: return 'B';

21: else

22: return 'W';

23: }

24: }

25: }

26:

27: /**

28: * @param arr

29: * @param ch

30: * @return number of times the specified char appears in the array

31: */

32: public static int getNumOfChars(String arr, char ch) {

33: int num = 0;

34: for (int i = 0; i < arr.length(); i++) {

35: if (arr.charAt(i) == ch)

36: num++;

37: }

38: return num;

39: }

your strategy seems to have gone haywire... not a solution at all if you ask me but yes even i don't know the solution.. :)

ReplyDeletePlease elaborate. The solution above is the implementation of actual solution as described on their website and provides atleast 29 correct guesses, out of 30. Here's the complete code if you're interested in trying it yourself: https://gist.github.com/1636207#file_prisoner_puzzler.java

DeleteThe output is something like this:

Series: B W B W B B B W W B W W W W B B W B B W W B B B W B W B W W

Strat: W W B W B B B W W B W W W W B B W B B W W B B B W B W B W W

Correct Guesses=29