Project Euler Problem #35

Jun 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 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
if (!isPrime[s.toInteger()]) break
n++
}
}
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

Jun 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 ]
}

```

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

Jun 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
}
}

```

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

Jun 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 =  + *total

coins.each { coin ->
coin.upto(total) { nways[it] += nways[it - coin] }
}

```

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 nth 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
while (i <= LIMIT) {
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) {
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] }) {
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()
}