Project Euler Problem #68

May 21, 2010

Read the details of the problem here

Summary

What is the maximum 16-digit string for a “magic” 5-gon ring?

Solution

I really didn’t think I’d be able to do this in Groovy and get it to run within my 15 second limit, at least not without some fiddly recursive solution. However, I used Groovy 1.7.2 which has been out for a while now and offers somewhat improved performance and a few extra collection operators. Notable in this solution is the eachPermutation() method which will iterate over a collection and call the closure for each permutation of elements.

The solution itself is quite straightforward and obvious. I don’t want to have duplicated (i.e. rotational symmetric) results so I enforce an ordering of numeral around the outer ring, this means that the first element can’t be greater than 6 otherwise there would be insufficient numbers available. I then enforce the ordering. The next step is to make sure that the number ten doesn’t appear in the inner ring otherwise it would appear twice in the concatenation and make it 17-digits. After getting through those basic guard conditions it’s then a case of making sure the various legs all add to the same total before assembling the string & checking to see if a new maximum has been found.

```def SEQ = [ 0, 6, 7, 1, 7, 8, 2, 8, 9, 3, 9, 5, 4, 5, 6 ]

(1..10).eachPermutation { nums ->

if (nums[0] > 6) return

for (i in 1..<5) {
if (nums[0] > nums[i]) return
}

for (i in 5..<10) {
if (nums[i] == 10) return
}

def sum = nums[0] + nums[6] + nums[7]

def p = 3
while (p < 15) {
if (sum != nums[SEQ[p]] + nums[SEQ[p+1]] + nums[SEQ[p+2]]) return
p += 3
}

def sb = new StringBuilder()
for (i in 0..<15) {
sb.append(nums[SEQ[i]])
}

}
```

It runs in 8.3 seconds. Not fast, but within the 15s target so I’ll leave it there! Improvement is left, as they say, as an exercise for the reader…

Update: Having gained access to the forum, it seems that there is an additional logical tweak, actually a slight refinement to the commencing number that can be used. If I make that minor change the run time drops to 4.3 seconds. Even better!

Conclusion

I thought that Groovy allowed for quite a quick time-to-solution for this problem. Although not the top in performance it wasn’t bad considering this is a brute-force approach. The code is quite clear in intent without a lot of supporting noise.