Project Euler Problem #118

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.