Project Euler Problem #112

September 5, 2010

Read the details of the problem here

Summary

Investigating the density of “bouncy” numbers.

Solution

The problem reads as being relatively straightforward and fairly non-mathematical in nature (though I can see that it might have to become a statistical problem on a larger scale) so, before I tried anything too clever I went for a simple brute force approach. I just looked to see if the digits of the number were already sorted in either ascending or descending order.

def (answer, b) = [ 100, 0 ]

while (true) {
  def s = answer.toString()
  def sorted = (s as List).sort().join()
  if ((s != sorted) && (s != sorted.reverse())) b++
  if (answer * 0.99 == b) break
  answer++
}

This runs in 13.24 seconds and so just sneaks in under the wire to satisfies my success conditions!

This did seem a little slow though and replacing lines 4-6 in the solution above with a call to the method below brought the runtime down to 10.59 seconds.

def isBouncy(n) {
  def s = n.toString()
  def direction = 0
  def len = s.length()
  for (i in 1..<len) {
    if (direction == 1 && (s[i] < s[i-1])) return true
    if (direction == -1 && (s[i] > s[i-1])) return true
    if (direction == 0) {
      if (s[i] > s[i-1]) {
        direction = 1
      }
      else if (s[i] < s[i-1]) {
        direction = -1
      }
    }
  }
  return false
}
 

Is the added complexity worth that reduction of 20%? In this case, probably not!

Conclusion

Groovy made this a nice, terse solution. Performance wasn’t excellent but the solution was quick to write and easy to understand when reading it back.

Advertisements

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.

Read the details of the problem here

Summary

Investigating the number of ways of tiling a row using different-sized tiles.

Solution

This question follows on nicely from Problem 114, Problem 115 & Problem 116. I used my solution from Problem 115 as a base and amended it so that, rather than having a hardcoded block/tile size iteration it would accept a range as parameter m into the count method. Apart from the change to allow no gaps between tiles and a corresponding change to F() to allow ranges that was about it.

def count(m, gap, cache) {

  if (gap < m[0]) return 0
  if (cache[gap] != -1) return cache[gap]

  def total = 0L
  for (len in m) {
    def maxpos = gap - len + 1      
    total += maxpos
    for (pos in 0..maxpos) {
      total += count(m, gap - len - pos, cache)
    }
  }
  cache[gap] = total
}

def F(m, n) {
  def cache = new long[n+1]
  Arrays.fill(cache,-1)
  cache[m[0]] = 1
  1 + count(m, n, cache)
}

def answer = F((2..4), 50)

This runs in 64 milliseconds and returns an amazingly high number!

Conclusion

As per the solution to Problems 114, 115 & 116, Groovy kept the syntax terse but it wasn’t really a Groovy solution. It did make the adding the ability to accept a range parameter a really trivial exercise though, so big win for Groovy over Java in this respect.

Read the details of the problem here

Summary

Investigating the number of ways of replacing square tiles with one of three coloured tiles.

Solution

This question follows on nicely from Problem 114 and Problem 115. It was just a matter of amending the count() method from Problem 115 to cater for the facts that (i) the block is a fixed size and (ii) no gap is required to be kept between blocks. The F() method had to be changed slightly as an empty solution are not permitted. The rest was just a case of adding the values for each block type which a listop made easy.

def count(m, gap, cache) {

  if (gap < m) return 0
  if (cache[gap] != -1) return cache[gap]

  def total = gap - m + 1L
  def maxpos = total
  for (pos in 0..maxpos) {
    total += count(m, gap - m - pos, cache)
  }
  cache[gap] = total
}

def F(m, n) {
  def cache = new long[n+1]
  Arrays.fill(cache,-1)
  cache[m] = 1L
  count(m, n, cache)
}

def answer = (2..4).sum { F(it,50) }

This runs in 67 milliseconds. Again, acceptable for this solution especially with so little editing needed from my earlier solution!

Conclusion

As per the solution to Problems 114 & 115, Groovy kept the syntax terse but it wasn’t really a Groovy solution (apart from the last line!).

Read the details of the problem here

Summary

Finding a generalisation for the number of ways to fill a row with separated blocks.

Solution

Having just completed Problem 114 and with that fresh in my mind, this problem was very straightforward. I just parameterised the count() function to accept the block length and created a wrapping function F() (as per the question) that would create an appropriately sized & initialized cache and then call count() to do the grunt work of the calculation. After that I had to find a way to call this with sufficient efficiency to return in a timely manner – I could have coded up a bisection search but, in this case, a simple ascending search was efficient enough for this purpose.

