Softwire Speed Coding Challenge – Question 4 Discussion


28 May 2012, by

previous article in series

In our last coding challenge post, we posed the final question from our coding challenge. Did you manage to finish it?

Here’s a reminder of what the question was, in case you’ve forgotten:

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

Hampton Court Maze - Click for full size

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.

We didn’t get quite so many finishers for this question (it was getting pretty late…) but the winning entry this time was from Preeyan Parmar, a 2011 intern not currently working at Softwire but who was keen to enter.

Answer

 

Maze Answer - Click for Full Size

Again, I’ve decided to add some comments to the winning solution, to show what is happening although this solution is pretty clear so I haven’t added very much. Where I have added comments, I’ve also added my initials (CAW), as Preeyan did make some comments of his own!

Winning Solution – Submitted by Preeyan Parmar

static Queue xq = new Queue();
static Queue yq = new Queue();
static long[,] val = new long[1024, 680];

static void Main(string[] args)
{
  var img = (Bitmap)Image.FromFile("C:\Users\Preeyan\Desktop\hampton.png");
  int x, y;

  //-----------------------------------------------------------------------
  // CAW: Initialise minimum distances from each pixel. Only initialise
  // pixels that are the right colour.
  //-----------------------------------------------------------------------
  for (int i = 0; i < 1024; i++)
  {
    for (int j = 0; j < 680; j++)
    {
      if (img.GetPixel(i, j).ToArgb() == -1)
      {
        val[i, j] = long.MaxValue;
      }
      else
      {
        val[i, j] = -1;
      }
    }
  }

  val[511, 679] = 0;
  xq.Enqueue(511);
  yq.Enqueue(679);

  //-----------------------------------------------------------------------
  // CAW: Cycle through all adjacent pixels to find their minimum distance
  // to the goal. If necessary, this updates the minimum distance from the
  // current pixel as well.
  //-----------------------------------------------------------------------
  while (xq.Count > 0)
  {
    x = xq.Dequeue();
    y = yq.Dequeue();

    if (x != 0) examine(x, y, x - 1, y);
    if (x != 1023) examine(x, y, x + 1, y);
    if (y != 0) examine(x, y, x, y - 1);
    if (y != 679) examine(x, y, x, y + 1);

    if (x != 0 && y != 0) examine(x, y, x - 1, y - 1);
    if (x != 1023 && y != 0) examine(x, y, x + 1, y - 1);
    if (x != 0 && y != 679) examine(x, y, x - 1, y + 1);
    if (x != 1023 && y != 679) examine(x, y, x + 1, y + 1);
  }

  Console.WriteLine("length: " + val[511, 339]);

  x = 511;
  y = 339;

  //-----------------------------------------------------------------------
  // CAW: Backtrack through the maze, looking at the lengths, so that we
  // can draw the fastest route (or at least *a* fastest route, as there
  // are multiple routes with the same distance.
  //-----------------------------------------------------------------------
  while (val[x, y] > 0)
  {
    img.SetPixel(x, y, Color.Magenta);

    if (x != 0 && val[x-1,y] == val[x,y] - 1) {x--; continue;}
    if (x != 1023 && val[x+1,y] == val[x,y] - 1) {x++; continue;}
    if (y != 0 && val[x,y-1] == val[x,y] - 1) {y--; continue;}
    if (y != 679 && val[x,y+1] == val[x,y] - 1) {y++; continue;}

    if (x != 0 && y != 0 && val[x - 1, y - 1] == val[x, y] - 1)
    { x--; y--; continue; }

    if (x != 1023 && y != 0 && val[x + 1, y - 1] == val[x, y] - 1)
    { x++; y--; continue; }

    if (x != 0 && y != 679 && val[x - 1, y + 1] == val[x, y] - 1)
    { x--; y++; continue; }

    if (x != 1023 && y != 679 && val[x + 1, y + 1] == val[x, y] - 1)
    { x++; y++; continue; }
  }

  img.Save("C:\Users\Preeyan\Desktop\outmaze.png");

  Console.ReadLine(); // stop the output window from disappearing until you press 'enter'
}

//-------------------------------------------------------------------------
// CAW: If the current minimum distance from the adjacent pixel is higher
// than the distance of the current route, update it (and update any pixels
// linked to it, based on the new information).
//-------------------------------------------------------------------------
static void examine(int x, int y, int xn, int yn)
{
  if (val[xn, yn] > val[x, y] + 1)
  {
    val[xn, yn] = val[x, y] + 1;
    xq.Enqueue(xn);
    yq.Enqueue(yn);
  }
}

Comments on the Winning Solution

As was the case with the last question, the answers followed the same broad structure as the question provided a good algorithm for both the distance calculation and the subsequent route highlighting.

I did have some comments though:

  • It would have saved on some memory (and possibly some time in comparisons) if the array of distances was an int[,] rather than a long[,]; more so if short[,] was used. Given we have an array with almost 700k values, it does add up!
  • The code is clear and nicely laid out. If Preeyan had made any off-by-one errors or similar at an early stage, the layout of the code would have made it easier to debug and therefore easier to figure out where the issue was
  • Only a useful hint if you are using Visual Studio, but if  you run your program using Ctrl + F5, rather than just F5, it will pause at the end for you doing the equivalent of Preeyan’s final Console.ReadLine();

Other Comments

I feel I should mention that straight-up Dijkstra isn’t the most efficient pathfinding algorithm out there (in fact, something like A* may lead to a quicker solution in terms of processing). Dijkstra is probably the best choice however, if trying to strike a balance between efficiency of the code itself and efficiency generating that code (which is obviously just as important, if not more so in a speed coding challenge).

In other news, Sam Carr got a bonus point for coming up with this image, where red pixels are not traversable (i.e. not pure white in the original image) and the lighter a pixel is, the further away from the start point it is.

Sam's Stylish Hampton Court Maze

Final Standings

Here’s what you’ve all been waiting for, the final scores! You weren’t really just waiting for the answer, were you?

The top 5 finishers (and their respective points in each question) were:

1st Place: Matthew Richards – 18 points (5+1, 5, 4, 3)

2nd Place: Rupert Wood – 12 points (1, 3+1, 5+1, 1)

3rd Place: Iain Munro – 11 points (0, 4+1, 3+1, 2)

4th Place: Joey Taylor – 8 points (0, 2, 2, 4)

5th Place: Preeyan Parmar – 7 points (0, 1, 1, 5)

Honourable mentions also go to Joe Lee-Moyet, Chris Harris, myself and Sam Carr for scoring points.

So a big congratulations to Matthew, who is now responsible for the organisation of this year’s challenge. Until then, keep practicing!

Tags: , , , , ,

Categories: Social, Softwire, Technical

«
»

Leave a Reply

* Mandatory fields


eight + = 12

Submit Comment