Today we had our second ever "Vrolijke Framboos" (Dutch for Happy Raspberry) Java code challenge at JDriven and it was a blast! This year’s challenge was to create a REST service client that would play a number guessing game with the server. After setting up a session you would guess a number and the server would respond with either "lower", "higher" or "bingo". The goal was to guess as many numbers in the two minutes you’d be given. Given the name of the challenge you can probably guess that the target platform would be a Raspberry Pi!
It was an incredible and fun experience and in this post I want to explain how I approached the challenge and how my solution ended up in the second place, making me just miss the opportunity to take home the trophy and a new Raspberry.
Preparation
All I knew from the previous installment of the challenge (which I wasn’t a part of unfortunately) was that we’d have to supply a runnable jar which would be executed on a raspberry. I prepared by setting up an empty maven project that assembled itself and it’s dependencies into a fat jar that was runnable from the commandline with java -jar <jarfile>.jar. I also included a bunch of standard dependencies (Log4j, Junit, Guava) which I didn’t even end up using.
Execution
When we were explained that we would be talking to a REST service through post request I started by adding Apache HTTP client (the fluent API is nice!) and Jackson for the client.
I also used an existing Spring Boot REST test project to add my own mock version of the server since the server would not be available to us until 30 minutes before the deadline. Quite a bit of my time was spent creating the server endpoints just so my client had someone to talk to.
With the server in place I implemented the client interface. With Jackson + Apache HTTP client this is very straightforward. An example:
public GuessResponse guess(GuessRequest req) throws IOException {
String result = Request.Post(baseUrl + "/api/numbergame")
.bodyString(toJson(req), ContentType.APPLICATION_JSON)
.execute().returnContent().asString();
return mapper.readValue(result, GuessResponse.class);
}This is the REST call that does the guessing; pretty straightforward!
Algorithm
The 'brains' of the operation was a Worker thread that kept starting new games and within a game used a straightforward binary search to drill down to a correct guess as soon as possible. Guessing a number through a binary search in psuedo is:
low_bounds = 0
high_bounds = 2^63
loop:
pivot = low_bounts + (high_bounds - low_bounds / 2)
guess = guess(pivot)
if guess == "lower":
high_bounds = pivot - 1
else if guess == "higher":
low_bounds = pivot + 1
else if guess == "bingo"
return pivot
else
throw ErrorThe typical complexity is O(log n), much better than an O(n) brute force.
My first implementation used an upper bound of 2^31 but I soon found out that the server was handing out much higher numbers.
Optimizations
With the basic implementation working I started out to try to optimize the solution since I guess I would not be the only one with a binsearch implementation. My first guess was to parallelize the work by having multiple workers playing the game simultaneously. This worked very well; it appeared that the largest bottleneck was the HTTP round trip and moving to 8 threads gave me a large speedup.
Unfortunately when the deadline neared I heard that actual contest would only allow one single session to be active, so my approach would not work. I spend quite a bit of time trying to figure out a way to have multiple threads working on the problem to try an circumvent the HTTP overhead but I unfortunately lacked the time to come up with a solution.
Match time
We handed in our solutions (we had about 13 implementations out of 20 or so contestants) and my colleague Pepijn started running them. The server had a very neat reporting capability showing us the score going up in real time!
Some solutions didn’t work at all but a bunch did, and they were fast! My chance of ending up in the top 3 was starting to look slim indeed. My submission was actually last to be executed so it was pretty nerve-wracking to have to wait. When they finally ran my solution it was a lot faster that I was expecting it to be based on the speed I saw running my own machine. This was obviously due to the wired connection between the raspberry and the server.
All the solutions ran for 2 minutes and I ended up second with 556 correct guesses. The number 1 (submitted by Ricardo) was 714 and the number 3 was 289, so I’m incredibly happy with the result!
Postmortem
It was an amazing evening and it was so much fun to see everyone going into extreme focus mode the moment we were handed the assignment. Most of us wasted very little time (if any) to eat pizza and instead worked very hard to get a working solution.
-
Preparation: having an IDE with an empty project that’s already ready to build into a jar is a must. Setting something like this up does not take a lot of time, but those 15 minutes are very valuable when the total time you have is around 2-3 hours!
-
Algorithm: my binary search approach worked very well, especially compared to brute force approaches some people took. At first I had assumed they would use the entire 'int' search space but I soon learned that it was actually a 'long'. Brute force simply won’t cut it.
-
Focus on speed: I did not bother with unit tests or creating proper Java POJO’s with getters/setters. CheckStyle would’ve had a heart attack with my code. What was important was getting it working.
-
Removing debug statements: System.out is expensive! Some people forgot to remove prints inside tight loops and this slows down your application a ton. Mine only reported guessed numbers.
-
Preparation: although I had an IDE set up I had no idea I would be implementing a mock REST service. If I would’ve had something like Node.js and a basic REST service available I would’ve made much progress on the integration of the client much sooner.
-
Focus on multi threading: it was a gamble that didn’t work out in the end; the session system would not allow parallel games to be executed and a binary search doesn’t really parallelize well at all.
-
Lack of focus on the search space: I assumed that the full space between 0 and 2^63 would be guessable but it was clear quite soon when we started the contest that it was always guessing VERY high numbers. Had I created a histogram of the first test results I would probably have seen that the distribution wasn’t uniform at all. I could have made the low and high bounds adaptive to the numbers found.
-
Lack of focus on the HTTP overhead: I didn’t have any time to find out how to reduce HTTP overhead by for example keeping the connection open. In retrospect that could have made a huge difference.
Conclusion
This was my first code challenge / hackaton I participated in and it was so much fun I can recommend it to anyone. Coding in a competitive setting is very different from your normal day to day work. It’s much more intense and because of this everyone just end up straight in the 'zone' where you are in fact incredibly productive. This 'zone' is a happy place for me and it’s rather addictive; the downside is that I was so hyped I couldn’t even sleep. The main reason I write this; to get it out of my head ;)