Project Euler Problem #49

April 28, 2010

Read the details of the problem here

Summary

Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other.

Solution

Quite straight-forward to do. In this case I made use of the BigInteger.isProbablePrime() method to select the primes rather than creating a sieve as the prime range was fairly limited. It was then a case of grouping them by their sorted sequences and filtering out any that didn’t have any permutations (as well as the exemplar value). It was then just a case of running through the list of permutations for each prime and seeing if three values with the same difference could be found by taking two values at a time and seeing if a suitable third value was present in the list.

def answer = ""

(1003..9997).findAll { BigInteger n -> n.isProbablePrime(100) }
            .groupBy { it.toString().toList().sort().join() }
            .findAll { it.key != "1478" && it.value.size() > 2 }
            .each {
              def p = it.value
              for (i in 0..<p.size()-2) {
                for (j in (i+1)..<p.size()-1) {
                  def p3 = 2 * p[j] - p[i]
                  if (p.contains(p3)) {
                    answer = [ p[i], p[j], p3 ].join()
                  }
                }
              }
            }

This executes in 0.42 seconds. Not particularly fast but good enough for this solution. It could be made faster by causing the loop to break when the answer was found, in this case it would require an exception to be thrown & caught which would just add noise into the solution for such a small benefit.

Conclusion

Groovy listops made it simple to provide declarative filtering for the list of primes and kept the syntax terse in the inner-loops. All-in-all a win for Groovy over straight Java for this particular problem.

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: