Softwire Speed Coding Challenge – Question 4

---

21 May 2012, by Chris Williams

previous article in series

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.

Hint:

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!

next article in series

Tags: .NET, puzzles, social, softwire, speed coding, technical

Categories: Social, Softwire, Technical