Project Euler Problem #43

April 28, 2010

Read the details of the problem here


Find the sum of all pandigital numbers with an unusual sub-string divisibility property.


I initially started to do this with a brute-force solution based on permutations but it became quickly apparent that Groovy just wasn’t going to be performant enough to run this sort of solution with 15 seconds.

I then opted to try a recursive solution, where the program attempts to find matching eligible substrings for each of the primes in turn. The “6” in the call to matching() relates to the highest index of the primes array in getCandidates(). It works, though it’s not the most elegant piece of programming!

def uniqueDigits(s) {
  (s.toList() as Set).size()

def getCandidates(lvl) {
  def primes = [17, 13, 11, 7, 5, 3, 2]
  def result = []
  for (i in 1..<1000) {
    def s = ("000" + i.toString())[-3..-1]
    if ((i % primes[lvl] == 0) && (uniqueDigits(s) == 3)) result << s
  return result

def matchSets(p1, p2) {
  def res = []
  for (s1 in p1) {
    p2.findAll { s2 -> (s1[-2..-1] == s2[0..1]) && (!s2.contains(s1[0])) }
      .each { res << (s1[0] + it) }
  return res

def matching(lvl) {
  if (lvl == 0) return getCandidates(lvl)
  return matchSets(getCandidates(lvl), matching(lvl-1))

def pandigitals = matching(6).collect {
  for (n in "0".."9") {
    if (!it.contains(n)) return n + it

def answer = pandigitals.sum { it.toLong() }

This runs in 0.17 seconds. So, not bad considering the mess.


Groovy did quite a good job with this. The syntax was quite terse and the performance adequate. I stayed clear of metaClass extensions which might have improved readability in places as they don’t perform as well as straight method invocations (but given that it ended up being quite fast this was probably unnecessary).


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your 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: