Project Euler Problem #30

February 14, 2010

Read the details of the problem here

Summary

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution

I used a straightforward brute force approach. The highest number that can be attained with these criteria is at most going to be a 6-digit number as 7*95 = 413343 so that forms an upper bound for the search. The only real optimisation I made was pre-calculating the fifth powers.

def p5 = [:]
0.upto(9) { p5[it.toString()] = it ** 5 }

def answer = (2..(6*p5["9"])).findAll { n->
    n.toString().toList().sum { p5[it] } == n
}.sum()

This ran in 12.41 seconds so just inside my 15 second constraint. A more procedural approach, using an integer array for holding the fifth powers and a numerical approach to extracting the digits ran in a little over 4 seconds.

Conclusion

Again, I may have used an overly Groovy approach to this and sacrified a lot in terms of efficiency for use of the listop features. You can see that in terms of time-to-solution for questions like this, Groovy scores very well, as long as runtime performance isn’t an issue.

Advertisements

Project Euler Problem #29

February 14, 2010

Read the details of the problem here

Summary

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

Solution

Maybe this was a challenging question back in Oct 2002 (or maybe not) when it was set but certainly not any more. A brute force approach with suitable collection class support makes this very easy.

def set = [] as Set

for (a in 2..100)
    for (b in 2..100)
        set << (a ** b)

def answer = set.size()

This runs in 0.49 seconds. Java does it in around 34 ms – a mere 14x faster showing that the majority of the work is being done in the Java collection and Maths classes.

Interestingly, replacing the for-loops with (2..100).each{} closures pushes the runtime out to 0.59 seconds. Using 2.upto(100){} closures gives a 0.56 second elapsed time. This 15% overhead is quite surprising given that most of the time would probably be spent in the set insertion.

Conclusion

Groovy made this a snap to write without the boilerplate overhead in Java. Adequate performance for the scope of the question.

Project Euler Problem #28

February 14, 2010

Read the details of the problem here

Summary

What is the sum of both diagonals in a 1001 by 1001 spiral?

Solution

Another straightforward problem. The sum of the corners of a ring is quite simple and it’s just a case of spotting the increment that the bottom right-hand corner undergoes as the spiral expands.

def ( answer, brval ) = [ 1, 3 ]

(1..500).each { ring ->
  answer += 4 * brval + 6 * (2 * ring)
  brval += 8 * ring + 2
}

Note that the answer (sum of numbers) starts at 1 as ring 0 is a special case having only one element and isn’t handled in the loop.

This runs in 0.47 seconds. A Java version using longs runs in around 0.28 ms – more than 1500x faster. Jeepers.

Conclusion

I didn’t really use any specific Groovy feature here apart from multiple assignment in a few places and in the loop syntax. Performance was completely adequate for the scope of this problem but still dismally slow compared to Java for this type of work.

Project Euler Problem #27

February 14, 2010

Read the details of the problem here

Summary

Find a quadratic formula that produces the maximum number of primes for consecutive values of n.

Solution

I used a straightforward approach to this problem. I assumed that b had to be positive and that both |a| and |b| had to be prime numbers themselves to reduce the chance of b being a multiple of a so I used a sieve to generate the numbers and worked from that.

def isPrime = new boolean[12000]
Arrays.fill(isPrime, true)
(0..1).each { isPrime[it] = false }

for (i in 2..<(int)Math.sqrt(isPrime.size())) {
    if (!isPrime[i]) continue
    def j = i + i
    while (j < isPrime.size()) {
        isPrime[j] = false
        j += i
    }
}

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

for (a in -999..<1000) {
    if (!isPrime[Math.abs(a)]) continue
    for (b in 1..<1000) {
        if (!isPrime[b]) continue
        def n = 0
        while (isPrime[ (n * n) + (a * n) + b ]) {
            n++
        }
        if (n > maxlen)
            (maxlen, answer) = [ n, a * b ]
    }
}

This runs in 0.76 seconds with the creation of the sieve taking 0.54 seconds (68%). Rather than generating lists of primes and working from that I just used the array directly as performance is generally better like that (though in this case it probably wouldn’t have mattered). Selection of the upper bound of the prime sieve was initially larger than the 12,000 shown in order to prevent out-of-bound exceptions.

