Project Euler Problem #20

February 8, 2010

Read the details of the problem here

Summary

Find the sum of digits in 100!

Solution

Really straightforward if you’ve got BigInteger support.

def answer =
    ((2..100).inject(1G) { p, n -> p * n })
        .toString().toList()*.toInteger().sum()

Runs in 0.48 seconds. Using BigInteger.ONE (in Groovy – 1G) as the seed to inject(){} seems like the cleanest way of forcing type that I’ve found for problems like this.

Conclusion

Groovy made this a simple one liner (though I’ve split it for readability).

Project Euler Problem #19

February 8, 2010

Read the details of the problem here

Summary

How many Sundays fell on the first of the month during the twentieth century?

Solution

If you’ve got it, flaunt it. Here’s a brute-force solution that simply uses the Java built-in calendar classes for a very quickly derived answer.

def (answer, cal)  = [ 0, new GregorianCalendar() ]

1901.upto(2000) { y ->
    12.times { m ->
        cal.set(y, m , 1)
        if (cal.get(Calendar.DAY_OF_WEEK) == Calendar.SUNDAY) answer++
    }
}

Runs in 0.57 seconds. Seems slow for what it’s doing but that’s Groovy for you…

Conclusion

Groovy didn’t make a lot of impact here, apart from keeping the syntax a little cleaner than Java would have been.

Project Euler Problem #18

February 8, 2010

Read the details of the problem here

Summary

Find the maximum sum travelling from the top of the triangle to the base.

Solution

When I first read this I thought that I was going to have to implement some sort of A* algorithm for route finding as I’d done in AI game routines before. However, it’s a LOT simpler than that!

It’s just a case of noting that the value of a location is the sum of the value of the location itself plus the highest value of its child nodes. It’s then really just a matter of working from the bottom of the pyramid to the top summing these values as you go.

Taking the example triangle as a demonstration.

 3
 7  4
 2  4  6
 8  5  9  3

The bottom row is terminal having no child nodes, so the value of the nodes stay as they are. On the next row up, it’s possible to reach either the 8 or the 5 on the bottom row from the 2 – so take the highest value (8) and add it to give 10. The 4 can reach either the 5 or the 9, so select the 9 and add it, giving 13, and so on.

 3
 7  4
10 13 15 

Just continue the process for the next row.

 3
20 19 

So, on the next level of addition we get 23 for the value of the top node, which is the answer as given in the question. Taking this simple approach makes the coding quite trivial.

def triangle =
""" 75
    95 64
    ...
    63 66 04 68 89 53 67 30 73 16 69 87 40 31
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
"""

def tiers = []
triangle.split("\n").each { line ->
    tiers << line.trim().split(" ")*.toInteger()
}

(tiers.size()-2).downto(0) { row ->
    for (i in 0..<tiers[row].size()) {
        tiers[row][i] += [tiers[row+1][i], tiers[row+1][i+1]].max()
    }
}

def answer = tiers[0][0]

Runs in 0.52 seconds.

On a personal preference basis, I’m not sure that I like the upto(){} and downto(){} type of syntax though I’ve been using it a bit now to try and get used to it. Maybe I’m just a luddite and too used to reading for-loop syntax over the last 20 years or so!

Conclusion

Groovy made it easy to create a ragged array from the data, the [] operator overrides for the lists in the array kept the syntax terse when accessing the elements and the max() method kept the solution clean of noise. All-in-all much better than Java for code clarity and time to implement.



			

Project Euler Problem #16

February 4, 2010

Read the details of the problem here

Summary

What is the sum of the digits of the number 21000?

Solution

Very little to say about this one. The only slight twist is the ugly cast to a BigInteger otherwise Groovy will create a BigDecimal and give an engineering string representation.

def answer =
    ((BigInteger)(2**1000)).toString().toList()*.toInteger().sum()

Runs in 0.42 seconds.

Conclusion

Quick and easy to write in Groovy using BigInteger support.

Project Euler Problem #17

February 3, 2010

Read the details of the problem here

Summary

How many letters would be needed to write all the numbers in words from 1 to 1000?

Solution

This isn’t actually too bad to just solve on paper but, in the spirit of the problem, here’s a Groovy something that constructs a dictionary of the words up to one thousand omitting whitespace.

