The second part of today’s puzzle is very misleading.
FYI, each of the ghosts has only one possible position that ends with a "Z" on its path.
3 Likes
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
3 Likes
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
2 Likes
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))
4 Likes
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:
3 Likes
Good to know. Thanks.
I did my validation of the input, too.
And all the numbers in the return value are a multiple of the length of the L/R instructions.
2 Likes
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)
2 Likes
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.
1 Like
I used Wolfram to solve the LCM, but then went back and implemented it myself: https://github.com/midouest/advent-of-code-2023/blob/main/notebooks/day08.livemd
1 Like
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.
2 Likes
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:
3 Likes
Someone on Reddit plotted the paths of the ghosts.
https://svgshare.com/i/10YN.svg
The red nodes are the starting positions, and the green ones are the nodes ending with a Z.
1 Like
Wow, I love this - thanks for sharing. I didn’t think about generating these visualizations. I think what captivates me now is whether or not it’s possible for a given solvable input to produce a graph such as this where a Z-node is included in more than one of these graphs. In my earlier post I was sure it wasn’t, but the more I thought about it I’m not so sure. Hopefully trying to answer this question doesn’t eat away from AoC solving time!
Edit Do you happen to have link to the post? I might want to play around with this and if they shared the code for making this vis. that would make life easier.
1 Like
For me it was not obvious that ghosts converge into cyclic paths so I went with brute force with some optimizations.
1 Like
My beginner’s solution, Day 8 part 1
defmodule Day08 do
def part1(input) do
[directions, nodes, start, finish] = parse(input)
# [[:L, :L, :R], [{1, 1}, {0, 2}, {2, 2}], 0, 2]
cycle(directions, nodes, start, finish)
end
def step(directions, nodes, position, finish, count)
def step([:L | d], n, p, f, c), do: step(d, n, elem(elem(n,p), 0), f, c+1)
def step([:R | d], n, p, f, c), do: step(d, n, elem(elem(n,p), 1), f, c+1)
def step(_d, _n, p, f, c) when p == f, do: {c}
def step([], _n, p, _f, c), do: {p, c}
def cycle(d, n, p, f, c \\ 0) do
case step(d, n, p, f, c) do
{count} -> count
{position, count} -> cycle(d, n, position, f, count)
end
end
def parse(raw_document) do
[raw_directions,
raw_nodes] = String.split(raw_document, "\n\n")
directions = raw_directions
|> String.graphemes
|> Enum.map(&(case &1 do "L" -> :L; "R" -> :R end))
split_nodes = raw_nodes
|> String.replace([" = (", ", ", ")"], " ")
|> String.split("\n")
|> Enum.map(&String.split/1)
start = Enum.find_index(split_nodes, &(List.first(&1) == "AAA"))
finish = Enum.find_index(split_nodes, &(List.first(&1) == "ZZZ"))
nodes = for [_node, left, right] <- split_nodes do
left = Enum.find_index(split_nodes, &(List.first(&1) == left))
right = Enum.find_index(split_nodes, &(List.first(&1) == right))
{left, right}
end |> List.to_tuple
[directions, nodes, start, finish]
end
end
2 Likes
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
3 Likes
I guess that’s impossible. If there’s a loop in the path, then starting from the ghost enters the loop, after at most lcm(instruction_length, loop_circumfrerence_length), the ghost will go back to its starting point in the loop.
3 Likes
I’ve had this in draft and haven’t finished writing all I wanted to, day 10 sucked away most of my time from giving this the full attention I wanted to. The short answer is it’s not possible.
The longer answer is that it is sort of possible, but maybe not as interesting as one might hope. One could create a solvable puzzle input s.t. one of the ghosts path gets stuck in a loop that doesn’t include the room Z*. To do this, you need only make sure that the number of steps from the ghost start room to its Z is divisible by the lengths of the other paths. E.g., if the other ghosts reach their Z rooms, in say, 2, 3, and 5 steps you could create such a path that took the ghost 30 steps to reach its Z room, then after that got stuck in a loop and never returned to Z. This path doesn’t repeat Z ever, but is still solvable because the other paths repeat.
*this isn’t exactly what you asked, you can’t have a path go on endlessly without ever repeating, because endless implies infinite steps and as you know the number of rooms is finite, so you must repeat at some point.
Edit: as I mentioned above, I didn’t get to write the full post I was originally planning on writing. There are some other interesting things in this puzzle I didn’t first notice. We all know that the answer to pt 2 is the lcm of all of the ghosts paths, but did you also know that each of the ghosts answers is divisible by the length of the instructions? This isn’t technically a requirement to make the puzzle solvable (the example input for pt 2 does not have this property), but something interesting I noticed.
2 Likes
I suspect this is an artifact of the problem-generation process, but it has an interesting consequence: applying the whole sequence of moves to every starting point creates a permutation of the points.
That turns “apply the whole sequence of moves N times” into “apply a single permutation N times”, and then fundamental mathematical properties tell us that permutation has multiple disjoint cycles.
Going to try applying one of the “write a permutation in cycle notation” algorithms for part 2 - I suspect the sizes of the cycles will be very familiar.
2 Likes
