Softwire Speed Coding Challenge – 2013
24 July 2013, by Chris Arnott
Softwire recently hosted their third speed coding challenge. The competition was open to current employees and was designed to give everyone a chance to show off their ability to code solutions to a variety of problems in as short a time as they can!
The night was organised by Matthew Richards, winner of the challenge last year. Questions were created by Matthew and were designed to be challenging (but solvable) programming puzzles which would take 30-45 minutes each. Any programming language could be used, C# was by far the most popular, but we also had some interesting solutions in languages such as Node.js, and Haskell.
The competition comprised of four questions to be answered. Two questions were set before a brief pizza break (paid for by Softwire morale) with the final two questions being set after everyone had recovered their strength!
For each question, points were given based on the speed of the (correct) response, with a maximum of 10 points for 1st place, 9 for 2nd, 8 for 3rd and so on. In addition to this, extra style points (maximum 4 in total per question) could be given “for solutions that were particularly neat, elegant or otherwise impressive” as well as extra bonus points (maximum 4 in total per question) for answering the extension questions.
Questions could go on as long as necessary until someone got an answer, at which point everyone else would have half as much time again to finish (so a question answered correctly in 20 minutes would be ended after a half-hour).
The following question is one that was posed on the night. Why not try it yourself? We’ll publish the winning answer in the next post.
Question – Hidden Images
We saw in the last Speed Coding that you have to be careful when encrypting things lest your encryption is not as robust as you thought it was. So this time round we’ll try a different technique – hiding your message so no-one even knows there’s something to decrypt. In this problem we will consider an algorithm for hiding one image within another one. (Note: In reality you probably want to use decent encryption as well!).
The hiding algorithm
Call the image you want to hide the secret. Find another, non-secret, image 3 times as wide and 3 times as tall – call this the cover. You will hide the top-left pixel (0,0) of the secret in the top-left 3*3 pixels of the cover, and so on – in general pixel (i,j) of the secret is hidden in the 3*3 block starting at (i*3,j*3).
Each pixel is hidden as follows. Consider the red element of the pixel, which is in the range 0..255. Consider this as a binary number 0..28-1 i.e. there are 8 bits of data to hide. Hide the least significant bit of the redness (which I’ll label 20) in the top left pixel, the next most significant bit (21) in the next pixel to the right, and so on as per this diagram:
Hiding one bit of redness in a pixel is achieved by taking the redness of the cover pixel, and changing its least significant bit to match the bit you’re hiding. Repeat this process for green and blue to hide the entire image. (Ignore transparency considerations – treat each pixel as having red, green and blue elements only). Since you’re only mangling the bottom bit of each colour byte, the impact on the overall image is minor – not readily visible to the naked eye.
The speed coding challenge
Here is an image of a Scottish loch in winter. Hopefully you will agree it’s not immediately obvious that I’ve hidden a secret image within it, using the above algorithm. But I have. Find that secret image. (Hint: The answer looks like a proper picture, not e.g. a random blur of colours).
That wasn’t the real secret image. Having created a perfectly good secret, I let my colleague Greg loose on it for testing purposes and it acquired five more hidden images, encoded in a very similar way. Find them all.
And obviously Greg didn’t go as far as he could have done. Add some more secrets!