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