def words = [
    0:"", 1:"one", 2:"two", 3:"three", 4:"four", 5:"five",
    6:"six", 7:"seven", 8:"eight", 9:"nine", 10:"ten",
    11:"eleven", 12:"twelve", 13:"thirteen", 14:"fourteen",
    15:"fifteen", 16:"sixteen", 17:"seventeen", 18:"eighteen",
    19:"nineteen", 20:"twenty", 30:"thirty", 40:"forty",
    50:"fifty", 60:"sixty", 70:"seventy", 80:"eighty",
    90:"ninety", 1000:"onethousand" ]

1.upto(999) {
  if (!words[it]) {
    if (it < 100) {
      words[it] = words[it.intdiv(10) * 10] + words[it % 10]
    }
    else {
      words[it] = "${words[it.intdiv(100)]}hundred"
      def r = it % 100
      if (r > 0) words[it] += "and${words[r]}"
    }
  }
}

def answer = words.values()*.size().sum()

A fun little problem to do. Note that, although the problem doesn’t need it, adding in a empty string for zero avoids some code that would otherwise have to deal with zero values. It runs in 0.69 seconds.

Conclusion

Quick and easy to write in Groovy. Wouldn’t actually be much much more complex or verbose to do in Java using the same algorithm. The Groovy listops made it easy to do the final summation of the word lengths.

Project Euler Problem #15

January 29, 2010

Read the details of the problem here

Summary

Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Solution

Compared to that palava I went through the Project Euler Problem #14 this was very easy indeed!

Solved it by noting that the number of paths to a corner is simply the sum of the paths to the adjacent corners. This gave Pascal’s Triangle values across the diagonals. This is used for binomial expansions and calculating combinations. It can be generated using the following formula:

combination(n, r) = n!/(n-r!)r! – i.e. Ways of picking r elements from n

Solving for: n = 40, r = 20
= 40! / (40-20)!20!
= 40! / 20!20!
= 13 * 20 * 21 * 23 * 29 * 31 * 33 * 37

If you don’t want to do this by hand, Groovy listops make it a straightforward one-liner. Note that it’s only necessary to divide by 20! once as the other division is being done by starting at 21 for the 40! element.

BigInteger answer =
    (21..40).inject(1G) { p, n -> p * n } / (2..20).inject(1G) { p, n -> p * n }

Runs in 0.42 seconds. It’s quicker by a factor of 20 to use a recursive factorial routine than the listops but then it wouldn’t be as Groovy!

Conclusion

Quick to write in Groovy for a one off calculation as simple as this one.

Project Euler Problem #14

January 29, 2010

Read the details of the problem here

Summary

Find the longest sequence using a starting number under one million.

Solution

This one was hard. Not so much in working out an algorithm, which is just pretty much as it says in the question, but simply in getting Groovy to execute it in under 15 seconds.

Here is my first realistic attempt; I put in a cache to store partial results, initially I had tried a dictionary/map and then a List but the performance was lousy so I reverted to using a simple array. I also tinkered with the CACHE_SIZE and found that it was pretty much optimal to have the size the same as the maximum value of i as this saved having another range validation when updating the cache.

def ( maxlen, answer ) = [ 0, 0 ]

def CACHE_SIZE = 1000000
def cache = new int[CACHE_SIZE]

for (i in 1..<1000000) {
  long n = i
  def len = 1
  while (n > 1) {
      if ((n < CACHE_SIZE) && (cache[(int)n] != 0)) {
          len += cache[(int)n] - 1
          break
      }
      n = (n % 2 == 0) ? n / 2 : (3 * n + 1)
      len++
  }
  cache[i] = len
  if (len > maxlen) ( maxlen, answer ) = [ len, i ]
}

This ran in 102.6 seconds. (The ArrayList version of the cache, defined as [0] * CACHE_SIZE had been a lot slower than the native array, taking 144 seconds.) So nowhere near the 15 second target. A bit of profiling showed that the single calculation line was taking 81% of the runtime. Talk about a hotspot!

I couldn’t see how the algorithm could be significantly changed so some micro-optimisation was in order. I’d done low-level performance programming when I used to be interested in graphics programming back in the days of 66 MHz 80486 CPUs but was hoping that today’s high-level Java compilers would remove some of that burden.

