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)
}
}

```

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