Project Euler Problem #67

February 8, 2010

Read the details of the problem here

Summary

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

Solution

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.

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

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: