Day 19: Medicine for Rudolph

Section

defmodule P1 do
  def parse(input) do
    lines = String.split(input, "\n", trim: true)

    replacement_map =
      Enum.reduce(lines, %{}, fn line, acc ->
        if String.contains?(line, "=>") do
          [from, to] = String.split(line, " => ")
          Map.update(acc, from, [to], &[to | &1])
        else
          acc
        end
      end)

    medicine_string = List.last(lines)
    {replacement_map, medicine_string}
  end

  def replace_all(medicine_string, replacement_map) do
    Enum.reduce(replacement_map, MapSet.new(), fn {from, tos}, acc ->
      Enum.reduce(tos, acc, fn to, acc_inner ->
        apply_replacements(medicine_string, from, to, acc_inner)
      end)
    end)
  end

  defp apply_replacements(medicine_string, from, to, acc) do
    Regex.scan(~r/#{from}/, medicine_string, return: :index)
    |> Enum.reduce(acc, fn [{start, length}], acc_inner ->
      {prefix, rest} = String.split_at(medicine_string, start)
      {_match, suffix} = String.split_at(rest, length)
      new_medicine = prefix <> to <> suffix
      MapSet.put(acc_inner, new_medicine)
    end)
  end

  def expand_to_target(replacement_map, target) do
    bfs([{"e", 0}], replacement_map, target, MapSet.new(["e"]))
  end

  # If no solution is found
  defp bfs([], _replacement_map, _target, _visited), do: -1

  defp bfs([{current, steps} | rest], replacement_map, target, visited) do
    if current == target do
      steps
    else
      next_states = generate_next_states(current, replacement_map, visited, steps)
      bfs(rest ++ next_states, replacement_map, target, visited)
    end
  end

  defp generate_next_states(molecule, replacement_map, visited, steps) do
    Enum.reduce(replacement_map, [], fn {from, tos}, acc ->
      Enum.reduce(tos, acc, fn to, acc_inner ->
        apply_replacements(molecule, from, to, visited, steps, acc_inner)
      end)
    end)
  end

  defp apply_replacements(molecule, from, to, visited, steps, acc) do
    Regex.scan(~r/#{from}/, molecule, return: :index)
    |> Enum.reduce(acc, fn [{start, length}], acc_inner ->
      {prefix, rest} = String.split_at(molecule, start)
      {_match, suffix} = String.split_at(rest, length)
      new_molecule = prefix <> to <> suffix

      if MapSet.member?(visited, new_molecule) do
        acc_inner
      else
        [{new_molecule, steps + 1} | acc_inner]
      end
    end)
  end
end

{map, target} =
  "/Users/eli/Desktop/input.txt"
  |> File.read!()
  |> P1.parse()

P1.replace_all(target, map)
|> Enum.count()

576

defmodule P2 do
  def create_reverse_map(replacement_map) do
    Enum.reduce(replacement_map, %{}, fn {from, tos}, acc ->
      Enum.reduce(tos, acc, fn to, acc_inner ->
        Map.update(acc_inner, to, [from], &[from | &1])
      end)
    end)
  end

  def reduce_to_e(target, reverse_map) do
    dfs(target, reverse_map, 0, %MapSet{})
  end

  defp dfs("e", _reverse_map, steps, _visited) do
    {:ok, steps}
  end

  defp dfs(target, reverse_map, steps, visited) do
    if MapSet.member?(visited, target) do
      {:error, :cycle_detected}
    else
      visited = MapSet.put(visited, target)

      case reduce_xrnyar(target, reverse_map, steps, visited) do
        {:ok, new_target, new_steps} -> dfs(new_target, reverse_map, new_steps, visited)
        :error -> reduce_greedily(target, reverse_map, steps, visited)
      end
    end
  end

  defp reduce_xrnyar(target, reverse_map, steps, visited) do
    regex = ~r/(\w+)(Rn)(\w+)(Ar)/

    case Regex.run(regex, target, capture: :all_but_first) do
      [_x, "Rn", y, "Ar"] ->
        reduced_y =
          Enum.reduce_while(reverse_map, y, fn {from, [to | _]}, acc ->
            if String.contains?(acc, from) do
              {:halt, String.replace(acc, from, to, global: false)}
            else
              {:cont, acc}
            end
          end)

        if reduced_y == y do
          :error
        else
          new_target = String.replace(target, y, reduced_y)

          case reduce_greedily(new_target, reverse_map, steps + 1, visited) do
            {:ok, final_target, final_steps} -> {:ok, final_target, final_steps}
            _ -> :error
          end
        end

      _ ->
        :error
    end
  end

  defp reduce_greedily(target, reverse_map, steps, visited) do
    Enum.find_value(reverse_map, {:error, :no_reduction}, fn {from, [to | _]} ->
      if String.contains?(target, from) do
        new_target = String.replace(target, from, to, global: false)

        case dfs(new_target, reverse_map, steps + 1, visited) do
          {:ok, _} = result -> result
          _ -> nil
        end
      else
        nil
      end
    end)
  end
end

reverse_map = P2.create_reverse_map(map)
P2.reduce_to_e(target, reverse_map)

{:ok, 207}