Project Euler Problem #174

Read the details of the problem here

Summary

Counting the number of “hollow” square laminae that can form one, two, three, … distinct arrangements.

Solution

Having just completed Problem #173 the previous evening, I found this a very easy one to start the day with! The same solution could be used with just a few minor alterations.

Rather than just incrementing the count of laminae I incremented an element in an array corresponding to the number of tiles in use for the lamina so, for the examples given, element 8 => 1 and element 32 => 2. This should have had a negligible effect on the runtime and given me an array containing how many laminae were created for any particular number of tiles.

The question is worded a little confusingly but is really just asking “How many tile counts, in the given range, can form between one to ten laminae?” This information is easily extracted from the array using a couple of Groovy listops.

def LIMIT = 1000000
def MAX = LIMIT.intdiv(4)+1
def (MINW, MAXW) = [ 3, LIMIT.intdiv(4)+1 ]

def L = new int[LIMIT+1] 
Arrays.fill(L,0)

for (width in MINW..MAXW) {
  def tiles = (width - 1) * 4
  L[tiles]++
  def (inner, inside) = [ width - 2, tiles - 8 ]
  while ((tiles + inside <= LIMIT) && (inner >= MINW)) {
    tiles += inside
    L[tiles]++
    inner -= 2
    inside -= 8
  }
}

def answer =
    L.toList().findAll { it > 0 && it < 11 }.size()

This runs in 2.09 seconds, well within the alloted time but taking 1.18 seconds longer that than before! The addition of the array to the Problem #173 solution brought the runtime up to 1.09 seconds (adding 180ms) so the bulk of that time – 1 second – was in the single line assignment to the answer! I found that coding an explicit accumulation loop over L reduced the runtime down to 1.31 seconds, so was 5x faster than the listop method.

Note: A Java version runs in about 15ms – 140x faster than this Groovy code, but 5x slower than before. Only 2ms is attributable to the final accumulation loop, the other 10ms is simply from array access. I must look into this!

Conclusion

Groovy didn’t add or detract from this solution, but it only goes to show that, while Groovy listops are great syntactically, they suck in performance. I know that I should really be using Groovy lists rather than explicit arrays but, in this case, they bump up the runtime by another 30% or more.

Project Euler Problem #173

Read the details of the problem here

Summary

Using up to one million tiles how many different “hollow” square laminae can be formed?

Solution

I started by considering a maths solution based around differences of sums of squares. In the examples given: 6²-2² = 9²-7² = 32. This seemed a viable approach to working out areas of laminae given the outline width and “hole” widths but it was getting late and I thought I’d go for something more obviously correct when coding!

All I do is start with a single ringed lamina and then add rings inside it until I run out of tiles, or run out of space in which to contain an inner ring. I then repeat this process with a lamina that starts one tile wider. Essentially I was trading mathematically complexity for computational iterations which suited me just fine at 2am!

The coding for this was trivial. Each inner ring is 2 tiles narrower and so 8 tiles smaller – only basic addition and subtraction is required in the inner loop. The solution is simple and “obviously correct”! No understanding of maths required!

def LIMIT = 1000000
def (answer, MINW, MAXW) = [ 0, 3, LIMIT.intdiv(4)+1 ]

for (width in MINW..MAXW) {
  def tiles = (width - 1) * 4
  answer++
  def (inner, inside) = [ width - 2, tiles - 8 ]
  while ((tiles + inside <= LIMIT) && (inner >= MINW)) {
    tiles += inside
    answer++
    inner -= 2
    inside -= 8
  }
}

This runs in 0.91 seconds, well within the alloted time. A Java version runs in about 3ms – 310x faster. Unsurprisingly, the algorithm doesn’t scale well but was perfectly adequate for this solution. I may have to revisit it for subsequent problems of this nature.

Conclusion

Groovy didn’t add or detract from this solution. It saved some boilerplate but that was about it.

Project Euler Problem #179

Read the details of the problem here

Summary

Consecutive positive divisors.

Solution

I went straight to Java for this problem. I felt that a sieve approach to count the divisors would be better than trying to actually calculate the divisors themselves for such a large range of numbers. Given past performance of Groovy when carrying out such activity I thought it would be a non-starter to use it and I couldn’t see a better algorithm.

Coding was straightforward. I used a simple optimisation to allow the outer-loop to only run to the square-root of LIMIT but nothing extraordinary.

final int LIMIT = 10000000;
int[] sieve = new int[LIMIT+1];
Arrays.fill(sieve, 2);  // don't worry about elements 0 & 1

for (int i = 2; i <= (int)Math.sqrt(LIMIT); i++) {

    int j = i * i;
    sieve[j]--;

    while (j <= LIMIT) {
        sieve[j] += 2;
        j += i;
    }
}

int answer = 0;

for (int i = 2; i < LIMIT; i++) {
    if (sieve[i] == sieve[i+1]) answer++;
}

This runs in 2.16 seconds.

Conclusion

Groovy? A simple ported implementation that doesn’t use any special features runs in 15.3 seconds. So not far out, but not quite there!

Note: After solving this and gaining access to the forum, it seems that there is a technique that solves this in an amazing 312 ms using Java, but porting this to Groovy actually takes longer, at 24.1 seconds, than the simple optimisation. I’ll do some more research into why this is because it seems like a strange pathological behaviour, maybe to do with memory management or array access patterns.