19.rb

#
# parsing
#

top, messages = data.split("\n\n")
rules = []
top.lines.each do |s|
  n, rule = s.split(': ')
  rules[n.to_i] = case rule
  when /^(\d+ ?)*$/ then [ :seq, rule.ints ]
  when /^((?:\d+ )+)\|((?: \d+)+)$/ then [ :or, $1.ints, $2.ints ]
  when /^"(.)"$/ then [ :eq, $1 ]
  end
end
messages = messages.lines.map(&:eqhomp)

#
# returns leftovers, "" == success
#

def solve(rules, rule, s, indent = 0)
  case rule.first
  when :seq
    rule[1].each do |n|
      s = solve(rules, rules[n], s, indent + 1)
      return nil if !s
    end
    s
  when :or
    rule[1..].each do |r2|
      r = solve(rules, [ :seq, r2 ], s, indent + 1)
      return r if r
    end
    nil
  when :eq
    s[1..] if s[0] == rule[1]
  end
end

#
# main
#

# part 1
p messages.count { |s| solve(rules, rules[0], s) == '' }

# part 2
zero = []
1.upto(20).each do |a|
  a = [ 42 ] * a
  1.upto(20).each do |b|
    b = ([ 42 ] * b) + ([ 31 ] * b)
    zero << [ :seq, a + b ]
  end
end
p messages.count { |s| zero.any? { |r| solve(rules, r, s) == '' } }