Project Euler Problem #60

November 20, 2016

Read the details of the problem here

Summary

Prime pair sets.

Solution

This problem took a little bit of thinking about, primarily to get it to perform adequately – on the basis that I’m trying to get this to run in under 5 seconds. When I first solved this problem I simply couldn’t get the computational performance out of Groovy to do the prime validation quickly enough and ended up calling out to a native Java method. With the introduction of the @CompileStatic AST transformation this has made it possible to do. After my next laptop upgrade, I’m going to be having to aim for maybe 2 seconds at the most on these questions!

The solution uses a fairly naive implementation of an isPrime() method which is still substantially faster than using BigInteger#isProbablePrime() from Groovy when using @CompileStatic – at least for the range of numbers being used here. I made an assumption that 4-digit primes would be sufficient to solve this question and, luckily, it worked out to be correct.

The program starts by constructing a list of primes mapped to a list of other primes that conform to the question’s constraints of both orders of concatenation also being prime. Using lists of strings rather than integers saves a lot of overhead in the subsequent checks. The lists only contain primes that are greater than the key. So, for example, 3’s list contains 7 (as both 37 and 73 are prime), but that of 7 doesn’t contain 3. Any numbers that have fewer than 4 entries in their list are dropped as a set of 5 primes are being sought. The lowest number in that set will have the full membership in it’s list.

Having generated this list of prime-pairs, a set of primes are grown to find a five members set that fulfil the criteria. At each recursion the entries of the list of the most recently added member are checked to make sure that they meet the concatenation criteria of each of the other member of the list (by making sure that it’s on their respective lists of potential pairs) and that it wouldn’t exceed the current minimum value found. For each of the values that fulfil this criteria, a recursion is called with this appended to the current list. The minimum value found for that particular path is returned. In this respect it’s like creating a directed graph with the nodes (of which there are only 1,227) being the primes and the edges (of which there are 17,845) being the fact that two nodes fulfil the concatenation criteria.

There are probably some algorithmic optimisations that could be made here but, as it is, the code is quite simple to understand.

import groovy.transform.CompileStatic

@CompileStatic
boolean isPrime(final int num) {

  if (num <= 1) return false
  if (num <= 3) return true
  if ((num % 2 == 0) || (num % 3 == 0)) return false

  int r = (int)Math.sqrt(num)
  int f = 5

  while (f <= r) {
    if (num % f == 0) return false
    if (num % (f + 2) == 0) return false
    f += 6
  }

  true
}

def getPrimePairs(maxnum) {

  def primes = ((2..maxnum).findAll { isPrime(it) })*.toString()
  def primeCount = primes.size()
  def pairs = [:]

  for (ip1 in 0..<primeCount - 1) {
    def sp1 = primes[ip1]
    pairs[sp1] = [] as Set
    for (ip2 in (ip1 + 1)..<primeCount) {
      def sp2 = primes[ip2]
      if (isPrime((sp1 + sp2).toInteger()) &&
          isPrime((sp2 + sp1).toInteger())) {
        pairs[sp1] << sp2
      }
    }
    if (pairs[sp1].size() < 4) pairs.remove(sp1)
  }
  pairs
}

def find5(list, min, pairs) {

  def sum = list*.toInteger().sum()
  if (list.size() == 5) return sum

  pairs[list[-1]].findAll { p -> ((sum + p.toInteger()) < min) &&
                                  (list.every { pairs[it].contains(p) }) }
                 .each { min = [ min, find5(list + it, min, pairs) ].min() }
  min
}

def (answer, primePairs) = [ Integer.MAX_VALUE, getPrimePairs(10000) ]

for (p in primePairs.keySet()) {
  answer = [ answer, find5([p], answer, primePairs) ].min()
}

This executes in Groovy 2.4.7 under Java 8u112 in around 2.9 seconds, so within my 5 second cut-off. The build of the list of primes takes about 115 ms, with the construction of the prime pair map taking another 1.5 seconds. The isPrime() method is called around 850,000 times and takes around 960 ms of the total runtime.

Conclusion

Quite surprisingly, Groovy was perfectly good for this problem as long as @CompileStatic is used to optimise the isPrime() method. Left as dynamic, the runtime pushes out to just under 30 seconds. The Groovy listops made it easy to construct the prime-pair lists and for quite an expressive statement for the recursive descent conditions.

Advertisements

Project Euler Problem #54

November 18, 2016

Read the details of the problem here

Summary

Poker hands.

Solution

This was a straightforward programming problem rather than anything taxing from a mathematical perspective. I used Groovy listops to process the input file into a sorted list of [ count, face_value ] pairs that could then just be inspected in order of priority (along with some flags to indicate whether there was a monotonic sequence and a only a single suit in the hand) to rank the hand.

There are only 5 combinations of counts available (as given below). It would have been possible to simply check against these to provide a basic classification of the hand but with the need to have the flush and straight processing it just seemed easier and clearer to have the ranking done explicitly.

Count Permutations: [ 1, 1, 1, 1, 1 ], [ 2, 1, 1, 1 ], [2, 2, 1 ], [ 3, 2 ], [4, 1]

Ties were broken by using a base-13 (tridecimal) system with the rank being the most-significant digit and then using the first two group face values as the differentiators so a simple score was created for each hand. As it happened there were no clashes that weren’t broken by this method – it would have to be extended to subsequent cards and then suits (which were ignored in this question) otherwise, so you’d end up with a base-52 (duopentagecimal) system where each card had a unique value but were grouped unless there were clashes.

It didn’t take a lot of coding to get this done. It could be done more tersely, perhaps, but it would be more cryptic!

class Hand {

  private final _cards
  private final _isStraight
  private final _isFlush

  Hand(cardList) {
    def vals = cardList.collect { ['face': '23456789TJQKA'.indexOf(it[0]), 'suit': it[1]] }

    _isFlush = (vals.groupBy { it.suit }.size() == 1 )
    _cards   = vals.groupBy { it.face }
                   .collect { [ (it.value.size), it.key ] }
                   .sort { -(it[0] * 13 + it[1]) }
    _isStraight = (_cards.size() == 5) && (_cards[0][1] - _cards[-1][1] == 4)
  }

  def score() {
    rank() * 169 + _cards[0][1] * 13 + _cards[1][1]
  }

  def rank() {
    if (_isStraight && _isFlush && _cards[0][1] == 12) return 9
    if (_isStraight && _isFlush)                       return 8
    if (_cards[0][0] == 4 )                            return 7
    if (_cards[0][0] == 3 && _cards[1][0] == 2 )       return 6
    if (_isFlush)                                      return 5
    if (_isStraight)                                   return 4
    if (_cards[0][0] == 3 )                            return 3
    if (_cards[0][0] == 2 && _cards[1][0] == 2 )       return 2
    if (_cards[0][0] == 2)                             return 1
    0
  }

  def beats(opponent) {
    def (s1, s2) = [ this.score(), opponent.score() ]
    if (s1 > s2) return true
    assert (s1 != s2)
  }
}

def answer = new File('pe054_poker.txt').readLines().count {
  def cards = it.split(" ")
  new Hand(cards[0..4]).beats(new Hand(cards[5..-1]))
}

This executes in Groovy 2.4.7 under Java 8u112 in around 0.25 seconds, so well within my 5 second cut-off.

Conclusion

Groovy was perfectly good for this problem with the simple file handling and listops allowing the input to be prepared for processing very easily.

Read the details of the problem here

Summary

Investigate the number of primes that lie on the diagonals of the spiral grid.

Solution

Not a particularly difficult problem to understand, the only real issue was that the potential scope of the primes didn’t lend themselves to a sieve approach so I used BigInteger support for prime determination. There shouldn’t be that many numbers to check. It’s only necessary to check three corners of the square as the lower right will never be prime.

On this basis I coded up a fairly straightforward brute-force approach as shown below. There are some micro-optimisations that could be made to remove some repeated multiplications with additions, for example, the increase of sqr on each iteration, or the calculation of the cell value, but this is only going to save a couple of hundred milliseconds at best.

Integer.metaClass.isPrime() { ->
    delegate.toBigInteger().isProbablePrime(100)
}

def (answer, primes, count, side) = [ 0, 0, 1, 3 ]

while (answer == 0) {

    def sqr = side * side
    primes += (1..3).findAll { (sqr - it * (side-1)).isPrime() }.size()
    count += 4

    if (primes / count < 0.1) answer = side

    side += 2
}

Run time is 2.4 seconds, so not the fastest solution in the world. Using a non-sieving isPrime(int) method coded in native Java brings the runtime down to 0.38 seconds so it’s actually spending quite a lot of time in prime determination.

Conclusion

Again, not really a Groovy solution in that it didn’t use many of the clever Groovy features, though the ability to add the Integer.isPrime() was nice. I did try coding the isPrime method in Groovy but that pushed the time up above 8 seconds so still an acceptable result but not as good as the BigInteger approach and, as that’s part of the JVM runtime it’s a better solution in my opinion.

Read the details of the problem here

Summary

Investigate the expansion of the continued fraction for the square root of two.

Solution

