Project Euler 83: Find the minimal path sum from the top left to the bottom right by moving left, right, up, and down.

Problem 83 of Project Euler is the natural continuation of Problem 81 and 82 which we have already solved. The problem reads

NOTE: This problem is a significantly more challenging version of Problem 81.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331

Find the minimal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.

The main difference between this and the previous problems is that we can’t use dynamic programming here since we cannot make smaller sub problems since we can move in any direction. So we need to look into something else, here a path finding algorithm would be the obvious choice.

Looking into that kind it seems that A is the industry choice at the moment. I like to explain the algorithms to you, but in case of A I must admit that I have read this introduction to the A* algorithm and realised that there is no way I can do it better.  So before proceeding I would suggest that you follow the link and read through. Don’t forget to come back though.

Ok, so you are back? Just one more note, when I searched for the planning algorithm I came across this rather interesting book call C# Game Programming As you will know by now the A* relies on heuristics so lets look briefly into my choice of Heuristics.

Heuristics

We need a best guess for how far the there is from a square to the goal. This guess has to be smaller than or equal to the real length. So the approach I took was to find the minimal value of the matrix and multiply that by the number of squares that we have to move in order to get to the goal. That way we do fulfil the requirements of the heuristics, and I don’t see a way to improve it.

For the 5×5 example the H matrix would look something like this

162 144 126 108  90
144 126 108  90  72
126 108  90  72  54
108  90  72  54  36
 90  72  54  36  18

The open and closed lists

The difficult part of the algorithm as I see it is keeping track of the open list such that we always investigate the square with the most potential.

I did two things to keep track of the open list. The most important of them was to use a SortedList where the key is the F value of the square and the value is a tuple with the x and y coordinates. There is one small issue with that, since keys have to be unique. So in order to ensure that there were no similar keys I made the key a tuple with the first entry being the F value and the second being an integer to make it unique. I am sure this is not the fastest way, but it works for this problem.

The second thing I did was for speedup. I have to maintain a closed list, which I started by making a bool matrix and setting them to true when I closed a square. In the final implementation I changed it to an integer array such that 0 means unexplores, 1 means in the open list and 2 means in the closed list. That way I only had to access the open list to update a square if it was in the open list and that was quite a speed up.

Implementing A*

I don’t think there is too much to say about the implementation that we haven’t already been through. So here is the code

//init arrays
int minval = readInput(filename);
int gridSize = grid.GetLength(0);
int[,] g = new int[gridSize, gridSize];
int[,] h = new int[gridSize, gridSize];
int[,] searched = new int[gridSize, gridSize];

SortedList, Tuple> openList = new SortedList, Tuple>();

for (int i = 0; i < gridSize; i++) {
    for (int j = 0; j < gridSize; j++) {
        h[i, j] = minval*(2*(gridSize-1)+1-i-j);
        g[i, j] = int.MaxValue;
    }
}

//Add the start square
g[0,0] = grid[0,0];
openList.Add(new Tuple(g[0, 0] + h[0, 0],0), new Tuple(0, 0));

while (searched[gridSize-1, gridSize-1] < 2) {
    Tuple current = openList.ElementAt(0).Value;
    openList.RemoveAt(0);
    int ci = current.Item1;
    int cj = current.Item2;
    searched[current.Item1, current.Item2] = 2;

    //Check the four adjacent squares
    for (int k = 0; k < 4; k++) { int cinew = 0; int cjnew = 0; switch (k) { case 0: //Check the square above cinew = ci - 1; cjnew = cj; break; case 1: //Check the square below cinew = ci + 1; cjnew = cj; break; case 2: //Check the square right cinew = ci; cjnew = cj+1; break; case 3: //Check the square left cinew = ci; cjnew = cj -1; break; } if (cinew >= 0 && cinew < gridSize && cjnew >= 0 && cjnew < gridSize &&
            searched[cinew, cjnew] < 2) { if (g[cinew, cjnew] > g[ci, cj] + grid[cinew, cjnew]) {
                g[cinew, cjnew] = g[ci, cj] + grid[cinew, cjnew];

                if(searched[cinew, cjnew] == 1){
                    int index = openList.IndexOfValue(new Tuple(cinew, cjnew));
                    openList.RemoveAt(index);
                }
                int l = 0;
                while(openList.ContainsKey(new Tuple(g[cinew, cjnew] + h[cinew, cjnew],l))) l++;
                openList.Add(new Tuple(g[cinew, cjnew] + h[cinew, cjnew],l), new Tuple(cinew, cjnew));
                searched[cinew, cjnew] = 1;
            }
        }
    }
}

Wrapping up

The code for this A* algorithm is rather specific for this exact problem and probably not very robust. But it is a sample implementation of an algorithm which I consider very strong. When we run the algorithm it gives us the following result

In the 80x80 grid the min path is 425185
Solution took 26,1002 ms

So it is significantly slower than the dynamical programming. However, it can likely be faster if we employ binary heaps as suggested in the tutorial.

The full source code for this problem is found here. How did you solve the problem, and if you used the A* algorithm did you find a better implementation technique?