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.

Advertisements

2 Responses to “Project Euler Problem #118”


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

  2. serinox Says:

    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.)


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: