Puzzler Solution: Prisoners and Hats and a Jungle

Can’t believe it’s been 2 months since I posted the puzzle. I’ve been involved in test automation using Selenium WebDriver over last couple of months and it has been a great experience designing and coding the test suite. The 1st step is complete - smoke tests for 2 of our applications have been automated and can be run on different browsers concurrently. Now we’re moving to the next steps (which are still TBD). I have lots of ideas in my head but I have to evaluate their feasibility and to break them into different phases so we can realize the added value as we continue to improve the automation suite.

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

Puzzler: Prisoners and Hats and a Jungle, Oh My!

This puzzler was mentioned in Car Talk sometime ago and I really liked it. In brief, it goes like this:

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.

Intercepting SSL traffic using WebScarab

The last time I wrote about intercepting web requests using WebScarab, I was successful in intercepting SSL traffic generated through a custom Java client. Even though the process to do that was quite tedious – involving exporting the WebScarab server certificates into .cer format, importing the certificate into a Java keystore and then running WebScarab as a reverse proxy – I was able to intercept and view the SSL traffic that was being generated. But there was an inherent issue with that process that I overlooked.

When a proxy is setup to intercept SSL traffic, the security issue is that the SSL certificate that is presented by the proxy is not signed by a trusted authority. Web browsers detect this and give the user an option to accept or not accept this risk. So there is no problem in using the proxy to intercept web traffic to secure sites and we can just point the browser to the proxy and accept when warned about certificate error. But in case of Java clients using JSSE, there is no assumption of an interactive user session and so by default it throws an exception if there are any certificate related issues – be it an unknown certificate in which case it throws the exception:

javax.net.ssl.SSLHandshakeException: sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target

or a hostname mismatch:

javax.net.ssl.SSLHandshakeException: java.security.cert.CertificateException: No name matching … found

The latter is thrown because when a new HTTPS connection is created using HttpsURLConnection class, it implements a default HostnameVerifier interface which checks if the host we’re trying to connect to matches the name in the certificate in its certificate store (specifically the cn within the certificate). If it doesn’t, it throws the above exception. The client I was using earlier overrode the default HostnameVerifier with a custom one, which ignored the hostname mismatch. But this time with a new client for a different application, it didn’t and I had to go one extra step to intercept the requests, which is detailed below. So first:

1. Start WebScarab and run it as a reverse proxy on port 443. This is so that WebScarab behaves as a secure server to the client, even if with a self-signed certificate instead of one signed by a trusted authority. (If running WebScarab from the same machine that is generating the requests, we should also select “Intercept requests” check box. This is important because in that case, the proxy is an infinite loop to its own interface and so we want to be able to break the flow and Abort after the first intercept)
   
2. Modify the hosts file to point WebScarab hostname to the IP of the machine where it is running. In case of local, it should be:
   127.0.0.1    WebScarab
   This is specifically so we can get around the issue of hostname mismatch because we’ll try to connect to host “WebScarab” instead of actual target server. If the client overrides the default HostnameVerifier to ignore those errors, it can be setup so that the client points to the actual host:
   <ip where WebScarab is running>    <target hostname>
   
3. Use the java program available here to create a keystore with the WebScarab certificate
   >>java InstallCert WebScarab
   Since WebScarab hostname is pointing to the WebScarab proxy, this program will connect to it and retrieve its certificate. It will create a keystore file called jssecacerts with WebScarab’s certificate (keystore password is blank by default).
   
4. Configure the client to use WebScarab as the host within the URL. So instead of https://<hostname>/<path>, it should be https://WebScarab/<path>.
   
5. Run the java client with the truststore and password properties: -Djavax.net.ssl.trustStore=<location to jssecacerts file> -Djavax.net.ssl.trustStorePassword=<password, default blank>

At this point, WebScarab proxy should intercept the request. I can review it, and abort it so it doesn’t repeat. Obviously, the request can’t be sent to the actual destination server. As I’ve noted above and as far as I know, there’s no way to get around the hostname mismatch error unless the default HostnameVerifier is overridden. But in my case, I was fine with just intercepting the request and creating my LoadRunner scripts using the raw HTTP request.

Rubik Timer

I'm currently working on writing a Java based Rubik Timer. A Rubik timer is a specialized timer that can be used to track the time it takes to solve a Rubik's Cube. There are some implementations available currently but the ones that I tried lacked some much needed features. And since the current projects I'm working on are not proving challenging enough, I needed something else to keep my life exciting.

Even though I've written some code already and am faced with some design decisions, it came to my mind that it'll be a good opportunity to put myself in different shoes - as a requirements/business analyst and document the requirements, as a programmer/designer and design/develop the solution, as a tester and test the implemented solution and finally as a user and use the application. Inextricably entangled with all these roles will be a project management role that I will have throughout the project. So I plan to follow and document the project as it goes through its own lifecycle, in an attempt to learn more about different phases that a project goes through. In the process, I also want to understand the roles of all these different actors and the challenges they face. I know it is easier said than done and at times, it may seem like an undiscerning adventure. But I want to at least give it a try and even though the project is smaller in terms of effort required as compared to real life ones, I believe that it'll prove to be an enjoyable and learning experience. And the fact that I'll be playing all those roles will make it as challenging as (or even more than) those I face in real-life.

In upcoming related posts, I plan to detail the progress as I find time to work on this project. As it seems, resource availability will be the toughest challenge this project faces since my current projects, even though minimally challenging can be substantially time consuming and resource (in this case, my mind!) draining. And every now and then, smaller challenges have a tendency to pop-up and provide exciting distractions.