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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: