Advent of Code 2023 - Day 8

Learning Questions & Discussions Coding Challenges
,
21

Still haven’t done the “convert to cycle notation” part, but the transformation to a permutation works (at least for my input):

defmodule Day8Part2 do
  def read(filename) do
    [path | map] =
      filename
      |> File.read!()
      |> String.split("\n", trim: true)

    {parse_path(path), parse_map(map)}
  end

  defp parse_path(path) do
    path
    |> String.split("", trim: true)
    # |> Stream.cycle()
  end

  @regex ~r/([A-Z]{3})\s+=\s+\(([A-Z]{3}),\s+([A-Z]{3})/

  defp parse_map(map) do
    map
    |> Enum.map(&Regex.run(@regex, &1, capture: :all_but_first))
    |> Map.new(fn [x, l, r] -> {x, %{"L" => l, "R" => r}} end)
  end

  def step(direction, from, map) do
    map[from][direction]
  end

  def start?(point) do
    String.ends_with?(point, "A")
  end

  def done?(point) do
    String.ends_with?(point, "Z")
  end

  def perm_multiply(p1, p2) do
    Map.new(p1, fn {k, v} -> {k, p2[v]} end)
  end

  def perm_power(p, n) when rem(n, 2) == 0 do
    perm_power(perm_multiply(p, p), div(n, 2))
  end

  def perm_power(p, 1), do: p

  def perm_power(p, n) when n > 0 do
    perm_multiply(p, perm_power(p, n-1))
  end
end

{path, map} = Day8Part2.read("input.txt")

step = fn dir, froms ->
  Enum.map(froms, &Day8Part2.step(dir, &1, map))
end

starts = Map.keys(map)

one_cycle = Enum.reduce(path, starts, step)

permutation =
  starts
  |> Enum.zip(one_cycle)
  |> Map.new()

product =
  Day8Part2.perm_power(permutation, LARGE_NUMBER_WITH_SIX_FACTORS)

product
|> Map.filter(fn {k, _} -> Day8Part2.start?(k) end)
|> IO.inspect()

The exponent passed to perm_power is the answer for part 2 divided by the length of the move sequence. For my input, this prints:

%{
  "AAA" => "ZZZ",
  "DTA" => "FQZ",
  "JHA" => "TBZ",
  "MMA" => "QDZ",
  "NCA" => "LQZ",
  "TVA" => "FNZ"
}

which is where the ghosts ended up at the end of the many trillions of steps!

Another interesting fact: using a smaller exponent with only some of the factors from the final answer will give the position of the ghosts when only some of them were at points ending in “Z”:

%{
  "AAA" => "KGP",
  "DTA" => "FQZ",   # <===
  "JHA" => "KXQ",
  "MMA" => "CVC",
  "NCA" => "LQZ",   # <===
  "TVA" => "FBH"
}
1 Like