## Project Euler Problem #35

### June 16, 2010

Read the details of the problem here

**Summary**

How many circular primes are there below one million?

**Solution**

Again, playing catch up writing this one up too. Very straightforward brute-force solution to this one too. Just created a prime sieve and then, for each prime, simply ran through the rotations of the digits checking in the sieve for primality. I did consider creating some sort of memoization of numbers that had been checked as being a rotation of another prime but the solution ran quite quickly enough without such embellishments.

def LIMIT = 1000000 def isPrime = new boolean[LIMIT] Arrays.fill(isPrime, true) (0..1).each { isPrime[it] = false } def SQRT_LIMIT = (int)Math.sqrt(LIMIT) for (i in 2..<SQRT_LIMIT) { if (!isPrime[i]) continue def j = i + i while (j < LIMIT) { isPrime[j] = false j += i } } def answer = 1 def i = 3 while (i < LIMIT) { if (isPrime[i]) { def ( s, n ) = [ i.toString(), 0 ] for (j in 1..<s.size()) { s = s[1..-1] + s[0] if (!isPrime[s.toInteger()]) break n++ } if (n == s.size()-1) answer++ } i += 2 }

This runs in 0.94 seconds. It’s necessary to initialize *answer* to 1 (one) as 2 is a circular prime and the main loops only checks odd numbers. Apart from that, not much else to say on this one as it’s so obvious in operation.

**Conclusion**

Not really a Groovy solution, more like normal Java apart from a few syntactic niceties. As such, performance was fine for the scale of the problem.

## Project Euler Problem #33

### June 16, 2010

Read the details of the problem here

**Summary**

Discover all the fractions with an unorthodox cancelling method.

**Solution**

Playing catch up writing this one up too. Just been reading this one back after six months or something…what dreadful code! I was trying for a Groovy solution and this is what I came up with. It just does an exhaustive search to find the four items and their product, and then uses a GCD routine to reduce it into it’s lowest term to extract the answer.

def ( np, dp ) = [ 1, 1 ] (12..<99) .findAll { it % 10 != 0 } .each { n -> (n+1..99) .findAll { (it % 10 != 0) && (n % 10 == it.intdiv(10)) } .each { d -> def ( n1, d1 ) = [ n.intdiv(10), d % 10 ] if (n/d == n1/d1) ( np, dp ) = [ np * n1, dp * d1 ] } } def ( gcd, n ) = [ np, dp ] while (n != 0) { ( gcd, n ) = [ n, gcd % n ] } def answer = dp.intdiv(gcd)

This runs in 80 ms. Well within the 15 second deadline but the code does seem a bit convoluted in hindsight.

**Conclusion**

I did this with an over-use of Groovy features and, as such, it looks quite terrible. Performance was OK, but a less Groovy approach I put together after revisiting it ran in under 10 ms and, if anything, was even more terse.

## Project Euler Problem #32

### June 16, 2010

Read the details of the problem here

**Summary**

Find the sum of all numbers that can be written as pandigital products.

**Solution**

Playing catch up writing this one up too. Straightforward to create a brute-force solution to this. Just a matter of searching across the problem space and checking for the criteria to be met. Used a Set to make sure that duplicates were being handled appropriately.

String.metaClass.isPandigital { -> delegate.toList().sort().join() == "123456789" } def nums = [] as Set for (a in 2..98) { def (minb, maxb) = (a < 10) ? [ 1234, 9876 ] : [ 123, 987 ] for (b in minb..maxb) { def p = a * b def s = "$a$b$p".toString() if (s.length() > 9) break if ((s.length() == 9) && s.isPandigital()) nums << p } } def answer = nums.sum()

This runs in 0.35 seconds, so good enough to call it a success.

**Conclusion**

Groovy allowed the use of metaClass extensions to make the solution read neatly but it wasn’t a particularly Groovy solution apart from the *isPandigital()* method. Performance was adequate for the scale of the problem.

## Project Euler Problem #31

### June 16, 2010

Read the details of the problem here

**Summary**

Investigating combinations of English currency denominations.

**Solution**

Solved this one ages ago, but hadn’t written it up yet, so just playing catch up! It was a straightforward enough problem. The choice was between an accumulating array for the coin combinations or a nested loop for each coin value. The former would create less code and, using Groovy listops would be quite neat too, so that’s the approach I took.

