## Project Euler Problem #118

### May 20, 2010

Read the details of the problem here

**Summary**

Exploring the number of ways in which sets containing prime elements can be made.

**Solution**

Groovy beat me on this one, or at least I couldn’t think of an algorithm that would it allow it to run in less than around 16.5 seconds even with the prime determination being done in native Java. So I switched over to 100% Java…

The solution is almost brute force in that it generates all the permutations of 9-digit pandigital numbers and then, for each permutation recursively tries to pull off primes from the front of the number, passing the remainder on for the same processing when it finds one. If the whole number is successfully consumed then that particular breakdown is sorted and stored in a result set in order to remove duplicates.

public class EulerProblem118 extends AbstractEulerProblem { private Set<List> _results; private void splitPrimes(String s, Stack<Integer> stack) { for (int len = 0; len < s.length(); len++) { int i = Integer.valueOf(s.substring(0, len+1)); if (!isPrime(i)) continue; stack.push(i); if (len == s.length()-1) { List<Integer> r = new ArrayList<Integer>(stack); Collections.sort(r); _results.add(r); } else { splitPrimes(s.substring(len+1), stack); } stack.pop(); } } @Override protected void callback(Object obj) { splitPrimes((String)obj, new Stack<Integer>()); } @Override public String solve() { _results = new HashSet<List>(); eachPermutation("123456789", this); return String.valueOf(_results.size()); } }

The implementations of the non-sieve *isPrime()* and *eachPermutation()* methods are provided by the underlying base class. The latter calls the generic *callback()* method for each permutation of the string that it’s given. The implementation is pretty much the same as that for Problem 41. (Note: This callback is also used by other generators hence the non-specific *Object* argument.)

This runs in 5.3 seconds. Not very fast or efficient but it got the job done and is quite simple to understand.

**Conclusion**

Groovy just wasn’t fast enough for my solution for this problem. Having now got access to the forum it looks like there may be ways in which it might be achieved but it’s still going to be a challenge to get it under 15 seconds in Groovy. I’ll have a look at this some time.

Nov 11, 2011 at 05:22

can you put the source code of the eachPermutation() methods and AbstractEulerProblem.java

Jul 24, 2012 at 17:02

you store the whole arraylist r inside the results. But since every element of r is prime and we just need uniqueness you can just store the product of the elements of r and check against that for duplicates. (using the idea that numbers have unique prime decompositions.)