Prob 0067 ‐ Maximum Path Sum II - maccergit/Euler GitHub Wiki

This is basically the same problem as Prob 0018, but scaled to 100 rows read from a file.

01

We don't even think about a brute force approach here - so we start with the solution for Prob 0018 and see it it does the trick,

The first thing we do is examine the data file, and the first obvious issue is the name does not exactly match what was shown in the problem - it has a "0067-" prefix. Not a problem, but something we need to remember when we open the file - we don't want to retype all the data but instead load it from the file. The data is in a nice format - each row separated by newlines, left justified, and space between data values - looks like all data values are two digits, some with leading zero. To use the existing solution, we want to read it in to a list of lists, split on spaces.

As it turns out, the existing solution is more than capable of handling this - so we go from billions of years to around 1.4 milliseconds :

NOTE: The code takes care to not modify the original data - we pass a new copy of the data to the solution function, and not a reference to the original data (this is done by building a new list). This is so we can run multiple tests without the need to re-read the data file each time. This way, we can load the data outside the timing calls, and not include the I/O in the timing (we just want to know how good the algorithm is).