This looked like it was going to be a complicated question requiring some sort of recursive function but it ended up actually being quite simple. The key was spotting the (in retrospect somewhat obvious) pattern in the changes to the numerator and denominator in each expansion, which is why Euler puts so much stress on it in the question I suppose!

numn / denomn = numn-1 + 2 * denomn-1 / numn-1 + denomn-1

This then leads to a very simple and easy to code iterative solution. The use of BigInteger prevents overflow and makes it easy to compare the lengths.

def ( num, denom, answer ) = [ 3G, 2G, 0 ]

1000.times {
    ( num, denom ) = [ num + 2 * denom, num + denom ]
    if (num.toString().length() > denom.toString().length()) answer++
}

Run time is 0.13 seconds. Performance was quite adequate. Nothing much else to say on this as it’s very straightforward.

Conclusion

Not really a very Groovy solution, but the transparent integration Groovy has with BigInteger made it very easy to put this together without all the noise that you get in Java when using them.

Read the details of the problem here

Summary

Considering natural numbers of the form, ab, finding the maximum digital sum.

Solution

Very easy to create a brute force solution with Java’s BigInteger support. I guessed that the answer would be found up in the high end of the range specified and only searched there.

BigInteger.metaClass.digitSum() { ->
  delegate.toString()*.toInteger().sum()
}

def answer = 0

(90G..99G).each { a ->
  (90G..99G).each { b ->
    answer = [ answer, a.pow(b).digitSum() ].max()
  }
}

Run time is 95 milliseconds.

Conclusion

Groovy’s transparent integration with the Java BigInteger class made this a snap to put together. The listops, spread operator and metaClass extensions made for a clean syntax.

It’s actually possible to do the calculation as Groovy “one-liner” which has the same run time.

def answer =
    ([(90G..99G).toList()]*2).combinations()
                             .collect { it[0].pow(it[1]).digitSum() }
                             .max()

Not sure if I like this or not.

Read the details of the problem here

Summary

How many Lychrel numbers are there below ten-thousand?

Solution

Very straightforward. I even used a couple of BigInteger metaClass extensions to make it more readable, well, perhaps more readable! The algorithm was just a simple implementation of the details in the question.

BigInteger.metaClass.isPalindrome() { ->
  def s = delegate.toString()
  s == s.reverse()
}

BigInteger.metaClass.reverse() { ->
  delegate.toString().reverse().toBigInteger()
}

def answer = 0

for (i in 1G..<10000G) {
  def n = i
  answer++
  for (c in 0..50) {
    n += n.reverse()
    if (n.isPalindrome()) {
      answer--
      break
    }
  }
}

Not much else to say on this, it just does what it says on the tin. It runs in 0.39 seconds.

It’s possible to do this as a one-liner with Groovy listops but it’s not as clear as to what’s going on – or maybe it is?

BigInteger.metaClass.isPalindrome() { ->
  def s = delegate.toString()
  s == s.reverse()
}

BigInteger.metaClass.reverse() { ->
  delegate.toString().reverse().toBigInteger()
}

def answer = 
    (1G..<10000G).findAll { i ->
            !(0..50).any {  (i += i.reverse()).isPalindrome() }
    }.size()

Run time is 0.50 seconds, so not too bad considering but around 30% up from the iterative solution.

Conclusion

Groovy was fine to do this in. The metaClass extensions made the syntax a little more natural (maybe) and the rest was reasonably terse. No real performance concerns for the scale of the problem.

Read the details of the problem here

Summary

How many values of C(n,r), for 1 ≤ n ≤ 100, exceed one-million?

Solution

From the look of the question it appeared that it was going to require a lot of multiplication and division of the fairly non-performant BigIntegers as n! gets very large, very quickly. As per other problems of this nature it seemed that using log values might be better.

This would involve reformulating the combinations equation as
log(n!)-(log(r!)+log((n-r)!) so quite straightforward really. In order to reduce the time spent calculating factorials (and their logs) I just initialised them into an array up front rather than using any special memoization technique.

The actual summation was then easy to do with Groovy listops.

def MAXNUM = 100
def LIMIT = Math.log10(1e6)

def fact = new double[MAXNUM+1]
(0..1).each { fact[it] = Math.log10(1) }

for (i in 2..MAXNUM) {
  fact[i] = Math.log10(i) + fact[i-1]
}

def answer =
    (1..MAXNUM).sum { n ->
        (1..<n).findAll { r -> fact[n] - (fact[r] + fact[n-r]) > LIMIT }
               .size()
    }

This runs in just under 80 ms which seems quite reasonable given that it’s essentially a listop-based declarative solution.

Conclusion

Groovy’s features made the creation of this solution quite simple and was surprisingly performant.