Project Euler Problem #67

February 8, 2010

Read the details of the problem here


Using an efficient algorithm find the maximal sum in the triangle?


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.

def tiers = []
new File("triangle.txt").eachLine { 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.69 seconds so the algorithm scaled sufficiently.


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.


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: