Advent of Code 2023 Day 8

Mix.install([
  {:kino_aoc, "~> 0.1.5"}
])

Prep

{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2023", "8", System.fetch_env!("LB_AOC_SESSION"))

IO.puts(puzzle_input)

[instructions, "" | paths] = String.split(puzzle_input, "\n")

instructions =
  for <<instruction <- instructions>> do
    case instruction do
      ?L -> 0
      ?R -> 1
    end
  end

map =
  paths
  |> Map.new(fn <<from::binary-3, " = (", left::binary-3, ", ", right::binary-3, ")">> ->
    {from, {left, right}}
  end)

instructions_stream = Stream.cycle(instructions)

Part 1

instructions_stream
|> Enum.reduce_while({"AAA", 0}, fn instruction, {curr, steps} ->
  if curr == "ZZZ" do
    {:halt, {curr, steps}}
  else
    {:cont, {elem(map[curr], instruction), steps + 1}}
  end
end)
|> elem(1)

Part 2

ghost_initial_positions = map |> Map.keys() |> Enum.filter(&String.ends_with?(&1, "A"))

steps =
  ghost_initial_positions
  |> Task.async_stream(
    fn ghost ->
      instructions_stream
      |> Enum.reduce_while({ghost, 0}, fn instruction, {curr, steps} ->
        if String.ends_with?(curr, "Z") do
          {:halt, {curr, steps}}
        else
          {:cont, {elem(map[curr], instruction), steps + 1}}
        end
      end)
      |> elem(1)
    end,
    ordered: false
  )
  |> Enum.map(&elem(&1, 1))

gcd = fn
  a, b, recur when a < b ->
    recur.(b, a, recur)

  a, b, recur ->
    case rem(a, b) do
      0 -> b
      r -> recur.(b, r, recur)
    end
end

lcm = fn a, b ->
  div(a * b, gcd.(a, b, gcd))
end

steps |> Enum.reduce(lcm)

Verify that each ghost can goes back to its original position

tmp =
  for ghost <- ghost_initial_positions do
    instructions_stream
    |> Enum.reduce_while({ghost, 0, []}, fn instruction, {curr, steps, zettas} ->
      if String.ends_with?(curr, "Z") do
        if length(zettas) > 1 do
          {:halt, {curr, steps, [{curr, steps} | zettas]}}
        else
          {:cont, {elem(map[curr], instruction), steps + 1, [{curr, steps} | zettas]}}
        end
      else
        {:cont, {elem(map[curr], instruction), steps + 1, zettas}}
      end
    end)
    |> then(&{ghost, elem(&1, 2)})
  end
  |> Map.new()

l = length(instructions)

tmp
|> Map.values()
|> List.flatten()
|> Enum.all?(fn {_, v} ->
  rem(v, l) == 0
end)