Euler Problem 81

Euler Problem 81 asks:

In the 5 by 5 matrix below, the minimal path Min from the top left to the bottom right,
by only moving to the right and down, is indicated in red and is equal to 2427.

Find the minimal path Min, 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 only moving right and down.

This is very similar to problems 18 and 67, except that they ask for the maximum path to the bottom, not the minimum path to the lower right corner. #81 can absolutely be done in a spreadsheet, as Tushar shows here for numbers 18 and 67. I like to solve them in VBA. The difference between this problem and #67 is that we have to get to a specific matrix cell, and by the rules, if we end up at the right edge, we can only go down, and if we end up at the bottom, we can only go right. In other words, on the right, progressively sum upwards from the lower right corner, and on the bottom, progressively sum leftwards from that same corner. The goal is to abstract the problem so the choice at matrix cell(0)(0) is the minimum of all paths to cell(0)(0). The answer will be the sum of cell(0)(0) and that minimum. Here is my code that does this. It runs in a blink (less that a tenth of a second.)

Sub Problem_081()
   Dim Cell(0 To 79) As Variant
   Dim R As Long, C As Long
   Dim NumRows As Long, NumCols As Long
   Dim Min As Long, IsTest As Boolean
   Dim Answer As Long, T As Single
   Const text  As String = “D:DownloadsEulermatrix.txt”
 
   T = Timer
 
   R = 0
   Open text For Input As #1   ’80 lines, comma delimited
  Do While Not EOF(1)
      Line Input #1, Cell(R)
      R = R + 1
   Loop
   Close #1
 
   IsTest = False
   If IsTest Then
      NumRows = 4
      NumCols = 4
      Cell(0) = “131,673,234,103,18”
      Cell(1) = “201,96,342,965,150”
      Cell(2) = “630,803,746,422,111”
      Cell(3) = “537,699,497,121,956”
      Cell(4) = “805,732,524,37,331”
   Else
      NumRows = 79
      NumCols = 79
   End If
 
   For R = 0 To NumRows
      Cell(R) = Split(Cell(R), “,”) ‘ making a NumRows X NumCols matrix
  Next R
 
   For C = NumCols – 1 To 0 Step -1 ‘rolling up right and bottom edges
     R = C
      Cell(NumRows)(C) = CLng(Cell(NumRows)(C)) + CLng(Cell(NumRows)(C + 1))
      Cell(R)(NumCols) = CLng(Cell(R)(NumCols)) + CLng(Cell(R + 1)(NumCols))
   Next C
 
   For R = NumRows – 1 To 0 Step -1 ‘rolling up the minimums
     For C = NumCols – 1 To 0 Step -1
         Min = Application.WorksheetFunction.Min(CLng(Cell(R + 1)(C)), CLng(Cell(R)(C + 1)))
         Cell(R)(C) = CLng(Cell(R)(C)) + Min
      Next C
   Next R
 
   Answer = Cell(0)(0)
 
   Debug.Print Answer; ”  Time:”; Timer – T
 
End Sub

Having done #67, this was very straight forward. Problem #83, which uses the same matrix, is similar but harder. It’s having its way with me. Here is #83:

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 red and is equal to 2297.

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.

Note the NOTE, the rules change, and the snaking path. It takes 12 moves, whereas #81 only takes 8. The minimum on the left depends on the minimum on the right. As Doug J has said, ’tis circular, and I’ve not grasped it yet. The various code I’ve written does the example, but either takes more than 6400 moves (visiting every cell several times) or ends up in an endless loop in the lower right corner of matrix.txt.

…mrt

Posted in Uncategorized

