## 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 } def answer = 0 c[0..-2].eachWithIndex { d1, i -> c[(i+1)..-1].each { d2 -> if (squares.every { d1.contains(it[0]) && d2.contains(it[1]) || d1.contains(it[1]) && d2.contains(it[0]) }) answer++ } }

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.