# Advent of Code 2023 - Day 8

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
[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
[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)
|> 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
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