## 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.