You have an infinite binary tree where each vertex is labeled: the left child has the label `2n`, right child `2n + 1`, with the root node having the label 1. The input is a walking sequence containing L (go to the left child), R (go to the right child), P (stay), and * (all of these). Output the sum of all the labels you can end up at following…

gistfile1.rb

s = gets.strip

m = {
  ?L => ->(z) { z + z.real },
  ?R => ->(z) { z + Complex(z.real, z.real) },
  ?P => ->(z) { z },
  ?* => ->(z) { m[?L][z] + m[?R][z] + z }
}

z = s.reverse.each_char.inject(Complex(1)) { |z, c| m[c][z] }

puts z.imag + z.real