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.15.7. Then the LCM simply becomes div(x * y, Integer.gcd(x, y))

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:

FYI, each of the ghosts has only one possible position that ends with a "Z" on its path.

Edit: I was thinking about this and this post might not be true because entry node could leave the terminal node in different ways (by being on different steps and exiting either left or right). I thought about removing this post, but maybe someone will find interesting. Skip past if you don’t like sort-of-wrong explanations of things.

A bit of graph theory, if folks are interested: the instructions induce a set of disjoint cyclic graphs (in non-graph theory speak the entry “room”, its exit, and all of the rooms in between form a ring). So, each entry node (read, node that ends in A) belongs to some cycle that also contains a terminating node (read, node that ends in a Z). Otherwise the problem wouldn’t be solvable.

What may not be obvious, is if any cycle contains more than one terminating node (if any room could reach multiple exits) it must also contain an additional entry node. That is, if any entry node could reach more than one terminating node then there exists at least one other entry node that can also reach both.

If such a cycle existed (one that contains two terminating nodes), the only way this problem would be solvable is if both entry nodes reach their corresponding terminus in the same number of steps.

Visually, this a graph like this would never be solvable:

DAY8501×483 23.3 KB

Reading the discussion makes me think I just got lucky making an assumption about the paths cycling. I think the assumption must hold that all paths will cycle IF every starting node actually can reach a finishing node AND every finishing node can be reached by a starting node. As long as that is true the LCM approach should be valid, I think. Can anyone think of a counter example where the cycle of the instructions and the length of at least one path from start to finish are such you could endlessly cycle with out ever repeating?

Here’s my code:

  defmodule Parser do
    import NimbleParsec

    instructions = times(choice([ascii_char([?L]), ascii_char([?R])]), min: 1) |> wrap()

    node = times(ascii_char([?A..?Z]), 3) |> wrap()

    parent = node |> ignore(string(" = "))

    children =
      ignore(string("("))
      |> concat(node)
      |> ignore(string(", "))
      |> concat(node)
      |> ignore(string(")\n"))

    tree =
      ignore(string("\n\n"))
      |> times(parent |> concat(children) |> wrap(), min: 1)

    defparsec(:parser, instructions |> concat(tree))
  end

# it was probably overkill to use NimbleParsec on this input, but I'm trying to get more comfortable with it. Starting to feel a little more intuitive.

defmodule Day8 do
  @moduledoc """
  Day8 AoC Solutions
  """

  alias AocToolbox.Input

  def input(:test),
    do: """
    RL

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

  def input(:test2),
    do: """
    LLR

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

  def input(:test3),
    do: """
    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)
    """

  def input(:real), do: Input.load(__DIR__ <> "/input.txt")

  def solve(1, mode) do
    __MODULE__.Part1.solve(input(mode))
  end

  def solve(2, mode) do
    __MODULE__.Part2.solve(input(mode))
  end

  defmodule Part1 do
    def solve(input) do
      input
      |> parse()
      |> build_tree()
      |> traverse_instructions()
    end

    def parse(input) do
      input
      |> Input.Parser.parser()
      |> elem(1)
    end

    defp build_tree([instructions | tree]) do
      graph =
        tree
        |> Enum.reduce(%{}, fn [p, l, r], acc ->
          Map.put(acc, p, %{~c"L" => l, ~c"R" => r})
        end)

      {instructions, graph}
    end

    defp traverse_instructions({instructions, tree}) do
      instructions
      |> Stream.cycle()
      |> Enum.reduce_while({~c"AAA", 0}, fn direction, {key, steps} ->
        if key == ~c"ZZZ" do
          {:halt, steps}
        else
          {:cont, {tree[key][[direction]], steps + 1}}
        end
      end)
    end
  end

  defmodule Part2 do
    def solve(input) do
      input
      |> parse()
      |> build_tree()
      |> traverse_all_starting_nodes()
      |> Enum.reduce(&AocToolbox.Math.lcm(&1, &2))
    end

    defp parse(input) do
      Part1.parse(input)
    end

    defp build_tree([instructions | tree]) do
      {instructions,
       tree
       |> Enum.reduce({%{}, MapSet.new()}, fn
         [[_, _, ?A] = p, l, r], {graph, starters} ->
           {Map.put(graph, p, %{~c"L" => l, ~c"R" => r}), MapSet.put(starters, p)}

         [p, l, r], {graph, starters} ->
           {Map.put(graph, p, %{~c"L" => l, ~c"R" => r}), starters}
       end)}
    end

    defp traverse_all_starting_nodes({instructions, {tree, starters}}) do
      starters
      |> Task.async_stream(fn starter ->
        instructions
        |> Stream.cycle()
        |> Enum.reduce_while({starter, 0}, fn direction, {key, steps} ->
          if match?([_, _, ?Z], key) do
            {:halt, steps}
          else
            {:cont, {tree[key][[direction]], steps + 1}}
          end
        end)
      end)
      |> Enum.map(&elem(&1, 1))
    end
  end
end