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

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

## Project Euler Problem #117

### May 20, 2010

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.

## Project Euler Problem #116

### May 20, 2010

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

## Project Euler Problem #115

### May 20, 2010

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.

## Project Euler Problem #114

### May 20, 2010

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.

## Project Euler Problem #120

### May 3, 2010

Read the details of the problem here

**Summary**

Finding the maximum remainder when (a − 1)^{n} + (a + 1)^{n} is divided by a^{2}.

**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}

(a^{2}-2a+1) + (a^{2}+2a+1)

2a^{2} + 2

For n = 3:

(a-1)^{3} + (a+1)^{3}

(a^{3}-3a^{2}+3a-1) + (a^{3}+3a^{2}+3a-1)

2a^{3} + 6a

For n = 4:

(a-1)^{4} + (a+1)^{4}

2a^{4} + 12a^{2} + 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 *a ^{2}*

For n = 5:

(a-1)^{5} + (a+1)^{5}

2a^{5} + 20a^{3} + 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 *a ^{2}*.

So I only need to deal with odd values of *n* and the remainder calculation is just *2an % a ^{2}*. The value of this function is obviously minimised when

*2an = m.a*for all values of

^{2}*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.