Project Euler Problem #92

September 11, 2010

Read the details of the problem here

Summary

Investigating a square digits number chain with a surprising property.

Solution

Simple and straight-forward non-mathematical problem to solve. I coded up the following program – note that after one pass the value of the sum of the squares will reduce to 7×92 (or 567) at most so the cache is relatively small for the entire range of numbers.

def LIMIT = 10000000
def CACHE_SIZE = 9 * 9 * 7
def sumsOfSquares = new int[CACHE_SIZE+1]

Arrays.fill(sumsOfSquares,0)
sumsOfSquares[1] = 1
sumsOfSquares[89] = 89

def answer = 0

for (i in 2..LIMIT) {

  def sum = i

  while ((sum != 1) && (sum != 89)) {
    def n = sum
    sum = 0

    for (c in n.toString()) {
      def v = c.toInteger()
      sum += v * v
    }

    if (sumsOfSquares[sum] != 0) sum = sumsOfSquares[sum]
  }
  if (i <= CACHE_SIZE) sumsOfSquares[i] = sum
  if (sum == 89) answer++
}

This ran in 36.14 seconds so it was well outside my 15 second target. I did some tweaks to the code converting it into to a recursive function and trying some extra cache lookups at the beginning of the calculation but only managed to reduce the runtime down to 31.81 seconds. (Using Groovy listops rather than the explicit loops for calculating the sum pushes the time out to over 2 minutes.) Although a straight Java conversion would probably run in a second or two I felt that some improvement could be made to the algorithm as the curent solution didn’t really use much of one to speak of.

The obvious observation is that the sum of squares function is being performed many times for numbers that are fundamentally the same as the sum will be the same for all permutations of a given set of digits i.e. the number 3241218, is the same as 2314821 or 1122348. A quick experiment revealed that there are only 11,440 such unique permutations – that would reduce the number of times the expensive summing operation had to be called by a factor of around 870.

In order to maintain the count it would be necessary to know many times a given set of digits can occur in the full 107 range. This is simply the factorial of the total number of elements divided by the product of the factorials of the counts of the unique elements.

As there were only a total of 7 digits I could have just coded nested loops to construct the numbers but I already had a generator for such a purpose built as part of the solution to Problem #110. This generates the digits in descending order and is general purpose but would do the job easily though, as it uses Groovy listops, isn’t the fastest means.

So it was just a case of pre-populating the cache, generating the unique digit sequences, calculating the initial sum of squares, pulling the terminal result from the cache and, for those that resulted in 89 getting the multiples of that to add to the total.

def sumOfSquares(n) {
  def sum = 0
  for (c in n.toString()) {
    def v = c.toInteger()
    sum += v * v
  }
  return sum
}

def permutations(n) {
  def factorials = [ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 ]                     
  def s = 1
  for (i in n) {
    s *= factorials[i]
  }
  return factorials[7].intdiv(s)
}

def gen_digits(range, maxlen, yield) {
  gen_digits(range, maxlen, [], yield)
}

def gen_digits(range, maxlen, digits, yield) {
  if (digits.size() == maxlen)
    yield(digits)
  else if (digits.size() == 0)
    range.each { gen_digits(range, maxlen, [it], yield) }
  else
    range.findAll { it >= digits[0] }
         .each { gen_digits(range, maxlen, [it]+digits, yield) }
}

def MAX = 9 * 9 * 7
def sumsOfSquares = new int[MAX+1]

Arrays.fill(sumsOfSquares,0)
sumsOfSquares[1] = 1
sumsOfSquares[89] = 89

for (i in 2..MAX) {
  def sum = i
  while ((sum != 1) && (sum != 89)) {
    sum = sumOfSquares(sum)
    if (sumsOfSquares[sum] != 0) sum = sumsOfSquares[sum]
  }
  sumsOfSquares[i] = sum
}

def answer = 0

gen_digits((0..9), 7) { digits ->
  def sum = sumsOfSquares[sumOfSquares(digits.join().toInteger())]
  if (sum == 89) {
    def nn = new int[10]
    digits.each { nn[it]++ }
    answer += permutations(nn)
  }
}

It’s all a little too verbose for my liking but does run in 0.57 seconds so nicely succeeds in the objective. Expanding out the listops to explicit loops in the gen_digits() generator method reduces the runtime to 0.36 seconds – a substantial saving of 37% but at the expense of a few more lines of code.

Conclusion

Groovy general “slowness” meant that some “cleverness” was required to get this to execute in a reasonable amount of time. If I’d been using C++ or native Java for this I would have just stuck with the simple initial approach.

Advertisements

Project Euler Problem #97

September 5, 2010

Read the details of the problem here

Summary

Find the last ten digits of the non-Mersenne prime: 28433 × 27830457 + 1.

Solution

Easy to translate straight into code as it stands. No working out necessary!

def PREC = 10G ** 10
def answer =
    (2G.modPow(7830457G, PREC) * 28433G + 1G).mod(PREC)

