If this doesn't pique the interest of my fellow developers then I don't know what will: a problem that will take twenty billion years to solve (at an extremely optimistic estimate), unless we find an efficient algorithm. The problem in question is Project Euler Problem 67. We're given a triangle made up of one hundred rows of numbers, and asked to consider all routes from the top to the bottom, made by moving from one row to the next via adjacent cells. Over all such routes, we have to find the maximum sum. Can't picture it? Let me help:
For the route that I've drawn, the sum is 5 + 15 + 29 + 45 = [train your brain and work it out yourself!].
If we only wanted to tackle the baby brother of this problem (Problem 18 - the same problem for a triangle with just 15 rows), we could get away with checking each of the routes. But it's not feasible to do that here because there are 299 possibilities: hence the need for an efficient algorithm. Any ideas?
You could take a bath and wait for the Eureka moment. Or if you want to avoid the ensuing streaking, read on.
An algorithm
Suppose that for each cell in a row we know the maximum sum over all routes ending at that cell. From that it's easy to work out the same for each of the cells in the next row. Here's how you do it. If you've got a cell with value c, somewhere in the middle of the row, then you can only reach it from either of the two cells adjacent to it in the row above.
We're assuming that we already know the maximum sum for routes ending at these cells: suppose it is a and b respectively. So the biggest possible sum we can get for routes ending at c is Max(c + a, c + b). For the two cells at either end of the row the calculation is even simpler: they can only be reached from the cell at the appropriate end of the row above them, so we just sum the cell value with the known maximum sum to the cell above. In this way, we can crunch through the rows, 'flattening' the triangle until we reach the last row, at which point we will know the maximum possible sum over all routes ending at each of the cells in that row.
That's the middle of an algorithm. To solve the overall problem we just need to add a beginning and an end. The middle part starts by assuming that we already know the maximum sum for all routes ending at a particular row. So to get the algorithm rolling we need a row for which we do have that information, and the first row of the triangle is the obvious candidate: all routes start there, so the maximum up to that point is just the value of the cell in that row. How about the end of the algorithm? To solve the problem, we need to know the maximum sum from top to bottom through the triangle; we've calculated the maximum sum ending at each of the cells in the last row, so we just need to take the maximum over all these cells.
Some code
To code this, we'll reach once again into our Functional Programming toolbox. I think the Aggregate method is just the hammer to crack this particular nut. Do you see how?
Ignore the input part for now, and assume we've got a sequence of List<int>, one List for each row of the triangle. Like this:
{75}
{95, 64}
{17, 47, 82}
{18, 35, 87, 10}
...
In this layout, it's a little tricky to visualise which cells are adjacent to which: you need to look at the cell directly above, and the one above but to the left. For example, the 35 in row four is adjacent to 47 and 17 in the row above.
We'll use Aggregate to 'flatten' the triangle represented by this sequence of Lists using the algorithm I described above: the aggregate that we'll be calculating is a List containing the maximum sum over all routes to each cell up to the last row we've processed. Remember that Aggregate needs a function that combines the aggregate so far with the next item in the series. We'll supply a function that takes the maximums so far and combines them with the cell values for the next row. The code looks like this:
return rows.Aggregate(
new List<int> {0},
(currentMaxima, nextRow) =>
{
var rowLength = nextRow.Count();
return nextRow
.Select((cell, index) =>
index == 0 ? cell + currentMaxima[index]
: index == rowLength - 1 ? cell + currentMaxima[index - 1]
: Math.Max(cell + currentMaxima[index - 1], cell + currentMaxima[index]))
.ToList();
}
)
.Max();
Notice that at line 7 we're processing the sequence nextRow (containing the cell values) using an overload of the Select method that gives us the index of each cell value in the sequence; we use this index to find the appropriate entries in the list currentMaxima containing the maximum sums to the cells in the row above.
And with that, I believe we've solved the problem. It takes 2 milliseconds to solve the 100-row triangle problem on my computer - a satisfying improvement over 20 billion years.
Here's the complete code. Note that in the source code project I have included two files containing the data for these problems.
namespace ProjectEuler
{
[EulerProblem(18, Title = "Find the maximum sum travelling from the top of the triangle to the base.")]
public class Problem18
{
public long Solve()
{
var dataPath = @"ProblemData\Problem18Data.txt";
return MaximumSumThroughTriangleSolver.SolveFromFile(dataPath);
}
}
[EulerProblem(67, Title = "Using an efficient algorithm find the maximal sum in the triangle?")]
public class Problem67
{
public long Solve()
{
var dataPath = @"ProblemData\Problem67Data.txt";
return MaximumSumThroughTriangleSolver.SolveFromFile(dataPath);
}
}
public static class MaximumSumThroughTriangleSolver
{
public static int SolveFromFile(string dataFilePath)
{
string problemData = File.ReadAllText(dataFilePath);
return Solve(problemData);
}
public static int Solve(string problemData)
{
var rows = problemData
.Split(new[] {Environment.NewLine}, StringSplitOptions.RemoveEmptyEntries)
.Select(line =>
line.Split(' ')
.Select(token => int.Parse(token))
.ToList()
)
.ToList();
return rows.Aggregate(
new List<int> {0},
(currentMaxima, nextRow) =>
{
var rowLength = nextRow.Count();
return nextRow
.Select((cell, index) =>
index == 0 ? cell + currentMaxima[index]
: index == rowLength - 1 ? cell + currentMaxima[index - 1]
: Math.Max(cell + currentMaxima[index - 1], cell + currentMaxima[index]))
.ToList();
}
)
.Max();
}
}
}
