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.

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: