Project Euler Problem #9

January 25, 2010

Read the details of the problem here

Summary

Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

Solution

Straightforward, brute force approach but trying to avoid as much “complex” computation as possible in order to keep the performance up.

def answer = 0

for (a in 1..<500) {
    for (b in (a+1)..500) {
        def c = 1000 - (a + b)
        if ((c > b) && (c * c == a * a + b * b)) {
             answer = a * b * c
             break
        }
    }
    if (answer > 0) break
}

This runs in 0.53 seconds. A Java equivalent runs in 5 ms – two orders of magnitude faster. The breaks on the loops are messy but clear enough given this limited context.

Conclusion

Groovy’s language features didn’t really play any part in this solution. It was just straightforward number crunching. It did originally use <range>.each {} closure constructs for the loops but didn’t like the way it was necessary to throw an exception to bale out when an answer was found. I don’t think that it made the solution any clearer or simpler to write in this particular scenario. Groovy maths performance was dire.

Project Euler Problem #10

January 7, 2010

Read the details of the problem here

Summary

Calculate the sum of all the primes below two million.

Solution

Again, more of a programming challenge than a mathematical one – at least I’m unaware of a quick algebraic solution to this. I just used a simple sieve and then totalled up the primes.

def isPrime = new boolean[2000000]
Arrays.fill(isPrime, true)
isPrime[1] = false

for (int i in 2..isPrime.size()**0.5) {
    if (isPrime[i]) {
        def j = i + i
        while (j < isPrime.size()) {
            isPrime[j] = false
            j += i
        }
    }
}

def answer = 0L

for (i in 2..<isPrime.size()) {
    if (isPrime[i]) answer += i
}

This completes in 4.58 seconds with the sieve taking about 4.19 seconds (91%) of that. A BigInteger#isProbablePrime implementation takes far longer than the 15 seconds I’ve allowed for these solutions. Note that I’ve changed my sieve creation look from being a Java-like for (;;) construct that I’ve used before to a verbose while() loop. I found that the former was taking upwards of 7 seconds to run i.e. a 50% overhead for syntactic sugar. Given the runtime constraints I’ve imposed on these answers this wasn’t acceptable.

Conclusion

Groovy language features didn’t play much of a part in this solution. In fact, with the rather odd performance issue mentioned above they actually proved to be a detriment compared to a Java solution. Even at just 10 questions in, I can see that Groovy’s overheads in straight computational processing is likely to be an issue as I progress in the Euler problems – a Java implementation of this executes in 70 ms (65x faster).

Addendum

Added 26th July 2010

I don’t normally try to optimize when the runtime is comfortably within the 15 second cut off, but following on from a comment on this post I did a few more tests on speeding up the sieve generation. Here are the results:

Version Changes Normalized Runtime
1 As-Is 1.000
2 Change j=i+i to j=i*i 0.999
3 Change for-loop to while 0.965
4 Use an increment value 0.631
5 Take SQRT outside loop 0.563
6 Use LIMIT rather than isPrime.size() 0.244
7 Make JUST the LIMIT change 0.411

The change (2) to using a “j = i * i” rather than “j = i + i” make hardly any performance difference. Groovy is quite slow on multiplication compared to addition and this balances with the improvement that running fewer loops makes. The second main change (4), using a double increment after the initial pass, makes quite a difference (35%) as you’d might expect. Another big improvement (6) is using a constant (well, variable really) rather than getting the size() of the array each time. This saves 57% even after the other improvements, making a total of 76% overall. This change alone (7) saves a consistent amount (59%) when applied to the base code.

Project Euler Problem #8

January 6, 2010

Read the details of the problem here

Summary

Discover the largest product of five consecutive digits in the 1000-digit number.

Solution

Nice and straightforward, this is just a programming rather than an algorithmic puzzle. Not much to say on this, the implemention is fairly minimal and trivial.

def s =
  "73167176531330624919225119674426574742355349194..." +
  "...36269561882670428252483600823257530420752963450"

def answer = 0
for (i in 0..s.length()-5) {
   answer = [ answer, (s[i..i+4]).inject(1) { r, n -> r * n.toInteger() } ].max()
}

This runs on 0.66 seconds and was very straightforward to write.

Conclusion

Groovy, with its list#inject method, made it very easy to create what is essentially a one liner – albeit not the most efficient piece of code in the world. As always, performance was slower than hoped for but perfectly adequate for solving this problem.

Project Euler Problem #7

January 6, 2010

Read the details of the problem here

Summary

Find the 10001st prime.

Solution

I took a brute force approach to this and used a simple prime sieve with a fairly arbitrary but generous upper limit and then just counted through the primes in the sieve.

def isPrime = new boolean[200000]
Arrays.fill(isPrime, true);
isPrime[1] = false

for (int i in 2..isPrime.size()**0.5) {
    if (isPrime[i]) {
        for (j = i + i; j < isPrime.size(); j += i) isPrime[j] = false
    }
}

def (answer, n) = [ 0, 0 ]
for (i in 2..<isPrime.size()) {
    if (isPrime[i]) {
        n++
        if (n == 10001) {
            answer = i
            break
        }
    }
}

This completed in 1.3 seconds with the generation of the sieve taking 1.2 seconds, although with some judicious tweaking of the upper bound, once the answer was known, the runtime comes down to 0.99 seconds. I could further reduce the runtime during the count itself by only checking odd numbers but it’s not going to make that much difference to the overall duration.

Conclusion

Groovy didn’t really offer much in the way of assistance in this solution. The code in pretty much plain Java and runs MUCH slower that an equivalent 100% Java solution. Such an implementation, even with the broader upper bound, completes within 9 ms – that’s around 0.7% of the runtime. Groovy is 140x slower than Java in this particular scenario!

I strongly suspect that, at some point, I’m going to have to build (or source) some sort of prime engine in Java for use in the Groovy solutions if I’m going to be keeping within the 15 seconds of allotted time.

Even using the BigInteger#isProbablePrime method is quite slow, with a simple counting solution based on this taking 8.14 seconds in Groovy and 7.72 seconds in Java. Interestingly, making the prime check only on odd numbers brings the Groovy runtime down to 7.89 seconds – a saving of just 3%. The isProbablePrime method must (obviously) be efficient at ruling out even numbers!

Project Euler Problem #6

January 6, 2010

Read the details of the problem here

Summary

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution

Little need for commentary on this quick solution which is very descriptive of the problem being set.

def answer = (1..100).sum() ** 2 - (1..100).sum { it * it }

This runs in 445 ms. Very slow for what it’s doing but well within my permitted 15 seconds.

Conclusion

Sure, I could have solved this algebraically (as below) but Groovy listops were calling…

def answer = (100 ** 2 * 101 ** 2 / 4) - (100 * 101 * 201 / 6)

This algebraic solution, which doesn’t need any actual programming, is run by Groovy in 14 ms. Hmm, that’s an eternity for a simple statement like that!

Project Euler Problem #5

November 7, 2009

Read the details of the problem here

Summary

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Solution

I didn’t need to write a program for this question. I vaguely remembered from school that the LCM of a series of numbers is just the product of the maximum powers of its prime factors, or something like that terminology.

It goes something like this. 2^4 = 16, which is less than 20, so that’s included but 2^5 isn’t as 32 is greater than 20. Similarly 3^2 = 9, is in, but 3^3 = 27 is out. Intermediate numbers will always be able to be factored into products of lesser powers of the primes and can therefore be ignored.

So this gives the list: 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

So it wasn’t really much of a program to be written though groovysh did the calculation admirably. Performance wasn’t an issue!

Conclusion

Just goes to show it’s sometimes worth engaging brain before hitting the keyboard.

Reading ahead in the Project Euler questions it looks like factorization of large numbers is an ongoing theme so I’ll probably end up writing something that does this but I’ll do that when I need it.

Project Euler Problem #4

November 7, 2009

Read the details of the problem here

Summary

Find the largest palindrome made from the product of two 3-digit numbers.

Solution

An obvious brute force solution completes in 1.14 seconds. The only simple optimizations I made were to count down rather than up for the two numbers and to put a guard condition on the expensive functions.

String.metaClass.isPalindrome = { ->;
    delegate == delegate.reverse()
}

def answer = 0

for (i in 999..100) {
    for (j in 999..100) {
       def p = i * j
       if ((p > answer)  && (p.toString().isPalindrome())) answer = p
    }
}

As they say, “‘Nuff Said!”

Conclusion

The ability to extend to the String metaclass with an “isPalindrome()” method leads to quite a nice syntax but isn’t much different to just defining a support method. (I could also have put the function into the Integer class directly and hidden the String conversion in that.)

The solution ran well within my 15 second limit but still felt slow for what it was doing. An equivalent Java version runs in 137 ms. That’s around 8x faster.