# coding: utf-8
# http://AdventOfCode.com/
# --- Day 19: Medicine for Rudolph ---
#
# Rudolph the Red-Nosed Reindeer is sick! His nose isn't shining very brightly, and he needs
# medicine.
#
# Red-Nosed Reindeer biology isn't similar to regular reindeer biology; Rudolph is going to need
# custom-made medicine. Unfortunately, Red-Nosed Reindeer chemistry isn't similar to regular
# reindeer chemistry, either.
#
# The North Pole is equipped with a Red-Nosed Reindeer nuclear fusion/fission plant, capable of
# constructing any Red-Nosed Reindeer molecule you need. It works by starting with some input
# molecule and then doing a series of replacements, one per step, until it has the right molecule.
#
# However, the machine has to be calibrated before it can be used. Calibration involves
# determining the number of molecules that can be generated in one step from a given starting
# point.
#
# For example, imagine a simpler machine that supports only the following replacements:
#
# H => HO
# H => OH
# O => HH
# Given the replacements above and starting with HOH, the following molecules could be generated:
#
# HOOH (via H => HO on the first H).
# HOHO (via H => HO on the second H).
# OHOH (via H => OH on the first H).
# HOOH (via H => OH on the second H).
# HHHH (via O => HH).
#
# So, in the example above, there are 4 distinct molecules (not five, because HOOH appears twice)
# after one replacement from HOH. Santa's favorite molecule, HOHOHO, can become 7 distinct
# molecules (over nine replacements: six from H, and three from O).
#
# The machine replaces without regard for the surrounding characters. For example, given the
# string H2O, the transition H => OO would result in OO2O.
#
# Your puzzle input describes all of the possible replacements and, at the bottom, the medicine
# molecule for which you need to calibrate the machine. How many distinct molecules can be created
# after all the different ways you can do one replacement on the medicine molecule?
#
# --- Part Two ---
#
# Now that the machine is calibrated, you're ready to begin molecule fabrication.
#
# Molecule fabrication always begins with just a single electron, e, and applying replacements one
# at a time, just like the ones during calibration.
#
# For example, suppose you have the following replacements:
#
# e => H
# e => O
# H => HO
# H => OH
# O => HH
# If you'd like to make HOH, you start with e, and then make the following replacements:
#
# e => O to get O
# O => HH to get HH
# H => OH (on the second H) to get HOH
# So, you could make HOH after 3 steps. Santa's favorite molecule, HOHOHO, can be made in 6 steps.
#
# How long will it take to make the medicine? Given the available replacements and the medicine
# molecule in your puzzle input, what is the fewest number of steps to go from e to the medicine
# molecule?
#

require_relative 'input'
day = /day(\d+)\.rb/.match(__FILE__)[1].to_i
input = <<-EOF
e => H
e => O
H => HO
H => OH
O => HH

HOHOHO
EOF
input = Input.for_day(day)

lines = input.each_line.map(&:chomp)
medicine = lines.pop
lines.pop

# expected = 7
# fail unless "HOHOHO" == medicine

require 'set'

# step = Set.new
# step << 'e'
# molecules = [step]
molecules = Set.new

class Rule
  include Comparable

  def initialize(description)
    @from, @to = description.split(/ *=> */)
    @from_len = @from.scan(/[A-Z][a-z]?/).size
    @to_len = @to.scan(/[A-Z][a-z]?/).size
  end

  def molecules(medicine, steps=1)
    medicine.gsub(@from) do |m|
      yield "#{$`}#{@to}#{$'}"
    end
  end

  def can_undo?(compound)
    compound.include?(@to)
  end

  def undo(compound)
    compound.sub @to, @from
  end

  def priors(medicine)
    medicine.gsub(@to) do |m|
      yield "#{$`}#{@from}#{$'}"
    end
  end

  def <=>(other)
    other.to_len <=> @to_len
  end

  def to_len
    @to_len
  end
end

rules = lines.map {|line| Rule.new(line) }

# loop do
#   partials = molecules.last
#   step = Set.new
#   partials.each do |partial|
rules.each do |rule|
  # puts rule.inspect
  rule.molecules(medicine) do |molecule|
    molecules << molecule
  end
end
#   end
#   break if step.include?(medicine)
#   molecules << step
#   print " #{molecules.size}\r"
# end

puts medicine

puts "Calibration: #{molecules.size}"

# Star 2 - Smart -- Under 300ms (aka, WIN!)
compound = medicine.dup
steps = 0
until compound == 'e'
  rules.sort_by(&:to_len).reverse.each do |rule|
    if rule.can_undo? compound
      while rule.can_undo? compound
        compound = rule.undo(compound)
        steps += 1
      end
      break
    end
  end
end

puts "Medicine can be made in #{steps} steps"

exit
# star 2 - brute force (aka, FAIL!)
# in 10 hours, this was working on the BFS for step 5
# (psst, the answer was 212)
compounds = [Set.new([medicine])]
loop do
  targets = compounds.last
  priors = Set.new
  targets.each do |target|
    rules.each do |rule|
      rule.priors(target) do |prior|
        priors << prior
      end
    end
  end
  break if priors.include?('e')
  puts "#{compounds.size}: #{priors.size} prior inputs"
  compounds << priors
end

puts "Medicine can be made in #{compounds.size} steps"
