Project Euler Problem #11

January 26, 2010

Read the details of the problem here

Summary

What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?

Solution

Another straightforward programming, rather than mathematical, problem from Euler’s stables.

def numgrid =
    """08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77...
       ...70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"""

def nums = []
numgrid.split("\n").each {
    nums << it.trim().split(" ")*.toInteger()
}

def ( maxx, maxy ) = [ nums[0].size(), nums.size() ]

def prod4(nums, y , x, dy, dx) {
    (0..3).collect { nums[y+it*dy][x+it*dx] }.inject(1) { p, n -> p * n }
}

def p = []
for (y in 0..<maxy) {
    for (x in 0..<maxx) {
      if (x < maxx-3) p << prod4(nums, y, x, 0,  1)
      if (y < maxy-3) p << prod4(nums, y, x, 1,  0)
      if ((x < maxx-3) && (y < maxy-3)) p << prod4(nums, y, x, 1,  1)
      if ((x > 2) && (y < maxy-3)) p << prod4(nums, y, x, 1, -1)
    }
}

def answer = p.max()

This runs in 0.65 seconds. I deliberately used the Groovy listops probably more than I should have and this has impacted the overall performance which would probably be a little faster if a more imperative approach was taken. I did actually try it with prod4 being a closure on the num array object but, whilst this was a neat solution syntactically, it pushed the runtime out to 0.91 seconds – a 40% overhead on the procedural solution.

Conclusion

Groovy was a fun language to do this in. It made it very simple to interpret the input and prepare it for the main routine. The listops made calculating the product for any particular 4-number sequence a one-liner. The Groovy syntax enhancements are very neat but aren’t as performant as their more verbose procedural equivalents

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: