Solution to Project Euler problem #215

pe-215.rb

=begin

Most of the work here is in generating a sort of matrix of mutually
compatible "p-bricksets," or single-row arrangements of bricks. There are
something like 3,300 of these total.

Once you have that matrix - what in the code I call the "compatimap" - all you
do is exhaustively "expand" each p-brickset ten times (for the ten rows).

It helps to imagine the space of possible walls as a tree in which nodes are
p-bricksets, and the children of any given node are the set of p-bricksets
compatible with that node. So a p-brickset A might expand into p-bricksets B,
E, and M.

Our goal, then, is to find the number of leaf nodes on a tree ten levels deep.

You start with a hash {A => 1, B => 1, C => 1, ..., Z => 1, ...} that maps
p-bricksets (A, B, C, ...) to a number that tracks the number of leaf nodes
that use that p-brickset after a certain number of "expansions."

So after three rows you might have a hash {A => 17, B => 2294, C => 12, ..., 
Z => 10, ...}, which says that after going three nodes deep into your tree, A
is the last row 17 times, B is the last row 2,294 times, C 12 times, Z 10, 
etc. Add those up and you have the number of possible crackless walls.

To get the hash for the next step, you just take each of the p-bricksets you
already have, find candidates for the next row using the compatimap (so A
might be compatible with B, E, and M), and multiply the number of those
candidates by the number of the p-brickset you're expanding from - because
you have 17 As, you'd add 17 Bs, Es, and Ms to the next step's hash.

The code to do this last step (the expanding) runs in 360ms.

=end
 
# 1. Build and collect the possible bricksets.
X = 32
Y = 10
 
if X % 2 == 0
  l = [2] * (X / 2)
else
  l = [3] + [2] * (X / 2 - 1)
end
 
bricksets = []
while true
  bricksets << l
  l = l.clone
  i = l.index(2)
  break if i.nil?
  l[i] += 1
  begin l[i + 1] += 1 rescue break end
  l.pop()
  break if l.sum != X
end

# 2. Generate every permutation of the bricksets.
def slide(i, l)
  "[2, 2, 3, 2, 2] => [2, 2, 2, 3, 2]"
  if (i + 1) < l.length
    l[i + 1] = 3
    l[i] = 2
  end
  l
end

def reset(i, l)
  "[2, 2, 3, 3, 2, 2, 3] => [2, 2, 3, 2, 3, 3, 2]"
  remainder = l[i + 1..-1]
  ts_left = remainder.count(3)
  ws_left = remainder.count(2)
  l[0..i] + [3] * ts_left + [2] * ws_left
end

def tick(b)
  "Generate the 'next' permutation for a given brickset."
  if b.rindex(3) == (b.length - 1) and (b.rindex(3) - b.index(3)) == (b.count(3) - 1)
    return false
  elsif (i = b.rindex(3)) != (b.length - 1)
    return slide(i, b)
  else
    i = b[0..i - 1].rindex(3) until (b[i + 1] != 3 and !b[i + 1].nil?)
    slide(i, b)
    reset(i, b)
  end
end

def pbsets(b)
  "Enumerate all the p-bricksets of a given brickset,
  using the tick function."
  if b.count(2) == b.length
    return [b]
  end
  z = b.clone
  ps = [b]
  while b = tick(b)
    x = b.clone
    ps << x
  end
  ps.shift
  ps.unshift(z)
end

pbs = []
bricksets.each {|b| pbsets(b).each {|pb| pbs << pb}}
PBS = pbs.collect {|x| [pbs.index(x), x]}

# 3. Create an index mapping partial x-wise sums to p-bricksets,
# and use that index to create a matrix of mutually compatible
# p-bricksets
def partials(b)
  "Starting from the left, calculate partial sums of a brickset."
  (0..b.length - 2).collect {|i| b[0..i].sum}
end

Index = {}
PBS.each do |pb|
  partials(pb[1]).each {|x| if Index[x] then Index[x] << pb[0] else Index[x] = [pb[0]] end}
end

def compatibles(b)
  "Gives the list of p-bricksets compatible with b."
  incompatibles = []
  partials(b[1]).each {|b| incompatibles += Index[b]}
  (0..PBS.length - 1).to_a - incompatibles
end

compatimap = {}
PBS.each {|pb| compatimap[pb[0]] = compatibles(pb)}

## 4. Explore the tree exhaustively, expanding at each level using
## the compatimap, a process not unlike the expansion of sentences
## in a context-free grammar.
u = {}
PBS.each {|pb| u[pb[0]] = 1}
n = 0
while (n += 1) < Y
  x = {}
  u.keys.each do |k|
    compatimap[k].each do |i|
      if x[i] then x[i] += u[k] else x[i] = u[k] end
    end
  end
  u = x
end
p u.values.sum