Advent of Code 2023 - Day 8

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 did the same thing. Here’s my impl of lcm/2 as an anonymous function:

gcd = fn
  a, b, recur when a < b -> recur.(b, a, recur)
  a, b, _recur when rem(a, b) == 0 -> b
  a, b, recur -> recur.(b, rem(a, b), recur)
end

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

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

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

Good to know. Thanks.

I did my validation of the input, too.

image1200×755 53.3 KB

And all the numbers in the return value are a multiple of the length of the L/R instructions.

Day 08

Setup

defmodule Day08 do
  def find_path(instructions, pos, map) do
    Enum.reduce_while(instructions, pos, fn
      {_, idx}, <<_, _, ?Z>> -> {:halt, idx}
      {step, _}, pos -> {:cont, elem(Map.fetch!(map, pos), step)}
    end)
  end
end

[instructions | rest] =
  String.split(puzzle_input, "\n", trim: true)

instructions =
  Stream.cycle(for <<c <- instructions>>, do: if(c == ?L, do: 0, else: 1))
  |> Stream.with_index()

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

Part 1

Day08.find_path(instructions, "AAA", map)

Part 2

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

Task.async_stream(starts, &Day08.find_path(instructions, &1, map), ordered: false)
|> Enum.reduce(1, fn {:ok, a}, b ->
  div(a * b, Integer.gcd(a, b))
end)

Ok so I cheated. I had absolutely no idea hwo to tackle part 2 (except letting it run for ever) so I came here and just saw LCM so I went back to check with some code that indeed each ending position cycles.

What I did understand in the problem description is that LR is equivalent to LRLRLRLR..., but I did not get that the Z position will be found at exactly N repetitions of the moves. So I assumed that, when reaching a Z, you may be left with remaining moves of the moves list, cancelling many possibilities of solving the problem with maths.

So, not posting my solution as it will be mostly the same.

I used Wolfram to solve the LCM, but then went back and implemented it myself: advent-of-code-2023/notebooks/day08.livemd at main · midouest/advent-of-code-2023 · GitHub

I was on my way to find an already implemented LCM function on Elixir to solve the second challenge of Day 8 of AoC and Google led me directly to this topic!

I think my solution does not bring anything new to what was already discussed here, but I will share it here anyway

defmodule AdventOfCode.DayEight do
  @moduledoc """
  Implements solutions for the first and second star
  of `DayEight` for AoC '23.
  """
  @type network :: %{String.t() => %{left: String.t(), right: String.t()}}

  @spec first_star(String.t()) :: non_neg_integer()
  def first_star(path) do
    {:ok, file} = File.read(path)
    [path_str, map_str] = String.split(file, "\n\n")
    path = get_path(path_str)
    map = get_network_map(map_str)
    traverse_network(map, path, "AAA")
  end

  @spec second_star(String.t()) :: non_neg_integer()
  def second_star(path) do
    {:ok, file} = File.read(path)
    [path_str, map_str] = String.split(file, "\n\n")
    path = get_path(path_str)
    map = get_network_map(map_str)

    Map.keys(map)
    |> Enum.filter(&String.ends_with?(&1, "A"))
    |> Enum.map(fn start -> Task.async(fn -> traverse_network(map, path, start) end) end)
    |> Task.await_many()
    |> lcm()
  end

  @spec traverse_network(network(), Stream.t(), String.t()) :: non_neg_integer()
  defp traverse_network(map, path, start),
    do:
      Enum.reduce_while(path, {start, 0}, fn
        _, {<<_, _, ?Z>>, steps} -> {:halt, steps}
        direction, {node, steps} -> {:cont, {map[node][direction], steps + 1}}
      end)

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

  defp lcm(list) do
    Enum.reduce(list, &lcm(&2, &1))
  end

  @spec get_path(String.t()) :: Stream.t()
  defp get_path(str),
    do:
      str
      |> String.graphemes()
      |> Enum.map(fn
        "R" -> :right
        "L" -> :left
      end)
      |> Stream.cycle()

  @spec get_network_map(String.t()) :: network()
  defp get_network_map(str),
    do:
      str
      |> String.split("\n", trim: true)
      |> Enum.map(&(Regex.scan(~r/[0-9A-Z]{3}/, &1) |> List.flatten()))
      |> Map.new(fn [node, left, right] -> {node, %{left: left, right: right}} end)
end

My solutions to the other challenges.