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.



					
Advertisements

One Response to “Project Euler Problem #18”


  1. […] 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. […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: