## Project Euler Problem #61

### January 3, 2010

Read the details of the problem here

Summary

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

Solution

This is a pretty straightforward problem to solve, it’s really just a matter of working out an appropriate way to crunch through the numbers in order to determine the cycle. It would actually be quite a nice problem to program in a declarative language such as Prolog as it would be naturally expressed by a set of constraints on list elements.

Given this observation, a backtracking recursive approach seemed to be appropriate for an imperative language implementation with the constraints being applied to the selection of the next number in the cycle.

```def polyfuncs = [
3 : { (it * (it + 1)) / 2 },   4 : { it * it },
5 : { it * (3 * it - 1) / 2 }, 6 : { it * (2 * it - 1) },
7 : { it * (5 * it - 3) / 2 }, 8 : { it * (3 * it - 2) } ]

def buildCycle(numbers) {
def cycle = []
buildCycle(cycle, numbers)
return cycle
}

def buildCycle(cycle, numbers) {
if (cycle.size() == numbers.size()) return true
for (poly in numbers.keySet().findAll { p -> !cycle.any { it[0] == p } }.sort().reverse() ) {
def nums = numbers[poly].findAll { n ->
(!cycle.any { it[1] == n }) &&
((cycle.size() == 0) || (n.intdiv(100) == cycle[-1][1] % 100)) &&
((cycle.size() < numbers.size()-1) || (n % 100 == cycle[0][1].intdiv(100)))
}
for (n in nums) {
cycle.push([ poly, n ])
if (buildCycle(cycle, numbers)) return true
cycle.pop()
}
}
return false;
}

def numbers = [:]

for (p in polyfuncs.keySet()) {
numbers[p] = []
def i = 1
while (true) {
Integer n = polyfuncs[p](i)
if (n > 9999) break
if ((n > 999) && (n % 100 > 9)) numbers[p] << n
i++
}
}

def answer = buildCycle(numbers).sum { it[1] }
```

It ran in 0.92 seconds with the generation of the number lists themselves taking 0.61 seconds (66%) of the total runtime. Based on other solutions, I’m assuming that a 100% Java version (as they used to say) would run 40-100x faster but involve quite a lot more code.

The only slight micro-optimisations I made were to reverse the ordering of the lists of eligible numbers such that the lists with the fewest numbers were scanned first – so an empty cycle will begin with octagonal numbers (this makes quite a lot of difference – runtime goes up to 4+ seconds without it), and to deselect during list generation any four-digits numbers that had zero as their third digit as these would never match.

Conclusion

Groovy’s collection enhancements made this quite easy to translate from a problem statement to a solution. The ability to create closures made the building of the six number lists very easy & quite terse (and could have been terser if I’d reversed the logic and used (1000..9999).findAll { <condition> } type clauses). The selection constraints translated quite nicely to declarative search conditions for the findAll{} calls at the heart of the buildCycle() method to extract the eligible number lists and numbers therein.

So, all-in-all, and actual runtime not-withstanding, I would say that Groovy scores nicely over Java in the solution to this problem.