#!/usr/bin/env ruby

require "debug"

input = (ARGV.first.nil? ? DATA : ARGF)
  .readlines(chomp: true)

towels = input.first.split(", ")
designs = input[2..]

def count_candidates(design, towels, cache = {})
  return 1 if design == ""
  return cache[design] if cache.key?(design)

  cache[design] = towels
    .select { design.start_with?(_1) }
    .map { count_candidates(design[_1.size..], towels, cache) }
    .sum
end

p designs.count { _1.match?(/^#{Regexp.union(*towels)}+$/) }
p designs.map { count_candidates(_1, towels) }.sum

__END__
r, wr, b, g, bwu, rb, gb, br

brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwb