# samskivert: Euler 60

## 27 July 2010

``````object Euler60 extends EulerApp {
val primes = genprimes(10000) filter(0.!=)
val ppairs = Set() ++
(for { ii <- 0 until primes.length-1; jj <- ii until primes.length;
val pi = primes(ii); val pj = primes(jj);
if (isprime((pi.toString+pj).toInt) && isprime((pj.toString+pi).toInt))
} yield (pi, pj))
def isset (pset :List[Int], prime :Int) =
pset.foldLeft(true)((b, a) => b && ppairs((a, prime)))
def find (pset :List[Int], plist :List[Int]) :Option[List[Int]] = {
if (pset.size == 5) Some(pset)
else if (plist.isEmpty) None
else if (!isset(pset, plist.head)) find(pset, plist.tail)
else find(plist.head :: pset, plist.tail).orElse(find(pset, plist.tail))
}
Now we climb up the list of primes, each time checking whether the current prime can expand our current set of concatenable primes. This check only requires that the candidate prime properly pair with each prime in the set, since we already know that all the primes in the set pair with one another (because they were each checked before they were added). If it does pair, add it to the set and either way we continue with the next prime. If we reach the end of our list of primes and we haven't found a set of five, we backtrack (making use of the call stack) and execute the `orElse` and try again without that most recently added pairable prime.