Project Euler Problem #86

May 24, 2011

Read the details of the problem here

Summary

Exploring the shortest path from one corner of a cuboid to another.

Solution

It’s been a while since I’ve posted a Project Euler solution and the ones I have posted have been catch-ups. The other day I saw a specific search on this site for a solution to Problem 86 which I hadn’t yet completed so I thought I’d give it a go…

On first reading this seemed a little unclear but it comes apart quite easily with a little prodding and poking. Taking the example that Euler gives and flattening it makes it apparent what’s going on. The shortest path (SF) is the hypotenuse of a Pythagorean triangle with sides of { 6, 8 (3+5), 10 }. The diagram below shows the case of an M x M x M cuboid to demonstrate the three variants of the shortest path in a very obvious manner. So it’s just a case of checking for Pythagorean triangles with an adjacent side of length M, and up to 2M for the opposite side. Note that, due to this abstraction from the actual cuboid, it’s not necessary to deal with the other two sides individually – the opposite side length is taken as the total of the depth and height of the cuboid. Once a suitable triangle is found the number of solutions for it, taking into account the ways in which the opposite side length may be composed for any given potential cuboids, are added onto the running total.

```def ( answer, solutions ) = [ 1, 0 ]

while (true) {
for (i in 2..(2 * answer)) {
if (hyp == Math.floor(hyp)) {
solutions += (i > answer + 1) ?
}
}
if (solutions > 1e6) break
}
```

The solution is quite succinct and, even though it’s simply a brute force algorithm, runs in around 1.31 seconds – so well within the 15 second target. Smarter algorithms might include changing this one to a bisection search of across the solution space, or maybe pre-generating Pythagorean triangles and driving directly off of those.

Conclusion

Groovy was perfectly fast enough for solving this problem, both in terms of coding and runtime. From a performance perspective it’s advisable to use the Math.floor() function rather than a straight cast to (int) and calling intdiv() is also a must compared to a straight division.

Project Euler Problem #85

May 14, 2010

Read the details of the problem here

Summary

Investigating the number of rectangles in a rectangular grid.

Solution

Firstly, I reduced this down to a basic 1D problem, solving the number of consecutive tiling solutions on a single line, as per the diagram below.

It is evident that the combinations for each line is simply the sum of terms.

Length Rectangles
1 1
2 3
3 6
4 10

The 3×2 rectangular exemplar has 18 rectangles which is simply the product of the linear combinations, i.e. Sum[1,2,3] x Sum[1,2] = 18, and extending this (as shown below) to blocks of 2×2 (9 rectangles) and 3×3 (36 rectangles) shows this rule to hold.

The program is therefore very straightforward, I just need to multiply the combinations for the various length sides and look for the closest to 2 million. The square root of 2 million is 1414.2. Sum(1..53) is 1431 but this question needs to minimize the difference so it may be over or under the stated target. I simply picked a maximum side length of 100, kept my fingers crossed and it gave the correct answer.

```def ( mindiff, answer ) = [ Integer.MAX_VALUE, 0 ]

def sums = (0..100).collect { (it * it + it) / 2 }

for (i in 1..100) {
for (j in i..100) {
def n = sums[i] * sums[j] - 2000000
if ( Math.abs(n) < mindiff )
( mindiff, answer, x, y ) = [ Math.abs(n), i * j ]
if (n > 0) break
}
}
```

This runs in 74 ms, so even though it’s brute-force it performs quite adequately for this purpose.

Conclusion

Groovy provided a certain convenience in syntax but I didn’t really use any special features in this solution. A Java solution would have been almost as terse.

Project Euler Problem #87

May 14, 2010

Read the details of the problem here

Summary

Investigating numbers that can be expressed as the sum of a prime square, cube, and fourth power?

Solution

Strictly speaking, I failed on this one. Groovy was taking just under 16 seconds to create a prime sieve for numbers up to 50 million and so I had to use Java to generate the sieve (a naive implementation taking 1.81 seconds).

Having got a set of primes it was then just a case of contructing three lists for the various powers of the primes and finding combinations that matched the criteria. As there are some duplicates possible it was necessary to store the results in a Set (again easy to do in Groovy) and just get the number of entries.

```import com.keyzero.euler.EulerUtils

def LIMIT = 50000000
def powers = [ 2:[], 3:[], 4:[] ]
def sqrt = (int)Math.sqrt(LIMIT)
def primes = EulerUtils.getPrimes(sqrt)

for (i in 2..sqrt) {
if (primes.isPrime(i)) {
for (p in 2..4) {
def n = i ** p
if (n < LIMIT) powers[p] << n
}
}
}

def numbers = [] as Set

powers.each { p2 ->
powers.findAll { (p2 + it) < LIMIT }.each { p3 ->
powers.findAll { (p2 + p3 + it) < LIMIT }.each { p4 ->
numbers << (p2 + p3 + p4)
}
}
}

```

This runs in 5.36 seconds. Acceptable, but not the fastest of solutions, so maybe there’s a better way of approaching this problem. Switching over to an explicit set of nested loops (as code below) to process the prime power lists drops the runtime to 3.11 seconds. A reduction of 43% overall and 64% when excluding the sieve generation.

```for (p2 in powers) {
for (p3 in powers) {
def p2p3 = p2 + p3
if (p2p3 > LIMIT) break
for (p4 in powers) {
def sum = p2p3 + p4
if (sum > LIMIT) break
numbers << sum
}
}
}
```

Conclusion

Groovy was a bit of a two-edged sword in this solution. It’s lack of raw performance meant that I had to import some Java (which was easy to do though) but it’s listops made the rest easy to do, albeit not very performant. This solution shows again that using listops is convenient but carries a high runtime performance penalty.

Project Euler Problem #89

May 14, 2010

Read the details of the problem here

Summary

Develop a method to express Roman numerals in minimal form.

Solution

A nice little programming problem rather than anything mathematical for this one. The FAQ gave some interesting background on Roman numerals too!

Looking at the input data, it did look like it might be possible to solve this just with straight textual substitution but, in the spirit of the site, I wrote a routine to parse the input Roman numeral sequences and then another to write them out in minimal form – the latter actually being more straightforward than the former as it just a case of considering the set of Roman character (including the subtractive combinations) as a sort of a working base and just dividing through and subtracting the multiples.

```def fromRoman(s) {

def romans = [ I:1, V:5, X:10, L:50, C:100, D:500, M:1000 ]
def ( lastChar, grpValue, sum ) = [ null, 0, 0 ]

s.toList().eachWithIndex { v, i ->

if (i == 0) {
lastChar = v
grpValue = romans[v]
}
else if (v == lastChar) {
grpValue += romans[v]
}
else {
if (romans[lastChar] < romans[v]) grpValue *= -1
sum += grpValue
grpValue = romans[v]
lastChar = v
}

if (i == s.size()-1) {
if (romans[lastChar] < romans[v]) grpValue *= -1
sum += grpValue
}
}

return sum
}

def toRoman(n) {

def s = ""

[ 1000:"M", 900:"CM", 500:"D", 400:"CD", 100:"C", 90:"XC",
50:"L",  40:"XL",  10:"X",   9:"IX",   5:"V",  4:"IV",
1:"I" ].each { k, v ->
def m = n.intdiv(k)
if (m > 0) {
s += v * m
n -= k * m
}
}
return s
}

new File("euler_p89_roman.txt").eachLine {
}
```

This runs in 0.14 seconds so well within the time allowed.

Conclusion

Groovy’s file handling and terse syntax was nice to use, but wouldn’t have been much more in Java. For the scale of the problem, performance wasn’t an issue at all.

Project Euler Problem #90

Apr 12, 2010

Read the details of the problem here

Summary

An unexpected way of using two cubes to make a square.

Solution

Pretty straight-forward problem to solve. Just generate the 210 combinations of die faces and then compare all possible pairs of them to see if they could satisfy the squares. The only slight wrinkle was the handling of 6s and 9s – I addressed this by replacing both of these with a value of -1 in the tuples representing the squares and the numbers on the dice (essentially making -1 a “wildcard” value).

```def squares = []
(1..9).each {
def n = it * it
def sqr = [ n.intdiv(10), n % 10 ]
[6,9].each { d -> Collections.replaceAll(sqr, d, -1) }
squares << sqr
}

def c = []
combinations(10, 6) {
def digits = it.toList()
[6,9].each { d -> Collections.replaceAll(digits, d, -1) }
c << digits
}

c[0..-2].eachWithIndex { d1, i ->

c[(i+1)..-1].each { d2 ->

if (squares.every {
d1.contains(it) && d2.contains(it) ||
d1.contains(it) && d2.contains(it)
}
}
```

I reused a combination generator that I created for the solution of Problem 121. The code for this is shown below.

```def combinations(n, k, yield) {
def selected = new int[k]
for (i in 0..<k) { selected[i] = i }
while (true) {
yield(selected)
def i = k - 1
while ((i >= 0) && (selected[i] == ( n - k + i ))) { i-- }
if (i < 0) break
selected[i]++
for (j in (i + 1)..<k) { selected[j] = selected[i] + j - i }
}
}
```

This runs in an acceptable 0.34 seconds even though it’s using the slow Groovy listops.

Conclusion

Groovy made this a really simple solution to put together, being able to use easily use lightweight types such as lists and tuples.

Update: I found that Groovy Collections have a method added called combinations() that will create the cross-product of two member lists. This means that I don’t actually need to use an explicit loop to match the two lists of die face combinations but can do it declaratively as shown below:

```def answer =
[c,c].combinations()
.findAll { d1, d2 ->
squares.every { s0, s1 ->
d1.contains(s0) && d2.contains(s1) ||
d1.contains(s1) && d2.contains(s0) } }
.size()
.intdiv(2)
```

Runtime for this is 0.77 seconds. Note the intdiv(2) requirement as doing it this way essentially repeats every combination twice as the list is being joined with itself. I did try using the unique() method on the list of combinations (44,100 pairs of 6-tuples) but it pushed the runtime up into minutes and caused a lot of GC thrashing.