def count(m, gap, cache) {

  if (gap < m) return 0
  if (cache[gap] != -1) return cache[gap]

  def total = 0L
  for (len in m..gap) {
    total += gap - len + 1
    def maxpos = gap - len + 1
    for (pos in 0..maxpos) {
      total += count(m, gap - len - pos - 1, cache)
    }
  }
  cache[gap] = total
}

def F(m, n) {
  def cache = new long[n+1]
  Arrays.fill(cache,-1)
  cache[m] = 1    
  1 + count(m, n, cache)
}

def ( BLOCK_LEN, LIMIT ) = [ 50, 1e6 ]

def answer = BLOCK_LEN

while (F(BLOCK_LEN, answer) <= LIMIT) {
  answer++
}

This runs in 0.49 seconds. Perfectly acceptable for this solution and could be further tweaked for performance if needed.

Conclusion

As per the solution to Problem 114, Groovy kept the syntax terse but it wasn’t really a Groovy solution.

Read the details of the problem here

Summary

Investigating the number of ways to fill a row with separated blocks that are at least three units long.

Solution

Nice little problem to start the day with. I opted for a recursive solution that places blocks of length 3 upwards into a gap, shuffling them to the right as far as possible. For each position it calls itself to place blocks in a new gap to the right of the placed block leaving a space of 1 unit between them. Note that it’s important to initialize total as a long to prevent overflow (that had me flummoxed for a few minutes!). It’s also necessary to add one to the returned answer to cater for an empty solution with no blocks placed.

def cache = new long[51]
Arrays.fill(cache,-1)
cache[3] = 1

def count(gap, cache) {

  if (gap < 3) return 0
  if (cache[gap] != -1) return cache[gap]

  def total = 0L
  for (len in 3..gap) {
    total += gap - len + 1
    def maxpos = gap - len + 1
    for (pos in 0..maxpos) {
      total += count(gap - len - pos - 1, cache)
    }
  }
  cache[gap] = total
}

def answer = 1 + count(50, cache)

This runs in 91 milliseconds. A Java version runs in 960 microseconds or thereabouts, so about 95x faster.

Conclusion

Groovy kept the syntax terse but it wasn’t really a Groovy solution. Although it’s possible to rewrite the loops as listops, I don’t really think that it adds any value to the solution and has an adverse impact on performance.

Read the details of the problem here

Summary

Finding the maximum remainder when (a − 1)n + (a + 1)n is divided by a2.

Solution

It’s best, as always, to try to understand and to simplify the search space for these maths type problems in an attempt to reduce the processing complexity especially where Groovy is concerned. The total is the sum of two polynomial expansions which will rapidly grow too large to process as the value of n increases so probably won’t be amenable to a brute-force attempt – at least not without some optimization.

So, looking at the expanded polynomial calculations this is what we get.

For n = 1:
   (a-1)1 + (a+1)1
   2a

For n = 2:
   (a-1)2 + (a+1)2
   (a2-2a+1) + (a2+2a+1)
   2a2 + 2

For n = 3:
   (a-1)3 + (a+1)3
   (a3-3a2+3a-1) + (a3+3a2+3a-1)
   2a3 + 6a

For n = 4:
   (a-1)4 + (a+1)4
   2a4 + 12a2 + 2

This pattern is true for all even values of n – the last element will always just be 2 and the other terms are all even powers of a and so evenly divisible by a2

For n = 5:
   (a-1)5 + (a+1)5
   2a5 + 20a3 + 10a

This pattern is followed for all of the odd values of n. Only the lowest element in the expansion, 2an, is significant as the leading elements will always evenly divisible by a2.

So I only need to deal with odd values of n and the remainder calculation is just 2an % a2. The value of this function is obviously minimised when 2an = m.a2 for all values of m. Ignoring m and rearranging that I get n = a/2 – this means that the function will be maximized for n = (a-1)/2. Substituting this back into the exemplar of a=7, n=3 to test it – 2 * 7 * (7-1)/2 = 2 * 7 * 3 = 42. Cool. This means that there’s no need to loop through values for n at all.

Coding this is then very straightforward.

def answer =
    (3..1000).sum { 2 * it * (it - 1).intdiv(2) }
 

This runs in 43 ms.

Conclusion

In the end, Groovy was quite capable of implementing this in a terse and effective manner. A brute force attempt might not have been so successful though.