day-8.livemd

Day 8: Haunted Wasteland

Part one

sample_input =
  """
  RL

  AAA = (BBB, CCC)
  BBB = (DDD, EEE)
  CCC = (ZZZ, GGG)
  DDD = (DDD, DDD)
  EEE = (EEE, EEE)
  GGG = (GGG, GGG)
  ZZZ = (ZZZ, ZZZ)
  """

sample_input_2 =
  """
  LLR

  AAA = (BBB, BBB)
  BBB = (AAA, ZZZ)
  ZZZ = (ZZZ, ZZZ)
  """

defmodule HauntedWasteland do
  def steps_to_reach_zzz(maps) do
    {tree, instructions} = parse_input(maps)
    path_to_exit(tree, instructions)
  end

  def steps_to_reach_ghost_z(maps) do
    {tree, instructions} = parse_input(maps)
    path_to_exit_with_ghosts(tree, instructions)
  end

  defp parse_input(maps) do
    [instructions, tree_spec] = String.split(maps, "\n\n", trim: true)
    instructions = String.split(instructions, "", trim: true)
    tree = to_tree(tree_spec)
    {tree, instructions}
  end

  defp to_tree(spec) do
    spec
    |> String.split("\n", trim: true)
    |> Enum.map(fn <<src::binary-3, " = (", left::binary-3, ", ", right::binary-3, ")">> ->
      {src, %{"L" => left, "R" => right}}
    end)
    |> Enum.into(%{})
  end

  defp path_to_exit(tree, instructions),
    do: path_to_exit(tree, instructions, "AAA", 0, &(&1 == "ZZZ"))

  defp path_to_exit_with_ghosts(tree, instructions) do
    tree
    |> Map.keys()
    |> Enum.filter(&match?(<<_::binary-2, "A">>, &1))
    |> Enum.map(fn start_node ->
      path_to_exit(tree, instructions, start_node, 0, &match?(<<_::binary-2, "Z">>, &1))
    end)
    |> lcm()
  end

  defp path_to_exit(tree, [first | rest] = _instructions, node, steps, stop_cond) do
    next_node = tree[node][first]

    if stop_cond.(next_node) do
      steps + 1
    else
      next_instructions = rest ++ [first]
      path_to_exit(tree, next_instructions, next_node, steps + 1, stop_cond)
    end
  end

  defp lcm([a]), do: a

  defp lcm([a, b | rest]), do: lcm([lcm(a, b) | rest])

  defp lcm(a, b), do: (a * b) |> div(Integer.gcd(a, b))
end

HauntedWasteland.steps_to_reach_zzz(sample_input)
# expected 2

HauntedWasteland.steps_to_reach_zzz(sample_input_2)
# expected 6

Path.join(__DIR__, "day-8.input")
|> File.read!()
|> HauntedWasteland.steps_to_reach_zzz()

# 12169

Part two

sample_input_part_two =
  """
  LR

  11A = (11B, XXX)
  11B = (XXX, 11Z)
  11Z = (11B, XXX)
  22A = (22B, XXX)
  22B = (22C, 22C)
  22C = (22Z, 22Z)
  22Z = (22B, 22B)
  XXX = (XXX, XXX)
  """

HauntedWasteland.steps_to_reach_ghost_z(sample_input_part_two)
# expected 6

Path.join(__DIR__, "day-8.input")
|> File.read!()
|> HauntedWasteland.steps_to_reach_ghost_z()

# 12030780859469