Klarna programming challenge

At the beginning of this week the results of the Klarna Programming Contest 2010 were published.

Most important news from my perspective:

Overall best solution:

Second prize: Fabian Linzberger (Apple iPhone)

Yay, I made second place! Yay, I won a smartphone!

Since I was asked about the problems I thought I would write up a bit of my experience.

Problem 1

(picture converted to png for the webbrowser. original PPM here)

A picture in PPM format (http://en.wikipedia.org/wiki/Netpbm_format#PPM_example), was given, that contained a hidden message.

I was totally mislead by the hint “what may seem red and insignificant is not”. I thought it referred to the red text in the picture, when (obviously, in retrospect, haha!) it was in fact referring to the least significant bit of the red part of the pixels in the picture. I spent quite some time filtering the shades of grey around the text before I finally realized I was looking in the wrong place.

Basically some of the first 60 or so pixels would appear white to the eye just like the others around them, but in reality about half of them were just a tiny, tiny bit less red. Decode the white pixels to 0s and the less red pixels to 1s in bits, translate to letters and you had the secret message.

Problem 2

(picture converted to png for the webbrowser. original PPM here)

Another picture, another hidden message. Using the solution program from problem 1 gave a hint: “iccanobiF”.

Clearly “Fibonacci”, just backwards. Now it came in handy that I had actually programmed a decoder for the picture file for problem one. Searching around for suspicious pixel values, quickly revealed around 10 or so which were just a little less red, this time distributed somewhere among the blue of the tulip.

Turns out if you make a list of all blue and slightly less blue pixels in the picture, reverse it and use the Fibonacci sequence as indices you again get a list of bits that decode to letters. Reverse that once again and you had the second keyword. Phew.

Problem 3

A variant of the Game of Life. An encoding of letters to a start configurations of cells on a matrix and the other way round was specified. The solution program had to use this on a keyword, run a certain number of iterations and afterwards decode the resulting configuration of cells to another keyword.

This was a bit of work to implement, but overall I found it a lot easier than the previous two picture puzzles: at least the objective was clear.

Problem 4

A hex encoded and Vigenère encrypted message was given. The task was to decode it. The encryption key could be obtained by running another simulation on the solution program for problem 3. Again a bit of coding, but more straightforward than 1 and 2.

All my coding was done in Haskell. Overall experience was quiet pleasant. Converting bits to text felt like taking a bit too much effort, maybe because I am not used to the libraries. As always: Quickcheck rocks!