This runs in 18 ms. A Java version, using long-hand BigInteger syntax takes about 1 ms – so around 18x faster. That’s the cost of syntactic sugar in Groovy.

Conclusion

This was one of those “if you’ve got it, flaunt it” problems. The combination of the powerful JVM and convenient Groovy syntax for BigInteger support made for a simple solution albeit less performant than a native Java implementation.

Read the details of the problem here

Summary

Devise an algorithm for solving Su Doku puzzles.

Solution

I kicked this one off with a straightforward list-based recursive solution but couldn’t get the time down below around 36 seconds using solely this approach. I managed to get it down to 27 seconds using an array for representing the grid and lists just for validity checking but I really needed an algorithmic fix to get the time down significantly. (recurse() calls = 2,842,877 (100%).)

At this point I did consider whether I should jump to a full-blown OO solution and model the grid, cells and row/column/subgrid structures appropriately. Although this would have probably led to much neater solution, it seemed overkill for this problem. I just ploughed ahead with the idea of putting in the minimum function to get the problem answered. After all, this was a programming, rather than a maths, problem.

I initially inserted a simple reduction routine that kept iterating through the grid, reducing the eligible entries for each cell (which I had to add when setting the grid up) based on the contents of the row, column and subgrid that the cell belongs to. That cost only 300 ms or so, was sufficient to solve 12/50 puzzles directly (which meant that the recusive routine was never used) and dropped the overall runtime down to 22.8 seconds. So nearly there. (recurse() calls = 1,680,969 (59%). Cells completed by logic: 718.)

I then added a routine, uniques(), that checked just the rows for cells that had a missing number in only one location. If such a number was found the number would be entered in the appropriate cell. As it was only working on a row-by-row basis it didn’t need to handle updates of the eligible lists for affected cells, leaving that operation to the interleaved  reduce() function (as above).

I did consider making these functions recursive themselves but it seemed overcomplicated. Instead, I just combined these two routines such they kept on being called until they found no potential updates.

Adding the uniques() function cost another 300 ms or so, but managed to solve 23/50 of the puzzles completely (which I thought was quite amazing given the simplicity of the algorithm) and reduced the overall runtime to 3.3 seconds as many more of the missing cells had been filled in before the recursive search was called so it then had a lot less work to do. Doubling the number of cells resolved by logic dropped the recursive effort by an order of magnitude. (recurse() calls = 194,793 (7%). Cells completed by logic: 1,388.)

Unfortunately, all this makes the code a little too long…even in Groovy.

def recurse(grid, r, c) {
  if (grid[r][c][0] != 0) {
    if (( r == 8 ) && ( c == 8 )) return true
    def (r1, c1) = ( c == 8 ) ? [ r + 1, 0 ] : [ r, c + 1 ]
    return recurse(grid, r1, c1)
  }

  def unavail = used_numbers(grid, r, c)

  for (i in 1..9) {
    if (unavail.contains(i)) continue
    grid[r][c][0] = i
    if (recurse(grid, r, c)) return true
  }

  grid[r][c][0] = 0
  return false
}

def used_numbers(grid, r, c) {
  def used = [] as Set
  for (i in 0..8) {
    used << grid[r][i][0]
    used << grid[i][c][0]
  }
  def (gr, gc) = [ 3 * r.intdiv(3), 3 * c.intdiv(3) ]
  for (y in gr..gr+2) {
    for (x in gc..gc+2) {
      used << grid[y][x][0]
    }
  }
  used
}

def reduce(grid) {
  def updated = true
  def count = 0
  while (updated) {
    updated = false
    grid.eachWithIndex { row, y ->
      row.eachWithIndex { cell, x ->
        if (cell[0] == 0) {
          cell[1] -= used_numbers(grid, y, x)
          if (cell[1].size() == 1) {
            cell[0] = cell[1][0]
            ( updated, count ) = [ true, count + 1 ]
          }
        }
      }
    }
  }
  count
}

def uniques(grid) {
  def count = 0
  grid.each { row ->
    def uniq =
        row.findAll { it[0] == 0 }
           .collect { it[1] }
           .flatten()
           .groupBy { it }
           .findAll { it.value.size() == 1 }
           .keySet()

    uniq.each { v ->
      def cell = row.find { it[1].contains(v) }
      cell[0] = v
      cell[1] = [v]
      count++
    }
  }
  count
}

def solve(lines) {
  def grid =
      lines.collect { line ->
        line.collect {
          def v = it.toInteger()
          [ v, v == 0 ? (1..9).toList() : [v] ] }
      }

  def updates = -1
  while (updates != 0) {
    updates = 0
    updates += reduce(grid)
    updates += uniques(grid)
  }

  if ((0..2).any { grid[0][it][0] == 0 }) recurse(grid, 0, 0)

  grid[0][0..2].inject(0) { p, v -> p * 10 + v[0] }
}

def answer = 0

