#!/usr/bin/env ruby

def getreps(str, from, to)
  re = Regexp.new(from)
  md = str.match(re)

  reps = []
  until md.nil?
    reps << str[0...md.begin(0)] + to + str[md.end(0)..-1]
    md = str.match(re, md.end(0))
  end

  reps
end

*istrs, _, init = File.readlines("day19.input").map(&:strip)
istrs.map! { |istr| istr.split(" => ") }

results = Set.new
istrs.each do |from, to|
  results += getreps(init, from, to)
end

puts "Part 1: #{results.length}"


istrs.map! { |from, to| [to, from] }

space = [[init, 0]]
mindis = init.length

loop do
  break if space.empty?
  this, thisdis = space.pop

  if this == ?e
    mindis = thisdis if thisdis < mindis
    next
  end

  istrs.each do |from, to|
    getreps(this, from, to).each do |rep|
      space.push([rep, thisdis + 1])
    end
  end
end

puts "Part 2: #{mindis}"