9 thoughts on “Euler Problem 81

  1. Michael wrote: “#81 can absolutely be done in a spreadsheet, as Tushar shows here for numbers 18 and 67?

    LOL! Yes, Euler 81 is trivial to solve in Excel. Suppose the matrix is in A1:CB80.

    In CB180 enter =CB80+MIN(CB181,CC180). Copy it to A180:CA180. Copy A180:CB180 to rows 101:179. A101 will have the desired answer.

  2. Hi Tushar –

    ;-) Yep, never said it was hard. Except for the order of cells in the MIN() that was exactly my approach, down to having the answer is A101. Must have been looking over my shoulder… ;-) Nicely, the MIN() ignores empty cells beyond the boundaries. In VBA I got out-of-range errors. That necessitated the early rollups of the right and bottom.

    Now, #82 and #83 (using the same matrix) are tougher. See Doug’s iterative spreadsheet solution in the 123 thread for #83.

    …mrt

  3. Re #83: I have some code that does the sample and gives *a* result for the 80×80 matrix (4****5), but how do I know if it’s the right answer?

    (Edited by Michael to conceal the answer)

  4. If 4****5 is the right answer, a Tushar solution is:
    – Import the matrix into B2:CC81 (i.e. with a blank row above and left of it)
    – In B83: =B2
    – In C83: =MIN(C82,B83,C84,D83)+C2
    – Turn on iteration and set max to 1000 or so (100 might not be enough!)
    – Copy C83 to the rest of an 80×80 grid and watch it iterate
    – CC162 has the answer

    (Edited by Michael to conceal the answer)

  5. Hi Stephen –

    In the spirit of Project Euler, we try not to post the answers, particularly the right ones ;-). So, Euler forgive us…

    If you join Project Euler (http://projecteuler.net/index.php), when you then further click on a problem, there is a submit button. Submitting your answer will either come back with a nice apology that “We’re sorry, but your answer appears to be incorrect…” or a check mark and admission into the often-locked discussion group with those that have also solved the problem. Occasionally, there is also a pdf file that provides more insight. Most solutions offered on the inside are written in obfuscated code, usually Python, and often by high-schoolers. But there are a few gems among the pebbles. An author named “rayfil” does the problems in assembly, and while there are some BASIC authors, not many, if any at all, post VBA. That’s what led me to ask Dick if I could post here.

    Doug Jenkins beat you to it and did exactly your spreadsheet solution in the 123 thread. That’s were I first brought up my #83 ineptitude.

    The number of apologies I’ve received greatly exceeds the number of checkmarks…

    …mrt

  6. Since the spreadsheet solutions seem to be well-documented, I’ll describe my VBA method. I used Dijkstra’s pathfinding algorithm (good writeup with pseudocode on Wikipedia). Dijkstra’s is a rudimentary version of how mapfinding programs like Mapquest work. The method is thus: The points in the matrix are nodes, and the values are the distance (cost) to get to that node. Set up a new 80×80 array with values initialized to infinity, except the top-left node to its actual value. Mark all nodes as unvisited (I used an 80×80 array of booleans).
    The Main Loop:
    1. Find the node with the lowest cost (upper-left to start).
    2. For the current node, consider all unvisited neighbors and update the total if it is less than its current value. For example, node (1,2) is initially set to infinity, but its new cost would be 4445+2697=7142, and node (2,1) would be 4445+1096=5541.
    3. Mark the current node as visited. This means it has the lowest possible value and is never considered again. Thus, we never consider node (1,1) again.
    4. If you’re at your goal node, stop, print, cheer. Otherwise, go back to step 1.

    My first attempt solved the problem in about 3s, but I noticed that about 98% of the time was finding the node with the current lowest cost, as in step 1. Each time through, I was looping through all 6400 points, looking for the lowest value. Obviously, an extreme waste of time. After some searching, I decided to learn something new and use a priority queue in the form of a binary heap to always keep track of the node with the lowest cost. I had a heck of a time fiddling with array indices, but eventually the answer came out in 0.1s. I’d be happy to post the code if anyone is interested. I used basically the same code (without the priority queue) for 81 & 82, only changing which nodes are considered as neighbors.

    If you manage to solve a problem and you’re looking at the forum posts for insight, then I recommend that you look for postings by a user named GraemeMcRae. He does the problems with spreadsheet / VBA. His solutions are concise, highly readable, and thoroughly explained. He also appears to have a strong math background and does a good job with explanations. I’ve learned quite a bit from him.

    -Josh

  7. Hi Josh –

    Tomorrow night I’ll try to post my VBA implementation of Doug’s approach. Please feel free to answer with your implementation. We’ll try to get all this Problem 83 stuff in a Problem 83 thread ;-)

    Note Dick’s advice about posting code inside [ V B ] tags, and be watchful for angle bracket pairs inside the VB tags. WordPress treats those pairs as html and hides (throws away) anything in there. Has the virtue of shortening your code ;-) I use LT, GT, LTE, GTE and != for the angle brackets.

    Thanks for the steer on Graeme. Another author to look for is petrw1. He writes in BASIC. If you DIM his variables and change his PRINT to debug.print, it’ll usually run. He’s no good at telling you what his variables do, though.

    …mrt

  8. Michael,
    Thanks for the posting tips. I’ll keep my eyes open for petrw1, though he doesn’t seem to be active anymore. I’ll wait for you to start the P83 thread and I’ll use the time to clean up my code.

    Josh

Leave a Reply

Your email address will not be published. Required fields are marked *