28 May 2012, by Chris Williams
In our last coding challenge post, we posed the final question from our coding challenge. Did you manage to finish it?
21 May 2012, by Chris Williams
We’re back, with the final question of the 2011 Softwire Coding Challenge!
Navigating The Hampton Court Maze
Here is a picture of a familiar-looking maze. This version of the image is slightly cut down from the version used in the competition itself; click it to see the full-size image (which you should use if you’re trying this yourself).
Write a program to draw a magenta line (#FF00FF) from the exact bottom middle of the image to the exact centre of the image in the shortest distance possible. Pixels are considered adjacent if they touch horizontally, vertically or diagonally, and only perfectly white pixels (#FFFFFF) are traversable. The answer should contain the total distance travelled in terms of number of pixels (not spatial distance) and the program you used.
The simplest optimal path finding algorithm is called Dijkstra’s algorithm (hope you brushed up on it!), and goes something like this:
- Assign each pixel a distance from the start, initialise these values to +infinity
- Assign the start pixel distance 0, add it to the back of a FILO queue
- While your queue is not empty, pop the first pixel from the queue: call this “current pixel”
- Examine all the pixels adjacent to the current pixel
- If their recorded distance is greater than the current pixel’s recorded distance + 1, then:
- Set their distance to be the current pixel’s recorded distance + 1
- Add the pixel to the back of the queue
- When you have examined all pixels in this fashion, each pixel will be marked with its minimum possible distance to the start
- You can then trace the optimal route from the end to the start by placing a pointer at the “end” pixel and moving repeatedly to an adjacent pixel whose distance is 1 less than where you are looking (until you reach distance “0” – the start)
Once again, best of luck with this one; let us know how you get on with this in the comments and we’ll post the answer soon!
14 May 2012, by Chris Williams
In our last coding challenge post, we posted question 3 from our coding challenge. Did you try it yourself? Here’s the question again, as a reminder:
6 May 2012, by Chris Williams
Welcome to the next in our series on Softwire’s coding challenge! Last time, we discussed the winning answer to the second question. This time round we’ve got a cryptography question for you (although you won’t need to know anything special) – I’ll post the winning answer and some further discussion in a week or so.
Truly Unbreakable Security
- Short summary of the encryption: XOR each byte of the plaintext file with the next byte produced by a new instance of System.Random in C#
- I have linked the source code of the encrypting app as Vernam.zip (NOTE: you do not need to read this)
I would like you to decrypt secret.dat (feel free to unzip it manually first).
To aid you in this, here are the 7 most common “magic numbers” from Wikipedia. These are byte sequences which appear at the start of a file to mark the file format:
CAFEBABE class 47494638 gif FFD8FFE0 jpeg 89504E47 png 4D546864 midi 25504446 pdf 504B0304 zip
As if that weren’t enough, you also get these two enormous hints:
- There are two constructors for System.Random – the default no-args constructor uses Environment.TickCount as a seed
- I rebooted my system less than an hour before encrypting this file
Best of luck with this one, we’ll post the winning solution and the answer in a couple of weeks!
30 April 2012, by Chris Williams
So, in our last speed coding post, we set you the second question in our challenge. Here it is again, just to remind you!
23 April 2012, by Chris Williams
Welcome to the next in our series on Softwire’s coding challenge! Last time, we discussed the winning answer to the first question. Here’s question 2 for you to try, which may require a bit of mathematical knowledge – I’ll post the winning answer and some further discussion in a week or so.
16 April 2012, by Chris Williams
Last time out, we set you the first question from our recent Speed Coding Challenge, giving you the opportunity to answer it yourselves and compare your efforts to our winning answer. Here’s question 1 again, just to remind you what it was!
9 April 2012, by Chris Williams
Softwire recently hosted their second speed coding challenge, after the inaugural competition proved to be a resounding success. The competition was open to current employees (and recently departed interns) 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!
Over the course of the next few months, I’ll be adding some details of the questions that were asked and discussing the winning answers (as well as announcing the eventual winner). In this post, I’ll explain the format of the night and the scoring system used and will give you the first question, so you can give it a shot yourself!