Project Euler Problem #43

April 28, 2010

Read the details of the problem here

Summary

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

Solution

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.

Conclusion

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

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: