Project Euler Problem #90

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: