I tried letting it run for 5 minutes in part 2 hoping it would work out. It didn’t lol.

Turns out elixir already has gcd in the stdlib: Integer — Elixir v1.20.2. Then the LCM simply becomes div(x * y, Integer.gcd(x, y))

https://github.com/shritesh/advent/blob/main/2023/08.livemd

import AOC
import Math

aoc 2023, 8 do
  def p1(input) do
    {instructions, map} = parse(input)
    traverse("AAA", map, 0, instructions, instructions, &(&1 == "ZZZ"))
  end

  def extract(s) do
    <<key::binary-size(3), " = (", left::binary-size(3), ", ", right::binary-size(3), ")">> = s
    {key, {left, right}}
  end

  def traverse(key, map, n, [], path, finished?), do: traverse(key, map, n, path, path, finished?)
  def traverse(key, map, n, [move | moves], path, finished?) do
    if finished?.(key) do
      n
    else
      {left, right} = map[key]
      case move do
        "L" -> traverse(left, map, n+1, moves, path, finished?)
        _ -> traverse(right, map, n+1, moves, path, finished?)
      end
    end
  end

  def parse(input) do
    [instructions_str, map_str] = input |> String.split("\n\n")
    {instructions_str |> String.split("", trim: true),
     map_str |> String.split("\n") |> Enum.map(&extract/1) |> Map.new}
  end

  def p2(input) do
    {moves, map} = parse(input)
    map
    |> Map.keys()
    |> Enum.filter(&String.ends_with?(&1, "A"))
    |> Enum.map(fn start -> traverse(start, map, 0, moves, moves, &String.ends_with?(&1, "Z")) end)
    |> Enum.reduce(1, &lcm/2)
  end
end

I suspected that was the case, but burned by previous AoC puzzles by making assumptions not explicitly stated in the problem descriptions, I now try to avoid simplifying my code based on assumptions. For this puzzle, I tested all possible end positions for each start positions.

My solution:

https://github.com/bjorng/advent-of-code-2023/blob/main/day08/lib/day08.ex