## Project Euler Problem #18

### February 8, 2010

Read the details of the problem here

**Summary**

Find the maximum sum travelling from the top of the triangle to the base.

**Solution**

When I first read this I thought that I was going to have to implement some sort of A* algorithm for route finding as I’d done in AI game routines before. However, it’s a LOT simpler than that!

It’s just a case of noting that the value of a location is the sum of the value of the location itself plus the highest value of its child nodes. It’s then really just a matter of working from the bottom of the pyramid to the top summing these values as you go.

Taking the example triangle as a demonstration.

3 7 4 2 4 6 8 5 9 3

The bottom row is terminal having no child nodes, so the value of the nodes stay as they are. On the next row up, it’s possible to reach either the 8 or the 5 on the bottom row from the 2 – so take the highest value (8) and add it to give 10. The 4 can reach either the 5 or the 9, so select the 9 and add it, giving 13, and so on.

3 7 4 10 13 15

Just continue the process for the next row.

3 20 19

So, on the next level of addition we get 23 for the value of the top node, which is the answer as given in the question. Taking this simple approach makes the coding quite trivial.

def triangle = """ 75 95 64 ... 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23 """ def tiers = [] triangle.split("\n").each { line -> tiers << line.trim().split(" ")*.toInteger() } (tiers.size()-2).downto(0) { row -> for (i in 0..<tiers[row].size()) { tiers[row][i] += [tiers[row+1][i], tiers[row+1][i+1]].max() } } def answer = tiers[0][0]

Runs in 0.52 seconds.

On a personal preference basis, I’m not sure that I like the `upto(){}`

and `downto(){}`

type of syntax though I’ve been using it a bit now to try and get used to it. Maybe I’m just a luddite and too used to reading for-loop syntax over the last 20 years or so!

**Conclusion**

Groovy made it easy to create a ragged array from the data, the [] operator overrides for the lists in the array kept the syntax terse when accessing the elements and the max() method kept the solution clean of noise. All-in-all much better than Java for code clarity and time to implement.

February 8, 2010 at 16:40

[…] This is just a larger version of the problem first introduced in Problem 18 and the algorithm and code I used for that was suitable for this problem too. For details on that see my previous post for a solution. […]