Conclusion

I didn’t really use any specific Groovy feature here apart from multiple assignment in a few places and in the for-loop syntax. Performance was completely adequate for the scope of this problem.

Project Euler Problem #26

February 14, 2010

Read the details of the problem here

Summary

Find the value of d < 1000 for which 1/d contains the longest recurring cycle.

Solution

This has me a little puzzled as to the best way to do it. I did consider simply using BigDecimal to calculate the fraction to, say, 2000 decimal places and then use a regex or a contracting substring search to find the recurring sequences but it didn’t feel very “Project Euler-like” for a question that was so obviously mathematical in nature.

A little digging around found the Wolfram page on Decimal Expansion which said that the length of the sequence was found from the Multiplicative Order of it’s denominator. This boiled down to just executing a repeated modulus operation until the remainder had already been seen, at which point a cycle would occur (the remainder being used as the input to the subsequent modulus operation). This seemed like quite a nice approach as I wouldn’t have to worry about the noise on the front of the expansion before detecting the cycle start.

I wrote it using perhaps more Groovy features that it deserved but it ends up in being a fairly neat solution.

def answer = (1..<1000).collect {
    def ( found, remainder, divisor ) = [ [:], 10, 2 ]
    while (true) {
        if (remainder == 0) return [ it, 0 ]
        if (found.containsKey(remainder))
            return [ it, divisor - found[remainder] ]
        found[remainder] = divisor
        ( remainder, divisor )  = [ 10 * (remainder % it), divisor+1 ]
    }
}.max { it[1] }[0]

This runs in 1.12 seconds. I could made it a little faster perhaps by only checking primes as candidates or short-circuiting even numbers but it’s not going to save a lot of time, and it’s already well-within the 15 second limit. One thing that might make it a lot quicker would be to check to see if the multiplicative order of a number was one less than the number itself – that would be the highest possible length. If I did a descending search and broke out if this condition occurred then it would be faster. However, this way I have a way of getting a list of the multiplicative order of all the numbers which might stand me in good stead for later puzzles.

Conclusion

Groovy offered a few nice features such the list transformation collect{} function, the ability to return tuples and the parameterised max{} listop that made this code quite concise. The multiple assignment feature was convenient in keep the code short but didn’t really add anything to the solution.

Project Euler Problem #25

February 9, 2010

Read the details of the problem here

Summary

What is the first term in the Fibonacci sequence to contain 1000 digits?

Solution

I just took the brute-force naive approach for this as Java, with BigInteger support, makes it just too tempting not do so. Note that it’s quicker (by about 30%) to check the length of the string representation rather than comparing it to a terminal value.

def (fib1, fib2, answer) = [ 1G, 2G, 3 ]

while (fib2.toString().size() < 1000) {
    (fib1, fib2, answer) = [ fib2, fib1+fib2, answer+1 ]
}

This runs in 2.94 seconds. There are cleverer ways to do this using the Golden Ratio relationships to derive the value of the term mathematically but this took seconds to write and is obviously correct!

Conclusion

Groovy, with automatic support for Java’s BigInteger, made this very quick and simple to write.

Project Euler Problem #24

February 9, 2010

Read the details of the problem here

Summary

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Solution

A quick look on Wikipedia found the information about lexicographic order permutation. It was then just a case of coding that up in Groovy and remembering that the millionth permutation is actually permutation 999999.

def (s, perm) = [ "0123456789", 1000000-1 ]
def (elems, len) = [ s.toList(), s.size() ]

def fact = (2..<len).inject(1) { p, v -> p * v }

for (i in 0..<len-1) {
    def p = perm.intdiv(fact) % (len-i)
    def temp = elems[i+p];
    (i+p).downto(i+1) { elems[it] = elems[it-1] }
    elems[i] = temp;
    fact = fact.intdiv(len-(i+1))
}

def answer = elems.join("")

This runs in 0.45 seconds. A Java version, that uses char[] rather than an ArrayList runs in under 0.05 ms (or thereabouts – nanoTime() is precise but not that accurate under Windows Vista). I make that about 9000x times faster which is just ridiculous!

Conclusion

Groovy did the job OK for this solution. Kept the coding noise level to a minimum and avoided some boilerplate but nothing that can’t easily be done in Java.