Project Euler Problem #84

Apr 9, 2010

Read the details of the problem here

Summary

In the game, Monopoly, find the three most popular squares when using two 4-sided dice.

Solution

When I first read this problem, I thought it was quite straightforward and just relied on the initial roll of the dice, starting from GO. However, assuming this approach for six-sided dice gave me completely different percentages to what were cited in the question. It became apparent to me that what was required was the long-term probabilities of landing on a specific square.

I considered extending my original approach using chains of probabilities but it quickly got out of hand once I considered how to incorporate the rolling of 3-doubles and the random events from the Community Chest and Chance cards. The search space that was required was becoming very large indeed. I had wondered why only some 1,960 or so people had solved this since it was posted on 3-Dec-2004 (it being 8-Apr-2010)and now it became apparent!

Not wanting to be beaten on this I decided to go for a simulation approach and hoped that the probabilities didn’t require too much accuracy. The question was just looking for an ordering rather than the probabilities themselves so a Monte Carlo technique might pay off.

Having decided this it was more straightforward to write than I thought it might be, although it did raise a few implementation questions that weren’t addressed in the problem statement. Specifically, when sent to Jail due to a random card event, or landing on the Go To Jail square, are your double counts reset? I always played that way so that’s how I coded it. Also, I assumed that the card packs remained in order and all the jump cards were essentially at the front of the pack. I didn’t shuffle them or pick cards at random which would have been alternative approaches. I also noted that it was possible, given a Go Back 3 Squares from Chance 3 (Square:CH3) that you’d land back on CC3 and have to also take a CC card – this therefore dictated the ordering of the card pack selections in the simulation.

```def ( GO, G2J, JAIL ) = [  0, 30, 10 ]
def ( R1, R2, R3 )    = [  5, 15, 25 ]
def ( U1, U2 )        = [ 12, 28 ]
def ( CC1, CC2, CC3 ) = [  2, 17, 33 ]
def ( CH1, CH2, CH3 ) = [  7, 22, 36 ]
def ( C1, E3, H2 )    = [ 11, 24, 39 ]

def counts = new int
def ( location, cci, chi, dbls ) = [ GO, 0, 0, 0 ]

for (i in 1..1000000) {

def r1 = (int)(Math.random() * 4) + 1
def r2 = (int)(Math.random() * 4) + 1

dbls = (r1 == r2) ? dbls+1 : 0
location = (location + r1 + r2) % 40

if ((dbls == 3) || (location == G2J)) {
location = JAIL
dbls = 0
}

if (location in [ CH1, CH2, CH3 ]) {
switch (chi) {
case 0: location = GO; break
case 1:
location = JAIL
dbls = 0
break
case 2: location = C1; break
case 3: location = E3; break
case 4: location = H2; break
case 5: location = R1; break
case 6..7:
location = [(CH1):R2,(CH2):R3,(CH3):R1][location]
break
case 8:
location = [(CH1):U1,(CH2):U2,(CH3):U1][location]
break
case 9: location -= 3; break
}
chi = ++chi % 16
}

if (location in [ CC1, CC2, CC3 ]) {
switch (cci) {
case 0: location = GO; break
case 1:
location = JAIL
dbls = 0
break
}
cci = ++cci % 16
}

counts[location]++
}

def odds = []
counts.eachWithIndex { v, i -> odds << [ i, v/10000 ] }

def answer = odds.sort { -it }[0..2].collect {
sprintf("%02d",it)
}.join()
```

I could have taken a much more OO approach to this simulation, modelling the dice, board, card packs (maybe with each card holding a Closure that transformed the position in a Command pattern approach), etc. but it would have been complete overkill for this solution.

As it is, this ran in 4.19 seconds, with simulation itself taking 4.16 seconds. Post-processing the results was quick to write and obviously ran sufficiently fast enough for the scale of this problem.

Note: The separation of 3rd and 4th rank elements is only something in the order of 0.06% – through numerous runs of the simulation I have found that one million iterations reliably makes this distinction but does, very rarely, transpose them. For reference, I make the first five probabilities as follows: 6.96%, 3.59%, 3.29%, 3.23%, 3.12%, but results can obviously differ slightly from run-to-run.

Having got the correct answer using this approach and so gained access to the Project Euler forum for the problem, I was interested to see most people had taken the simulation approach. A few brave souls had used Markov Chains and similar statistical approaches (sometimes just ignoring the inconvenient doubles and CH3->CC3 rules as these didn’t have any material effect on the ranking it seemed, though they would on the absolute probabilities). This sort of problem seems to come up in later Project Euler questions so I should spend some time in understanding this technique more.

Conclusion

I didn’t actually use too many Groovy specific features in this, apart from variable declarations, multiple assignment, the easy map lookups for the rail and utility jumps, and the listops to process the results array at the end of the simulation. So…maybe I did use quite a few features after all but it’s still very much like a standard Java program though somewhat too procedural perhaps!

Note: I’ve now completed 89/286 problems ranking me at 140/2245 members in England though I am still a n00b on the site! Only 11 more to solve before I get be included in the Novice category.