def sudoku_text =
    new File("euler_p96_sudoku.txt").text.split("\r\n")

sudoku_text.eachWithIndex { line, idx ->
  if (line.startsWith("Grid")) {
    answer += solve(sudoku_text[idx+1..idx+9])
  }
}

Being one to tinker, I made a few more enhancements and got the runtime down to 1.52 seconds with all but two grids, #7 and #50, being solved entirely by logic. It soon got to a point of dimishing returns though. The additional logic was taking just about as long to run as just calling the recursive solver with the increased number of completed cells.

Conclusion

Not the neatest of solutions, but reasonable interesting. I made use of a lot of Groovy listops here which probably impacted performance unduly, but was otherwise easy to work with. It could have easily been done just using a 100% Java version of the recursive solution without any “clever” logic being required. (Indeed such an implementation, using an int array rather than lists, runs in 0.18 seconds…though not really a direct comparison that’s 100+ times faster.)

Read the details of the problem here

Summary

Investigating words, and their anagrams, which can represent square numbers.

Solution

When I first read this question I had visions of having to create mappings of characters to a full set of digit permutations from 0-9. As it happens though it wasn’t necessary to do this and instead just map potential solutions onto the given strings which greatly reduced the search space.

The solution begins by constructing a map of lists of squares of appropriate lengths. Then there’s a boilerplate method of reading the file and breaking the words up into a list, before grouping words and finding all the entries with anagrams.

For each of those entries, the list of words is then run through, with the intent of comparing each word with each other in the list. (There is only one word that has three anagrams, so usually this just checks two words against each other.) For each number in the appropriate list of matching squares, it will try to get a mapping of characters to digits for the first word, calculate the value of the second word (after ruling out palindromes) using that mapping and then check to see if that value is a valid square. (It’s not necessary to do an explicit check for leading zeroes as, if the solution included one, the value wouldn’t be found on the specific list of squares.) If a valid square number is found then the maximum value is tracked as the answer.

def ( nums, answer ) = [ [:], 0 ]

(2..10).each {
  def min = Math.ceil(Math.sqrt(10 ** (it-1)))
  def max = Math.floor(Math.sqrt((10 ** it)-1))
  nums[it] = (min..max).collect { (it * it).toInteger() }
}

new File("euler_p98_words.txt").text.replace("\"","").tokenize(",")
    .groupBy { it.toList().sort().join() }
    .findAll { it.value.size() > 1 }
    .each { key, words ->
       for (i in 0..<words.size()-1) {
         def len = words[i].size()
         for (n1 in nums[len]) {
           def map = getMapping(words[i], n1.toString())
           if (map.size() == 0) continue
           for (j in i+1..<words.size()) {
             if (words[i].reverse() == words[j]) continue
             def n2 = words[j].collect { map[it] }.join().toInteger()
             if (n2 in nums[len]) answer = [ n1, n2, answer ].max()
           }
         }
       }
     }

The getMapping() function (shown below) takes two string arguments; a word to be mapped, along with the number (which will be a valid square solution) that it’s to be mapped to. It returns the appropriate mapping, or an empty map if the mapping was not possible due to trying to map a character to multiple digits, or if a digit is mapped against multiple characters.

def getMapping(word, number) {
  def map = [:]
  for (i in 0..<word.size()) {
    def ( c, digit ) = [ word[i], number[i] ]
    if (!((map[c] == null) || (map[c] == digit))) return [:]
    map[c] = digit
  }
  if (map.groupBy { it.value }.any { it.value.size() > 1 }) map = [:]
  return map
}

This runs in 1.82 seconds. It would faster in native Java (of course!) but would require considerable more code.

Conclusion

Groovy’s features were used a lot here in: specifically in reading and filtering the original list of words and again in decoding the subsequent anagrams against the map. I’d say that Groovy is a winner on this one but I don’t know how performant it would be on much larger volumes of data.

Project Euler Problem #99

November 18, 2009

Read the details of the problem here

Summary

Which base/exponent pair in the file has the greatest numerical value?

Solution

I took the straightforward approach to this one. As the resulting numbers would be huge it was just a matter of using log10(base) * exp and comparing those values. The coded solution is trivial.

def ( i, answer, max ) = [ 1, -1, 0.0 ]

new File("base_exp.txt").eachLine {
    def ( base, exp ) = it.split(",")*.toDouble()
    def log = Math.log10(base) * exp
    if (log > max) ( answer, max ) = [ i, log ]
    i++ 
}

It ran in 46 ms and took a very short time to write!

Conclusion

Groovy was a very nice language to use for this. It was very easy to read the file and process the contents. See how the spread-dot operator is used on the list resulting from the split to convert both operands in to Doubles ready for the next step. The only slightly irritating part was that I had to maintain my own record count as there is no eachWithIndex() method available on a File object. I could have treated this differently by reading into a list first but this seemed quicker!

As there was no heavy maths processing performance was fine, it was quick to write and the code intent is clear.