My first change was to make the maths (n % 2 == 0) statement into a logical one. I was only interested in the low-bit so I could replace it with ((n & 1) == 0). This brought the runtime down to 97.1 seconds – a saving of 5% – so not too impressive.

Next I changed the (n / 2) statement into n.intdiv(2). As n is defined as a long (and has to be as it exceeds 32-bits for some values of i) and 2 is a constant integer I figured that Groovy should be forcing integer division anyway, but I’d put it in explicitly in any case. This made a HUGE difference, bringing the runtime down to 20.3 seconds. A reduction of 79%!

So, if division was so expensive, could the same be said for multiplication? I next changed the (3 * n + 1) statement to (n + n + n + 1). This got the execution time down to 19.7 seconds – another 3% shaved off. Not much but I’ll take what I can get.

I went back to the n.intdiv(2) statement. One of the tricks when writing in assembler/C is to use a right- or left-shift to divide or multiply by two though this can have implications on the sign-bit. I thought I’d give it a go and changed n.intdiv(2) to (n >> 1). This dropped the time down to 19.3 seconds – barely a 2% saving but worth having. (I did also try the unsigned right-shift operator “>>>” but this had no material effect either way.)

I stopped and had a bit of a think about the problem. I’d reduced the maths overhead as low as I could. It was now only 33% of the runtime. How could I do less of the other 67%? It was only possible to arrive at the termination condition from an even number, a “2” (obviously). The formula used meant that any odd value of n would be changed to a non-terminal even number which would then be immediately divided by 2 on the next pass. So, could these steps be combined and reduce the runtime of the inner while-loop?

The answer was, of course, yes. With the inner-loop replaced with the code below it runs in 15.2 seconds – some 21% faster than before. Still fractionally outside my 15 second cut-off but 85% faster than my initial attempt! The Java equivalent runs in 196 ms – 77x faster – and, for what it matters, a Delphi 6 version takes a mere 117 ms.

if ((n & 1) == 0) {
    n >>= 1
    len++
}
else {
    n = (n + n + n + 1) >> 1
    len += 2
}

How about multithreading the solution? I’ve got 2 cores on my CPU – so let’s use them. Groovy makes this very easy as Closures are Runnables. I took some liberties with thread safety around the cache which the threads share for efficiency and the division of labour between threads was fairly arbitrary. I could have used a queue with the threads pulling work off as they became free, but as this was a hack anyway, these conditions sufficed for my purpose.

Here’s my final offering:

def solve14(start, end, cache, results) {

    def ( maxlen, answer ) = [ 0, 0 ]
    def cache_size = cache.size()

    for (i in start..<end) {
      long n = i
      def len = 1
      while (n > 1) {
          if ((n < cache_size) && (cache[(int)n] != 0)) {
              len += cache[(int)n] - 1
              break
          }
          if ((n & 1) == 0) {
              n >>= 1
              len++
          }
          else {
              n = (n + n + n + 1) >> 1
              len += 2
          }
      }
      cache[i] = len
      if (len > maxlen) ( maxlen, answer ) = [ len, i ]
    }
    results[maxlen] = answer
}

def results = [:] as Hashtable
def CACHE_SIZE = 1000000
def cache = new int[CACHE_SIZE]

def threads = [
    new Thread() { solve14(670000, 1000000, cache, results) },
    new Thread() { solve14(0, 670000, cache, results) }
]

for (thread in threads) {
    thread.start()
}

for (thread in threads) {
    thread.join()
}

def answer = results[results.keySet().max()]

This completes in 10.7 seconds – quite comfortably inside my, admittedly somewhat arbitrary, limit of 15 seconds! It’s marginally faster (by 1 second) to start the upper bound thread first. Although I’ve cheated by using multiple threads to get below the cut-off, it’s not a bad result given how poor initial performance was.

Conclusion

If calculation performance really is needed, then steer clear of Groovy. If you do stick to using Groovy there are a few manual tricks you can use to make it go faster as Groovy doesn’t do it for you!

I’m not going to muck about like this again for computationally intensive solutions. If Java will do the job within the timeframe then I’ll use it either in whole, or in part. After all, what’s the point of having tight Java integration if you don’t use it from time-to-time?