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

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

Written by on 11 February 2012

Topics: Project Euler

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.

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

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?

10 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    I used Dijkstra’s algorithm. I think it’s more fitting here, since I can’t see how any heuristic would be beneficial for solving this problem.

  2. Kristian says:

    I do believe that the A* algorithm is Dijkstra’s algorithm without the Heuristics. So if you remove the Heuristics you would be back at Dijkstra’s algorithm. Djikstra’s algorithm seem to empty the whole search space, so with a bit of luck A* should be able to cut of a few notes.

    However, for this problem I don’t think there will be much of a difference. That being said I think it is a hugely interesting field to work in. So much fun.

    /Kristian

  3. qwe says:

    First I did backtracking with recursion, since I never had to traverse a graph in my life before 😀 and never being heard of Dijkstra or so. Using global minimum path-sum(dropping search if current path-sum goes above that) took miserable ten minutes. (and dramatic total 180k visits to nodes)

    I got dramatic speed-ups thorough doing Dijkstra multiple times – until none of the path-sums are updated.

  4. Kristian says:

    Hi

    So the global minimum path-sum you mention. Do you search every path basically, and drop them once you reach the current minimum? In that case, yes that should take a while.

  5. Sergio says:

    Hi

    I also used Dijkstra’s algorithm, but my heap implementation was wrong. As I was a little desperate, I jumped the heaps and just sorted a list with a quick search algorithm for inserting and deleting. At the end, I also forgot to add the weight on the 1,1 position, so I was about 4,000 low from correct answer.

  6. LouWeed says:

    (just started doing pe problems again after taking a 2 year break that was caused by the frustration of (not) solving #78)
    About the heuristic calculation: a better and more accurate estimation of the minimal cost from a given node to the end is to take the lowest n values of the matrix where n is the minimum distance, and then add them together. So the heuristic matrix for the example matrix would look like:
    767 617 486 365 254
    617 486 365 254 151
    486 365 254 151 55
    365 254 151 55 18
    254 151 55 18 0

    Using this heuristic, I get the solution in 939ms. I’m not sure if the different heuristic is responsible for the performance improvement, but it’s the only obvious difference I could see. Note that I am caching the heuristic for each distance so they only need to be calculated once.

  7. Kristian says:

    It makes sense to improve the heuristics like that, you could try to use both heuristics to see if you get a performance difference. It would be an interesting comparison.

  8. cn says:

    I have used Dijkstra too. Considered the matrix to be a graph of size n * n . The edge cost for (u, v) is matrix[ln, col], where ln = u/n and col = u%n and v is a neighbor in the matrix (4 values at most, (ln+-1)*n + col, ln*n + col+-1).

  9. nuri says:

    I tried to convert your code to C++. I admit I was so lazy to rewrite 🙂
    Due to differences between C# and C++, it didn’t work.
    So I decided to implement from scratch.
    It’s a Dijkstra derivative since I don’t care about heuristics. And since the path itself is irrelevant, nodes don’t have parent nodes.
    It seems pretty fast, finding correct answer in ~0.6 ms (only dijkstra part, reading input file is not included).

    If anyone is interested, here is the code: http://pastebin.com/FjbuGrbU

  10. Ernst says:

    I agree that A* is a very strong minimum-path tactic, but not very suitable for this problem with a relative small grid (only 1600 nodes) without any uncertainty. Which translates to: no uncertainty -> no heuristics needed (imo)

    For my C# solution I (too) used Dijkstra, which ran in 8 ms.
    Source at https://gist.github.com/anonymous/68dc59a289fcc20abc5b

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.