def ( total, coins ) = [ 200, [ 1, 2, 5, 10, 20, 50, 100, 200 ] ] def nways = [1] + [0]*total coins.each { coin -> coin.upto(total) { nways[it] += nways[it - coin] } } def answer = nways[total]

This runs in 43 ms, so well within my 15 second limit.

**Conclusion**

Groovy made this a terse solution, and performance was quite adequate too even using Groovy a list rather than an array.

## Project Euler Problem #40

### May 19, 2010

Read the details of the problem here

**Summary**

Finding the *n ^{th}* digit of the fractional part of the irrational number.

**Solution**

No need for clever maths for this solution. Just create the string as described and pull the characters out as necessary.

def LIMIT = 1000000 def sb = new StringBuilder(LIMIT+10) sb.append(".") def i = 1 while (sb.length() <= LIMIT) { sb.append(i.toString()) i++ } i = 1 def answer = 1 while (i <= LIMIT) { answer *= sb[i].toInteger() i *= 10 }

This runs in 0.17 seconds. Being able to explicitly use a *StringBuilder* means that I can make this reasonably performant with losing the simple string-based approach to the solution. A Java version takes just 11 ms.

**Conclusion**

This is where Groovy’s easy explicit access to Java libraries can make a killer combination.

## Project Euler Problem #37

### May 4, 2010

Read the details of the problem here

**Summary**

Find the sum of all eleven primes that are both truncatable from left to right and right to left.

**Solution**

Straightforward to create a simple, though somewhat wordy, solution using maths functions to truncate the primes. I did consider using a string solution but thought that this version would be faster. I used a prime sieve and guessed at a suitable maximum, as performance with *BigInteger().isProbablePrime()* is poor.

def LIMIT = 1000000 def isPrime = new boolean[LIMIT+1] Arrays.fill(isPrime, true) (0..1).each { isPrime[it] = false } for (int i in 2..<Math.sqrt(LIMIT)) { if (!isPrime[i]) continue def j = i + i while (j < LIMIT) { isPrime[j] = false j += i } } def (answer, c) = [ 0, 0 ] for (i in 11..<LIMIT) { if (isPrime[i]) { def n = i.intdiv(10) while ((n > 0) && isPrime[n]) { n = n.intdiv(10) } if (n > 0) continue def m = 10 ** (int)Math.log10(i) n = i % m while ((n > 0) && isPrime[n]) { m = m.intdiv(10) n %= m } if (n == 0) { answer += i if (++c == 11) break } } }

This runs in 0.78 seconds. So fast enough for this solution. As a matter of interest I also created a string-based version (code as below, making use of the same sieve routine as above) and this ran in 1.21 seconds. An iterative solution still using strings would probably be faster as it could shortcut when the criteria wasn’t met.

def (answer, c) = [ 0, 0 ] for (i in 11..<LIMIT) { if (!isPrime[i]) continue def s = i.toString() if ((0..<s.size()-1).collect { s[0..it].toInteger() }.every { isPrime[it] } && (1..<s.size()).collect { s[it..-1].toInteger() }.every { isPrime[it] }) { answer += i if (++c == 11) break } }

So that’s the two-for-one deal on this solution.

**Conclusion**

Apart from the looping constructs I didn’t really use any significant Groovy features in the maths-based solution. String functions and listops were made good use of in the string-based one.

## Project Euler Problem #36

### May 3, 2010

Read the details of the problem here

**Summary**

Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

**Solution**

Straightforward brute-force solution using Java library calls to check for palindromes and get the binary representation. Only slight optimization was to quickly eliminate numbers ending in zero and even numbers (so the LSb was 0) rather before checking for palindromic properties.

String.metaClass.isPalindrome = { -> delegate == delegate.reverse() } def answer = (1..<1000000).findAll { ((it % 10 != 0) && ((it & 1) == 1) && it.toString().isPalindrome() && Integer.toBinaryString(it).isPalindrome()) }.sum()

This runs in 3.12 seconds. Not particularly fast, but OK for this solution. A Java version runs in 116 ms – 26x faster – not so much a discrepancy as usual as a lot of the work is being done within the Java runtime libraries.

**Conclusion**

Groovy makes it possible to write fairly declarative code using listops, although in this case the Java version is just as simple. Runtime performance is wanting, as always, but time-to-solution is very good. I used metaClass extensions to add the *isPalindrome()* method to strings to improve readability (perhaps?) and performance was comparable to just using a method call.