Code Challenge “Vrolijke Framboos” Postmortem

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

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:

The 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.

What went well for me was
  • 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.
What could have gone better
  • 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 ;)

Original Article

Leave a Reply

Your email address will not be published. Required fields are marked *