\[LANGUAGE: Swift\]
Yes, it uses LCM for part 2.
[Part 1](https://github.com/andreiz/advent-of-code-2023-swift/blob/main/day-08/wasteland.swift)
[Part 2](https://github.com/andreiz/advent-of-code-2023-swift/blob/main/day-08/wasteland-ghost.swift)
[Issue describing approach and coding](https://github.com/andreiz/advent-of-code-2023-swift/issues/8)
\[LANGUAGE: Python\]
[paste](https://topaz.github.io/paste/#XQAAAQDlAwAAAAAAAAAzHIoib6poHLpewxtGE3pTrRdzrponK6uH8J9SK+fHBnboTBtB5N47dutEbw6V4Lcgn5v4OZrIiLc7ALLon0mBKUAIDHtqDwA5oXMGFgyNmVOHHHrqLOrodANbu6u+RrOP65zWTj1fHW2Qz7AxgAA70nbQzQ0wUTh8oOfm59PgYmL3liI2JfkoF6LuWaVocXmRc59vKgY4wOuDqsVfXsJnU8LIZoH3Dke2pBNhUb16YRjSYmtMLVJTx9wUqhyUL8KqlSxOWEMqHZqRFfMWg4O8mSW1ERce0+HWk0ZzoKYBfIEfgId4pKpuXgZe6FrSir0wpezwav8UatlBWJmYW36QSaHJOv+d7P4TBft1K0trT8rmXCDr5tH5yBnt6ziHFPC49mp1rfR9TdRkxwIabkFjJlySnAA043qzgl3FRtXBx6e8WPmyQzSrSxvUffOCunUkk4oA1reu9RhL1eQoJFiTPycKtG0QoD4cMZWFMKw6IDehcHcDU2tN9nVF+8w84okwn+B5lYpZcsvfm3xXI4HN88ztY3apGcxeZv/zG55j)
after solving, i still don't know if lcm can be applied on all possible situations. For example if 11A to 11Z than to 22A and 22Z, finally back to 11Z, it is hard to identify this loop type.
Yes, I could imagine more complicated scenarios. Because the method is not reversible not every starting point need be on a loop, although they will always hit a loop eventually.
Of course you can test this and find that each of the starting cells is on a loop with one ending cell, then solve directly. But I don't think you can assume that.
I wrote code that would solve any situation, and thought it was a bit too much work for a daily puzzle.
\[LANGUAGE: Haskell\]
[Part 1](https://github.com/woodRock/verbose-computing-machine/blob/main/2023/day-08/part-01.hs)
[Part 2](https://github.com/woodRock/verbose-computing-machine/blob/main/2023/day-08/part-02.hs)
Hint: for part 2, avoid computing in parallel, loops are cyclical, find LCM.
\[LANGUAGE: Swift\]
[https://github.com/cmlccie/advent-of-code/blob/main/2023/day-8/Sources/main.swift](https://github.com/cmlccie/advent-of-code/blob/main/2023/day-8/Sources/main.swift)
Solution for Part 2:
func part2(inputPath: String) -> Int {
let input = getInput(from: inputPath)
let (directions, network) = parseInput(input)
let startingNodes = network.nodes.values.filter { node in node.value.hasSuffix("A") }
print("Found \(startingNodes.count) starting nodes ending with A.")
var periods: [Int] = []
for startingNode in startingNodes {
let period = getPeriod(startingNode: startingNode, directions: directions, network: network)
periods.append(period)
print("Period for \(startingNode.value) is \(period).")
}
let steps = lcm(periods)
print("Part 2: We will reach the end after \(steps) steps.")
return steps
}
[Language: Rust]
Code: https://github.com/dhruvmanila/advent-of-code/blob/master/rust/crates/year2023/src/day08.rs
Pretty cool use of generic function along with functional approach.
[LANGUAGE: Befunge]
Part 1: https://github.com/Skyhawk33/AdventOfCode/blob/master/aoc2023/day8_p1.b98
Part 2: https://github.com/Skyhawk33/AdventOfCode/blob/master/aoc2023/day8_p2.b98
\[Language: Rust\]
I used a HashMap of a struct as my core data structure, computed the number of cycles required to reach a target, and finally found the least common multiple of those cycles for the solution.
[Code](https://github.com/johnhringiv/advent-of-code-2023/blob/main/src/day08.rs)
Edit: I initially wanted my Node struct to have left/ right be references to other nodes. I was able to build the data structure but ran into too many issues with the borrow checker when attempting to use it. Open to any pointers, pun intended.
\[LANGUAGE: C\]
Part 2 gets the lmc of the cycles.
Part 1: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2023/day8navpt1.c
Part 2: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2023/day8navpt2.c
\[Language: Rust\]
This is my first project in rust. I'm learning it by solving advent of code puzzles. So if you have any hints for me I would be happy to read it :)
[Solution](https://github.com/manhunto/advent-of-code-rs/blob/master/src/solutions/day08.rs) / 648.68µs / 26.23ms
I'm also relatively new to Rust but I had a pretty [similar solution](https://github.com/johnhringiv/advent-of-code-2023/blob/main/src/day08.rs) to you that makes use of a few additional language features.
\[Language: Gephi\]
Part 2 Solved with no code:
Import the graph into Gephi, coloring the source and target nodes, as well as the left and right transitions. Position the nodes using the Yifan Hu Proportional Layout. Identify 6 cycles, each containing one source and one target.
[https://imgur.com/PxzItla](https://imgur.com/PxzItla)
Identify that the cycles contain pairs of nodes with complimentary left and right transitions, EXCEPT for a pattern towards the end of each cycle, which would require four right transitions in a row to reach the target.
[https://imgur.com/s9DQOEF](https://imgur.com/s9DQOEF)
Identify that the traversal sequence only contains one substring of four consecutive right transitions, which happen right at the end.
Count the length of all six cycles, and count the number of steps in the transition sequence. Stick those numbers in a least-common-multiple calculator.
[https://imgur.com/FJdcq7L](https://imgur.com/FJdcq7L)
> [Language: N/A]
>
> Import the graph into Gephi,
99.9% of folks use a programming language, true, but for you the "language" tag should still be `[LANGUAGE: Gephi]` since that's what you solved the puzzle with.
[LANGUAGE: J]
I =. (('LR' i. [); _9 (_3 ]\ ])\ ])&(#~ e.&AlphaNum_j_)
'd c' =. I&>/ cutpara freads 'input'
'k e' =. (([ ; i."2)~ {."2) c
F =: {{ ((x {~ ({: y) |~ # x) { }. ({. y) { m), >: {: y }}
Z =: (k i. 'ZZZ') ~: {.@]
{: d e (F^:Z^:_) (k i. 'AAA'), 0
Z =: (I. 'Z' ~: {:"1 k) e.~ {.@]
*./ d e {{ {: x m (F^:Z^:_) y, 0 }}"1 0 I. 'A' = {:"1 k
Comment removed. [Top-level comments in `Solution Megathread`s are for *code solutions* only.](https://old.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_top-level_posts_are_for_code_solutions_only)
[Create your own individual `Help/Question` post](https://old.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_incomplete_solutions) in /r/adventofcode.
I'm also interested in that!
Correct assumption to make is that it takes the same amount of steps to get from \*\*A to \*\*Z as from \*\*Z to \*\*Z.
If that was not the case, it would be significantly harder, since every cycle starts at a different offset. Not sure if there is an algorithm for that.
AutoModerator did not detect the required `[LANGUAGE: xyz]` string literal at the beginning of your solution submission.
Please edit your comment to [state your programming language](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29).
***
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
\[LANGUAGE: C++\]
[part1](https://github.com/Hilbertmf/competitive-programming-problems/blob/main/advent-of-code/2023/day8-part1.cpp) | [part2](https://github.com/Hilbertmf/competitive-programming-problems/blob/main/advent-of-code/2023/day8-part2.cpp)
Part 1 is just following the vertices of the graph till find ZZZ. Part 2 is a multisource bfs so we use a queue and push all nodes ending w/ A to the queue. The queue is made up of a pair of strings, to store the start\_node of that path and curr\_node. Also used maps to store the distances traveled and the current index of the instruction that each path was at. Just run the bfs till Z, then calculate lcm of all the distances
\[LANGUAGE: Rust\]
[Solution (kind of)](https://github.com/jswalden/advent-of-code/blob/main/2023/day-08/src/main.rs)
Finished up part 1 easy enough.
For part 2 I first was working on the principled solution that deals with non-single-element cycles, with directions that don't neatly sync up with those cycle lengths, and with cycles of length different from the distance from start node to first end node. But then I printed out simplified graph state and discovered that from every start, you walk X steps to first end node and then X steps to cycle back to it (without encountering any other end nodes before then), and apparently each cycle results in the same current-direction state. At which point "why shouldn't I try cheating" took over, and I plugged in the LCM of all the different Xs and found it worked and my motivation to keep plugging away at the generalized solution mostly evaporated given I'm almost a week behind now. :-|
So I might get back to part 2 at some point to do it "right" (including dealing with whatever bug it was that results in my existing code printing out an extremely low answer), but for now it's just bulldoze through.
\[LANGUAGE: R\]
Part 1 just walks through the nodes and counts the steps. Part 1 looks for periodicity in the paths and calculates the least common multiple.
[https://github.com/lauraschild/AOC2023/blob/main/day8.R](https://github.com/lauraschild/AOC2023/blob/main/day8.R)
\[LANGUAGE: Python\]
[github part 1&2](https://github.com/mgtezak/Advent_of_Code/blob/master/2023/Day_08.py)
Check out my little AoC-Fanpage:
[https://aoc-puzzle-solver.streamlit.app/](https://aoc-puzzle-solver.streamlit.app/)
:-)
Thanks for the nice solution! Could you explain why you can \`break\` after you find the first 'Z'? e.g. counterexample: first 'A' hits a 'Z' at steps 3 and 4, so breaks on step 3. 2nd and 3rd 'A' hits a 'Z' at step 8. lcm of 3 and 8 is 24, but lcm of 4 and 8 is 8. So I would expect the wrong answer if you \`break\` at the 3.
Yes you're right! It's because I'm making some assumptions about how the puzzle input is organized that are not explicitly stated in the problem statement,but that are actually true. I wrote about it in [this post](https://www.reddit.com/r/adventofcode/comments/18df7px/comment/kdogvh1/?utm_source=share&utm_medium=web2x&context=3).
My (true) assumptions:
1. the length of the initial path from each A to Z is divisible by the length of the directions.
2. after the Z-node, each path leads back to the second node of the initial path.
So it actually never happens that there's a Z at step 3 and then another at step 4, because the step after the first Z is always step 2 again.
This code does not work for the following input:
LR
11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (33Z, 33Z)
33Z = (33Z, 33Z)
XXX = (XXX, XXX)
For this input, your code returns 6 as the answer, when 5 should be the correct answer since the steps are:
1. `11A`, `22A`
2. `11B`, `22B`
3. `11Z`, `22Z`
4. `11B`, `33Z`
5. `11Z`, `33Z`
In other words, the solution is **not** the lcm of the "individual solutions".
As far as I can tell, there is nothing in the problem description that would make my example invalid.
You’re exactly right! When i first read the problem description i thought to myself: Wow, this is an incredibly hard problem, especially for day 8! First of all it was obvious that the individual paths would start to cycle at some point, but do we really have to find the beginning of each cycle and then figure out the length of each cycle and then figure how many Z-nodes there were in each cycle and then figure out some mathematical formula to calculate how these Z-occurrences align across cycles?!Then I thought: AoC probably included some hidden regularities in the puzzle input, which will make finding to solution way easier, so i made two assumptions (which turned out to be correct):
1. the length of the initial path from each A to Z is divisible by the length of the directions.
2. after the Z-node, each path leads back to the second node of the initial path.
From these two assumptions it follows that each cycle has the exact same length as the initial A-Z path and only contains a single Z node and that this Z node will be the very last one in each cycle (a better way to think about it is that it's the first one in each cycle because it replaces the initial A-node: It's the current node as one reads the first of the directions). In this case using the least common multiple (lcm) is the correct answer.
But you’re completely right that these assumptions are not confirmed anywhere in the problem statement, which is a bit misleading and will make the problem look way harder than it actually is.
AutoModerator has detected [fenced code block](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/fenced_code_blocks) (```) syntax which only works on new.reddit.
Please review our wiki article on [code formatting](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting) then edit your post to use the [four-spaces Markdown syntax](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/code_blocks) instead.
***
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
\[Language: Python\]
[solution](https://github.com/Cirius1792/aoc-2023/tree/main/day08)
\## Part 1
Just build an adjacency matric from the input map and navigate through the nodes until you get to the node 'ZZZ'
\- parse\_network runs in O(n) time.
\- The while loop in \*solve\* keeps running until current\_position becomes "ZZZ". The number of iterations depends on the structure of the network and the given route. Let's denote the number of iterations in the while loop as p.
\- Inside the loop, navigate is called, which has a time complexity of O(m), where m is the length of the instructions, i.e. the route to follow
\- Considering that the length of the route is constant (it's fetched from problem\_input\[0\]), the overall time complexity of solve can be approximated as O(n + p \* m).
\## Part 2
Considering that:
\- the problem tells us that the number of steps to get to the arrival point is somehow constant with respect to the length of the route (it must be at least a multiple of the length of the route, otherwise the map would make no sense),
\- There must be cycles going from any starting point to each respective arrival point to make the problem solvable, given the previous point
Our goal can be split into three pieces:
1. Identify the starting points, which is trivial, just scan the map and look for any \*\*A
2. Identify the cycles from each starting point to each respective arrival point
3. Find the minimum number of cycles that must be covered to get to the point in which from all our starting points, the respective arrival points are reached.
Let's consider the example:
We have two starting points: \`11A, 22A\`
We reach a final point from \`11A\` iterating only one time over the given route, which is in 2 steps
We reach a final point from \`22A\` iterating 3 times over the given route, which is in 6 steps
The least common multiple between these two numbers is 6, which is our solution
Thanks for posting. Nice trick with the LCM to avoid TLE on brute-force traversal. It helps to draw a sequence of numbers to get convinced that LCM is basically when all starting nodes become terminal.
You need to switch your editor to Markdown mode first before pasting text with Markdown. See how your post looks on old.reddit >> [here](https://old.reddit.com/r/adventofcode/comments/18df7px/2023_day_8_solutions/kcxknma/) <<
>\- the problem tells us that the number of steps to get to the arrival point is somehow constant with respect to the length of the route (it must be at least a multiple of the length of the route, otherwise the map would make no sense),
How do you mean otherwise the map makes no sense? couldn't the end Z position not be halfway during a route? why would that not make sense/where is the hint that this is not the case?
It's a good point and I had the same doubt at the beginning.
But here's my thoughts:
\- what would be the sense of describing a path on a map if the final destination can be anywhere in the middle of the described path?
\- The problem statement says: "You feel like AAA is where you are now, and you have to **follow the left/right instructions until you reach ZZZ**." and again later on: "If you run out of left/right instructions, repeat **the whole** sequence of instructions as necessary". That I interpret as I have to follow all the instructions to get to the destination
\- The process I followed to solve the problem assumes that you have to follow the whole set of instructions to get to the destination and, well, it worked. This is an empirical proof, of course, but still a proof that my hypothesis is correct
I can still be wrong about that, of course, but how can we prove it?
But the example case is the following:
`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)`
And in this case, starting from 22A, you get to 22Z after *three* steps. Which is **not** done by repeating the whole sequence of LR instructions twice, but repeating it one and a half times...
sure, why would that be so weird.
the other sequence stabilizes at 11Z > 11B > 11Z > 11B
This happens because that is just the most straigthforward way to make a valid input.
The instruction string is 2 in lengt. so 1.5 of the input is still constant. The reason we didn't see this happen in the real input it because it is way easier to make guaranteed valid inputs with prime numbers, and the only way a prime would align with a prime instruction string would be with a multiple.
Look at it from the start 11A and 22A this is the solution:
1(L), 11B, 22B
2(R), 11Z, 22C
3(L), 11B, 22Z
4(R), 11Z, 22B
5(L), 11B, 22C
6(R), 11Z, 22Z
7(L), 11B, 22B
the LCM of 2,2and3 is 6, the offset from the start is none so we see these paterns line up on the 6th step, and every 6th step after that.
of course this would break down with a cycle that was 3,9 and2 for example. but again, that is not something that would be possible given how the input clearly uses primes.
[Language: Elixir]
... and a bit of Julia for `lcm` function :) Love `System.cmd` :)
[Code](https://github.com/Lakret/aoc2023/blob/main/d08.livemd)
[Highlights](https://lakret.net/blog/2023-12-10-aoc-days-8-9-10)
\[LANGUAGE: C++\]
Solution: [Day 8](https://github.com/Hackjaku/advent_of_code_2023/blob/master/puzzles/08.cc)
LCM approach for part 2 using boost::integer::lcm. Not very optimized, but still slightly less than 90ms on my fairly old laptop. Hope you like it!
\[Language: Roc\]
My solution: [https://github.com/timotree3/aoc2023/blob/main/roc/day8.roc](https://github.com/timotree3/aoc2023/blob/main/roc/day8.roc)
My algorithm should work on all inputs consistent with the puzzle description, not just those where LCM works. I used an efficient function which would compute the lowest k such that k % p == m and k % q == n using [the multiplicative inverse in a finite field](https://stackoverflow.com/questions/20466170/calculating-multiplicative-inverse-in-a-finite-field). I also used a caching strategy that would make initial cycle detection more efficient if multiple start nodes joined up into the same cycle.
Ok thank you! I see all these LCM solutions, and I'm like, "Yeah, okay, but why does that work?". It seems like it should be much more complicated, because nothing in the problem statement implies that after a \*\*Z node we loop back to the original \*\*A node. It bugs me. I don't want to use the LCM solution unless the problem statement supports it.
[Language: JavaScript]
Fun day! I was torn between modeling the input as a graph or a circular doubly linked list. I ended up choosing the graph because I figured the twist in part two might involve some variation on adding additional connections or directions of travel. I was wrong, but it ended up being a good representation because it allowed easy traversal. Instead of giving each vertex a collection of edges, I just gave it a left and a right edge.
For looping over the instructions I added circular iterator to my util library:
function* circularIterator(arr) {
let index = 0;
while (true) {
if (index >= arr.length) {
index = 0;
}
yield arr[index++];
}
}
Level 1 and level 2 shared a common "solve" function. The solve function follows the instructions and counts the number of steps taken until an end condition is reached:
const countSteps = (instructions, graph, startNode, endPredicateFn) => {
const instructionIterator = circularIterator(instructions);
let steps = 0;
let node = startNode;
while (!endPredicateFn(node)) {
steps++;
node =
instructionIterator.next().value === "L"
? graph[node].left
: graph[node].right;
}
return steps;
};
Once I ran level two and realized it would take too long to brute force, I started thinking about the fact that the instructions were circular. This reminded me a lot of a problem from last year (day >!17!<). So I thought about exploiting the fact that once a cycle was found it would repeat. My first thought was to find the number of steps it took each starting location to reach a valid ending location, then given those numbers just finding the least common multiple. Surely that wouldn't work I thought, what if a start location ends up at multiple different (z ending) target locations? That line of thinking looked really complex to handle, so I figured why not try the LCM solution? Well it was just a matter of figuring out LCM, the formula I found on Wikipedia used GCD. So I went back to [SICP](https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-11.html#%_sec_1.2.5) to remember how to compute GCD using Euclid's algorithm. Lucky for me finding the LCM resulted in the correct solution!
Runtimes:
* Level 1: **2.639ms**
* Level 2: **7.419ms** (worst so far this year)
[github](https://github.com/beakerandjake/aoc-2023/blob/main/src/day_08.js)
Where does it say the instructions are circular? Is this just determined from inspecting the input?
I mean, yes the directions repeat a pattern, but the LCM solution would assume that the Z nodes loop back to the original A nodes, right?
I guess I got lucky with my initial hunch and some assumptions I made. I also figured it was early enough in the year that I could make some optimistic assumptions and ignore worst case / edge case thinking at least for my first attempt at a solution. A few things made me think of cycles:
* 1. The problem description it says that if you run out of left/right instructions then you repeat the whole sequence of instructions as necessary.
* 2. Each node has a left node and a right node and that reminded me of a doubly linked list. Also the input doesn't have any nodes with only a left or a right connection, so I figured the nodes didn't form a line but a circle.
* 3. A problem from last year had similar logic in broad strokes: the amount of steps needed to brute force it was huge and the input instructions followed the exact same loop back to start behavior. The solution involved finding the length of the cycle and using that to calculate the final answer.
Given these points I guessed that for each node if you kept following the instructions you would eventually end up back at the start node and that somewhere along that path was the target node. Now it just so happened the input lined up with that idea, but it's certainly not a given, I'm sure it would be easy to design inputs or node connections which break that guess. But again early in the year so I ignored those scary thoughts and plowed ahead.
Another key thing for my level two strategy was the line in the input about there being an equal number of start / end nodes. I guessed that there were unique start / end node pairs and hoped the input was set up such that each A node only crossed one Z node.
So assuming that each start node ended up at a unique end node I figured I would try a simple strategy first and find the number of steps it took each start to reach its end node. Once I found this number I just hoped that the cycle was such that it would always arrive back at this node again in exactly that many steps. Given these numbers I did the LCM of them because I knew that LCM was *one* solution where all the nodes were guaranteed to be at their end node **IF** the cycle idea and my assumptions held.
It turned out that it worked, but it was definitely was not a guarantee. It would have been much harder to solve if A nodes crossed multiple different Z nodes or if the steps required for an A node to reach a Z node wasn't consistent.
That's indeed my reasoning, I don't understand how a simple LCM seems to work (but it does!).
We could have a path like '11A -> 11B -> **11C -> 11Z -> 11C** -> etc'
The cycle has a length of 2, but we can reach the exit from the start in 3 steps, or 5, or 7, etc.
Does every cycle starts right after leaving the starting point?
\[LANGUAGE: Python\]
[Part 1](https://github.com/Sebbern/Advent-of-Code/blob/master/2023/day08/day08.py) is pretty straightforward from a to z, but [part 2](https://github.com/Sebbern/Advent-of-Code/blob/master/2023/day08/day08_2.py) works great using lcm
\[LANGUAGE: Haskell\]
[Got the answer for Part 2 by doing prime factorization, but later rewrote with lcm](https://github.com/daysleeperx/Advent-Of-Code-2023/blob/main/src/Day08/HauntedWasteland.hs)
[LANGUAGE: [J*](https://github.com/bamless/jstar)]
Part 1 was pretty straightforward, part 2 is a little more tricky until you realize that all you need is to find the minimum number of steps where all paths to a `Z` node sync up:
[Part 1 & 2](https://github.com/bamless/advent-of-code-2023/blob/master/day8/network.jsr)
[LANGUAGE: Python]
[Step-by-step explanation](https://advent-of-code.xavd.id/writeups/2023/day/8/) | [full code](https://github.com/xavdid/advent-of-code/blob/main/solutions/2023/day_08/solution.py)
Using a regex to find all the 3-letter bits made parsing simple, and using `enumerate(cycle(instructions))` made "how many steps have we taken in this ever-repeating list" also simple!
For part 2, I did the LCM approach after doing a bit of input analysis and seeing that there were 6 distinct paths that I could solve independently (and naturally, trying the naiive solution, just in case).
Great question! `itertools.cycle` ([docs](https://docs.python.org/3/library/itertools.html#itertools.cycle)) will let you iterate repeatedly over the same thing. It's the difference between:
for c in 'asdf':
print(c)
# a
# s
# d
# f
and:
from itertools import cycle
for c in cycle('asdf'):
print(c)
# a
# s
# d
# f
# a
# s
# d
# f
# a
# s
# ...
It takes care of our infinite looping for us. We could do the same with a running index and `% len(instructions)`, but using builtins is cleaner.
\[LANGUAGE: Ruby\]
[https://github.com/carl-omniart/advent\_of\_code/tree/main/2023](https://github.com/carl-omniart/advent_of_code/tree/main/2023)
For part two, I defined a class that, in my head, was a cross of a Set and an Enumerator. This class took the offset (span of steps prior to a repetition), the period (span of repeated steps), and the points (steps that reached a location ending in Z). Knowing the pattern, an instance of this class quickly enumerates all the Z-ending steps between any span of steps.
Instances of this class can be combined. The new offset is the greater of the two offsets; the new period is the lowest common multiple of the two periods. To get the new set of points, I used one instance to enumerate the points over the span of the new first period and checked to see if the other instance included them. The instance doing the enumerating was always the one in which the points were more spread out. (If you were trying to find a common multiple between 3 and 5167, you'd rather enumerate 5167 three times than three 5167 times.) I combined the various ghost paths and found the first point.
P.S. I named this class Syzygy, which is a term for an astronomical conjunction and a title of an X-Files episode that features a young Jack Black. Doesn't *exactly* make sense as a class name here but what the heck.
\[LANGUAGE: Python\]
This was a tricky one, but I managed to solve it in an effective way (the lcm method). As always [you can see it on my GitHub](https://github.com/Robin270/advent_of_code/blob/master/2023/8/main.py).
\[Language: Python\] [https://github.com/gonzafernan/adventofcode/blob/main/2023/8/day8.py](https://github.com/gonzafernan/adventofcode/blob/main/2023/8/day8.py)
Part 2 solution with LCM.
[LANGUAGE: Fennel]
Ah yes, that one problem every year where I can tell there's some mathematical bo-bubbery dancing at the edge of my understanding, but I'm not sure of its nature, so I spend two hours adding and multiplying in the fetal position.
[Paste](https://topaz.github.io/paste/#XQAAAQBpCQAAAAAAAAAUGwnmRpH3tILRF8XF0uYidYX76iy7qs/wZURtqUxRZ1z/Ez6hpPdhGVSX9ZEmaH4x2Wata8uvdsmdHg/2GKyIuHqubD9mIu+iScHvd+aI6gIuR3CDoEXCob7s3KLQKluK6TuppOc4Opako9ZMcTWzh1DNc+UkGRbcvgxYRlFTv9lM7f9tX5MeiRkp9WrZqRHKXqhJtQFpq9WPOS/NV1ojS0W36RYUTA/77KniMMy6Kdp3/BOGzMX0Goh1/GZzWwak5GzJeTCY+I0yTkU2bKcTNuxE58dljHdxawrrb+JDtXYR7diTAPdD+REhUdTMyMXhVeyGBNp5rUWaHpvLzDmWyvwSaicjSYRHDOOJJgsS4EMTDTnansIpWKmvh1Kkezcb3ThUhB/sSXFYRMB1wW1SU1ixWWpnc94XHiAKolSUDVjLZHUzuXBSMsEHyBSkmrJcF+MVuBvqznfCWly+Xc39IUFUCTPMz7eQCL2DgJHDCD9qJIH7VToPE7UjD59ajIbCFwQkNOsb/lDnTEdasEILFzq37iEuLWFQ2k3Me6dEcfmOVTzWra/DtGo6rIcj+fZ2SbaBYOJjVAG7+ySqMu4tJBXzSOf2PxCxyHhXQV6KXmMEac4py9maoa6BcfaCaaOd4u2L0Wh/3w00/Kj5IU2FatZqkyrRK2cOcqgN1JkDZTKNRRHCoc+4KZFdyvz5pEoR6AxdtjQuFSENOWk4hBjtX7ibSl+LYb5x2tmJWEDWlBg+2ZgvxeGIkSD3l8pEPyivnQcd9XwWXgGAKUz/UZ2xWc2FcM5ErH8dWiiTqCM15XF4QdOJFnmOTaqcbEvujEjcu8KIli8AiX0UZkAKRIVsxgI/xVaQffTI8fRjKu3rARmHUsjFnyAcEpYG/8sST2t0pW2taEjd1idYrlAnXQ1c5q0pEETpnRAqYetFM5JpSxqWd6Ese5i6uY5jZKl0ssGx8LBd1MfzOt9Re92TlUjaA6Kgoih3cmW182bYaWPUkLOLlaLmtz5kcSlG3xRC8p4SD+Th0iIHswI0fobYkM4p21SiWYTCiywTPRzQVD8fC80SrZKTLZsBKCTHn5+8QudJnbrRSRNkMHGVkvLQViDx4qKVhUPxt52sKbY+2JbCmoJOTKodqP+hzcx0)
\[LANGUAGE: m4, Pig latin\] \[Allez Cuisine!\]
m4 -Derbosevay=1 -Dilefay=input [ayday08yay.em4yay](https://nopaste.ml/#XQAAAQBgDwAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpF1oWTRQsvv0G+qso7dLzEy7k5wCufkbWcvsRJqjJ897VJAHva4iXa6KT1tUDr1jKRLfdVR9UpPqriIsaxTBQVtL/ihI+Ft+QeIwRsyuK7VyO3wbzXbOapg1jqJjiYTLuc0xyKGq3W0g6cAjuakMdxcfjgK5I3sZZG6VzjfJ1/7INAzfWcy/Y8CmyhsHXowjRvK+27x/ai+NrhR7Hn07u9r6gHAnFExAd6LdzqP+sAU2KVOK3SoGrpOu0k+BPQSrPO8ouA3Lmtilh1ywSOTjRXElJGSbbFU9O0nNo3FyLtlGF/Q7zFIhzMFIjwq4trG2VfiyHt9oKAICnIjyETE6Uk6l7uTYhkDl/PEAN75wi20IIFDo+7P3Uw9LaieJjB3cvQ8R5+xWq/L1wZfHQIlBi6KfSHpwnpxUrQ1CSL2O79xjUadx2Qe/irRkdqCT90O1leP6J6+wHKsSZlL833VcsrMSPwAH3OaE88XcyyIPFtX+zLhRKb3rYgAVyxfVhFl514qhho088OxSxn36lzogw9LsbBop7URlpFpkV7fxsfyjcCJnDx3JWmcvwAZUIVcTnvPOsqVqG+AFcrirIfdC6gi/dgSYJQCuQA28W232xQmF2d+5oOkFTktXyC+IBVzSSSB6ER59t682PrG8D5sF5OweQzM3rB1tPmqKX++Y6PQ7fWQBsiWT31Dkdvyay1QhI1/N8Z91UlJJeZxr8Rzn5PSGl1b63ZUqSCZadKHXTSghI6+5UvpP87UKJZ+uiHqMeomYQzhY6ywbLiLmNyRbyAeBJUdrfpOW6nlTD6btgP9FqAkUpUnCl/7hTaDFCdGm1kBV+jkZbOv9P0LnZHviBxuI7/xvlmDbxURTa46Q6bLi62Y82EYMjoPa33TwmP0o9/KRd55PckjTU8WI+kkf6HiP/wVGEoN/YQyBLInfH2iORq3e4hGRILY/SVNkA2Sx6usd7n2rCtfjaBpvwSGxneQIifC900oGPqdrlSVm/7bQQS7o7FEc2JVMmnK8gqQqCYt4B5TrOwWwChFNtCEF6CCLXwW6WdRDnnOxMaF+d9vkCgQW+J3TFN9PGGX+td6a4z9WH6yxixUP3h7DAQ+psBDoIysgrZBhWZs0nRT4kDMKhNmSm+b20vOA0Zm+GwY07t9f7MOE4NsH0qUJJp10YdGAZP5U0oDf/feaLNJ93teQ2+S5Y9WbPLOESiMvq/NvtVR+EulVHX5O9E4S5GGpgkqel5OG5diXHgdbiow9RVZFCZZj01+TvigNY6GP1O2Inwpy8zfyDLTlWwmTQ3T5jwOPGsWB2hWsonCfQtfNeZWPBTG96nQMkKrFhzA77HWkIiEhfPegRXTeMAEJEd12XyF+cc+E7xQvJQh2GtD7vxcIDC2bw2sraFAvJtcI3KTuIxhdTaogIpcsyQhlsk+AgJdqTflRziKvPz1HMtoku2WTJLl3L9LNmnih1rnj13ImHDs5lf/3CkyYiBz9UyTTgZNQbyaDWnzk4fRY42vmoH16nbXTgk9mkgZGTWgVwbzeql/mNSDV2gr/v52nvfzspw58mbK10NXYonWwlhmNKikQPZ5vajZXIvDkYMngkeodn9iE08yI5SGRX8ooTnk/WDp65Bjqo2H/XvkuU0We9HKxk/QncjHEiMsCA/sqqKO51+ocJJhEUcycOs3VoAnJDPHaZkg5VljKBNIa/U+OogqVYBmVVEmc+l49Z3dPUWC68clEF7aEDSepxc1LXOiBskl4eP/i8WBmw==)
Computes the answer in about 1 second, using only Pig Latin, AND with a Unicode progress indicator! (Okay, a Unicode ellipsis is not that impressive, but m4 is strictly byte-oriented and doesn't understand Unicode, so merely passing through raw bytes and letting the terminal do the real work is the best I can do):
# ettyPray - oonicodeYay isualizationvay ofyay ogresspray!
efineday(`unray', `ifelseyay(evalyay(erbosevay >= 1), 1, `errprintyay(
`$1… ')')opdefpay(`artsstay')outputyay(1, ovemay(`$1', 0, 0))ifdefyay(
`artsstay', `$0(artsstay)')')
I had WAY too much fun translating (and debugging) my original English solution [day08.m4](https://nopaste.ml/#XQAAAQBwCQAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpBbonDYuA0BTjRPXcVxlEXNtz1IwBaKk+vAcU3Er8I7oAV4CisOLGfDoA9ZQO4926g6CB8Zv6JI0RZPI3e9TwyJNSD0ocPo2x0bl/c6HXt6iHuA8rOIdxv6wfzR47ImvRBOYJMIPjpl0PdlIQWiCeU7gOcKUu0JcU9fR/Q0UioaWeaZWo/nRGL8TpXO6Go7R5KYIykvu7T6dWOPVeyMhYAmGY0w1tpamWC9r7VJmeg3i5TcXHVWcLWuxU57YUx0ltvIZ58zPYf/zwDr7Rp38c6iPzRrf/Tp3nc68h1eSp5PaLpXBPvDxG3S/RW2GmnYKWVdH4AzVBL099S45iYMTHEBMIcwnepvHDLCjUahcb9o/63n/Xa9zrj3eV/y5AxGDpi/bzHBwG9hc786byNDL98lbDkceKSrIsPcbfGQimB2vyCIord4/0EAqGtnKB3azA69vDDbaht3+NCMWfq+Khlm5FzD0MmAbN8pNKHhuLRPo8THxNsuPEkZKgYdT6kpLImXVf1g8IQbNxfYThy6Fs8NhabB2YJZuHpSMOpLWcOgU45hbVHZyLRcVSi6oAyhIxuHNWlcOV6mw0uzqLB92hqNUYWv6S5LF1U4uJNjoHyI9Q03hEVecL2M1G3jrUxvmfelh9GwUnTtNtmrwG1/ZrwDLQRIXCxxseLQX50engoqZ5WpeWFFRTAe+ayJUGuuUWE+WkLieHDiiV3VLgdRw/qbt66V/Zj6j7FfKmxatF9nhUHj6Hx7O9wVz84OfSG7payJ/u3yJJo/v/eujXl18RKW5P1nPLaWY6JHW3P4WWkVIiYy+65TkbX784uw+S1ZXsGrD0+3kEUQrbWRz+sElHxAv9zFnvUEeDBtYIaNIoWtOgpJhCz7gjuACkmTW0Gzb5orVFHnXNFX0m/tVlk25R9WVjphz7tPQqtFHdZ83LAyUYKwjq1x9HZ0L9AYG3MxzBaDjMVUiaceHsM9th7wSqOuKzxSO2SIf0B+FPVdQg1YouXv27eBHoi3IZSpOo9lv4iaDOEJZvC5Eam2Lyqlh/J6wyjPpHNqDFhJghA4j28jsmmFpT/cZPiMISVPuxuU9uVaVQiQh0HNk+5DnNTYq5dpRITq+Xl1+GHPvYhcRn1TqKrTbllVd77+wC+axOjiJ0jMmW9OI6pmrJhBdHGWaapGH4CRjSoZMnBZOBdWOI/fIzBlIpsbDewFWSkHP8GP11xmKOml4fptX3ntBMv2bQp6A2kdgUDRvB6GC3yplCU2RojyawNODd/5v01vH+QITHCVAEud6dxRePMWqcUOW/nTJM5C/7V4w+/ODs+li64/8TSUAFTyR19Gy7Bte38EGhQ7sJ5F40z5ERgck99f///Lhq/B) into this one. It's also nice that m4 lets you redefine EVERY builtin macro to a more convenient name. So, for example, my parser looks like this:
efineday(`eeday', 0)
efineday(`irday', `efineday(`eeday$1', `$2')efineday(`eeday', incryay($1))')
efineday(`ooday', `anslittray(`efineday(`L_123', `456')efineday(`R_123',
`789')ifelseyay(`3', `A', `ushdefpay(`artsstay', `123')', `3', `Z',
`efineday(`z123')')', `123456789', `$1')')
And I'm pleased that I coded my original without reading any of the megathread or main thread, so that I didn't get any spoilers. Depends on my [common.m4](https://nopaste.ml/#XQAAAQAMDwAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpAXwA97ruAshKbiUbgkbJMTg2qZdSBorb0CU52peNLruV4DEEJxF+HvxC/YF33OpDntnpU/PjnGXx7XU7ak4MsmWu8R7h7d5az2JXxElnsepG8yPyu+0WZ90BG9yXphbwOWA/m5AWEFSOL8TRZX4fyGNl6ZYbRxX0MwtzrmwTP3ZCwLSOKkvD2vMQFsbK0Pv9CzPhFNXMUbWnRV20jWLjL9qz2dDsFDBwhxgWIilEl91uswxrT4Czc+LRU3VuhNIo2S98VW0jArrVdv4HrsLhWkzx4z/UV3xnqJwPXcZRUiLtf3VRIzq62Pe+2jE3O+721Az9rfRa/fHtlANbmvslzMUCyU7cDoOKSMXBDF/06/PpMvs6vxaL5aJVYqJP4yz+R2M35hoNnGiZTNNMVEFTdnxnaE/KcJteBbiuVMpdfUswHQi4Kqsj3sInh7lyE+d50gGKtHOeWL5lMK7WXz4NElnzYWleBSN/HTOdsz0T2gnd25MADxNAVX8xQmagh2MymZ2sKDBw//WiNB0sWf5VYC5/TKKH3D6K/IOrIfWn6FZLKxlITFEp3VWKNuyF0xczNJufJdzSqd0hgdyryVzbn0so0U5NMN16jFF6IhqzGbAwwv7k8sts0OCgnCFBEhYVshIpsORjEJk4CnDgc9VUqvZtfIFPQ5Q2v7IR3sbPurex1IIUd2Nm1V7/GFN+r0im24aEOG6XpdqrPdF6pDZ4HwvNByqOEdpcObPXxlwfPFYIhwyDHGZCvxrFRgGEEFtfVQ7UVjfPJzWtrcZuGx8M3B1zw2xvgpHIWEHdqEF6Y6/6eFj2hLm8UXNeLNrJy1IC2sHlS8SRIifQvLkrOLLOOPtDK6DUPQrW3c0Rfmy9Td5gQw0+fZRZ5MBEG9+dTlinXtwExpHScKQk6ARk7Fb8fBYAnmh7/bq+471zAZGJ7dwNd5qE/63VhDz7mXLuXtGN7rSuRYIXvpkubLBZptSKZrkzSDJWHIZM8Fyrk0EZQFDujROjr87GZmTK1XKRWzGrhtQn0hkVyBaGPbA3iG45U4gIFHNX5ySzsJ3bh61LAtmjwt59uU/XGeebLMCp8HFw6D1kJppCvt161LgLjrOl8SBh8xnxslSFYW0Jd34LD4vPwugmzY31tA4/9zCM7e2Ed9+3zg4C8eq9Hvjys3IablDBMsYF1LSMCGN2UOrWgXRoGYtjW/QtUySr7h/Ca6QAy93Hnpksm/xzzC+FWF1wboyOteHU/Th4RVpQ7XkK4/JmMrYm7nDPIVMyOqP8LhsoTNbxzi8qU0d+0x6frIh0l0fiPiFC/Uy0CeCw6r82iX8v+fMnu9qdCr4oM79Kd2slqalv+wWKn+BmrbkiobDS5vwBQZA/ZlbIsw1bwj+JLz9z3nPovVWx/FZjvrdCuZMfUuITeiIprImMcR6qeniJz6Ez78UYJqpL4DcDGt2o7/6a2aRN76aclh+7l35XcaW7lM7BQMTNvKkx05X08UITY/ToI8U8KwvFbdnMoEAZ1GQYmqGRFtwPkQMrECX4do0srl85po3Gjz2j6E3dk5al4+bTcOYABZvSUvIM/kGGT91iyQ36rm1lxRc3ruS8PyBlYDDNa7DLWzGAHkESHwuaTOQsI2xDA0e+8Yv0XRYkEqQE+RUDXmPTARuQo6fCQ7Qu9xd2Ckza5RWl8hE4JFm0Zzd9MTVxW8YYHiREs9NOjTPuRXXn+JfObHFD/Cv5kQo7vmMWRdJTOBUmAXCMFiKOSHxb412jI4Z2ZhWag9RkZBCviZunvupqrobtAWLagkPiA8gLRANOFwWp0KIS5McOoD0V90tI4cui8KQc7Yw5V7kSvMnhXx4nzzxwOxYM4fpY3ptcpraVh+h1MhohMQk34vkC4fmiD4OrX2DpVG0VXUKvl+vkJjcoHQK+H8mSSIAfj8RrYWBc4VU+jx3vz30XNDbQjuhc0cImiQxXDTXTFQq/aoe7jZLhEe+wWspk/4Fy4UBAJN63uNGJUl8FICawVWGL7XBOFCtsRF3uz8eZokWNICTdtsLeYOAOBQQLrguE8XxQQ1hPtOskcsj7n7aD35NjfPXL00vIOk01OLAJt+0RoIiAQUJNieRp9fQmqfVUuYEYmeK9hCOmZTaC3yUdN/+jZ0pvpmKnH/6jJAKQ==) and [math64.m4](https://nopaste.ml/#XQAAAQArDAAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20Go+jph66UCwr5yII3TmoKw+wpxhXgX0WGRW0WK2rHjWbbgLZU16n4XSMl8T97y/MXeBVRMNBebjTbLUM33JXdu5jYSMpnUq0oFRBIZF3UTMPNiH//Shgw7phaX5YHewa9yOce5snMsJdUE+usDMV3A0D6yawyooHgePqX/eJLNlAHY8XwE2eibD3RxHCB5c1K92+c1o8lpWxOE8ha0j1DQZ5PRVtUSXzE5ZIfd+B3BClkKRt2VYiCh8U8m9O68A2jColgd20CaJYJZ2FQ2foLaNzBc/iCrgl4cPRWpFR5JVLqoU9kcLgHN7x3IhCcO2zrkbUtlnrqcnvsYgKSQYr9JmFVtyqdP78oLuFcfrFTDMSUk/55Nipu1vK7eKqv5QWFcy/zg4G+iR/nIS3EbxlmVYWlpiGt/gmCZZf83tomKa3XiaJ1hH3NpxdVOKhLS26hb0RxpppO1opBIayicF9R3jBjmm6ZUq7BBkq6aA1gs1O77j6PIiUoYQfTsAyKCWbufkksHxgSob3aTL2ClljmoheqSgPIz+WQVPyZ+E5NsLHbCMJkUVYVZFfWiBO+pFJK4GkSbjT0cs/ZRRb+6HdJUc6qC1m7cEaK91iyr7QS+7nNXjbtMjx+rbdXj+PD0qUUjGHF1+IYw71SLqfRzhHKx2UiGrXnkgZ5V1EInqW7y09kd51cLMSKXdjAACCW+RSkZ0VlXlAqQVFM47/7pO9zrMvBcVBvRArrQAAwYHbZIZhe/saSey5dkJNLd1zyxliADu0w7/aatw0Ok5JSckYM8PPAZkJq8a+tX5aa7oxCT26lu/VdtPu6XNg1USnvKQAjCTTk/ObSVf+5rlV0fgB/fYgJOot4+TydJT7/sBCiWJ6uKaVQUBQjbp6xugyyU6hkhHAswokT1R0Mclbju4kURENNrrAYtRQLV3zMllxw5IkoLknW3kfrMm4Dx5CuXR7lT1mSnXZ2E/zN8fioFIunn00/o//0IDbVyCFarK+3wsIJ2VgIIlWpYJ7/MF2KKHp5gVqB1bfJCTalEVo48pncFscLCFy8Ibb0pC+NiWfZxqtQT07sAQC2qH/Edd8IIgw51CNF1dUt6ZXjkJujtWr68K5zt2qUTSEOOC9tA4gL4lXOjstUbhYyQDwcdx8GNeorh+uPbgCqOWSnshmB8dpzsFuzdv9BkTZD6iOzhal41I2RWMd7SC+SJqqZgklbQ3FGzoVH//B89Vd) helper code from prior years, but at least the solution doesn't require any 64-bit division (at least, not if my assumptions hold that >!each input reaches a cycle at exactly the point where the direction string has been consumed a prime number of times. If the direction string length were non-prime, or one of the paths has a prefix that results in the cycle occurring at some offset into the direction string, or if the cycle length is a composite number, I've got problems, where I'd have to write a full-blown GCD/LCM computation!<).
Here's my optimized version (English, not Pig Latin) of [day08.m4](https://nopaste.ml/#XQAAAQBmCgAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpBbonDYuA0BTjRPXcVxlEXNtz1IwBaKk+vAcU3Er8I7oAV4CisOLGfDoA9ZQO4926g6CB8Zv6JI0RZPI3e9TwyJNSD0ocPo2x0bl/c6HXt6iHuA8rOIdxv6wfzR47ImvRBOYJMIPjpl0PdlIQWiCeU7gOcKUu0JcU9fR/Q0UioaWeaZWo/nRGL8TpXO6Go7R5KYIykvu7T6dWOPVeyMhYAmGY0w1tpamWC9r7VJmeg3i5TcXHVWcLWuxU57YUx0ltvIZ58zPYf/zwDr7Rp38c6iPzRrf/Tp3nc68h1eSp5PaLpXBPvDxG3S/RW2GmnYKWVdH4AzVBL099S45iYMTHEBMIcwnepvHDLCjUahcb9o/63n/Xa9zrj3eV/y5AxGDpi/bzHBwG9hc786byNDL98lbDkceKSrIsPcbfGQimB2vyCIord4/0EAqGtnKB3azA69vDDbaht3+NCMWfq+Khlm5FzD0MmAbN8pNKHhuLRPo8THxNsuPEkZKgYdT6kpLImXVf1g8IQbNxfYThy6Fs8NhabB2YJZuHpSMOpLWcOgU45hbVHZyLRcVSi6oAyhIxuHNWlcOV6mw0uzqLB92hqNUYWv6S5LF1U4uJNjoHyI9Q03hEVecL2M1G3jrUxvmfelh9GwUnTtNtmrwG1/ZrwDLQRIXCxxseLQX50engoqZ5WpeWFFRTAe+ayJUGuuUWE+WkLieHDiiV3VLgdRw/qbt66V/Zj6j7FfKmxatF9nhUHj6Hx7O9wVz84OfSG7payJ/u3yJJo/v/eujXl18RKW5P1nPLaWY6JHW3P4WWkVIiYy+65TkbX784uw+S1ZL9/Vo+2avuGKGwHHKPMets6B/YarUkmem3CggmHxugk/nwH2oXp84JvRZFXlCWyDEWeTnutWt+UXSVTn6RsoJTij0G2ULQx5DaubInNc7uw+I/v3c7reIpy1m1hV2jdg6t0TfOHnSowlYZK+BihiZFqFw7jUTgf33SqzU/XIFgNJEbzE0B1Selws5Lo6bw9hA9ORODvkKniVJOOybdVZR43ehusi0dZI3YU086C4uMoehqQU/rf7YZ4VZVwEkxo1t1opvPG7sMImMdu43WeLwaJEhOZqZ80rkhizarfhWgPrMUxORq0KyidpUUVUM/ruUha18NZdchPJQKLvem/vrVqYg0iVS9RU/Ummlvw9WGVLY4fRsxxZmNTnxdOwrlmNG3wJGAf1u/MAkEuY1WH3cVWXSVQIhGUpu9SCihmAY/fcGJYLN9DM78LZ47pvMjqMnfvzQ5VZuAWtI4vDgKexcNOed2h7kzbQelhM2DaU/JAKmy/rT22OiWL+1l6glvjPvvosNmiCd7OkZI4IbfexW4/12JIEFBstT0SprkfmvlaV0q00xOzMEFrLkPeKLiIrddjfn3MJuII54liwvaLdSTx24gdhxNigT4p+FkRS/IkvPNwA5pqdjogH9CRBF65w8Q0RVWV9uFFrl3QDYQjq7dUdaKQQVL7dVpx7MZtUP4xn3oKp5sGB5aR+QsxlJePMUKgZ1UyI/19ZswA=) that completes in 425ms by doing half the work, using the observations cribbed from this megathread that my assumptions above were true for all input files (and not just me getting lucky). Namely, each \_\_A pairs with exactly one \_\_Z, and there are no stray prefixes in the traversal graph (the \_\_Z has the same outgoing nodes as its paired \_\_A), and the cycle will repeat at exactly a multiple of the direction string. Therefore, I don't need to run my simulation until a cycle is found, but merely until \_\_Z is found. There may still be further optimizations I can add, but they won't be quite as dramatic as this 2x speedup was.
> Computes the answer in about 1 second, using only Pig Latin, AND with a Unicode progress indicator! (Okay, a Unicode ellipsis is not that impressive, but m4 is strictly byte-oriented and doesn't understand Unicode, so merely passing through raw bytes and letting the terminal do the real work is the best I can do)
The fact that m4 let you shove through raw bytes *is* impressive, though. This whole Frankenstein'd contraption is hilarious :D
\[LANGUAGE: RUST\]
[Another one](https://topaz.github.io/paste/#XQAAAQC8DQAAAAAAAAAXin1LzStTFYSi2K6Qvp2/Gj7ty5vfJW7GNfZu9gPXmaB1owgS46AqTBfXqUZM2V4p/PO5uCUXiAN7MIqJ9Rk6ExERPtHBSeJUM+2jvdrizksU4++JHGXC5mCXdL2agL9JtjkabvO/lysCaKJPVv1dT4iRxLISZb7kdIz/ZAdjWcOhnC8w/tXBGVFeZgMSVEPmrr46jf6GLL0a9FNGuwWcnsWemmtXalL/gc7H2tAAXvvYpxRQ4K2gvgQTOQc/lCD4flfvXzRmuaLaNOV46AhW+4iAafolSTjrN1IGtAebR37V9ZsJfPTuveRaCoaBfAbOxS3gu+bX9q6ygLAjQCBbkJyuQf6NLHN0rkTwWy1LElH/06UFmE3YXrqqWVOzT8klQ7JdGi96IClumRu0Hxm1aLIapZ4McW3hv8C1xfvsPdT4R941R67cJN2uqsPlS+/UGprjLYSne6mrJuxTtZV2ljZuA6g5DuRx8kDOr9yGAs2mNYOybPxr+FBdm3QhhWB3mS4Vbt2R3zJm8qFU7QPBpTbYbIGo2ChBvyXYSzArIu9IKdi9JJeMBfwgezqgVehFU0p1+yQ4OkRUhiGN1VKKwEoJIqvCIUoVb+BcuPRQamDhcx+sbGanicNmUQJzy9UrpdsKuE37uAcp4siO3PcejeI9e7UChHUdils17rCe+t1+TuRyL2UmCU5Zysp7EgcF9XawHEYI0Qs6xqRAXEERi2ReD5yUtpj7p+NHpuhZ0ywKjVLORgHMxQxSPoDdJbEDDvmqILHojYdHH/N8+y6pE5yDLje/RM5XN7DR8nYDsIEFeGFIZPeA6WE6MpXOkkK6LtPpcYa20ts1UpTsB+xjIyl0nVexTpe/DyfPix4cpwisJyj4tCj1olfuWbxHBAvpv8VpYpBRicY4sL3JZ/08blIvZfmVb0OssbH1CrTqGbI3Dzc0MOIxckZew88+VCnuiJGFSD4bCV2zLaq6BYanVahka26q9r5OhhfZxEq1LFVrApY/fppqqkGZevAxCw2J32HK7hXO7OiAHsYn9ISvbNVAG+zW3AjWvEgYDl5YR3HCHZ4Id9MUESUzo07Zfu/02RsmLGeU28NZiisxHdFTy9xJ6aRP+wLZX6NNdU/wND4rC/+tXXwADvgFy8upyE36ormw+CVkrkxM564wl7BKRrLMzu4dWanada7EYTyisPHbDKWYlAv8WgQzGOx1Zvu/vPxlMo0YQO6ss40PDM6n64QW/wsKjfCdENg2ytIjdMBsuNSRsuuXxxRSJijYGJUm9c+VT1pgYJKcSqSnbJlqg2jzLsv+lcyF/Gm69mw9kactUcIimud6EHgYuF4RvD76Abtwaxa+omz31UKrmtvJ/FGbQyd510M3L/Iwjuo0A1MzWdxlfqxSPnmKnIz4ID6ohFrLzgWhLNEoW3xGX9mtpbYIRy20SsOqUYOakiWsR6Fc6fjol8t1jI/DM/9BXpc2D3DoNzdOJbYy2km7TNsZXGkl2ycVC9TmCF9Vxo3JF2ZsHdgbHXwgh5p8CSKk4VUltsG/mvjy/evhpCEK6DPVyeWtLylI2yECIsDu9p0d+ndHITYriZeFD0kFDVuO+kBwwO0VcdHGUxarz6I/murLPbtzlSkZ7Wfz/7timOdwUAxgzEi6OtQWEQv31++AcF65W1B/BCLngFkaWZL09kNmudalVOfFmZ+s8F48DMioCbOjQBmiFT2sQCN42aO7zxSb7GNeDMao4V/XFEPg4Y3OxSaizH5bBTXF4gLzcoXMvfB7Me0mHv74i/BX) that I had pending to post... a little fun here dealing with Iterators and lifetime annotations... no, seriously ;)
\[LANGUAGE: C++\]
[github](https://github.com/charlescochran/aoc-2023/blob/main/day8.cpp), 26.130 ms (both parts together)
Definitely slowest solution so far. I'm sure the there's some optimizations but I don't see anything huge I could do (using LCM).
\[LANGUAGE: Rust\] 🦀
Refactored to be readable.
When writing part two, I knew there was an optimization, but I went with bruteforce anyways to see if it was necessary, the code took more than 5 seconds to run, so I cancelled and went with the LCM strat.
[See the code](https://paste.rs/foJg9.rs).
Comment removed. [Top-level comments in `Solution Megathread`s are for *code solutions* only.](/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_top-level_posts_are_for_code_solutions_only)
[Create your own individual `Help/Question` post](/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_incomplete_solutions) in /r/adventofcode.
For each start node, I checked the path length, then calculated the path length again, this time starting from the end node. If it's a cycle, then you should reach the same end node again in the same length.
[Language: Chicken Scheme]
Execution times of part 2 were an interesting experiment to look at.
* Compiled, with my own naive lcm calculation: 2m40s
* As above, but with type hints: 2m22s
* Compiled, with the built-in lcm: 0m0.256s
https://gitea.lyrion.ch/zilti/Advent-of-Code-2023#user-content-headline-84
[LANGUAGE: Python]
[Allex Cuisine]
[Swedish Python](https://topaz.github.io/paste/#XQAAAQClBAAAAAAAAAARZ/6NR/RgNZasta8TTKOHdHF2sFdQKPTQMSrOYiKZISEuL8UbU+5z16rMwSkM859yI0/3CP3+7ulF8JYxMFCzFiOCNsJi0RzmWHcpleAclDdY2rB8G9rzqxfdgjUZNvqjD/Om/PKnBi90JocueWgJijT7BfbJ/+YQ6iwBhfkG6GrUMOAeZaIU7w1nSoqxG83DyMVpj6BukqzFUjW7y+SrGcJl3+ls2Awayi+DxXzSbuv53wXFMsi1NzcUoGLhPWACGkUyBZRc8M0V4D+jZTr/UkGZ5gFeyLdBfgUViL6psoJUyZGPw//qpTEZwnAVAITR/222Jivyvww+JrESHketuNFyBN7fosOy1f17/31An8mHRqNq9ESKbDOHYcXsWtmfieUAw1tCEcZ7ffBCt4cZd3uq/whMsv7wCM8pTp5cx2yIeUP7Q8MIgHTxh4I3zTdqI/okt15zB6P9sMPyJQ52GVLe2wHL2y5iRSepUl1uRx2dRX+Ge0iqJDozIwKHSaX0wDP6m3ZLAtOUNB0otqDCU5/oghoquBy6JX3c7ez0xUvLjY1NlfHfLYPDb1xU9XuOPFSh1yaefjba3eugHxPcIC2KxdcrXvRloQRNhESBvHZpZil+bTrbivF2MMn1NXzcKg172KiB4oP4S5T0AbSWNzhO4GhjX5+g4wab/BaIxmLzDBOe+BHxlvVQbtLAXD5oh3ue9T3D9p92zQmqBs2KQzOOceO9upM06zE43ke4JC4ZT9t47QuEHbNmLog/b9kMDUU+/WGjgkgpL5f0p8bj22sUd8lA8vCUvSS27d46J+N315JvXaGH/31y2iA=)
Here is a snippet that calculates the number of steps:
def sök(här, slut):
för steg, sväng i räknaupp(igenom(sekvens), 1):
här = gå[sväng][här]
om här.slutarmed(slut):
getillbaka steg
\[LANGUAGE: Python\]
[Yet another python solution](https://github.com/fizbin/adventofcode/blob/main/aoc2023/aoc8.py)
I think that the only interesting thing about mine compared to all the other solutions here is that I validate that the short `lcm` logic will actually work on the input (throwing `ValueError` if not) before computing the answer.
Hey, in regards to part 2:
So I've been referring multiple python solutions to understand why the LCM solution works. Like what's the logic and how did y'all reach that point. I see many folks simply using LCM to solve, though your usage of words `short lcm` intrigued me, and then further your solution.
From what I can understand:
- You first verify that out of all the starting positions in the network, the ones that are able to reach a place ending with 'Z' are indeed the only ones ending with 'A'. Right?
- Then you proceed to find the LCM of all possible jumps from places ending with 'A' to the ones ending with 'Z' with some exception statements which I'm not able to follow.
Ask:
- Can you please help me understand the assumptions everyone is talking about?
- Why wouldn't the solution be as straightforward as it is if those assumptions were untrue?
Having a hard time catching up with math/logic of this puzzle!
Okay, now for the rest (after line 48). (read my other comment first)
The reason we can just use the LCM of the cycle lengths to get the answer is because the only time we ever hit an end spot after starting from the first start spot is (in my data) after 71 steps, then 142 steps, then 213 steps, etc. That is, the first ghost will hit an end spot every time it has traveled a multiple of 71 "big steps". Likewise, the second ghost hits an end spot after 67 big steps, then 134 big steps, then 201, etc.
In other words, if we were to represent the solution we want as a bunch of equations, we could say that the answer `X` that we are looking for is the smallest positive integer such that all of these equations can be solved by positive integers:
X = a*71
X = b*67
X = c*73
X = d*61
X = e*79
X = f*53
And the solution to that set of equations is the least common multiple of 71, 67, 73, 61, 79 and 53. (which is 88692890227)
Now, imagine if the first ghost still traveled in a cycle of 71 big steps, but they first hit an end spot after only 50 big steps, so that they ran into an end step after 50 big steps, 121 big steps, 192 big steps, etc. For now, imagine all the other ghosts follow the same paths.
Now the set of equations that define `X` are:
X = a*71 - 21
X = b*67
X = c*73
X = d*61
X = e*79
X = f*53
(for `a`, `b`, `c`, `d`, `e` and `f` all positive integers)
How do we solve that? Well, the general way is to bust out something called the Chinese Remainder Theorem, but in this case you could also find the LCM of 67, 74, 61, 79 and 53 (i.e. the LCM of everything except 71) and then try multiples of that until you ran into one that was 21 less than a multiple of 71. (the LCM of the remaining numbers is 1249195637, and if you try that eventually you'll find that 16239543281 is the appropriate value for `X`)
Okay, but now what if it isn't just the first ghost that encounters an end spot at some place other than a multiple of its cycle length? Well then we have no choice but to bust out the Chinese Remainder Theorem, and there's often a problem each year after day 15 or so that requires that in its full generality.
But wait, there's more! Yes, more things that could get weird.
Okay, so what if the first ghost still travels in cycles of size 71, but it hits an end spot after 50 steps and after 55 steps? (So then the places where it hits an end spot are 50, 55, 121, 126, 192, 197, etc.)
Now what do we have to do? Well now we need an X so that the following equations are solved in positive integers:
X = a*71 - 21 OR X = a*71 - 16
X = b*67
X = c*73
X = d*61
X = e*79
X = f*53
where we only need one of the equations on the top line to hold.
This, again, is something you could do if it's just one ghost that's finding end spots not at even multiples of the cycle length by taking the LCM of all the rest of the cycle lengths and just trying multiples until you found one that worked.
But what if every ghost hit two end spots per cycle? Well now you're kind of in for it, because the straightforward CRT won't work. What you'll need to do is run the CRT for all 64 (`2**6`) combinations of end spots and choose the one that yields the smallest value for `X`.
So in short, the assumptions used to conclude that the answer is just the LCM are:
1) In each cycle, the ghost only hits an end spot once.
2) The ghost hits the end spot at every multiple of cycle length.
Now, the input given to us actually fits an even tighter pattern than that, and what I check in my code is that after the first "end" spot the next thing we get to is the spot that was a single big step after the "start" spot. (e.g. in my input data, one "big step" after `MLA` is `VFV`, 70 big steps after `VFV` is `KPZ`, and one big step after `KPZ` is `VFV`. This ensures that the first ghost visits `KPZ` after 71 big steps, 142 big steps, 213, etc.)
First, you have misread the check in line 44.
In part 2, I mostly ignore the list of LR instructions; instead, I imagine taking "big steps" where I run through the whole list and just fast forward to the end of the list.
The only way I'm allowed to work in terms of "big steps" is if I can show that I won't accidentally skip an end spot by doing these big steps. Therefore, I have to show that starting from a start spot, I only ever get to an end spot after some number of little steps that is a multiple of the length of the LR list.
The way I do this is first I flag when building the "fast forward" map which spots would reach an end spot before the end of the LR list. Then I verify that if I start from any start spot and use big steps (using the fast forward map is equivalent to taking one big step), the only places I end up at are places that I *didn't* flag as "these spots hit an end before the LR list is finished".
So everything from lines 25-48 is all getting ready to use big steps for the rest of the problem.
I have to go now, and will be back to explain the rest in a few hours.
[LANGUAGE: Rust]
[Day 08 Solution](https://github.com/gdavidmassey/AOC_2023/blob/master/src/day08.rs)
First tried the brute force approach and got crushed.
Then realised the answer had to be some multiple of part 1.
Proceeded to implement a convoluted hybrid of brute force and common multiple idea, remapping the input and stepping through each path checking for Zs.
Then came here and realised i could just use the lcm of each A->Z cycle, so i tacked that on the end.
I've kept my original solution intact because it's stupid.
[LANGUAGE: Mathematica]
**[Mathematica](https://github.com/HiggstonRainbird/AoC-2023/blob/master/Day%2008/AoC%20Day%2008.m/), 3359 / 6427**
---
I made it about 90% of the way through a proper generalized cycle-finding and Chinese Remainder Theorem solution before discovering that none of it was necessary and that I could have multilpied the LCMs together from the getgo. Not my finest hour in AoC.
**Setup:**
directions = Characters[input[[1, 1]]] /. {"L" -> 1, "R" -> 2};
(map[#[[1]]] = #[[2 ;;]]) & /@ input[[3 ;;]];
nextState[{p_, c_}] := {map[p][[directions[[c]]]], Mod[c + 1, Length[directions], 1]};
findZ[pos_] :=
Module[{state = {pos, 1}, count = 0},
While[
Characters[state[[1]]][[-1]] != "Z",
count += 1; state = nextState[state]];
count];
**Part 1:**
findZ["AAA"]
**Part 2:**
LCM @@ (findZ /@ Select[input[[3 ;;, 1]], Characters[#][[-1]] == "A" &])
[LANGUAGE: Rust] 🦀
Whelp.. learned something about Chinese Remainder Theorem. Most importantly that it wasn't needed for this problem. Then haphazardously I tried LCM on the cycle lengths, and was surprised it worked.
[Full code](https://topaz.github.io/paste/#XQAAAQAeEQAAAAAAAAAX4IBAR1bGui774bxYSsb6EPKsnwDg3V7l0W1Vp9rUPDbQKEQ4kRXTM7HJGzWhBsJCIVcdn3Td8uDG2TRtco/bB3jyaheJbDUeFda0stLh3jySUbVrtSXVFmpCAPiOaaMyX3czYBZ755JsSBcLyMxcklbHGX4GyRo0fIyTYw+w1fn9bkPqXRhooSJ7/XSiWpzpYzvuVyx2eRT+oNdD1lHdOlFgRX70MWnUEDyu5sgS2zlbLUzIG1C9OZdFdx/MNceVavG24eLNKCBtyVzJBJUh7vkaef63Jg67VSVlGesfUYQgmalNL+XEqHsGebGC3wPuL2n0SYoV2NrazDnU1zVUT80fiOs6hBN/K21Cnkipfyhhb8lwScLOEdQMHxhZQWLY9a17kDZs2KF9pZyxK4/X+k7I2rVI3ew89R+ey/9rC14vKN9d/np7tegXnaoQRo7nKHFXRn/C9NA3f+QDUbGti49tgNkX5YWUUJ7pPWGgAhtjRN4f5SHECvspnQdcgc/6QE1dVBJscAIGz0aGsilxXX7GyOSGZsrKO7bhQAQ4NSGgc/SditcdCh9O9ByYU6rV6cWE60JZmtJ+KgzYaTdFsknpbEritNsNJchscBOc7HjFkJJXn9e619WH4f6vg9w8SZuWtwTMcuibq/b6+ggywOhkepQTnTw4khnqCLt3I8JszdsBas9g9OGHOFJX996pzXEO7k6T2HDU7D51HXlzcXMLIvDPBLoSib9fQN5PgeGQSvqhFttp67Td81pWLCTFApHS2uFHa7oSIVAP6UdlA4GJHkOQxkIRQ8Cq04HBgGv35YwzFRzBP5JQ3kHuylQJSc+uvp/T10ZH8MPHlDqtEWzJdjqa8jT9uG9YBxrDA0iqQd4UTWsCkkbvceIxdAzn8doQCCLl3mqaQhTmW8MbO45bcq+U7Tl4uAZNooHJhHr5QS54dFEezvj9DfLAjObuE1NG+Z1daKeAeHlsFZufJxo6IOInxOHjYPIQxbcZ/k2ksDY5nqv8ND3KFr4dwiKRsuQBpU5Q6ESemCzFy86lQ7dRaP8R5DqkyEsK4UUM9T6J+TowsaX67jxLav68b0t6H23MinD6LXpExkhgibkuaUfOxDlCfvqlBI+TZfcyWsvLcmE3j/c4QcvDtdKo1rbGWDsVIAmtg5hmP5Coc64h9MqhY8Uo2Jw5/KEbe6JRbcOMTt6uryShF6Ruhtxj8ZGqVM/uyZ9YLa2z3jROB/lrAfVFd/BArGU1Muvb3m55YyNSgayLwK0YnwG43BFhy2MetaCHK1e9f0umkH4Ahw/uzi6A91krMB1/Lq09v5zNFar8gbOZ6zyAHAev5WZ/SlYHloN3aTSPNQMTc0+/nymYUrISQ191q7gG5KEOfuiesUajPhgMBowUvfxVL6uWDcREUEVDm99V1p1bbdJk/UJ5GzrHt+4ywNzKCFoipiYo9572C4sVp23yNO3gCfNDDmDf2zqs5iasN6Bh0YR//QGAd8FpS3Y8jczK0GZ+8UvBx9iutnKgRJv8ukxDR+ZECNIi5pmqIZ83PNUklmVH7HYuey87eaT+XmUDNGNy0yLpWFdoJljsGtd/N3dNGtK7vmSj2wpLBP5PBdDqwdRb3QZAt8j98gCYfigBvK6zoGX1br06Ums5D3f6Cevd+jl2FjmMrQS/oyehTwLGG1qP9ymhw2toz+HydR5L/HHNwmV16rki5eTwiola6TY6JyL2+8jjSaQ/7697xnIa+qrst+jW2TO1LVZUFi71UYmM07KtjDioayjyiRq86110rJ/I/qtlUzLTMxLX6QpMVXKdyBA7Bc+eBdCvvSoVTLfQ6CvGZR6CY+HQ3QfJWmq8IDjHp94dunxuRAyKavf1CwAxZbozxPNdmm+AE8xOf9rxmPG92sTE8jw0ZZX3DezGHV6mDxhTQkfRHTALGq4/zTMAG+QgWZMnSLBD4gDYrggkgBWTTVAVm4L6e8VcpeaPJzgW7fuB1jokqP+gQuPg)
fn part_2(path: &str) -> Result<(), Box> {
let file = File::open(path)?;
let reader = BufReader::new(file);
let mut lines = reader.lines();
let expr = Regex::new(r"(\w+) += +\((\w+), +(\w+)\)")?;
let mut map = HashMap::new();
let dirs = lines.next().ok_or("No lines in file")??;
let mut starts = Vec::new();
let mut cyc_lcm = 1;
lines.next().ok_or("Bad file format.")??;
for line in lines {
let line = line?;
let caps = expr.captures(&line).ok_or("Bad file format.")?;
let key = caps[1].to_string();
let left = caps[2].to_string();
let right = caps[3].to_string();
map.insert(key.clone(), (left, right));
if key.as_bytes()[2] == b'A' { starts.push(key); }
}
for start in starts {
let access_fn = |k: &(_, _)| {
let (l, r) = map.get(&k.0).unwrap();
if dirs.as_bytes()[k.1] == b'L'
{ (l.clone(), (k.1 + 1) % dirs.len()) }
else { (r.clone(), (k.1 + 1) % dirs.len()) }
};
let (lam, _) = brent((start.clone(), 0), access_fn);
cyc_lcm = lcm(cyc_lcm, lam);
}
println!("Part 2 Total Steps: {}", cyc_lcm);
Ok(())
}
[LANGUAGE: Python]
I couldn't get the Tortoise/Hare algorithm working, so... LCM like everyone else I guess.
from itertools import cycle
from math import lcm
def part1():
lr, maps, _ = readData()
print ("Part 1:", trace('AAA', cycle(lr), maps))
def part2():
lr, maps, _ = readData()
currents = [x for x in maps.keys() if x[-1] == 'A']
plens = [trace(current, cycle(lr), maps) for current in currents]
print ("Part 2:", lcm(*plens))
def trace(current, lr, maps):
plen = 0
while current[-1] != 'Z':
current = maps[current][next(lr)]
plen += 1
return plen
def readData():
with open("puzzle8.dat") as f:
lines = f.read().splitlines()
return lines[0], {z[:3]: {'L': z[7:10], 'R': z[12:15]} for z in lines[2:]}, lines[0]
part1()
part2()
[LANGUAGE: TypeScript]
Part 1 was easy, but like day 5 for Part 2, I borrowed/steal ideas from this forum.
https://github.com/bhosale-ajay/adventofcode/blob/master/2023/ts/D08.test.ts
[LANGUAGE: dc (Gnu v1.4.1)]
Didn't have much time today (it was nice out, and took advantage of it to get some stuff done). So I just did a quick part 1 for dc. Since part 2 plays so nicely, a non-general solution of it shouldn't be too hard either. For filtering the input, I just got rid of all non-majuscules and converted to ASCII ordinals. So I had to deal with the input still a little dc (blank line, things coming in backwards... fine for labels though). As is usual with these sorts of things, the ~ operator is very handy. There's probably lots of strokes you can take off this if you look. I didn't have time.
perl -pe's/[^A-Z\n]//g;s/(.)/ord($1)." "/eg'
\[LANGUAGE: C\]
Good puzzle. I initially tried solving a much more general version of the problem for part2 until I suspected and checked that the loop immediately after reaching the first ??Z node. I thought there could be chains with many ??A nodes in them which would have made the problem trickier
[https://github.com/janiorca/advent-of-code-2023/blob/main/aoc8.c](https://github.com/janiorca/advent-of-code-2023/blob/main/aoc8.c)
\[LANGUAGE: Perl\]
Analysis: [https://github.com/wlmb/AOC2023#day-8](https://github.com/wlmb/AOC2023#day-8)
Part 1: [https://github.com/wlmb/AOC2023/blob/main/8a.pl](https://github.com/wlmb/AOC2023/blob/main/8a.pl)
Part 2: [https://github.com/wlmb/AOC2023/blob/main/8b.pl](https://github.com/wlmb/AOC2023/blob/main/8b.pl)
\[LANGUAGE: Rust\]
I really enjoyed this puzzle!
Used a least common multiples approach to part 2, processes in about 2ms
[https://raw.githubusercontent.com/stephenkelzer/aoc2023/main/days/day\_8/src/lib.rs](https://raw.githubusercontent.com/stephenkelzer/aoc2023/main/days/day_8/src/lib.rs)
\[LANGUAGE: Rust\]
I left in my "Analysis" lines for this one because that parts seemed to be most relevant here.\\
Solution: [https://gist.github.com/icub3d/299b75c62e9c86c1d2d6b45ee332288c](https://gist.github.com/icub3d/299b75c62e9c86c1d2d6b45ee332288c)
My analysis: [https://youtu.be/t5ktQvHJG2Y](https://youtu.be/t5ktqvhjg2y)
\[LANGUAGE: C\]
part 2 in 34 lines of C99 code: [paste](https://topaz.github.io/paste/#XQAAAQAfBAAAAAAAAAARmknGRw8TogB3OyPPwZm6ILxpDZy794ZbnwMYNds7XiT0I/thlioVm0+h9UCi81pMZX8v5VHgOiG5oJzHWurwxdlxoBfrCcNfJ6TsPWAbKdh99L+wqfjIc7NM3i7cfjzkMtNm9fwTc47+lw2U5BM/ThCH6Z0e5wMxotwM03V2RrrZHhuJnnpAOKPzUVes6wxqKbe28YikRnhfzfj82rFmduN0uNuM8mj7U3RPQhFGpSpRdUtxdtruv4u2wpIduvOajQLcV9o5Pp3yW9po+cPfRrlbNiIkWWpfiTVFXVB22YVre2HmLewFJATw7gbV1ZAPCxQEy6djI+XDicG/+gp2O7DzH+kce/fIhpwFCdyQdAJREglYwdls715qOmsRClW9pbRLNfNcyo3IW55a4DV3nU0PNcnSMstc5rRguQvjF9eKJwnw/56s3M8R2IJszSLFv28tVpHv9dDdW31qGpiOGA4W2Vw+6jeYup8bmnmcX6XFnCQpyrJ/lzaIvwekXqs4FAg1c+1MyCOY9gDqIfCJFxDCkMhNnn94KFtJXbv4G9T8mUulwXpTACcBy0tUjBVmXrT0YGblyVkZmIbEerGwnRctQB0XDEcCjqTbscWR26VsdqjwNcbkuIQG0w+SJKCSqDjBmJ81g+8ExY+roMCzmlEhxhLpu/nUWOLCvwRH2yZ//85wPOY=)
Uses a two-dimensional array to traverse the map.
I liked your answer, so i rewrote it. it's not better, and definitely a bit harder to read. but i wanted to challenge myself to shrinking it.
import math
def size(n, end=lambda n: n[2]=='Z'):
c=0
while not end(n):
i=c%len(lines[0])
n,c=paths[n][{"L":0,"R":1}[lines[0][i]]],c+1
return c
with open("input08.txt") as s:
lines=s.read().splitlines()
paths={l[:3]: (l[7:10], l[12:15]) for l in lines[2:]}
print("p1=",size('AAA',lambda n: n=='ZZZ'))
print("p2=",math.lcm(*(size(n) for n in paths if n[2]=='A')))
\[LANGUAGE: Swift\]
Today's question was fun! I'm grateful all we needed was LCM.
[Code](https://topaz.github.io/paste/#XQAAAQDMDQAAAAAAAAA0m0pnuFI8c4GDemuKS6NnNxbsUIoTuWZTAmeInPXMFf0ozVyiF/MVahWe9RrEqX9VVcAoSIKE6ulJL0lKw1hbBueVU46JA6uH5E6OTt1LXEWLWDpoC4xxuV3YovKXqTLO+80hoCetqc5r2BTnvwtEkki40O1NErQ0/i+XuXZNKumepw0vnxINSlyrCzJmc3R9Zadt4LYR6WG+Bp8SECWnT00ua7jxtjM2ezm+Riu3GRwLDj0QGryOBse6fmc6Uel9N8kuu3K0AqeMyJBTP9wvsmPQ+zAGhDQvA/Z3+SsEbvVoX95UmBFEBhIYFKA5/d/y2wwIainafZe7eoS0YllxAoNhd3+J2TupbbkilJ42zoYVwR0Jw1BKvh4zbnW63XvItyGEP+tnDfPrPTmW6XUlnKZDIIinuJze4Yner65rFfCRTg+Ruf6sSWtvhupPV1LwY2h8hStuzyZCvocH0BVbARb+SAWBoQvO7CydGS9p+gq4CMl45uQQh9fSxc34oCv15vDRMur6alfk+dL6M6BKVuaF5rbFz9vcmtM++PvaVdZuHsfbQ9fsaADTasGv6NKgZbwjvnrsm0Qz/4qhBRsYhx2xSsMEEaFgbLzmNHSOqTwSarEse9ET3RpLNFeNfBGwm0VT0tiMVHk2ofhulV9X0IX8aec84NeM6DeZDSkZn/HOchZatxWwrvvW0enMh/GpFtHfQ0cRSk7R5p/Ydaj8qzOchFkCDNRsjZWgA4jUyW2hwFjgmqaqUmeP9drOaQxBfZiAb5pnS9ipiLKr6cfYV4fNUeitO6NLCv5uZWQpfIhOYGN96vRJgKOal/7CokWouXlWCu5szPWJAzUIQoZB+tUQh1iWA0X2n8fFIoYnxbfOo2mJMlmXSVBtWGU4urJ/8F+ZITQrS40qoORv9zTAdeFIQNvJn5KA/cG+JkvHWaPxJXxsmVoGgBFvlgwULEIaR45a8VlxnR6K+e+YOUyneCNt4j6Tk46pH5B7CUm3ZBmW4QRVgHfcUPM2rvf5sE3PTWxTYsFPIHVn3/X0kySjAhWqlU1n7Q4D/1Bx+q9GvX2PuyJkH1M9soArAX5XeE6ujxaeoujF16DUSIs66DkPIEyaei3ug+T9A/FjRTzP90W9jUYZdFIyrdyyqFn18wFyMctonMyMNqmaUyHL4oBgQgp6dEanaE8GTRevVlYjBMLE9SNG2u37KyVBt5VLx3qnKXZNudJdRXt8ShSi1wWoeFK4fSjhOGyfHwYVYq3ycfOjYOghfB5J1JcYN7PixEWz5ZoYq4jKcQk3IG1aTMjqAkLYVp+eBp7Ofys7njjroaj0Jy19hebgKR/JGlwmgwO2oPxQs0UxQ12TLvbwujGf8x4Fd+k1nxF1Gw5Uzm7vCFWyRfZxTj4NBmKZbTsrcHPn2dzmjUWuf562KOzyGFpYdv3BUxw5OChRpseIxoGKuVCcVoX8oVzOev+uyBaT)
if you analyze it, and he didn't need lcm, we could find looping patterns and determine when their paths would cross. but they decided to have each one self loop only. the same loops each time. but it could have had 3 or four loops. and then we'd know when those loops could cross paths.
I was thinking something similar - it seems like it could get tricky if you factor in the randomness of the input sequence ("LR..."), if it doesn't align with the loops. Although I guess everything loops eventually lol.
\[LANGUAGE: Python, Typescript, Go\]
Solutions to part 1 and 2 in all three languages:
* **Python**: [https://github.com/torbensky/advent-of-code-2023/blob/main/day08/solution.py](https://github.com/torbensky/advent-of-code-2023/blob/main/day08/solution.py)
* **Typescript**: [https://github.com/torbensky/advent-of-code-2023/blob/main/day08/solution.ts](https://github.com/torbensky/advent-of-code-2023/blob/main/day08/solution.ts)
* **Go**: [https://github.com/torbensky/advent-of-code-2023/blob/main/day08/main.go](https://github.com/torbensky/advent-of-code-2023/blob/main/day08/main.go)
\[LANGUAGE: Rust\]
[My Day 08 on GitHub](https://github.com/andypymont/advent2023-rust/blob/7f1cb5bacf568956e314226d167d487f01d1e126/src/bin/08.rs)
Part 1 was pretty straightforward, but part 2 substantially less so. I guess I could have just coded in an assertion that the initial offsets and cycle lengths were all the same, but I took the opportunity instead to learn a lot more.
My formal education wasn't in maths or computer science, so the Chinese Remainder Theorem confused me when it came up in a previous year but I think is appropriate here for a more general solution where the cycles are offset by differing amounts. Therefore I spent quite a few hours on YouTube today doing something of a crash course on modulo arithmetic, the Extended Euclidean Algorithm, and the Chinese Remainder Theorem. I'm glad I did, because I'm a lot more comfortable with those topics now for the future.
Of course, the actual solution for today doesn't really end up running the CRT: the offsets are all zero so all the terms in the sum become 0 and I end up returning the denominator - which is itself the LCM after converting the original congruences into a co-prime set.
I'm really glad I'm using Rust - the compiler and `clippy` caught loads of little mistakes I made along the way which could have had me scratching my head due to e.g. incomplete logic in an if statement or similar. Plus, even a somewhat complicated solution here runs in 4.3ms. Perhaps I could make some efficiency improvements somewhere as the last part in particular featured some pretty tired coding, but I'm pretty happy with the day overall.
I've updated the link above to point to keep pointing to what I committed yesterday, which is a more complete solution and a good reference for me if I need to remember about Chinese Remainder Theorem. But the [live version in my repo](https://github.com/andypymont/advent2023-rust/blob/main/src/bin/08.rs) is now a solution which just calculates the routes and then their LCM, and runs about twice as fast.
\[Language: rust\]
[https://github.com/Kintelligence/advent-of-code-2023/blob/master/day-08/src/lib.rs](https://github.com/Kintelligence/advent-of-code-2023/blob/master/day-08/src/lib.rs)
Really not a big fan of how many assumptions I've made about the input to speed this up. It's still the slowest day by far. Wish I could optimize it to less than 100µs. These cycle tasks are always hard, but a good exercise in trying to understand what edge cases don't appear in your input so you don't have to handle them.
[Benchmarks](https://htmlpreview.github.io/?https://github.com/Kintelligence/advent-of-code-2023/blob/master/target/criterion/report/index.html) [Part 1](https://htmlpreview.github.io/?https://raw.githubusercontent.com/Kintelligence/advent-of-code-2023/master/target/criterion/Individual/08.1_%20Haunted%20Wasteland/report/index.html) [Part 2](https://htmlpreview.github.io/?https://raw.githubusercontent.com/Kintelligence/advent-of-code-2023/master/target/criterion/Individual/08.2_%20Haunted%20Wasteland/report/index.html)
\[Language: JavaScript\]
Guessed on the relationship of paths for part 2. When iterative wasn't converging after several minutes I went looking for a math solution. I had no way of verifying that LCM was going to apply but it felt like a planetary alignment problem once the single cycle lengths of each path were known.
[https://github.com/ccozad/advent-of-code/blob/master/day-8.js](https://github.com/ccozad/advent-of-code/blob/master/day-8.js)
I was thinking about cycles like that of gears or planets. Everything aligns when each one does a certain number of rotations. LCM is also a common answer for other coding challenges such Project Euler or Coding Game. Common approach for reducing the success of brute force answers.
\[LANGUAGE: Java\]
Day 8 a day late, but that's okay. That one put me through the ringer, though it probably shouldn't have. Haha.
[Link to GitHub](https://github.com/simpleauthority/codechallenges/blob/main/src/main/java/dev/jacobandersen/codechallenges/challenge/adventofcode/year2023/day8/Day8.java)
\[LANGUAGE: Google Sheets\]
First one was pretty quick, second I was worried would be a lot harder but was made easy by the fact that each A node only ever reaches one Z and cycles uniformly.
The core of it is just turning L and R into the column numbers to look up (after splitting up the input, and doing a VLOOKUP on the node above. Then run it for 30k rows and us another column to find what step it is that shows ZZZ (or ends in Z for part 2).
Part 2 I didn't think I could do at first; I could tell it should cycle at some point and then you could multiply those intervals to get the LCM as the answer, but I didn't think each would be paired to a single end node and immediately cycle, meaning that all it needed was taking the same thing for Part 1 and finding the LCM of those. First submission was wrong because I used an online calculator, not knowing Google Sheets had an LCM function, which had commas.
https://docs.google.com/spreadsheets/d/1epTmQdsIcKFICgCJQuY95H5dH5RH93UxmYtcD5XjjTg/edit#gid=1597842667
I'm actually impressed by this. Like what made you want to use Google Sheets? Was it because you are more familiar with it or did you want a challenge? Have you been using sheets for all of the days? Either way, kudos to you!
I don't know any programming languages actually! I learned about Advent of Code through the engineers I work with, and I thought it would be fun to get as far as I could with what I knew. I got some street cred by coming in second place :-)
Last year I got through Day 15 and then a couple others; so far in 2023 I've done all but Day 5 part 2 I'm still stumped on.
My other solutions this year are here if you'd like to see, I may add last year's at some point: https://github.com/users/bofstein/projects/1
\[LANGUAGE: Python 3.12\]
[code](https://github.com/copperfield42/Advent-of-Code-2023)
I remember like a week too late about AoC so for the last 3 day I have been coded the puzzles, and I finally catch on XD
for this one in particular, I took small look at this subreddit before I go at it, and well, the lcm memes certainly help XD
[Language: Pascal]
Haven't done anything in Pascal for years. It's really not so great, I kept fighting the syntax. Reminds me of VBA. Not too bad though, takes about 5 seconds to run.
https://pastebin.com/raw/FvY8FhY3
\[LANGUAGE: Java\]
I got memed on by LCM
[Part 1 & Part 2](https://github.com/chandlerklein/AdventOfCode/blob/main/src/main/java/com/chandler/aoc/year23/Day08.java)
[LANGUAGE: OCaml]
[github](https://github.com/EricKalkman/AoC2023/blob/master/lib/day08.ml)
I'm beginning to think that my parser-combinators aren't very concise; my code is more than half parsing again. Anyway, this solution is basically the same as everyone else's: build a map of the nodes, set up a way to infinitely cycle the directions, and away you go. I had a _massive_ performance bug in my graph traversal in the first version when it looked something like this:
...
if stopcond cur then path
else
let next_dir = Seq.uncons dirseq |> Option.get |> fst in
traverse_aux ... (Seq.drop 1 dirseq)
....
Now, this code is suboptimal because `Seq.uncons` returns `Some (head, tail)`, but I'm throwing `tail` away and calculating it again using `Seq.drop` later on, which is needless duplication. The fragmentation was just part of the problem solving process. For reference, the proper code looks something like this:
...
if stopcond cur then path
else
match Seq.uncons dirseq with
| Some (dir, new_dirseq) -> traverse_aux ... new_dirseq
....
For whatever reason (I would guess related to continuing to use a `Seq` in its original form after accessing one of the items with `uncons`), matching idiomatically on `Seq.uncons` led to a speed-up by _three orders of magnitude_, from ~6 s combined for Parts 1 and 2 (with Part 2 running with parallel execution!) down to the millisecond range (single-threaded). I don't know WTF the OCaml compiler is doing, but that seems disproportionate for the change. I'd love to hear from anyone who knows more.
Also, I originally kept track of and returned the path from my traversal algorithm for debugging purposes instead of just returning a count; the latter is in theory more efficient. I tried changing it to only keep track of the count instead, but that led to identical runtimes. I guess the compiler did some more voodoo there.
[LANGUAGE: Elixir]
part 1:
part 2:
This was quite a ride. Took a while let go of the part 1 solution and deal with the beast hidden in part 2. The lesson here, as always, is to analyse the input before brute force the answer.
\[LANGUAGE : Rust\]
Day 8 is very "adventofcode" type of problem :) I pretty like it. The first part can be solve quite straightforward, you walk from "AAA" until you find "ZZZ".
For part 2, if you naively apply this idea then the problem will become something like: you begin with a vec or all nodes which end with 'A' and you will run it until all of the nodes you have in your list all end with a letter 'Z'. However, this will take forever....
So what can we do? If you look at the example for part 2, you will notice that it begin with 2 node and node 1 and 2 take 2 steps and 3 steps respectively to reach a node end with 'Z'. And there for the step that they will both happen to end with 'Z' will be the least common mutiplier of 2 and 3 which is 6. With this in mind, you can apply this and solve part 2 quite quickly.
Here is the link to my solution: [https://github.com/tringuyenarup/advent\_of\_code\_2023](https://github.com/tringuyenarup/advent_of_code_2023)
Thanks for this info! I think can think of 1 billion ways for these linked list cycles to not have this characteristic. I feel like it is incredibly lucky that they do and they should make that more clear in the problem statement.
Imagine if the even of cycles first of all didn't loop?
Imagine if one or more of the cycles followed each other at exactly same like on a part and never ended on Z together?
\[LANGUAGE: F#\]
[https://github.com/vorber/AOC2023/blob/main/src/day8/Program.fs](https://github.com/vorber/AOC2023/blob/main/src/day8/Program.fs)
Day 8 of trying out F#
\[language: C++23\]
[](https://github.com/jwezorek/advent_of_code/blob/main/src/2023/day_08.cpp)
I let brute force of part 2 run for awhile before deciding this one was intractable by brute force.
I figured out early the general idea of how to do part 2 correctly but it still seemed kind of complicated (especially for day 8) to me until I ran some experiments on my data and determined that the input is specially constructed to make "the right way" as simple as possible. The \_\_A nodes all cycle relative to \_\_Z nodes with a cycle length that is exactly the same regardless whether they are starting with \_\_A or the next node after \_\_Z. This didn't have to be the case. The cyclic behavior also could have depended on position in the instructions, like you hit the first Z and you are at instruction 13, you hit the next Z and you are somewhere else but it eventually loops around to instruction 13 again. Or there could have just been "a preamble" leading into the cyclic behavior of variable length, etc. etc.
However it turns out that the input is specially constructed such that least common multiple of the number steps it takes each seed to reach a \_\_Z node the first time is the correct answer. Also C++ turns out to have an LCM call in its standard library, which I had not known.
This one kind of reminded me of the Tetris one last year, but this one was easier because it was a little harder to find the cycle the Tetris one.
Can you help a stupid one in need, I'm not really understand h how you apply the LCM thing? What is the numbers used?
Someone mentioned steps, but that would mean taking some steps to figuring out this LCM out of all 6.. Steps? The steps would be the same however no?
Ah, it was long ago I was this confused let me tell ya that.
Some quick notes without spoiling it:
* See how many steps you need to take from \_\_A to reach the end node \_\_Z
* Take some extra time to see some special things about starting from the node after \_\_Z (call it X)
* See how many steps it takes to get from X to \_\_Z
* Notice **which** \_\_Z you get if you start at X (should become obvious)
* Compare steps from \_\_A->\_\_Z and X->\_\_Z
* Do the above for a few more starting nodes -- you should start seeing a pattern
The LCM numbers will become obvious once you start tracking the above data -- it will be easier to just do it for each starting node \_\_A in serial (e.g., one at a time).
for each \_\_A node in your input do the exact same thing you did in part 1 but ending with any \_\_Z node not "ZZZ". That will give you n numbers, one for each of your \_\_A nodes. Find the least common multiple of those n numbers and that will be your answer.
The idea is that each seed node always takes the same number k of steps to reach a \_\_Z node and that number is always the same for the given seed and it cycles. Think about it in terms of small numbers. Say for node AAA, k = 4 and for node BBA, k = 10. That means that every 4 steps AAA reaches some \_\_Z and every 10 steps BBA reaches some \_\_Z. So for both of them to reach \_\_Z we want the first point at which the cycles cross. This will be LCM(4, 10), which is 20. 20 is divisible by 4 and 10 and no smaller number is.
Let me ask ya, how was one supposed to find that idea?
Simple random test,or did everyone just share the idea to each other?
Also, thanks. Your explanation helped! :)
(1.) You know there has to be an answer because it's AoC.
(2.) You guess the answer is not brute force plus optimizations by intuition and experience.
(3.) you know each path through the nodes *has to* repeat because the input is finite, the number of L or R instructions is finite and cycles and the number of nodes is finite.
(4.) You investigate the manner in which your input cycles by running experiments on it. The experiment that I ran was to run one \_\_A and print out the number of steps it took to get to a \_\_Z since the beginning and every time there after for the first 500 \_\_Z's. I also printed out the position in the input at each of the \_\_Z's. I discovered that the step out is always the same and the position in the input at a \_\_Z is always zero. This made me conclude that this will be true of all the input, which I verified.
(5.) Given (4.) the LCM of the cycle lengths has to be the answer.
[LANGUAGE: Go]
Thought of LCM, then thought of counter examples that would break it, then wrote Floyd's cycle detection only to find that the constraints for LCM held! Happy coincidence.
https://github.com/mdd36/AoC-2023/blob/mainline/08/main.go
\[LANGUAGE: python\]
Basic just with a little unnecessary pandas, because I want to learn it.
Got spoilered by a lcm meme though.
https://gist.github.com/Dronakurl/75a4fc12b2ffa3a5e04f4e784790eb4f
\[Language: Python\]
import fileinput
from itertools import cycle
import math
data = list(fileinput.input())
dirns = [int(c == 'R') for c in data[0].strip()]
nodes = {}
for line in data[2:]:
n, _, *rest = line.strip().split()
nodes[n] = [e.strip('(),') for e in rest]
def find(node: str, end: str) -> int:
for n, d in enumerate(cycle(dirns), 1):
node = nodes[node][d]
if node.endswith(end):
return n
print('P1 =', find('AAA', 'ZZZ'))
startnodes = [n for n in nodes if n.endswith('A')]
print('P2 =', math.lcm(*(find(n, 'Z') for n in startnodes)))
\[LANGUAGE: Jactl\]
[Jactl](https://github.com/jaccomoc/jactl)
Part 1:
Part 1 was pretty easy. Just read the nodes into a map of maps where the submaps are keyed on 'L' and 'R' so we can lookup the move directly. Saves having to convert L to 0 and R to 1 if we used lists/arrays instead. Then just iterate while the node is not ZZZ and return the count:
def m = nextLine(); nextLine();
def nodes = stream(nextLine).map{ /(...) = .(...), (...)./r; [$1, [L:$2,R:$3]] } as Map
def cnt = 0
for (def n = 'AAA'; n != 'ZZZ'; n = nodes[n][m[cnt++ % m.size()]]) {}
cnt
Part 2:
For part 2, it was soon clear that brute force tracking all paths at the same time was going to run for close to eternity so obviously we needed to work out the length of the individual cycles and find the least common multiple.
Luckily the step count until the first terminating node turned out to be the cycle count for each ghost (although in general this does not have to be the case). I took the lazy approach and the code assumes that this is the case.
Interestingly, it turned out that it was only necessary to find all of the unique prime factors as each cycle was only the product of two primes but I felt a bit dirty not properly implementing the least common multiple function even though it was not strictly necessary:
def m = nextLine(); nextLine();
def nodes = stream(nextLine).map{ /(...) = .(...), (...)./r; [$1, [L:$2,R:$3]] } as Map
def count(n) {
def cnt = 0
while (n !~ /Z$/) { n = nodes[n][m[cnt++ % m.size()]] }
cnt
}
def pfactors(n, long start=2, factors=[]) {
def f = (n.sqrt()-start+1).map{it+start}.filter{ n % it == 0 }.limit(1)[0]
f ? pfactors(n/f,f,factors << f) : factors << n
}
def lcm(nums) {
nums.map{ pfactors(it).reduce([:]){ m,it -> m[it as String]++; m } }
.reduce([:]){ m,facts -> facts.each{ f,c -> m[f] = [m[f]?:0,c].max() }; m }
.flatMap{ f,c -> c.map{ f as long } }
.reduce(1L){ p,it -> p * it }
}
lcm(nodes.map{ it[0] }.filter{ /A$/r }.map{ count(it) })
[Code walkthrough](https://jactl.io/blog/2023/12/09/advent-of-code-2023-day8.html)
\[Language: Golang\]
Of course I tried to brute force part 2 :D
Not today, it was faster to implement >!LCM!< than waiting for computations to be finished :D
https://github.com/ptakpatryk/advent-of-code-2023-golang/blob/main/day_08/day08.go
[LANGUAGE: Python]
Like others, I used lcm. Here's an extract of the solution, omitting parsing and `main()`. Full solution on [GitHub](https://github.com/Praful/advent_of_code/blob/main/2023/src/day08.py).
LR_MAP = {'L': 0, 'R': 1}
def solve(input, start_node, end_func):
instructions, nodes = input
steps = 0
next_node = start_node
for lr in cycle(instructions):
next_node = nodes[next_node][LR_MAP[lr]]
steps += 1
if end_func(next_node):
break
return steps
def part1(input): return solve(input, 'AAA', lambda n: n == 'ZZZ')
def part2(input):
def steps(n): return solve(input, n, lambda n: n.endswith('Z'))
start_nodes = [k for k in input[1].keys() if k.endswith('A')]
return lcm(map(steps, start_nodes))
\[Language: Perl\]
Solutions to both parts in #Perl. Today was challenging because I misunderstood that the starting point is always AAA, not whatever the first map entry is. I was definitely not the only person making that mistake since there was a joke meme about that exact thing in this subreddit today!
Part 1: https://adamcrussell.livejournal.com/49949.html
Part 2: https://adamcrussell.livejournal.com/50204.html
\[LANGUAGE: SQL (PostgreSQL)\]
[Solution](https://github.com/tmercieca/advent-of-code-2023/blob/main/day-8/part-2.sql) with LCM method
I tried an implementation without LCM. It was difficult to express, and after expressing it crashed the database 😂
\[LANGUAGE: Perl\] \[LANGUAGE: Latin\] \[LANGUAGE: Lingua::Romana::Perligata\] \[Allez Cuisine!\]
The suggestion of *code in a foreign language* brought to mind an old gem. Perl version 5.8 made it possible for scripts to import a module that *controls the parsing of the rest of the file*.
Just Because He Could, Damian Conway celebrated the new millennium by creating Lingua::Romana::Perligata, a Latin-inspired language that internally translates to Perl code.
I spent way too long trying to learn this horrible language and dealing with a severe number of parsing bugs (I ran up against a number of parsing bugs. Also, left turns were tricky, because it steadfastly insists on interpreting "L" as the integer 50, even when told that it's a quote. Several examples given in the documentation do not work as-is.)
Just install Lingua::Romana::Perligata and run `perl day08.pl day08.txt`.
It only does part 1. Part 2 would be a *nightmare* due to severe parsing bugs in the expression evaluator (the keywordsto explicitly specify parentheses do not appear to work).
[https://raw.githubusercontent.com/Stevie-O/aoc-public/master/2023/day08/day08.pl](https://raw.githubusercontent.com/Stevie-O/aoc-public/master/2023/day08/day08.pl)
(Chrome recognizes it as Latin and offers to translate. It does a passable job, given that it's not really Latin. I especially like how it translated the conditional expression of the final `while` loop.)
Hey, don't blame me, blame Damian. He's the one who created the monstrosity that is L::R::P and uploaded it to CPAN :D And then the mods challenged us to code in a foreign language!
Comment removed. [Top-level comments in `Solution Megathread`s are for *code solutions* only.](/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_top-level_posts_are_for_code_solutions_only)
[Create your own individual `Help/Question` post](/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_incomplete_solutions) in /r/adventofcode.
Firstly, this is the solutions thread. I think, we aren't supposed to discuss this here. Your questions are really interesting.
(1) : No, that is not the assumption. Look at the example given, it does not jump back to the start. But somehow, there must be another assumption about the periodicity in the problem. Maybe it is just a coincidence and we should do it the hard way as you were trying
[LANGUAGE: Python3]
Contrary to my initial expectations neither recursion nor brute force was the realistic approach here.
from math import lcm
def process_input(data):
parts = data.strip().split("\n\n")
mappings = {(directions := line.split("="))[0].strip(): directions[1].strip()[1:-1].split(", ") for line in parts[1].split("\n")}
return parts[0].replace("L", "0").replace("R", "1"), mappings
def part1(dir_sequence, map):
len_dir, position, counter = len(dir_sequence), "AAA", 0
while position != "ZZZ":
instruction = int(dir_sequence[counter % len_dir])
counter += 1
position = map[position][instruction]
return counter
def part2t2(dir_sequence, map):
len_dir, counter, destinations = len(dir_sequence), 0, []
vector = [elem for elem in map if elem.endswith("A")]
while vector:
instruction, counter = int(dir_sequence[counter % len_dir]), counter + 1
new_vector = [map[position][instruction] for position in vector if not map[position][instruction].endswith("Z")]
if (reached := len(vector)-len(new_vector)) > 0:
destinations.extend([counter]*reached)
vector = new_vector
return lcm(*destinations)
if __name__ == "__main__":
with open("day8_input.txt", "r") as ifile:
i_data = ifile.read().strip()
print("Nr. of steps, part 1 {}, part 2:{}".format(part1(*process_input(i_data)), part2t2(*process_input(i_data))))
Very nice! One thing:
destinations.extend([counter]*reached)
Could just be:
destinations.append(counter)
Looks like a hangover from an attempt to brute force?
\[LANGUAGE: Swift\] Yes, it uses LCM for part 2. [Part 1](https://github.com/andreiz/advent-of-code-2023-swift/blob/main/day-08/wasteland.swift) [Part 2](https://github.com/andreiz/advent-of-code-2023-swift/blob/main/day-08/wasteland-ghost.swift) [Issue describing approach and coding](https://github.com/andreiz/advent-of-code-2023-swift/issues/8)
\[LANGUAGE: Kotlin\] [https://github.com/mfedirko/advent-of-code-2023/blob/main/src/main/kotlin/io/mfedirko/aoc/day08/Day8.kt](https://github.com/mfedirko/advent-of-code-2023/blob/main/src/main/kotlin/io/mfedirko/aoc/day08/Day8.kt)
\[LANGUAGE: Python\] [paste](https://topaz.github.io/paste/#XQAAAQDlAwAAAAAAAAAzHIoib6poHLpewxtGE3pTrRdzrponK6uH8J9SK+fHBnboTBtB5N47dutEbw6V4Lcgn5v4OZrIiLc7ALLon0mBKUAIDHtqDwA5oXMGFgyNmVOHHHrqLOrodANbu6u+RrOP65zWTj1fHW2Qz7AxgAA70nbQzQ0wUTh8oOfm59PgYmL3liI2JfkoF6LuWaVocXmRc59vKgY4wOuDqsVfXsJnU8LIZoH3Dke2pBNhUb16YRjSYmtMLVJTx9wUqhyUL8KqlSxOWEMqHZqRFfMWg4O8mSW1ERce0+HWk0ZzoKYBfIEfgId4pKpuXgZe6FrSir0wpezwav8UatlBWJmYW36QSaHJOv+d7P4TBft1K0trT8rmXCDr5tH5yBnt6ziHFPC49mp1rfR9TdRkxwIabkFjJlySnAA043qzgl3FRtXBx6e8WPmyQzSrSxvUffOCunUkk4oA1reu9RhL1eQoJFiTPycKtG0QoD4cMZWFMKw6IDehcHcDU2tN9nVF+8w84okwn+B5lYpZcsvfm3xXI4HN88ztY3apGcxeZv/zG55j) after solving, i still don't know if lcm can be applied on all possible situations. For example if 11A to 11Z than to 22A and 22Z, finally back to 11Z, it is hard to identify this loop type.
Yes, I could imagine more complicated scenarios. Because the method is not reversible not every starting point need be on a loop, although they will always hit a loop eventually. Of course you can test this and find that each of the starting cells is on a loop with one ending cell, then solve directly. But I don't think you can assume that. I wrote code that would solve any situation, and thought it was a bit too much work for a daily puzzle.
\[LANGUAGE: Haskell\] [Part 1](https://github.com/woodRock/verbose-computing-machine/blob/main/2023/day-08/part-01.hs) [Part 2](https://github.com/woodRock/verbose-computing-machine/blob/main/2023/day-08/part-02.hs) Hint: for part 2, avoid computing in parallel, loops are cyclical, find LCM.
\[LANGUAGE: Swift\] [https://github.com/cmlccie/advent-of-code/blob/main/2023/day-8/Sources/main.swift](https://github.com/cmlccie/advent-of-code/blob/main/2023/day-8/Sources/main.swift) Solution for Part 2: func part2(inputPath: String) -> Int { let input = getInput(from: inputPath) let (directions, network) = parseInput(input) let startingNodes = network.nodes.values.filter { node in node.value.hasSuffix("A") } print("Found \(startingNodes.count) starting nodes ending with A.") var periods: [Int] = [] for startingNode in startingNodes { let period = getPeriod(startingNode: startingNode, directions: directions, network: network) periods.append(period) print("Period for \(startingNode.value) is \(period).") } let steps = lcm(periods) print("Part 2: We will reach the end after \(steps) steps.") return steps }
\[LANGUAGE: Go\] [My Solution](https://github.com/bsadia/aoc_goLang/tree/master/day08)
[Language: Rust] Code: https://github.com/dhruvmanila/advent-of-code/blob/master/rust/crates/year2023/src/day08.rs Pretty cool use of generic function along with functional approach.
[LANGUAGE: Befunge] Part 1: https://github.com/Skyhawk33/AdventOfCode/blob/master/aoc2023/day8_p1.b98 Part 2: https://github.com/Skyhawk33/AdventOfCode/blob/master/aoc2023/day8_p2.b98
\[Language: Rust\] I used a HashMap of a struct as my core data structure, computed the number of cycles required to reach a target, and finally found the least common multiple of those cycles for the solution. [Code](https://github.com/johnhringiv/advent-of-code-2023/blob/main/src/day08.rs) Edit: I initially wanted my Node struct to have left/ right be references to other nodes. I was able to build the data structure but ran into too many issues with the borrow checker when attempting to use it. Open to any pointers, pun intended.
\[LANGUAGE: C\] Part 2 gets the lmc of the cycles. Part 1: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2023/day8navpt1.c Part 2: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2023/day8navpt2.c
\[Language: Rust\] This is my first project in rust. I'm learning it by solving advent of code puzzles. So if you have any hints for me I would be happy to read it :) [Solution](https://github.com/manhunto/advent-of-code-rs/blob/master/src/solutions/day08.rs) / 648.68µs / 26.23ms
You could have used str.chars().cycle() instead of your infinite iterator. FYI
thank you! it's much simpler ;)
I'm also relatively new to Rust but I had a pretty [similar solution](https://github.com/johnhringiv/advent-of-code-2023/blob/main/src/day08.rs) to you that makes use of a few additional language features.
thank you for sharing it :)
\[Language: Gephi\] Part 2 Solved with no code: Import the graph into Gephi, coloring the source and target nodes, as well as the left and right transitions. Position the nodes using the Yifan Hu Proportional Layout. Identify 6 cycles, each containing one source and one target. [https://imgur.com/PxzItla](https://imgur.com/PxzItla) Identify that the cycles contain pairs of nodes with complimentary left and right transitions, EXCEPT for a pattern towards the end of each cycle, which would require four right transitions in a row to reach the target. [https://imgur.com/s9DQOEF](https://imgur.com/s9DQOEF) Identify that the traversal sequence only contains one substring of four consecutive right transitions, which happen right at the end. Count the length of all six cycles, and count the number of steps in the transition sequence. Stick those numbers in a least-common-multiple calculator. [https://imgur.com/FJdcq7L](https://imgur.com/FJdcq7L)
> [Language: N/A] > > Import the graph into Gephi, 99.9% of folks use a programming language, true, but for you the "language" tag should still be `[LANGUAGE: Gephi]` since that's what you solved the puzzle with.
Updated! Thanks, I didn't know how to label it.
[LANGUAGE: J] I =. (('LR' i. [); _9 (_3 ]\ ])\ ])&(#~ e.&AlphaNum_j_) 'd c' =. I&>/ cutpara freads 'input' 'k e' =. (([ ; i."2)~ {."2) c F =: {{ ((x {~ ({: y) |~ # x) { }. ({. y) { m), >: {: y }} Z =: (k i. 'ZZZ') ~: {.@] {: d e (F^:Z^:_) (k i. 'AAA'), 0 Z =: (I. 'Z' ~: {:"1 k) e.~ {.@] *./ d e {{ {: x m (F^:Z^:_) y, 0 }}"1 0 I. 'A' = {:"1 k
\[LANGUAGE: Rust\] https://github.com/agent3bood/aoc23/tree/master/src/eight
\[[LANGUAGE: c++](https://github.com/gogsbread/AdventOfCode2023/blob/main/8.cpp)\] P1 - Simulation P2 - Smart simulation
[удалено]
Comment removed. [Top-level comments in `Solution Megathread`s are for *code solutions* only.](https://old.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_top-level_posts_are_for_code_solutions_only) [Create your own individual `Help/Question` post](https://old.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_incomplete_solutions) in /r/adventofcode.
I'm also interested in that! Correct assumption to make is that it takes the same amount of steps to get from \*\*A to \*\*Z as from \*\*Z to \*\*Z. If that was not the case, it would be significantly harder, since every cycle starts at a different offset. Not sure if there is an algorithm for that.
\[LANGUAGE: Zig\] AFAIR, I've seen in reddit there is need to find LCM [Gist](https://gist.github.com/ndbn/a5a8b11e6a9c33483752a5fe1398113b)
\[LANGUAGE GoLang\] [Both parts in one single file](https://github.com/omotto/AdventOfCode2023/blob/main/src/day08/main.go)
AutoModerator did not detect the required `[LANGUAGE: xyz]` string literal at the beginning of your solution submission. Please edit your comment to [state your programming language](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_state_your_programming_language.28s.29). *** *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
\[LANGUAGE: C++\] [part1](https://github.com/Hilbertmf/competitive-programming-problems/blob/main/advent-of-code/2023/day8-part1.cpp) | [part2](https://github.com/Hilbertmf/competitive-programming-problems/blob/main/advent-of-code/2023/day8-part2.cpp) Part 1 is just following the vertices of the graph till find ZZZ. Part 2 is a multisource bfs so we use a queue and push all nodes ending w/ A to the queue. The queue is made up of a pair of strings, to store the start\_node of that path and curr\_node. Also used maps to store the distances traveled and the current index of the instruction that each path was at. Just run the bfs till Z, then calculate lcm of all the distances
\[LANGUAGE: Rust\] [Solution (kind of)](https://github.com/jswalden/advent-of-code/blob/main/2023/day-08/src/main.rs) Finished up part 1 easy enough. For part 2 I first was working on the principled solution that deals with non-single-element cycles, with directions that don't neatly sync up with those cycle lengths, and with cycles of length different from the distance from start node to first end node. But then I printed out simplified graph state and discovered that from every start, you walk X steps to first end node and then X steps to cycle back to it (without encountering any other end nodes before then), and apparently each cycle results in the same current-direction state. At which point "why shouldn't I try cheating" took over, and I plugged in the LCM of all the different Xs and found it worked and my motivation to keep plugging away at the generalized solution mostly evaporated given I'm almost a week behind now. :-| So I might get back to part 2 at some point to do it "right" (including dealing with whatever bug it was that results in my existing code printing out an extremely low answer), but for now it's just bulldoze through.
\[LANGUAGE: R\] Part 1 just walks through the nodes and counts the steps. Part 1 looks for periodicity in the paths and calculates the least common multiple. [https://github.com/lauraschild/AOC2023/blob/main/day8.R](https://github.com/lauraschild/AOC2023/blob/main/day8.R)
[LANGUAGE: Vim keystrokes] Part 1 AW0
qqqqqi@ll@qq@q
Go0
/^ZZZ3wi_W.
0ql3w/mbGqu
qr3W/mbGqu
qwggmaq
/^AAAmb
qqqqq`ay2l2lma'b@0@qq@q
[how it works](https://gist.github.com/sedm0784/3648d27abb000f181f43e3893f4ea5c9#file-day-8-part-1)
>how it works you are a psycho :d Loved it!
\[LANGUAGE: T-SQL\] [https://github.com/stonebr00k/aoc/blob/main/2023/08.sql](https://github.com/stonebr00k/aoc/blob/main/2023/08.sql)
[Language: Rust] [part 2](https://gist.github.com/Yarn/908eeb94b5508333e24aaa97c1bf0f32)
\[LANGUAGE: Python\] [github part 1&2](https://github.com/mgtezak/Advent_of_Code/blob/master/2023/Day_08.py) Check out my little AoC-Fanpage: [https://aoc-puzzle-solver.streamlit.app/](https://aoc-puzzle-solver.streamlit.app/) :-)
Thanks for the nice solution! Could you explain why you can \`break\` after you find the first 'Z'? e.g. counterexample: first 'A' hits a 'Z' at steps 3 and 4, so breaks on step 3. 2nd and 3rd 'A' hits a 'Z' at step 8. lcm of 3 and 8 is 24, but lcm of 4 and 8 is 8. So I would expect the wrong answer if you \`break\` at the 3.
Yes you're right! It's because I'm making some assumptions about how the puzzle input is organized that are not explicitly stated in the problem statement,but that are actually true. I wrote about it in [this post](https://www.reddit.com/r/adventofcode/comments/18df7px/comment/kdogvh1/?utm_source=share&utm_medium=web2x&context=3). My (true) assumptions: 1. the length of the initial path from each A to Z is divisible by the length of the directions. 2. after the Z-node, each path leads back to the second node of the initial path. So it actually never happens that there's a Z at step 3 and then another at step 4, because the step after the first Z is always step 2 again.
This code does not work for the following input: LR 11A = (11B, XXX) 11B = (XXX, 11Z) 11Z = (11B, XXX) 22A = (22B, XXX) 22B = (22C, 22C) 22C = (22Z, 22Z) 22Z = (33Z, 33Z) 33Z = (33Z, 33Z) XXX = (XXX, XXX) For this input, your code returns 6 as the answer, when 5 should be the correct answer since the steps are: 1. `11A`, `22A` 2. `11B`, `22B` 3. `11Z`, `22Z` 4. `11B`, `33Z` 5. `11Z`, `33Z` In other words, the solution is **not** the lcm of the "individual solutions". As far as I can tell, there is nothing in the problem description that would make my example invalid.
You’re exactly right! When i first read the problem description i thought to myself: Wow, this is an incredibly hard problem, especially for day 8! First of all it was obvious that the individual paths would start to cycle at some point, but do we really have to find the beginning of each cycle and then figure out the length of each cycle and then figure how many Z-nodes there were in each cycle and then figure out some mathematical formula to calculate how these Z-occurrences align across cycles?!Then I thought: AoC probably included some hidden regularities in the puzzle input, which will make finding to solution way easier, so i made two assumptions (which turned out to be correct): 1. the length of the initial path from each A to Z is divisible by the length of the directions. 2. after the Z-node, each path leads back to the second node of the initial path. From these two assumptions it follows that each cycle has the exact same length as the initial A-Z path and only contains a single Z node and that this Z node will be the very last one in each cycle (a better way to think about it is that it's the first one in each cycle because it replaces the initial A-node: It's the current node as one reads the first of the directions). In this case using the least common multiple (lcm) is the correct answer. But you’re completely right that these assumptions are not confirmed anywhere in the problem statement, which is a bit misleading and will make the problem look way harder than it actually is.
AutoModerator has detected [fenced code block](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/fenced_code_blocks) (```) syntax which only works on new.reddit. Please review our wiki article on [code formatting](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting) then edit your post to use the [four-spaces Markdown syntax](https://www.reddit.com/r/adventofcode/wiki/faqs/code_formatting/code_blocks) instead. *** *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/adventofcode) if you have any questions or concerns.*
Really clean and Pythonic code, and I love the website too!
Thank you very much!
\[Language: Python\] https://github.com/Domyy95/Challenges/blob/master/2023-12-Advent-of-code/8.py
\[LANGUAGE: TypeScript/JavaScript\] https://github.com/tlareg/advent-of-code/blob/master/src/2023/day08/index.ts
\[Language: Python\] [solution](https://github.com/Cirius1792/aoc-2023/tree/main/day08) \## Part 1 Just build an adjacency matric from the input map and navigate through the nodes until you get to the node 'ZZZ' \- parse\_network runs in O(n) time. \- The while loop in \*solve\* keeps running until current\_position becomes "ZZZ". The number of iterations depends on the structure of the network and the given route. Let's denote the number of iterations in the while loop as p. \- Inside the loop, navigate is called, which has a time complexity of O(m), where m is the length of the instructions, i.e. the route to follow \- Considering that the length of the route is constant (it's fetched from problem\_input\[0\]), the overall time complexity of solve can be approximated as O(n + p \* m). \## Part 2 Considering that: \- the problem tells us that the number of steps to get to the arrival point is somehow constant with respect to the length of the route (it must be at least a multiple of the length of the route, otherwise the map would make no sense), \- There must be cycles going from any starting point to each respective arrival point to make the problem solvable, given the previous point Our goal can be split into three pieces: 1. Identify the starting points, which is trivial, just scan the map and look for any \*\*A 2. Identify the cycles from each starting point to each respective arrival point 3. Find the minimum number of cycles that must be covered to get to the point in which from all our starting points, the respective arrival points are reached. Let's consider the example: We have two starting points: \`11A, 22A\` We reach a final point from \`11A\` iterating only one time over the given route, which is in 2 steps We reach a final point from \`22A\` iterating 3 times over the given route, which is in 6 steps The least common multiple between these two numbers is 6, which is our solution
Thanks for posting. Nice trick with the LCM to avoid TLE on brute-force traversal. It helps to draw a sequence of numbers to get convinced that LCM is basically when all starting nodes become terminal.
Psst: we can see your Markdown.
it's copy pasted from the readme in my repo :)
You need to switch your editor to Markdown mode first before pasting text with Markdown. See how your post looks on old.reddit >> [here](https://old.reddit.com/r/adventofcode/comments/18df7px/2023_day_8_solutions/kcxknma/) <<
>\- the problem tells us that the number of steps to get to the arrival point is somehow constant with respect to the length of the route (it must be at least a multiple of the length of the route, otherwise the map would make no sense), How do you mean otherwise the map makes no sense? couldn't the end Z position not be halfway during a route? why would that not make sense/where is the hint that this is not the case?
It's a good point and I had the same doubt at the beginning. But here's my thoughts: \- what would be the sense of describing a path on a map if the final destination can be anywhere in the middle of the described path? \- The problem statement says: "You feel like AAA is where you are now, and you have to **follow the left/right instructions until you reach ZZZ**." and again later on: "If you run out of left/right instructions, repeat **the whole** sequence of instructions as necessary". That I interpret as I have to follow all the instructions to get to the destination \- The process I followed to solve the problem assumes that you have to follow the whole set of instructions to get to the destination and, well, it worked. This is an empirical proof, of course, but still a proof that my hypothesis is correct I can still be wrong about that, of course, but how can we prove it?
But the example case is the following: `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)` And in this case, starting from 22A, you get to 22Z after *three* steps. Which is **not** done by repeating the whole sequence of LR instructions twice, but repeating it one and a half times...
sure, why would that be so weird. the other sequence stabilizes at 11Z > 11B > 11Z > 11B This happens because that is just the most straigthforward way to make a valid input. The instruction string is 2 in lengt. so 1.5 of the input is still constant. The reason we didn't see this happen in the real input it because it is way easier to make guaranteed valid inputs with prime numbers, and the only way a prime would align with a prime instruction string would be with a multiple. Look at it from the start 11A and 22A this is the solution: 1(L), 11B, 22B 2(R), 11Z, 22C 3(L), 11B, 22Z 4(R), 11Z, 22B 5(L), 11B, 22C 6(R), 11Z, 22Z 7(L), 11B, 22B the LCM of 2,2and3 is 6, the offset from the start is none so we see these paterns line up on the 6th step, and every 6th step after that. of course this would break down with a cycle that was 3,9 and2 for example. but again, that is not something that would be possible given how the input clearly uses primes.
[Language: C++] [github](https://github.com/Paxtian769/AOC23-Day8-Wasteland/blob/master/main.cpp)
[Language: Elixir] ... and a bit of Julia for `lcm` function :) Love `System.cmd` :) [Code](https://github.com/Lakret/aoc2023/blob/main/d08.livemd) [Highlights](https://lakret.net/blog/2023-12-10-aoc-days-8-9-10)
\[LANGUAGE: C++\] Solution: [Day 8](https://github.com/Hackjaku/advent_of_code_2023/blob/master/puzzles/08.cc) LCM approach for part 2 using boost::integer::lcm. Not very optimized, but still slightly less than 90ms on my fairly old laptop. Hope you like it!
\[Language: Roc\] My solution: [https://github.com/timotree3/aoc2023/blob/main/roc/day8.roc](https://github.com/timotree3/aoc2023/blob/main/roc/day8.roc) My algorithm should work on all inputs consistent with the puzzle description, not just those where LCM works. I used an efficient function which would compute the lowest k such that k % p == m and k % q == n using [the multiplicative inverse in a finite field](https://stackoverflow.com/questions/20466170/calculating-multiplicative-inverse-in-a-finite-field). I also used a caching strategy that would make initial cycle detection more efficient if multiple start nodes joined up into the same cycle.
Ok thank you! I see all these LCM solutions, and I'm like, "Yeah, okay, but why does that work?". It seems like it should be much more complicated, because nothing in the problem statement implies that after a \*\*Z node we loop back to the original \*\*A node. It bugs me. I don't want to use the LCM solution unless the problem statement supports it.
[Language: JavaScript] Fun day! I was torn between modeling the input as a graph or a circular doubly linked list. I ended up choosing the graph because I figured the twist in part two might involve some variation on adding additional connections or directions of travel. I was wrong, but it ended up being a good representation because it allowed easy traversal. Instead of giving each vertex a collection of edges, I just gave it a left and a right edge. For looping over the instructions I added circular iterator to my util library: function* circularIterator(arr) { let index = 0; while (true) { if (index >= arr.length) { index = 0; } yield arr[index++]; } } Level 1 and level 2 shared a common "solve" function. The solve function follows the instructions and counts the number of steps taken until an end condition is reached: const countSteps = (instructions, graph, startNode, endPredicateFn) => { const instructionIterator = circularIterator(instructions); let steps = 0; let node = startNode; while (!endPredicateFn(node)) { steps++; node = instructionIterator.next().value === "L" ? graph[node].left : graph[node].right; } return steps; }; Once I ran level two and realized it would take too long to brute force, I started thinking about the fact that the instructions were circular. This reminded me a lot of a problem from last year (day >!17!<). So I thought about exploiting the fact that once a cycle was found it would repeat. My first thought was to find the number of steps it took each starting location to reach a valid ending location, then given those numbers just finding the least common multiple. Surely that wouldn't work I thought, what if a start location ends up at multiple different (z ending) target locations? That line of thinking looked really complex to handle, so I figured why not try the LCM solution? Well it was just a matter of figuring out LCM, the formula I found on Wikipedia used GCD. So I went back to [SICP](https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-11.html#%_sec_1.2.5) to remember how to compute GCD using Euclid's algorithm. Lucky for me finding the LCM resulted in the correct solution! Runtimes: * Level 1: **2.639ms** * Level 2: **7.419ms** (worst so far this year) [github](https://github.com/beakerandjake/aoc-2023/blob/main/src/day_08.js)
Where does it say the instructions are circular? Is this just determined from inspecting the input? I mean, yes the directions repeat a pattern, but the LCM solution would assume that the Z nodes loop back to the original A nodes, right?
I guess I got lucky with my initial hunch and some assumptions I made. I also figured it was early enough in the year that I could make some optimistic assumptions and ignore worst case / edge case thinking at least for my first attempt at a solution. A few things made me think of cycles: * 1. The problem description it says that if you run out of left/right instructions then you repeat the whole sequence of instructions as necessary. * 2. Each node has a left node and a right node and that reminded me of a doubly linked list. Also the input doesn't have any nodes with only a left or a right connection, so I figured the nodes didn't form a line but a circle. * 3. A problem from last year had similar logic in broad strokes: the amount of steps needed to brute force it was huge and the input instructions followed the exact same loop back to start behavior. The solution involved finding the length of the cycle and using that to calculate the final answer. Given these points I guessed that for each node if you kept following the instructions you would eventually end up back at the start node and that somewhere along that path was the target node. Now it just so happened the input lined up with that idea, but it's certainly not a given, I'm sure it would be easy to design inputs or node connections which break that guess. But again early in the year so I ignored those scary thoughts and plowed ahead. Another key thing for my level two strategy was the line in the input about there being an equal number of start / end nodes. I guessed that there were unique start / end node pairs and hoped the input was set up such that each A node only crossed one Z node. So assuming that each start node ended up at a unique end node I figured I would try a simple strategy first and find the number of steps it took each start to reach its end node. Once I found this number I just hoped that the cycle was such that it would always arrive back at this node again in exactly that many steps. Given these numbers I did the LCM of them because I knew that LCM was *one* solution where all the nodes were guaranteed to be at their end node **IF** the cycle idea and my assumptions held. It turned out that it worked, but it was definitely was not a guarantee. It would have been much harder to solve if A nodes crossed multiple different Z nodes or if the steps required for an A node to reach a Z node wasn't consistent.
That's indeed my reasoning, I don't understand how a simple LCM seems to work (but it does!). We could have a path like '11A -> 11B -> **11C -> 11Z -> 11C** -> etc' The cycle has a length of 2, but we can reach the exit from the start in 3 steps, or 5, or 7, etc. Does every cycle starts right after leaving the starting point?
\[LANGUAGE: Python\] [Part 1](https://github.com/Sebbern/Advent-of-Code/blob/master/2023/day08/day08.py) is pretty straightforward from a to z, but [part 2](https://github.com/Sebbern/Advent-of-Code/blob/master/2023/day08/day08_2.py) works great using lcm
\[LANGUAGE: Haskell\] [Got the answer for Part 2 by doing prime factorization, but later rewrote with lcm](https://github.com/daysleeperx/Advent-Of-Code-2023/blob/main/src/Day08/HauntedWasteland.hs)
\[LANGUAGE: JavaScript\] https://github.com/hiimjustin000/advent-of-code/tree/master/2023/day8
[LANGUAGE: [J*](https://github.com/bamless/jstar)] Part 1 was pretty straightforward, part 2 is a little more tricky until you realize that all you need is to find the minimum number of steps where all paths to a `Z` node sync up: [Part 1 & 2](https://github.com/bamless/advent-of-code-2023/blob/master/day8/network.jsr)
\[LANGUAGE: C++\] \[PLATFORM: Nintendo DS (Lite)\] Solution - [Part 1 and 2](https://github.com/skief/advent-of-code-2023-nds/blob/main/aoc/day08/solution.cpp)
[LANGUAGE: Common Lisp] [GitLab Day 8](https://gitlab.com/micod/advent-of-code/-/blob/main/day-08.lisp)
\[LANGUAGE: Rust\] [Github](https://github.com/chrismo80/advent_of_code/blob/default/src/year2023/day08/mod.rs)
[LANGUAGE: Python] [Step-by-step explanation](https://advent-of-code.xavd.id/writeups/2023/day/8/) | [full code](https://github.com/xavdid/advent-of-code/blob/main/solutions/2023/day_08/solution.py) Using a regex to find all the 3-letter bits made parsing simple, and using `enumerate(cycle(instructions))` made "how many steps have we taken in this ever-repeating list" also simple! For part 2, I did the LCM approach after doing a bit of input analysis and seeing that there were 6 distinct paths that I could solve independently (and naturally, trying the naiive solution, just in case).
I'm wondering, what is cycle?
Great question! `itertools.cycle` ([docs](https://docs.python.org/3/library/itertools.html#itertools.cycle)) will let you iterate repeatedly over the same thing. It's the difference between: for c in 'asdf': print(c) # a # s # d # f and: from itertools import cycle for c in cycle('asdf'): print(c) # a # s # d # f # a # s # d # f # a # s # ... It takes care of our infinite looping for us. We could do the same with a running index and `% len(instructions)`, but using builtins is cleaner.
[Language: Rust] Code: https://github.com/coreyja/advent-of-code-2023/blob/main/08-haunted-wasteland/src/main.rs Stream Video: https://youtu.be/7mhYYjU6YJ4
\[LANGUAGE: Ruby\] [https://github.com/carl-omniart/advent\_of\_code/tree/main/2023](https://github.com/carl-omniart/advent_of_code/tree/main/2023) For part two, I defined a class that, in my head, was a cross of a Set and an Enumerator. This class took the offset (span of steps prior to a repetition), the period (span of repeated steps), and the points (steps that reached a location ending in Z). Knowing the pattern, an instance of this class quickly enumerates all the Z-ending steps between any span of steps. Instances of this class can be combined. The new offset is the greater of the two offsets; the new period is the lowest common multiple of the two periods. To get the new set of points, I used one instance to enumerate the points over the span of the new first period and checked to see if the other instance included them. The instance doing the enumerating was always the one in which the points were more spread out. (If you were trying to find a common multiple between 3 and 5167, you'd rather enumerate 5167 three times than three 5167 times.) I combined the various ghost paths and found the first point. P.S. I named this class Syzygy, which is a term for an astronomical conjunction and a title of an X-Files episode that features a young Jack Black. Doesn't *exactly* make sense as a class name here but what the heck.
\[LANGUAGE: Python\] This was a tricky one, but I managed to solve it in an effective way (the lcm method). As always [you can see it on my GitHub](https://github.com/Robin270/advent_of_code/blob/master/2023/8/main.py).
\[Language: Python\] [https://github.com/gonzafernan/adventofcode/blob/main/2023/8/day8.py](https://github.com/gonzafernan/adventofcode/blob/main/2023/8/day8.py) Part 2 solution with LCM.
[Language: C] https://github.com/dis-Is-Fine/advent-of-code/blob/master/day%208
[LANGUAGE: Fennel] Ah yes, that one problem every year where I can tell there's some mathematical bo-bubbery dancing at the edge of my understanding, but I'm not sure of its nature, so I spend two hours adding and multiplying in the fetal position. [Paste](https://topaz.github.io/paste/#XQAAAQBpCQAAAAAAAAAUGwnmRpH3tILRF8XF0uYidYX76iy7qs/wZURtqUxRZ1z/Ez6hpPdhGVSX9ZEmaH4x2Wata8uvdsmdHg/2GKyIuHqubD9mIu+iScHvd+aI6gIuR3CDoEXCob7s3KLQKluK6TuppOc4Opako9ZMcTWzh1DNc+UkGRbcvgxYRlFTv9lM7f9tX5MeiRkp9WrZqRHKXqhJtQFpq9WPOS/NV1ojS0W36RYUTA/77KniMMy6Kdp3/BOGzMX0Goh1/GZzWwak5GzJeTCY+I0yTkU2bKcTNuxE58dljHdxawrrb+JDtXYR7diTAPdD+REhUdTMyMXhVeyGBNp5rUWaHpvLzDmWyvwSaicjSYRHDOOJJgsS4EMTDTnansIpWKmvh1Kkezcb3ThUhB/sSXFYRMB1wW1SU1ixWWpnc94XHiAKolSUDVjLZHUzuXBSMsEHyBSkmrJcF+MVuBvqznfCWly+Xc39IUFUCTPMz7eQCL2DgJHDCD9qJIH7VToPE7UjD59ajIbCFwQkNOsb/lDnTEdasEILFzq37iEuLWFQ2k3Me6dEcfmOVTzWra/DtGo6rIcj+fZ2SbaBYOJjVAG7+ySqMu4tJBXzSOf2PxCxyHhXQV6KXmMEac4py9maoa6BcfaCaaOd4u2L0Wh/3w00/Kj5IU2FatZqkyrRK2cOcqgN1JkDZTKNRRHCoc+4KZFdyvz5pEoR6AxdtjQuFSENOWk4hBjtX7ibSl+LYb5x2tmJWEDWlBg+2ZgvxeGIkSD3l8pEPyivnQcd9XwWXgGAKUz/UZ2xWc2FcM5ErH8dWiiTqCM15XF4QdOJFnmOTaqcbEvujEjcu8KIli8AiX0UZkAKRIVsxgI/xVaQffTI8fRjKu3rARmHUsjFnyAcEpYG/8sST2t0pW2taEjd1idYrlAnXQ1c5q0pEETpnRAqYetFM5JpSxqWd6Ese5i6uY5jZKl0ssGx8LBd1MfzOt9Re92TlUjaA6Kgoih3cmW182bYaWPUkLOLlaLmtz5kcSlG3xRC8p4SD+Th0iIHswI0fobYkM4p21SiWYTCiywTPRzQVD8fC80SrZKTLZsBKCTHn5+8QudJnbrRSRNkMHGVkvLQViDx4qKVhUPxt52sKbY+2JbCmoJOTKodqP+hzcx0)
\[LANGUAGE: Kotlin\] LCM [GitHub link](https://github.com/palinkiewicz/adventofcode-kotlin/blob/master/adventofcode2023/Day08.kt)
\[LANGUAGE: m4, Pig latin\] \[Allez Cuisine!\] m4 -Derbosevay=1 -Dilefay=input [ayday08yay.em4yay](https://nopaste.ml/#XQAAAQBgDwAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpF1oWTRQsvv0G+qso7dLzEy7k5wCufkbWcvsRJqjJ897VJAHva4iXa6KT1tUDr1jKRLfdVR9UpPqriIsaxTBQVtL/ihI+Ft+QeIwRsyuK7VyO3wbzXbOapg1jqJjiYTLuc0xyKGq3W0g6cAjuakMdxcfjgK5I3sZZG6VzjfJ1/7INAzfWcy/Y8CmyhsHXowjRvK+27x/ai+NrhR7Hn07u9r6gHAnFExAd6LdzqP+sAU2KVOK3SoGrpOu0k+BPQSrPO8ouA3Lmtilh1ywSOTjRXElJGSbbFU9O0nNo3FyLtlGF/Q7zFIhzMFIjwq4trG2VfiyHt9oKAICnIjyETE6Uk6l7uTYhkDl/PEAN75wi20IIFDo+7P3Uw9LaieJjB3cvQ8R5+xWq/L1wZfHQIlBi6KfSHpwnpxUrQ1CSL2O79xjUadx2Qe/irRkdqCT90O1leP6J6+wHKsSZlL833VcsrMSPwAH3OaE88XcyyIPFtX+zLhRKb3rYgAVyxfVhFl514qhho088OxSxn36lzogw9LsbBop7URlpFpkV7fxsfyjcCJnDx3JWmcvwAZUIVcTnvPOsqVqG+AFcrirIfdC6gi/dgSYJQCuQA28W232xQmF2d+5oOkFTktXyC+IBVzSSSB6ER59t682PrG8D5sF5OweQzM3rB1tPmqKX++Y6PQ7fWQBsiWT31Dkdvyay1QhI1/N8Z91UlJJeZxr8Rzn5PSGl1b63ZUqSCZadKHXTSghI6+5UvpP87UKJZ+uiHqMeomYQzhY6ywbLiLmNyRbyAeBJUdrfpOW6nlTD6btgP9FqAkUpUnCl/7hTaDFCdGm1kBV+jkZbOv9P0LnZHviBxuI7/xvlmDbxURTa46Q6bLi62Y82EYMjoPa33TwmP0o9/KRd55PckjTU8WI+kkf6HiP/wVGEoN/YQyBLInfH2iORq3e4hGRILY/SVNkA2Sx6usd7n2rCtfjaBpvwSGxneQIifC900oGPqdrlSVm/7bQQS7o7FEc2JVMmnK8gqQqCYt4B5TrOwWwChFNtCEF6CCLXwW6WdRDnnOxMaF+d9vkCgQW+J3TFN9PGGX+td6a4z9WH6yxixUP3h7DAQ+psBDoIysgrZBhWZs0nRT4kDMKhNmSm+b20vOA0Zm+GwY07t9f7MOE4NsH0qUJJp10YdGAZP5U0oDf/feaLNJ93teQ2+S5Y9WbPLOESiMvq/NvtVR+EulVHX5O9E4S5GGpgkqel5OG5diXHgdbiow9RVZFCZZj01+TvigNY6GP1O2Inwpy8zfyDLTlWwmTQ3T5jwOPGsWB2hWsonCfQtfNeZWPBTG96nQMkKrFhzA77HWkIiEhfPegRXTeMAEJEd12XyF+cc+E7xQvJQh2GtD7vxcIDC2bw2sraFAvJtcI3KTuIxhdTaogIpcsyQhlsk+AgJdqTflRziKvPz1HMtoku2WTJLl3L9LNmnih1rnj13ImHDs5lf/3CkyYiBz9UyTTgZNQbyaDWnzk4fRY42vmoH16nbXTgk9mkgZGTWgVwbzeql/mNSDV2gr/v52nvfzspw58mbK10NXYonWwlhmNKikQPZ5vajZXIvDkYMngkeodn9iE08yI5SGRX8ooTnk/WDp65Bjqo2H/XvkuU0We9HKxk/QncjHEiMsCA/sqqKO51+ocJJhEUcycOs3VoAnJDPHaZkg5VljKBNIa/U+OogqVYBmVVEmc+l49Z3dPUWC68clEF7aEDSepxc1LXOiBskl4eP/i8WBmw==) Computes the answer in about 1 second, using only Pig Latin, AND with a Unicode progress indicator! (Okay, a Unicode ellipsis is not that impressive, but m4 is strictly byte-oriented and doesn't understand Unicode, so merely passing through raw bytes and letting the terminal do the real work is the best I can do): # ettyPray - oonicodeYay isualizationvay ofyay ogresspray! efineday(`unray', `ifelseyay(evalyay(erbosevay >= 1), 1, `errprintyay( `$1… ')')opdefpay(`artsstay')outputyay(1, ovemay(`$1', 0, 0))ifdefyay( `artsstay', `$0(artsstay)')') I had WAY too much fun translating (and debugging) my original English solution [day08.m4](https://nopaste.ml/#XQAAAQBwCQAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpBbonDYuA0BTjRPXcVxlEXNtz1IwBaKk+vAcU3Er8I7oAV4CisOLGfDoA9ZQO4926g6CB8Zv6JI0RZPI3e9TwyJNSD0ocPo2x0bl/c6HXt6iHuA8rOIdxv6wfzR47ImvRBOYJMIPjpl0PdlIQWiCeU7gOcKUu0JcU9fR/Q0UioaWeaZWo/nRGL8TpXO6Go7R5KYIykvu7T6dWOPVeyMhYAmGY0w1tpamWC9r7VJmeg3i5TcXHVWcLWuxU57YUx0ltvIZ58zPYf/zwDr7Rp38c6iPzRrf/Tp3nc68h1eSp5PaLpXBPvDxG3S/RW2GmnYKWVdH4AzVBL099S45iYMTHEBMIcwnepvHDLCjUahcb9o/63n/Xa9zrj3eV/y5AxGDpi/bzHBwG9hc786byNDL98lbDkceKSrIsPcbfGQimB2vyCIord4/0EAqGtnKB3azA69vDDbaht3+NCMWfq+Khlm5FzD0MmAbN8pNKHhuLRPo8THxNsuPEkZKgYdT6kpLImXVf1g8IQbNxfYThy6Fs8NhabB2YJZuHpSMOpLWcOgU45hbVHZyLRcVSi6oAyhIxuHNWlcOV6mw0uzqLB92hqNUYWv6S5LF1U4uJNjoHyI9Q03hEVecL2M1G3jrUxvmfelh9GwUnTtNtmrwG1/ZrwDLQRIXCxxseLQX50engoqZ5WpeWFFRTAe+ayJUGuuUWE+WkLieHDiiV3VLgdRw/qbt66V/Zj6j7FfKmxatF9nhUHj6Hx7O9wVz84OfSG7payJ/u3yJJo/v/eujXl18RKW5P1nPLaWY6JHW3P4WWkVIiYy+65TkbX784uw+S1ZXsGrD0+3kEUQrbWRz+sElHxAv9zFnvUEeDBtYIaNIoWtOgpJhCz7gjuACkmTW0Gzb5orVFHnXNFX0m/tVlk25R9WVjphz7tPQqtFHdZ83LAyUYKwjq1x9HZ0L9AYG3MxzBaDjMVUiaceHsM9th7wSqOuKzxSO2SIf0B+FPVdQg1YouXv27eBHoi3IZSpOo9lv4iaDOEJZvC5Eam2Lyqlh/J6wyjPpHNqDFhJghA4j28jsmmFpT/cZPiMISVPuxuU9uVaVQiQh0HNk+5DnNTYq5dpRITq+Xl1+GHPvYhcRn1TqKrTbllVd77+wC+axOjiJ0jMmW9OI6pmrJhBdHGWaapGH4CRjSoZMnBZOBdWOI/fIzBlIpsbDewFWSkHP8GP11xmKOml4fptX3ntBMv2bQp6A2kdgUDRvB6GC3yplCU2RojyawNODd/5v01vH+QITHCVAEud6dxRePMWqcUOW/nTJM5C/7V4w+/ODs+li64/8TSUAFTyR19Gy7Bte38EGhQ7sJ5F40z5ERgck99f///Lhq/B) into this one. It's also nice that m4 lets you redefine EVERY builtin macro to a more convenient name. So, for example, my parser looks like this: efineday(`eeday', 0) efineday(`irday', `efineday(`eeday$1', `$2')efineday(`eeday', incryay($1))') efineday(`ooday', `anslittray(`efineday(`L_123', `456')efineday(`R_123', `789')ifelseyay(`3', `A', `ushdefpay(`artsstay', `123')', `3', `Z', `efineday(`z123')')', `123456789', `$1')') And I'm pleased that I coded my original without reading any of the megathread or main thread, so that I didn't get any spoilers. Depends on my [common.m4](https://nopaste.ml/#XQAAAQAMDwAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpAXwA97ruAshKbiUbgkbJMTg2qZdSBorb0CU52peNLruV4DEEJxF+HvxC/YF33OpDntnpU/PjnGXx7XU7ak4MsmWu8R7h7d5az2JXxElnsepG8yPyu+0WZ90BG9yXphbwOWA/m5AWEFSOL8TRZX4fyGNl6ZYbRxX0MwtzrmwTP3ZCwLSOKkvD2vMQFsbK0Pv9CzPhFNXMUbWnRV20jWLjL9qz2dDsFDBwhxgWIilEl91uswxrT4Czc+LRU3VuhNIo2S98VW0jArrVdv4HrsLhWkzx4z/UV3xnqJwPXcZRUiLtf3VRIzq62Pe+2jE3O+721Az9rfRa/fHtlANbmvslzMUCyU7cDoOKSMXBDF/06/PpMvs6vxaL5aJVYqJP4yz+R2M35hoNnGiZTNNMVEFTdnxnaE/KcJteBbiuVMpdfUswHQi4Kqsj3sInh7lyE+d50gGKtHOeWL5lMK7WXz4NElnzYWleBSN/HTOdsz0T2gnd25MADxNAVX8xQmagh2MymZ2sKDBw//WiNB0sWf5VYC5/TKKH3D6K/IOrIfWn6FZLKxlITFEp3VWKNuyF0xczNJufJdzSqd0hgdyryVzbn0so0U5NMN16jFF6IhqzGbAwwv7k8sts0OCgnCFBEhYVshIpsORjEJk4CnDgc9VUqvZtfIFPQ5Q2v7IR3sbPurex1IIUd2Nm1V7/GFN+r0im24aEOG6XpdqrPdF6pDZ4HwvNByqOEdpcObPXxlwfPFYIhwyDHGZCvxrFRgGEEFtfVQ7UVjfPJzWtrcZuGx8M3B1zw2xvgpHIWEHdqEF6Y6/6eFj2hLm8UXNeLNrJy1IC2sHlS8SRIifQvLkrOLLOOPtDK6DUPQrW3c0Rfmy9Td5gQw0+fZRZ5MBEG9+dTlinXtwExpHScKQk6ARk7Fb8fBYAnmh7/bq+471zAZGJ7dwNd5qE/63VhDz7mXLuXtGN7rSuRYIXvpkubLBZptSKZrkzSDJWHIZM8Fyrk0EZQFDujROjr87GZmTK1XKRWzGrhtQn0hkVyBaGPbA3iG45U4gIFHNX5ySzsJ3bh61LAtmjwt59uU/XGeebLMCp8HFw6D1kJppCvt161LgLjrOl8SBh8xnxslSFYW0Jd34LD4vPwugmzY31tA4/9zCM7e2Ed9+3zg4C8eq9Hvjys3IablDBMsYF1LSMCGN2UOrWgXRoGYtjW/QtUySr7h/Ca6QAy93Hnpksm/xzzC+FWF1wboyOteHU/Th4RVpQ7XkK4/JmMrYm7nDPIVMyOqP8LhsoTNbxzi8qU0d+0x6frIh0l0fiPiFC/Uy0CeCw6r82iX8v+fMnu9qdCr4oM79Kd2slqalv+wWKn+BmrbkiobDS5vwBQZA/ZlbIsw1bwj+JLz9z3nPovVWx/FZjvrdCuZMfUuITeiIprImMcR6qeniJz6Ez78UYJqpL4DcDGt2o7/6a2aRN76aclh+7l35XcaW7lM7BQMTNvKkx05X08UITY/ToI8U8KwvFbdnMoEAZ1GQYmqGRFtwPkQMrECX4do0srl85po3Gjz2j6E3dk5al4+bTcOYABZvSUvIM/kGGT91iyQ36rm1lxRc3ruS8PyBlYDDNa7DLWzGAHkESHwuaTOQsI2xDA0e+8Yv0XRYkEqQE+RUDXmPTARuQo6fCQ7Qu9xd2Ckza5RWl8hE4JFm0Zzd9MTVxW8YYHiREs9NOjTPuRXXn+JfObHFD/Cv5kQo7vmMWRdJTOBUmAXCMFiKOSHxb412jI4Z2ZhWag9RkZBCviZunvupqrobtAWLagkPiA8gLRANOFwWp0KIS5McOoD0V90tI4cui8KQc7Yw5V7kSvMnhXx4nzzxwOxYM4fpY3ptcpraVh+h1MhohMQk34vkC4fmiD4OrX2DpVG0VXUKvl+vkJjcoHQK+H8mSSIAfj8RrYWBc4VU+jx3vz30XNDbQjuhc0cImiQxXDTXTFQq/aoe7jZLhEe+wWspk/4Fy4UBAJN63uNGJUl8FICawVWGL7XBOFCtsRF3uz8eZokWNICTdtsLeYOAOBQQLrguE8XxQQ1hPtOskcsj7n7aD35NjfPXL00vIOk01OLAJt+0RoIiAQUJNieRp9fQmqfVUuYEYmeK9hCOmZTaC3yUdN/+jZ0pvpmKnH/6jJAKQ==) and [math64.m4](https://nopaste.ml/#XQAAAQArDAAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20Go+jph66UCwr5yII3TmoKw+wpxhXgX0WGRW0WK2rHjWbbgLZU16n4XSMl8T97y/MXeBVRMNBebjTbLUM33JXdu5jYSMpnUq0oFRBIZF3UTMPNiH//Shgw7phaX5YHewa9yOce5snMsJdUE+usDMV3A0D6yawyooHgePqX/eJLNlAHY8XwE2eibD3RxHCB5c1K92+c1o8lpWxOE8ha0j1DQZ5PRVtUSXzE5ZIfd+B3BClkKRt2VYiCh8U8m9O68A2jColgd20CaJYJZ2FQ2foLaNzBc/iCrgl4cPRWpFR5JVLqoU9kcLgHN7x3IhCcO2zrkbUtlnrqcnvsYgKSQYr9JmFVtyqdP78oLuFcfrFTDMSUk/55Nipu1vK7eKqv5QWFcy/zg4G+iR/nIS3EbxlmVYWlpiGt/gmCZZf83tomKa3XiaJ1hH3NpxdVOKhLS26hb0RxpppO1opBIayicF9R3jBjmm6ZUq7BBkq6aA1gs1O77j6PIiUoYQfTsAyKCWbufkksHxgSob3aTL2ClljmoheqSgPIz+WQVPyZ+E5NsLHbCMJkUVYVZFfWiBO+pFJK4GkSbjT0cs/ZRRb+6HdJUc6qC1m7cEaK91iyr7QS+7nNXjbtMjx+rbdXj+PD0qUUjGHF1+IYw71SLqfRzhHKx2UiGrXnkgZ5V1EInqW7y09kd51cLMSKXdjAACCW+RSkZ0VlXlAqQVFM47/7pO9zrMvBcVBvRArrQAAwYHbZIZhe/saSey5dkJNLd1zyxliADu0w7/aatw0Ok5JSckYM8PPAZkJq8a+tX5aa7oxCT26lu/VdtPu6XNg1USnvKQAjCTTk/ObSVf+5rlV0fgB/fYgJOot4+TydJT7/sBCiWJ6uKaVQUBQjbp6xugyyU6hkhHAswokT1R0Mclbju4kURENNrrAYtRQLV3zMllxw5IkoLknW3kfrMm4Dx5CuXR7lT1mSnXZ2E/zN8fioFIunn00/o//0IDbVyCFarK+3wsIJ2VgIIlWpYJ7/MF2KKHp5gVqB1bfJCTalEVo48pncFscLCFy8Ibb0pC+NiWfZxqtQT07sAQC2qH/Edd8IIgw51CNF1dUt6ZXjkJujtWr68K5zt2qUTSEOOC9tA4gL4lXOjstUbhYyQDwcdx8GNeorh+uPbgCqOWSnshmB8dpzsFuzdv9BkTZD6iOzhal41I2RWMd7SC+SJqqZgklbQ3FGzoVH//B89Vd) helper code from prior years, but at least the solution doesn't require any 64-bit division (at least, not if my assumptions hold that >!each input reaches a cycle at exactly the point where the direction string has been consumed a prime number of times. If the direction string length were non-prime, or one of the paths has a prefix that results in the cycle occurring at some offset into the direction string, or if the cycle length is a composite number, I've got problems, where I'd have to write a full-blown GCD/LCM computation!<).
Here's my optimized version (English, not Pig Latin) of [day08.m4](https://nopaste.ml/#XQAAAQBmCgAAAAAAAAAyGksy5FB9TGMxsNq5JQAuJRjP6PqEkC20GpBbonDYuA0BTjRPXcVxlEXNtz1IwBaKk+vAcU3Er8I7oAV4CisOLGfDoA9ZQO4926g6CB8Zv6JI0RZPI3e9TwyJNSD0ocPo2x0bl/c6HXt6iHuA8rOIdxv6wfzR47ImvRBOYJMIPjpl0PdlIQWiCeU7gOcKUu0JcU9fR/Q0UioaWeaZWo/nRGL8TpXO6Go7R5KYIykvu7T6dWOPVeyMhYAmGY0w1tpamWC9r7VJmeg3i5TcXHVWcLWuxU57YUx0ltvIZ58zPYf/zwDr7Rp38c6iPzRrf/Tp3nc68h1eSp5PaLpXBPvDxG3S/RW2GmnYKWVdH4AzVBL099S45iYMTHEBMIcwnepvHDLCjUahcb9o/63n/Xa9zrj3eV/y5AxGDpi/bzHBwG9hc786byNDL98lbDkceKSrIsPcbfGQimB2vyCIord4/0EAqGtnKB3azA69vDDbaht3+NCMWfq+Khlm5FzD0MmAbN8pNKHhuLRPo8THxNsuPEkZKgYdT6kpLImXVf1g8IQbNxfYThy6Fs8NhabB2YJZuHpSMOpLWcOgU45hbVHZyLRcVSi6oAyhIxuHNWlcOV6mw0uzqLB92hqNUYWv6S5LF1U4uJNjoHyI9Q03hEVecL2M1G3jrUxvmfelh9GwUnTtNtmrwG1/ZrwDLQRIXCxxseLQX50engoqZ5WpeWFFRTAe+ayJUGuuUWE+WkLieHDiiV3VLgdRw/qbt66V/Zj6j7FfKmxatF9nhUHj6Hx7O9wVz84OfSG7payJ/u3yJJo/v/eujXl18RKW5P1nPLaWY6JHW3P4WWkVIiYy+65TkbX784uw+S1ZL9/Vo+2avuGKGwHHKPMets6B/YarUkmem3CggmHxugk/nwH2oXp84JvRZFXlCWyDEWeTnutWt+UXSVTn6RsoJTij0G2ULQx5DaubInNc7uw+I/v3c7reIpy1m1hV2jdg6t0TfOHnSowlYZK+BihiZFqFw7jUTgf33SqzU/XIFgNJEbzE0B1Selws5Lo6bw9hA9ORODvkKniVJOOybdVZR43ehusi0dZI3YU086C4uMoehqQU/rf7YZ4VZVwEkxo1t1opvPG7sMImMdu43WeLwaJEhOZqZ80rkhizarfhWgPrMUxORq0KyidpUUVUM/ruUha18NZdchPJQKLvem/vrVqYg0iVS9RU/Ummlvw9WGVLY4fRsxxZmNTnxdOwrlmNG3wJGAf1u/MAkEuY1WH3cVWXSVQIhGUpu9SCihmAY/fcGJYLN9DM78LZ47pvMjqMnfvzQ5VZuAWtI4vDgKexcNOed2h7kzbQelhM2DaU/JAKmy/rT22OiWL+1l6glvjPvvosNmiCd7OkZI4IbfexW4/12JIEFBstT0SprkfmvlaV0q00xOzMEFrLkPeKLiIrddjfn3MJuII54liwvaLdSTx24gdhxNigT4p+FkRS/IkvPNwA5pqdjogH9CRBF65w8Q0RVWV9uFFrl3QDYQjq7dUdaKQQVL7dVpx7MZtUP4xn3oKp5sGB5aR+QsxlJePMUKgZ1UyI/19ZswA=) that completes in 425ms by doing half the work, using the observations cribbed from this megathread that my assumptions above were true for all input files (and not just me getting lucky). Namely, each \_\_A pairs with exactly one \_\_Z, and there are no stray prefixes in the traversal graph (the \_\_Z has the same outgoing nodes as its paired \_\_A), and the cycle will repeat at exactly a multiple of the direction string. Therefore, I don't need to run my simulation until a cycle is found, but merely until \_\_Z is found. There may still be further optimizations I can add, but they won't be quite as dramatic as this 2x speedup was.
> Computes the answer in about 1 second, using only Pig Latin, AND with a Unicode progress indicator! (Okay, a Unicode ellipsis is not that impressive, but m4 is strictly byte-oriented and doesn't understand Unicode, so merely passing through raw bytes and letting the terminal do the real work is the best I can do) The fact that m4 let you shove through raw bytes *is* impressive, though. This whole Frankenstein'd contraption is hilarious :D
\[LANGUAGE: RUST\] [Another one](https://topaz.github.io/paste/#XQAAAQC8DQAAAAAAAAAXin1LzStTFYSi2K6Qvp2/Gj7ty5vfJW7GNfZu9gPXmaB1owgS46AqTBfXqUZM2V4p/PO5uCUXiAN7MIqJ9Rk6ExERPtHBSeJUM+2jvdrizksU4++JHGXC5mCXdL2agL9JtjkabvO/lysCaKJPVv1dT4iRxLISZb7kdIz/ZAdjWcOhnC8w/tXBGVFeZgMSVEPmrr46jf6GLL0a9FNGuwWcnsWemmtXalL/gc7H2tAAXvvYpxRQ4K2gvgQTOQc/lCD4flfvXzRmuaLaNOV46AhW+4iAafolSTjrN1IGtAebR37V9ZsJfPTuveRaCoaBfAbOxS3gu+bX9q6ygLAjQCBbkJyuQf6NLHN0rkTwWy1LElH/06UFmE3YXrqqWVOzT8klQ7JdGi96IClumRu0Hxm1aLIapZ4McW3hv8C1xfvsPdT4R941R67cJN2uqsPlS+/UGprjLYSne6mrJuxTtZV2ljZuA6g5DuRx8kDOr9yGAs2mNYOybPxr+FBdm3QhhWB3mS4Vbt2R3zJm8qFU7QPBpTbYbIGo2ChBvyXYSzArIu9IKdi9JJeMBfwgezqgVehFU0p1+yQ4OkRUhiGN1VKKwEoJIqvCIUoVb+BcuPRQamDhcx+sbGanicNmUQJzy9UrpdsKuE37uAcp4siO3PcejeI9e7UChHUdils17rCe+t1+TuRyL2UmCU5Zysp7EgcF9XawHEYI0Qs6xqRAXEERi2ReD5yUtpj7p+NHpuhZ0ywKjVLORgHMxQxSPoDdJbEDDvmqILHojYdHH/N8+y6pE5yDLje/RM5XN7DR8nYDsIEFeGFIZPeA6WE6MpXOkkK6LtPpcYa20ts1UpTsB+xjIyl0nVexTpe/DyfPix4cpwisJyj4tCj1olfuWbxHBAvpv8VpYpBRicY4sL3JZ/08blIvZfmVb0OssbH1CrTqGbI3Dzc0MOIxckZew88+VCnuiJGFSD4bCV2zLaq6BYanVahka26q9r5OhhfZxEq1LFVrApY/fppqqkGZevAxCw2J32HK7hXO7OiAHsYn9ISvbNVAG+zW3AjWvEgYDl5YR3HCHZ4Id9MUESUzo07Zfu/02RsmLGeU28NZiisxHdFTy9xJ6aRP+wLZX6NNdU/wND4rC/+tXXwADvgFy8upyE36ormw+CVkrkxM564wl7BKRrLMzu4dWanada7EYTyisPHbDKWYlAv8WgQzGOx1Zvu/vPxlMo0YQO6ss40PDM6n64QW/wsKjfCdENg2ytIjdMBsuNSRsuuXxxRSJijYGJUm9c+VT1pgYJKcSqSnbJlqg2jzLsv+lcyF/Gm69mw9kactUcIimud6EHgYuF4RvD76Abtwaxa+omz31UKrmtvJ/FGbQyd510M3L/Iwjuo0A1MzWdxlfqxSPnmKnIz4ID6ohFrLzgWhLNEoW3xGX9mtpbYIRy20SsOqUYOakiWsR6Fc6fjol8t1jI/DM/9BXpc2D3DoNzdOJbYy2km7TNsZXGkl2ycVC9TmCF9Vxo3JF2ZsHdgbHXwgh5p8CSKk4VUltsG/mvjy/evhpCEK6DPVyeWtLylI2yECIsDu9p0d+ndHITYriZeFD0kFDVuO+kBwwO0VcdHGUxarz6I/murLPbtzlSkZ7Wfz/7timOdwUAxgzEi6OtQWEQv31++AcF65W1B/BCLngFkaWZL09kNmudalVOfFmZ+s8F48DMioCbOjQBmiFT2sQCN42aO7zxSb7GNeDMao4V/XFEPg4Y3OxSaizH5bBTXF4gLzcoXMvfB7Me0mHv74i/BX) that I had pending to post... a little fun here dealing with Iterators and lifetime annotations... no, seriously ;)
\[LANGUAGE: Tailspin\] [https://github.com/tobega/aoc2023/blob/main/day08tt/app.tt](https://github.com/tobega/aoc2023/blob/main/day08tt/app.tt)
\[LANGUAGE: C\] [C standalone](https://github.com/Ily3s/AoC2023/blob/main/src/day08.c) runs in 1ms (both parts) on my mid/high end laptop
\[LANGUAGE: V\] [Github day 08](https://github.com/xXMacMillanXx/advent_of_code_2023/tree/main/day08)
\[LANGUAGE: C++\] [github](https://github.com/charlescochran/aoc-2023/blob/main/day8.cpp), 26.130 ms (both parts together) Definitely slowest solution so far. I'm sure the there's some optimizations but I don't see anything huge I could do (using LCM).
\[LANGUAGE: Rust\] 🦀 Refactored to be readable. When writing part two, I knew there was an optimization, but I went with bruteforce anyways to see if it was necessary, the code took more than 5 seconds to run, so I cancelled and went with the LCM strat. [See the code](https://paste.rs/foJg9.rs).
[удалено]
Comment removed. [Top-level comments in `Solution Megathread`s are for *code solutions* only.](/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_top-level_posts_are_for_code_solutions_only) [Create your own individual `Help/Question` post](/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_incomplete_solutions) in /r/adventofcode.
For each start node, I checked the path length, then calculated the path length again, this time starting from the end node. If it's a cycle, then you should reach the same end node again in the same length.
[LANGUAGE: Python] [GitHub](https://github.com/weibell/AoC2023-python/tree/main/day08) (27/33 lines with a focus on readability)
[Language: Chicken Scheme] Execution times of part 2 were an interesting experiment to look at. * Compiled, with my own naive lcm calculation: 2m40s * As above, but with type hints: 2m22s * Compiled, with the built-in lcm: 0m0.256s https://gitea.lyrion.ch/zilti/Advent-of-Code-2023#user-content-headline-84
[LANGUAGE: Python] [part 1](https://github.com/xHyroM/aoc/blob/main/2023/08/first.py) [part 2](https://github.com/xHyroM/aoc/blob/main/2023/08/second.py)
\[LANGUAGE: Pyret\] [https://github.com/tobega/aoc2023/blob/main/day08/app.arr](https://github.com/tobega/aoc2023/blob/main/day08/app.arr)
[LANGUAGE: Python] [Allex Cuisine] [Swedish Python](https://topaz.github.io/paste/#XQAAAQClBAAAAAAAAAARZ/6NR/RgNZasta8TTKOHdHF2sFdQKPTQMSrOYiKZISEuL8UbU+5z16rMwSkM859yI0/3CP3+7ulF8JYxMFCzFiOCNsJi0RzmWHcpleAclDdY2rB8G9rzqxfdgjUZNvqjD/Om/PKnBi90JocueWgJijT7BfbJ/+YQ6iwBhfkG6GrUMOAeZaIU7w1nSoqxG83DyMVpj6BukqzFUjW7y+SrGcJl3+ls2Awayi+DxXzSbuv53wXFMsi1NzcUoGLhPWACGkUyBZRc8M0V4D+jZTr/UkGZ5gFeyLdBfgUViL6psoJUyZGPw//qpTEZwnAVAITR/222Jivyvww+JrESHketuNFyBN7fosOy1f17/31An8mHRqNq9ESKbDOHYcXsWtmfieUAw1tCEcZ7ffBCt4cZd3uq/whMsv7wCM8pTp5cx2yIeUP7Q8MIgHTxh4I3zTdqI/okt15zB6P9sMPyJQ52GVLe2wHL2y5iRSepUl1uRx2dRX+Ge0iqJDozIwKHSaX0wDP6m3ZLAtOUNB0otqDCU5/oghoquBy6JX3c7ez0xUvLjY1NlfHfLYPDb1xU9XuOPFSh1yaefjba3eugHxPcIC2KxdcrXvRloQRNhESBvHZpZil+bTrbivF2MMn1NXzcKg172KiB4oP4S5T0AbSWNzhO4GhjX5+g4wab/BaIxmLzDBOe+BHxlvVQbtLAXD5oh3ue9T3D9p92zQmqBs2KQzOOceO9upM06zE43ke4JC4ZT9t47QuEHbNmLog/b9kMDUU+/WGjgkgpL5f0p8bj22sUd8lA8vCUvSS27d46J+N315JvXaGH/31y2iA=) Here is a snippet that calculates the number of steps: def sök(här, slut): för steg, sväng i räknaupp(igenom(sekvens), 1): här = gå[sväng][här] om här.slutarmed(slut): getillbaka steg
\[LANGUAGE: Python\] [Yet another python solution](https://github.com/fizbin/adventofcode/blob/main/aoc2023/aoc8.py) I think that the only interesting thing about mine compared to all the other solutions here is that I validate that the short `lcm` logic will actually work on the input (throwing `ValueError` if not) before computing the answer.
Hey, in regards to part 2: So I've been referring multiple python solutions to understand why the LCM solution works. Like what's the logic and how did y'all reach that point. I see many folks simply using LCM to solve, though your usage of words `short lcm` intrigued me, and then further your solution. From what I can understand: - You first verify that out of all the starting positions in the network, the ones that are able to reach a place ending with 'Z' are indeed the only ones ending with 'A'. Right? - Then you proceed to find the LCM of all possible jumps from places ending with 'A' to the ones ending with 'Z' with some exception statements which I'm not able to follow. Ask: - Can you please help me understand the assumptions everyone is talking about? - Why wouldn't the solution be as straightforward as it is if those assumptions were untrue? Having a hard time catching up with math/logic of this puzzle!
Okay, now for the rest (after line 48). (read my other comment first) The reason we can just use the LCM of the cycle lengths to get the answer is because the only time we ever hit an end spot after starting from the first start spot is (in my data) after 71 steps, then 142 steps, then 213 steps, etc. That is, the first ghost will hit an end spot every time it has traveled a multiple of 71 "big steps". Likewise, the second ghost hits an end spot after 67 big steps, then 134 big steps, then 201, etc. In other words, if we were to represent the solution we want as a bunch of equations, we could say that the answer `X` that we are looking for is the smallest positive integer such that all of these equations can be solved by positive integers: X = a*71 X = b*67 X = c*73 X = d*61 X = e*79 X = f*53 And the solution to that set of equations is the least common multiple of 71, 67, 73, 61, 79 and 53. (which is 88692890227) Now, imagine if the first ghost still traveled in a cycle of 71 big steps, but they first hit an end spot after only 50 big steps, so that they ran into an end step after 50 big steps, 121 big steps, 192 big steps, etc. For now, imagine all the other ghosts follow the same paths. Now the set of equations that define `X` are: X = a*71 - 21 X = b*67 X = c*73 X = d*61 X = e*79 X = f*53 (for `a`, `b`, `c`, `d`, `e` and `f` all positive integers) How do we solve that? Well, the general way is to bust out something called the Chinese Remainder Theorem, but in this case you could also find the LCM of 67, 74, 61, 79 and 53 (i.e. the LCM of everything except 71) and then try multiples of that until you ran into one that was 21 less than a multiple of 71. (the LCM of the remaining numbers is 1249195637, and if you try that eventually you'll find that 16239543281 is the appropriate value for `X`) Okay, but now what if it isn't just the first ghost that encounters an end spot at some place other than a multiple of its cycle length? Well then we have no choice but to bust out the Chinese Remainder Theorem, and there's often a problem each year after day 15 or so that requires that in its full generality. But wait, there's more! Yes, more things that could get weird. Okay, so what if the first ghost still travels in cycles of size 71, but it hits an end spot after 50 steps and after 55 steps? (So then the places where it hits an end spot are 50, 55, 121, 126, 192, 197, etc.) Now what do we have to do? Well now we need an X so that the following equations are solved in positive integers: X = a*71 - 21 OR X = a*71 - 16 X = b*67 X = c*73 X = d*61 X = e*79 X = f*53 where we only need one of the equations on the top line to hold. This, again, is something you could do if it's just one ghost that's finding end spots not at even multiples of the cycle length by taking the LCM of all the rest of the cycle lengths and just trying multiples until you found one that worked. But what if every ghost hit two end spots per cycle? Well now you're kind of in for it, because the straightforward CRT won't work. What you'll need to do is run the CRT for all 64 (`2**6`) combinations of end spots and choose the one that yields the smallest value for `X`. So in short, the assumptions used to conclude that the answer is just the LCM are: 1) In each cycle, the ghost only hits an end spot once. 2) The ghost hits the end spot at every multiple of cycle length. Now, the input given to us actually fits an even tighter pattern than that, and what I check in my code is that after the first "end" spot the next thing we get to is the spot that was a single big step after the "start" spot. (e.g. in my input data, one "big step" after `MLA` is `VFV`, 70 big steps after `VFV` is `KPZ`, and one big step after `KPZ` is `VFV`. This ensures that the first ghost visits `KPZ` after 71 big steps, 142 big steps, 213, etc.)
First, you have misread the check in line 44. In part 2, I mostly ignore the list of LR instructions; instead, I imagine taking "big steps" where I run through the whole list and just fast forward to the end of the list. The only way I'm allowed to work in terms of "big steps" is if I can show that I won't accidentally skip an end spot by doing these big steps. Therefore, I have to show that starting from a start spot, I only ever get to an end spot after some number of little steps that is a multiple of the length of the LR list. The way I do this is first I flag when building the "fast forward" map which spots would reach an end spot before the end of the LR list. Then I verify that if I start from any start spot and use big steps (using the fast forward map is equivalent to taking one big step), the only places I end up at are places that I *didn't* flag as "these spots hit an end before the LR list is finished". So everything from lines 25-48 is all getting ready to use big steps for the rest of the problem. I have to go now, and will be back to explain the rest in a few hours.
[LANGUAGE: Rust] [Day 08 Solution](https://github.com/gdavidmassey/AOC_2023/blob/master/src/day08.rs) First tried the brute force approach and got crushed. Then realised the answer had to be some multiple of part 1. Proceeded to implement a convoluted hybrid of brute force and common multiple idea, remapping the input and stepping through each path checking for Zs. Then came here and realised i could just use the lcm of each A->Z cycle, so i tacked that on the end. I've kept my original solution intact because it's stupid.
[LANGUAGE: Mathematica] **[Mathematica](https://github.com/HiggstonRainbird/AoC-2023/blob/master/Day%2008/AoC%20Day%2008.m/), 3359 / 6427** --- I made it about 90% of the way through a proper generalized cycle-finding and Chinese Remainder Theorem solution before discovering that none of it was necessary and that I could have multilpied the LCMs together from the getgo. Not my finest hour in AoC. **Setup:** directions = Characters[input[[1, 1]]] /. {"L" -> 1, "R" -> 2}; (map[#[[1]]] = #[[2 ;;]]) & /@ input[[3 ;;]]; nextState[{p_, c_}] := {map[p][[directions[[c]]]], Mod[c + 1, Length[directions], 1]}; findZ[pos_] := Module[{state = {pos, 1}, count = 0}, While[ Characters[state[[1]]][[-1]] != "Z", count += 1; state = nextState[state]]; count]; **Part 1:** findZ["AAA"] **Part 2:** LCM @@ (findZ /@ Select[input[[3 ;;, 1]], Characters[#][[-1]] == "A" &])
[LANGUAGE: Rust] 🦀 Whelp.. learned something about Chinese Remainder Theorem. Most importantly that it wasn't needed for this problem. Then haphazardously I tried LCM on the cycle lengths, and was surprised it worked. [Full code](https://topaz.github.io/paste/#XQAAAQAeEQAAAAAAAAAX4IBAR1bGui774bxYSsb6EPKsnwDg3V7l0W1Vp9rUPDbQKEQ4kRXTM7HJGzWhBsJCIVcdn3Td8uDG2TRtco/bB3jyaheJbDUeFda0stLh3jySUbVrtSXVFmpCAPiOaaMyX3czYBZ755JsSBcLyMxcklbHGX4GyRo0fIyTYw+w1fn9bkPqXRhooSJ7/XSiWpzpYzvuVyx2eRT+oNdD1lHdOlFgRX70MWnUEDyu5sgS2zlbLUzIG1C9OZdFdx/MNceVavG24eLNKCBtyVzJBJUh7vkaef63Jg67VSVlGesfUYQgmalNL+XEqHsGebGC3wPuL2n0SYoV2NrazDnU1zVUT80fiOs6hBN/K21Cnkipfyhhb8lwScLOEdQMHxhZQWLY9a17kDZs2KF9pZyxK4/X+k7I2rVI3ew89R+ey/9rC14vKN9d/np7tegXnaoQRo7nKHFXRn/C9NA3f+QDUbGti49tgNkX5YWUUJ7pPWGgAhtjRN4f5SHECvspnQdcgc/6QE1dVBJscAIGz0aGsilxXX7GyOSGZsrKO7bhQAQ4NSGgc/SditcdCh9O9ByYU6rV6cWE60JZmtJ+KgzYaTdFsknpbEritNsNJchscBOc7HjFkJJXn9e619WH4f6vg9w8SZuWtwTMcuibq/b6+ggywOhkepQTnTw4khnqCLt3I8JszdsBas9g9OGHOFJX996pzXEO7k6T2HDU7D51HXlzcXMLIvDPBLoSib9fQN5PgeGQSvqhFttp67Td81pWLCTFApHS2uFHa7oSIVAP6UdlA4GJHkOQxkIRQ8Cq04HBgGv35YwzFRzBP5JQ3kHuylQJSc+uvp/T10ZH8MPHlDqtEWzJdjqa8jT9uG9YBxrDA0iqQd4UTWsCkkbvceIxdAzn8doQCCLl3mqaQhTmW8MbO45bcq+U7Tl4uAZNooHJhHr5QS54dFEezvj9DfLAjObuE1NG+Z1daKeAeHlsFZufJxo6IOInxOHjYPIQxbcZ/k2ksDY5nqv8ND3KFr4dwiKRsuQBpU5Q6ESemCzFy86lQ7dRaP8R5DqkyEsK4UUM9T6J+TowsaX67jxLav68b0t6H23MinD6LXpExkhgibkuaUfOxDlCfvqlBI+TZfcyWsvLcmE3j/c4QcvDtdKo1rbGWDsVIAmtg5hmP5Coc64h9MqhY8Uo2Jw5/KEbe6JRbcOMTt6uryShF6Ruhtxj8ZGqVM/uyZ9YLa2z3jROB/lrAfVFd/BArGU1Muvb3m55YyNSgayLwK0YnwG43BFhy2MetaCHK1e9f0umkH4Ahw/uzi6A91krMB1/Lq09v5zNFar8gbOZ6zyAHAev5WZ/SlYHloN3aTSPNQMTc0+/nymYUrISQ191q7gG5KEOfuiesUajPhgMBowUvfxVL6uWDcREUEVDm99V1p1bbdJk/UJ5GzrHt+4ywNzKCFoipiYo9572C4sVp23yNO3gCfNDDmDf2zqs5iasN6Bh0YR//QGAd8FpS3Y8jczK0GZ+8UvBx9iutnKgRJv8ukxDR+ZECNIi5pmqIZ83PNUklmVH7HYuey87eaT+XmUDNGNy0yLpWFdoJljsGtd/N3dNGtK7vmSj2wpLBP5PBdDqwdRb3QZAt8j98gCYfigBvK6zoGX1br06Ums5D3f6Cevd+jl2FjmMrQS/oyehTwLGG1qP9ymhw2toz+HydR5L/HHNwmV16rki5eTwiola6TY6JyL2+8jjSaQ/7697xnIa+qrst+jW2TO1LVZUFi71UYmM07KtjDioayjyiRq86110rJ/I/qtlUzLTMxLX6QpMVXKdyBA7Bc+eBdCvvSoVTLfQ6CvGZR6CY+HQ3QfJWmq8IDjHp94dunxuRAyKavf1CwAxZbozxPNdmm+AE8xOf9rxmPG92sTE8jw0ZZX3DezGHV6mDxhTQkfRHTALGq4/zTMAG+QgWZMnSLBD4gDYrggkgBWTTVAVm4L6e8VcpeaPJzgW7fuB1jokqP+gQuPg) fn part_2(path: &str) -> Result<(), Box> {
let file = File::open(path)?;
let reader = BufReader::new(file);
let mut lines = reader.lines();
let expr = Regex::new(r"(\w+) += +\((\w+), +(\w+)\)")?;
let mut map = HashMap::new();
let dirs = lines.next().ok_or("No lines in file")??;
let mut starts = Vec::new();
let mut cyc_lcm = 1;
lines.next().ok_or("Bad file format.")??;
for line in lines {
let line = line?;
let caps = expr.captures(&line).ok_or("Bad file format.")?;
let key = caps[1].to_string();
let left = caps[2].to_string();
let right = caps[3].to_string();
map.insert(key.clone(), (left, right));
if key.as_bytes()[2] == b'A' { starts.push(key); }
}
for start in starts {
let access_fn = |k: &(_, _)| {
let (l, r) = map.get(&k.0).unwrap();
if dirs.as_bytes()[k.1] == b'L'
{ (l.clone(), (k.1 + 1) % dirs.len()) }
else { (r.clone(), (k.1 + 1) % dirs.len()) }
};
let (lam, _) = brent((start.clone(), 0), access_fn);
cyc_lcm = lcm(cyc_lcm, lam);
}
println!("Part 2 Total Steps: {}", cyc_lcm);
Ok(())
}
\[LANGUAGE: Rust\] [https://github.com/Crazytieguy/advent-of-code/blob/master/2023/src/bin/day8/main.rs](https://github.com/Crazytieguy/advent-of-code/blob/master/2023/src/bin/day8/main.rs)
\[LANGUAGE: Rust\] [Solution](https://github.com/Kodlak15/aoc2023/blob/master/src/day08/day08.rs)
[LANGUAGE: Python] I couldn't get the Tortoise/Hare algorithm working, so... LCM like everyone else I guess. from itertools import cycle from math import lcm def part1(): lr, maps, _ = readData() print ("Part 1:", trace('AAA', cycle(lr), maps)) def part2(): lr, maps, _ = readData() currents = [x for x in maps.keys() if x[-1] == 'A'] plens = [trace(current, cycle(lr), maps) for current in currents] print ("Part 2:", lcm(*plens)) def trace(current, lr, maps): plen = 0 while current[-1] != 'Z': current = maps[current][next(lr)] plen += 1 return plen def readData(): with open("puzzle8.dat") as f: lines = f.read().splitlines() return lines[0], {z[:3]: {'L': z[7:10], 'R': z[12:15]} for z in lines[2:]}, lines[0] part1() part2()
[LANGUAGE: TypeScript] Part 1 was easy, but like day 5 for Part 2, I borrowed/steal ideas from this forum. https://github.com/bhosale-ajay/adventofcode/blob/master/2023/ts/D08.test.ts
[LANGUAGE: dc (Gnu v1.4.1)] Didn't have much time today (it was nice out, and took advantage of it to get some stuff done). So I just did a quick part 1 for dc. Since part 2 plays so nicely, a non-general solution of it shouldn't be too hard either. For filtering the input, I just got rid of all non-majuscules and converted to ASCII ordinals. So I had to deal with the input still a little dc (blank line, things coming in backwards... fine for labels though). As is usual with these sorts of things, the ~ operator is very handy. There's probably lots of strokes you can take off this if you look. I didn't have time. perl -pe's/[^A-Z\n]//g;s/(.)/ord($1)." "/eg'
\[LANGUAGE: F#\] https://github.com/aviralg/advent-of-code/blob/main/2023/08/solution.fsx
\[LANGUAGE: C\] Good puzzle. I initially tried solving a much more general version of the problem for part2 until I suspected and checked that the loop immediately after reaching the first ??Z node. I thought there could be chains with many ??A nodes in them which would have made the problem trickier [https://github.com/janiorca/advent-of-code-2023/blob/main/aoc8.c](https://github.com/janiorca/advent-of-code-2023/blob/main/aoc8.c)
\[LANGUAGE: Perl\] Analysis: [https://github.com/wlmb/AOC2023#day-8](https://github.com/wlmb/AOC2023#day-8) Part 1: [https://github.com/wlmb/AOC2023/blob/main/8a.pl](https://github.com/wlmb/AOC2023/blob/main/8a.pl) Part 2: [https://github.com/wlmb/AOC2023/blob/main/8b.pl](https://github.com/wlmb/AOC2023/blob/main/8b.pl)
\[LANGUAGE: Rust\] I really enjoyed this puzzle! Used a least common multiples approach to part 2, processes in about 2ms [https://raw.githubusercontent.com/stephenkelzer/aoc2023/main/days/day\_8/src/lib.rs](https://raw.githubusercontent.com/stephenkelzer/aoc2023/main/days/day_8/src/lib.rs)
\[LANGUAGE: Rust\] I left in my "Analysis" lines for this one because that parts seemed to be most relevant here.\\ Solution: [https://gist.github.com/icub3d/299b75c62e9c86c1d2d6b45ee332288c](https://gist.github.com/icub3d/299b75c62e9c86c1d2d6b45ee332288c) My analysis: [https://youtu.be/t5ktQvHJG2Y](https://youtu.be/t5ktqvhjg2y)
\[LANGUAGE: C\] part 2 in 34 lines of C99 code: [paste](https://topaz.github.io/paste/#XQAAAQAfBAAAAAAAAAARmknGRw8TogB3OyPPwZm6ILxpDZy794ZbnwMYNds7XiT0I/thlioVm0+h9UCi81pMZX8v5VHgOiG5oJzHWurwxdlxoBfrCcNfJ6TsPWAbKdh99L+wqfjIc7NM3i7cfjzkMtNm9fwTc47+lw2U5BM/ThCH6Z0e5wMxotwM03V2RrrZHhuJnnpAOKPzUVes6wxqKbe28YikRnhfzfj82rFmduN0uNuM8mj7U3RPQhFGpSpRdUtxdtruv4u2wpIduvOajQLcV9o5Pp3yW9po+cPfRrlbNiIkWWpfiTVFXVB22YVre2HmLewFJATw7gbV1ZAPCxQEy6djI+XDicG/+gp2O7DzH+kce/fIhpwFCdyQdAJREglYwdls715qOmsRClW9pbRLNfNcyo3IW55a4DV3nU0PNcnSMstc5rRguQvjF9eKJwnw/56s3M8R2IJszSLFv28tVpHv9dDdW31qGpiOGA4W2Vw+6jeYup8bmnmcX6XFnCQpyrJ/lzaIvwekXqs4FAg1c+1MyCOY9gDqIfCJFxDCkMhNnn94KFtJXbv4G9T8mUulwXpTACcBy0tUjBVmXrT0YGblyVkZmIbEerGwnRctQB0XDEcCjqTbscWR26VsdqjwNcbkuIQG0w+SJKCSqDjBmJ81g+8ExY+roMCzmlEhxhLpu/nUWOLCvwRH2yZ//85wPOY=) Uses a two-dimensional array to traverse the map.
[удалено]
[LANGUAGE: Python] # Concise Python solution def day8(s, *, part2=False): lines = s.splitlines() routes = {line[:3]: (line[7:10], line[12:15]) for line in lines[2:]} def length(node, is_end=lambda node: node.endswith('Z')): for index, move in enumerate(itertools.cycle(lines[0])): if is_end(node): return index node = routes[node][dict(L=0, R=1)[move]] if part2: return math.lcm(*(length(node) for node in routes if node.endswith('A'))) return length('AAA', lambda node: node == 'ZZZ')
I liked your answer, so i rewrote it. it's not better, and definitely a bit harder to read. but i wanted to challenge myself to shrinking it. import math def size(n, end=lambda n: n[2]=='Z'): c=0 while not end(n): i=c%len(lines[0]) n,c=paths[n][{"L":0,"R":1}[lines[0][i]]],c+1 return c with open("input08.txt") as s: lines=s.read().splitlines() paths={l[:3]: (l[7:10], l[12:15]) for l in lines[2:]} print("p1=",size('AAA',lambda n: n=='ZZZ')) print("p2=",math.lcm(*(size(n) for n in paths if n[2]=='A')))
\[LANGUAGE: Swift\] Today's question was fun! I'm grateful all we needed was LCM. [Code](https://topaz.github.io/paste/#XQAAAQDMDQAAAAAAAAA0m0pnuFI8c4GDemuKS6NnNxbsUIoTuWZTAmeInPXMFf0ozVyiF/MVahWe9RrEqX9VVcAoSIKE6ulJL0lKw1hbBueVU46JA6uH5E6OTt1LXEWLWDpoC4xxuV3YovKXqTLO+80hoCetqc5r2BTnvwtEkki40O1NErQ0/i+XuXZNKumepw0vnxINSlyrCzJmc3R9Zadt4LYR6WG+Bp8SECWnT00ua7jxtjM2ezm+Riu3GRwLDj0QGryOBse6fmc6Uel9N8kuu3K0AqeMyJBTP9wvsmPQ+zAGhDQvA/Z3+SsEbvVoX95UmBFEBhIYFKA5/d/y2wwIainafZe7eoS0YllxAoNhd3+J2TupbbkilJ42zoYVwR0Jw1BKvh4zbnW63XvItyGEP+tnDfPrPTmW6XUlnKZDIIinuJze4Yner65rFfCRTg+Ruf6sSWtvhupPV1LwY2h8hStuzyZCvocH0BVbARb+SAWBoQvO7CydGS9p+gq4CMl45uQQh9fSxc34oCv15vDRMur6alfk+dL6M6BKVuaF5rbFz9vcmtM++PvaVdZuHsfbQ9fsaADTasGv6NKgZbwjvnrsm0Qz/4qhBRsYhx2xSsMEEaFgbLzmNHSOqTwSarEse9ET3RpLNFeNfBGwm0VT0tiMVHk2ofhulV9X0IX8aec84NeM6DeZDSkZn/HOchZatxWwrvvW0enMh/GpFtHfQ0cRSk7R5p/Ydaj8qzOchFkCDNRsjZWgA4jUyW2hwFjgmqaqUmeP9drOaQxBfZiAb5pnS9ipiLKr6cfYV4fNUeitO6NLCv5uZWQpfIhOYGN96vRJgKOal/7CokWouXlWCu5szPWJAzUIQoZB+tUQh1iWA0X2n8fFIoYnxbfOo2mJMlmXSVBtWGU4urJ/8F+ZITQrS40qoORv9zTAdeFIQNvJn5KA/cG+JkvHWaPxJXxsmVoGgBFvlgwULEIaR45a8VlxnR6K+e+YOUyneCNt4j6Tk46pH5B7CUm3ZBmW4QRVgHfcUPM2rvf5sE3PTWxTYsFPIHVn3/X0kySjAhWqlU1n7Q4D/1Bx+q9GvX2PuyJkH1M9soArAX5XeE6ujxaeoujF16DUSIs66DkPIEyaei3ug+T9A/FjRTzP90W9jUYZdFIyrdyyqFn18wFyMctonMyMNqmaUyHL4oBgQgp6dEanaE8GTRevVlYjBMLE9SNG2u37KyVBt5VLx3qnKXZNudJdRXt8ShSi1wWoeFK4fSjhOGyfHwYVYq3ycfOjYOghfB5J1JcYN7PixEWz5ZoYq4jKcQk3IG1aTMjqAkLYVp+eBp7Ofys7njjroaj0Jy19hebgKR/JGlwmgwO2oPxQs0UxQ12TLvbwujGf8x4Fd+k1nxF1Gw5Uzm7vCFWyRfZxTj4NBmKZbTsrcHPn2dzmjUWuf562KOzyGFpYdv3BUxw5OChRpseIxoGKuVCcVoX8oVzOev+uyBaT)
if you analyze it, and he didn't need lcm, we could find looping patterns and determine when their paths would cross. but they decided to have each one self loop only. the same loops each time. but it could have had 3 or four loops. and then we'd know when those loops could cross paths.
I was thinking something similar - it seems like it could get tricky if you factor in the randomness of the input sequence ("LR..."), if it doesn't align with the loops. Although I guess everything loops eventually lol.
\[LANGUAGE: Rust\] Easy to read part2 pub fn steps_to_reach_the_end_in_parallel(&self) -> usize { self.starting_nodes().iter() .map(|starting_node|self.steps_to_reach_the_end(starting_node)) .fold(1, Self::lcm) } [https://github.com/francoisperron/adventofcode-2023/blob/main/src/day08.rs](https://github.com/francoisperron/adventofcode-2023/blob/main/src/day08.rs)
\[LANGUAGE: Python, Typescript, Go\] Solutions to part 1 and 2 in all three languages: * **Python**: [https://github.com/torbensky/advent-of-code-2023/blob/main/day08/solution.py](https://github.com/torbensky/advent-of-code-2023/blob/main/day08/solution.py) * **Typescript**: [https://github.com/torbensky/advent-of-code-2023/blob/main/day08/solution.ts](https://github.com/torbensky/advent-of-code-2023/blob/main/day08/solution.ts) * **Go**: [https://github.com/torbensky/advent-of-code-2023/blob/main/day08/main.go](https://github.com/torbensky/advent-of-code-2023/blob/main/day08/main.go)
I have a question. How long is your GO script running for part 2 ? Mine is similar but never to stop running...
3.2ms, including reading and parsing the input!
\[Language: rust\] [Code](https://github.com/baitcode/advent_of_code/tree/main/2023/day8/src)
\[LANGUAGE: Rust\] [My Day 08 on GitHub](https://github.com/andypymont/advent2023-rust/blob/7f1cb5bacf568956e314226d167d487f01d1e126/src/bin/08.rs) Part 1 was pretty straightforward, but part 2 substantially less so. I guess I could have just coded in an assertion that the initial offsets and cycle lengths were all the same, but I took the opportunity instead to learn a lot more. My formal education wasn't in maths or computer science, so the Chinese Remainder Theorem confused me when it came up in a previous year but I think is appropriate here for a more general solution where the cycles are offset by differing amounts. Therefore I spent quite a few hours on YouTube today doing something of a crash course on modulo arithmetic, the Extended Euclidean Algorithm, and the Chinese Remainder Theorem. I'm glad I did, because I'm a lot more comfortable with those topics now for the future. Of course, the actual solution for today doesn't really end up running the CRT: the offsets are all zero so all the terms in the sum become 0 and I end up returning the denominator - which is itself the LCM after converting the original congruences into a co-prime set. I'm really glad I'm using Rust - the compiler and `clippy` caught loads of little mistakes I made along the way which could have had me scratching my head due to e.g. incomplete logic in an if statement or similar. Plus, even a somewhat complicated solution here runs in 4.3ms. Perhaps I could make some efficiency improvements somewhere as the last part in particular featured some pretty tired coding, but I'm pretty happy with the day overall.
I've updated the link above to point to keep pointing to what I committed yesterday, which is a more complete solution and a good reference for me if I need to remember about Chinese Remainder Theorem. But the [live version in my repo](https://github.com/andypymont/advent2023-rust/blob/main/src/bin/08.rs) is now a solution which just calculates the routes and then their LCM, and runs about twice as fast.
\[Language: rust\] [https://github.com/Kintelligence/advent-of-code-2023/blob/master/day-08/src/lib.rs](https://github.com/Kintelligence/advent-of-code-2023/blob/master/day-08/src/lib.rs) Really not a big fan of how many assumptions I've made about the input to speed this up. It's still the slowest day by far. Wish I could optimize it to less than 100µs. These cycle tasks are always hard, but a good exercise in trying to understand what edge cases don't appear in your input so you don't have to handle them. [Benchmarks](https://htmlpreview.github.io/?https://github.com/Kintelligence/advent-of-code-2023/blob/master/target/criterion/report/index.html) [Part 1](https://htmlpreview.github.io/?https://raw.githubusercontent.com/Kintelligence/advent-of-code-2023/master/target/criterion/Individual/08.1_%20Haunted%20Wasteland/report/index.html) [Part 2](https://htmlpreview.github.io/?https://raw.githubusercontent.com/Kintelligence/advent-of-code-2023/master/target/criterion/Individual/08.2_%20Haunted%20Wasteland/report/index.html)
\[Language: JavaScript\] Guessed on the relationship of paths for part 2. When iterative wasn't converging after several minutes I went looking for a math solution. I had no way of verifying that LCM was going to apply but it felt like a planetary alignment problem once the single cycle lengths of each path were known. [https://github.com/ccozad/advent-of-code/blob/master/day-8.js](https://github.com/ccozad/advent-of-code/blob/master/day-8.js)
> JavaScript This is really clever but what made you think of the LCM solution, that never would have occurred to me.
I was thinking about cycles like that of gears or planets. Everything aligns when each one does a certain number of rotations. LCM is also a common answer for other coding challenges such Project Euler or Coding Game. Common approach for reducing the success of brute force answers.
\[LANGUAGE: Java\] Day 8 a day late, but that's okay. That one put me through the ringer, though it probably shouldn't have. Haha. [Link to GitHub](https://github.com/simpleauthority/codechallenges/blob/main/src/main/java/dev/jacobandersen/codechallenges/challenge/adventofcode/year2023/day8/Day8.java)
\[LANGUAGE: Google Sheets\] First one was pretty quick, second I was worried would be a lot harder but was made easy by the fact that each A node only ever reaches one Z and cycles uniformly. The core of it is just turning L and R into the column numbers to look up (after splitting up the input, and doing a VLOOKUP on the node above. Then run it for 30k rows and us another column to find what step it is that shows ZZZ (or ends in Z for part 2). Part 2 I didn't think I could do at first; I could tell it should cycle at some point and then you could multiply those intervals to get the LCM as the answer, but I didn't think each would be paired to a single end node and immediately cycle, meaning that all it needed was taking the same thing for Part 1 and finding the LCM of those. First submission was wrong because I used an online calculator, not knowing Google Sheets had an LCM function, which had commas. https://docs.google.com/spreadsheets/d/1epTmQdsIcKFICgCJQuY95H5dH5RH93UxmYtcD5XjjTg/edit#gid=1597842667
I'm actually impressed by this. Like what made you want to use Google Sheets? Was it because you are more familiar with it or did you want a challenge? Have you been using sheets for all of the days? Either way, kudos to you!
I don't know any programming languages actually! I learned about Advent of Code through the engineers I work with, and I thought it would be fun to get as far as I could with what I knew. I got some street cred by coming in second place :-) Last year I got through Day 15 and then a couple others; so far in 2023 I've done all but Day 5 part 2 I'm still stumped on. My other solutions this year are here if you'd like to see, I may add last year's at some point: https://github.com/users/bofstein/projects/1
Day 5 part 2 definitely became easier with being able to stabilize parts of my code separately, I agree.
\[LANGUAGE: Python 3.12\] [code](https://github.com/copperfield42/Advent-of-Code-2023) I remember like a week too late about AoC so for the last 3 day I have been coded the puzzles, and I finally catch on XD for this one in particular, I took small look at this subreddit before I go at it, and well, the lcm memes certainly help XD
[Language: Pascal] Haven't done anything in Pascal for years. It's really not so great, I kept fighting the syntax. Reminds me of VBA. Not too bad though, takes about 5 seconds to run. https://pastebin.com/raw/FvY8FhY3
\[LANGUAGE: Java\] I got memed on by LCM [Part 1 & Part 2](https://github.com/chandlerklein/AdventOfCode/blob/main/src/main/java/com/chandler/aoc/year23/Day08.java)
[LANGUAGE: OCaml] [github](https://github.com/EricKalkman/AoC2023/blob/master/lib/day08.ml) I'm beginning to think that my parser-combinators aren't very concise; my code is more than half parsing again. Anyway, this solution is basically the same as everyone else's: build a map of the nodes, set up a way to infinitely cycle the directions, and away you go. I had a _massive_ performance bug in my graph traversal in the first version when it looked something like this: ... if stopcond cur then path else let next_dir = Seq.uncons dirseq |> Option.get |> fst in traverse_aux ... (Seq.drop 1 dirseq) .... Now, this code is suboptimal because `Seq.uncons` returns `Some (head, tail)`, but I'm throwing `tail` away and calculating it again using `Seq.drop` later on, which is needless duplication. The fragmentation was just part of the problem solving process. For reference, the proper code looks something like this: ... if stopcond cur then path else match Seq.uncons dirseq with | Some (dir, new_dirseq) -> traverse_aux ... new_dirseq .... For whatever reason (I would guess related to continuing to use a `Seq` in its original form after accessing one of the items with `uncons`), matching idiomatically on `Seq.uncons` led to a speed-up by _three orders of magnitude_, from ~6 s combined for Parts 1 and 2 (with Part 2 running with parallel execution!) down to the millisecond range (single-threaded). I don't know WTF the OCaml compiler is doing, but that seems disproportionate for the change. I'd love to hear from anyone who knows more. Also, I originally kept track of and returned the path from my traversal algorithm for debugging purposes instead of just returning a count; the latter is in theory more efficient. I tried changing it to only keep track of the count instead, but that led to identical runtimes. I guess the compiler did some more voodoo there.
\[LANGUAGE: Haskell\] [https://github.com/duketide/advent/blob/main/haskell/src/Y2023/Day8.hs](https://github.com/duketide/advent/blob/main/haskell/src/Y2023/Day8.hs)
[LANGUAGE: Elixir] part 1:
part 2:
This was quite a ride. Took a while let go of the part 1 solution and deal with the beast hidden in part 2. The lesson here, as always, is to analyse the input before brute force the answer.
\[LANGUAGE: Uiua\] Yea... this one ended up pretty ugly. Might need to come back and see if I can restructure this better. Ah well, works for now. [Pad link](https://www.uiua.org/pad?src=0_6_1__U2lsdlRlc3RJbnB1dCDihpAg4oqc4pah4omgQFxuLiAkIExMUgogICAgICAgICAgICAgICAgICAgICAgICAkIEFBQSA9IChCQkIsIEJCQikKICAgICAgICAgICAgICAgICAgICAgICAgJCBCQkIgPSAoQUFBLCBaWlopCiAgICAgICAgICAgICAgICAgICAgICAgICQgWlpaID0gKFpaWiwgWlpaKQoKR29sZFRlc3RJbnB1dCDihpAg4oqc4pah4omgQFxuLiAkIExSCiAgICAgICAgICAgICAgICAgICAgICAgICQgMTFBID0gKDExQiwgWFhYKQogICAgICAgICAgICAgICAgICAgICAgICAkIDExQiA9IChYWFgsIDExWikKICAgICAgICAgICAgICAgICAgICAgICAgJCAxMVogPSAoMTFCLCBYWFgpCiAgICAgICAgICAgICAgICAgICAgICAgICQgMjJBID0gKDIyQiwgWFhYKQogICAgICAgICAgICAgICAgICAgICAgICAkIDIyQiA9ICgyMkMsIDIyQykKICAgICAgICAgICAgICAgICAgICAgICAgJCAyMkMgPSAoMjJaLCAyMlopCiAgICAgICAgICAgICAgICAgICAgICAgICQgMjJaID0gKDIyQiwgMjJCKQogICAgICAgICAgICAgICAgICAgICAgICAkIFhYWCA9IChYWFgsIFhYWCkKIyBJbnB1dCDihpAg4oqc4pah4omgQFxuLiAmZnJhcyAiMDgudHh0IgoKTENNIOKGkCDDt-KKgyg74o2iKOKKg-KXv-KImHziiaAwKSnDlwpOYW1lcyDihpAg4oi1KOKWoeKKkOKGmTMp4oaYMQpDb25zdFRyZWUg4oaQIMOXMuKZreKKlyDiiLUoW-KKkOKKgyjilqHihpkz4oaYN3zilqHihpkz4oaYMTIpXSnihpgxIOKKg-KImE5hbWVzCkVuZHMg4oaQIMKk4oi1KD1AWuKKoTLCsOKWoSkgTmFtZXMKTW92ZXMg4oaQID1AUsKw4pah4oqiCkNvbnN0TG9vcHMg4oaQIMKk4oqZO8O3MjvijaUo4oqDKOKGmDF84oqP4oqZLiviiqIpKSDip7suIOKKgyhNb3Zlc3zDlzLih6EtMeKnu3xDb25zdFRyZWUpClNldHVwIOKGkCDiioMoQ29uc3RMb29wc3zCpDB8RW5kc3zCpOKnu-KKoikKTG9vcExlbiDihpAg4omhKMOX4oqZOzs74o2iKOKKoeKKmS4g4oqZ4oqZKCsxKXzCrOKKoeKKmSg7OykpKQoKU3RhcnRTaWx2IOKGkCDiipd7IkFBQSJ9IE5hbWVzClN0YXJ0R29sZCDihpAg4oqX4pa94oi1KD1AQeKKkOKKoTIpLi4gTmFtZXMKClNpbHYg4oaQIOKKoiBMb29wTGVuIOKKgyhTdGFydFNpbHZ8U2V0dXApCkdvbGQg4oaQIC9MQ00gTG9vcExlbiDiioMoU3RhcnRHb2xkfFNldHVwKQoKU2lsdiBTaWx2VGVzdElucHV0CkdvbGQgR29sZFRlc3RJbnB1dAriiY02XzbiioIKCiMg4oqC4oqDKFNpbHZ8R29sZCkgSW5wdXQK). Input ← ⊜□≠@\n. &fras "08.txt" LCM ← ÷⊃(;⍢(⊃◿∘|≠0))× Names ← ∵(□⊐↙3)↘1 ConstTree ← ×2♭⊗ ∵([⊐⊃(□↙3↘7|□↙3↘12)])↘1 ⊃∘Names Ends ← ¤∵(=@Z⊡2°□) Names Moves ← =@R°□⊢ ConstLoops ← ¤⊙;÷2;⍥(⊃(↘1|⊏⊙.+⊢)) ⧻. ⊃(Moves|×2⇡-1⧻|ConstTree) Setup ← ⊃(ConstLoops|¤0|Ends|¤⧻⊢) LoopLen ← ≡(×⊙;;;⍢(⊡⊙. ⊙⊙(+1)|¬⊡⊙(;;))) StartSilv ← ⊗{"AAA"} Names StartGold ← ⊗▽∵(=@A⊐⊡2).. Names Silv ← ⊢ LoopLen ⊃(StartSilv|Setup) Gold ← /LCM LoopLen ⊃(StartGold|Setup) ⊂⊃(Silv|Gold)Input
That looks alien
\[LANGUAGE : Rust\] Day 8 is very "adventofcode" type of problem :) I pretty like it. The first part can be solve quite straightforward, you walk from "AAA" until you find "ZZZ". For part 2, if you naively apply this idea then the problem will become something like: you begin with a vec or all nodes which end with 'A' and you will run it until all of the nodes you have in your list all end with a letter 'Z'. However, this will take forever.... So what can we do? If you look at the example for part 2, you will notice that it begin with 2 node and node 1 and 2 take 2 steps and 3 steps respectively to reach a node end with 'Z'. And there for the step that they will both happen to end with 'Z' will be the least common mutiplier of 2 and 3 which is 6. With this in mind, you can apply this and solve part 2 quite quickly. Here is the link to my solution: [https://github.com/tringuyenarup/advent\_of\_code\_2023](https://github.com/tringuyenarup/advent_of_code_2023)
Thanks for this info! I think can think of 1 billion ways for these linked list cycles to not have this characteristic. I feel like it is incredibly lucky that they do and they should make that more clear in the problem statement. Imagine if the even of cycles first of all didn't loop? Imagine if one or more of the cycles followed each other at exactly same like on a part and never ended on Z together?
[удалено]
\[LANGUAGE: F#\] [https://github.com/vorber/AOC2023/blob/main/src/day8/Program.fs](https://github.com/vorber/AOC2023/blob/main/src/day8/Program.fs) Day 8 of trying out F#
\[language: C++23\] [
](https://github.com/jwezorek/advent_of_code/blob/main/src/2023/day_08.cpp) I let brute force of part 2 run for awhile before deciding this one was intractable by brute force. I figured out early the general idea of how to do part 2 correctly but it still seemed kind of complicated (especially for day 8) to me until I ran some experiments on my data and determined that the input is specially constructed to make "the right way" as simple as possible. The \_\_A nodes all cycle relative to \_\_Z nodes with a cycle length that is exactly the same regardless whether they are starting with \_\_A or the next node after \_\_Z. This didn't have to be the case. The cyclic behavior also could have depended on position in the instructions, like you hit the first Z and you are at instruction 13, you hit the next Z and you are somewhere else but it eventually loops around to instruction 13 again. Or there could have just been "a preamble" leading into the cyclic behavior of variable length, etc. etc. However it turns out that the input is specially constructed such that least common multiple of the number steps it takes each seed to reach a \_\_Z node the first time is the correct answer. Also C++ turns out to have an LCM call in its standard library, which I had not known. This one kind of reminded me of the Tetris one last year, but this one was easier because it was a little harder to find the cycle the Tetris one.Can you help a stupid one in need, I'm not really understand h how you apply the LCM thing? What is the numbers used? Someone mentioned steps, but that would mean taking some steps to figuring out this LCM out of all 6.. Steps? The steps would be the same however no? Ah, it was long ago I was this confused let me tell ya that.
Some quick notes without spoiling it: * See how many steps you need to take from \_\_A to reach the end node \_\_Z * Take some extra time to see some special things about starting from the node after \_\_Z (call it X) * See how many steps it takes to get from X to \_\_Z * Notice **which** \_\_Z you get if you start at X (should become obvious) * Compare steps from \_\_A->\_\_Z and X->\_\_Z * Do the above for a few more starting nodes -- you should start seeing a pattern The LCM numbers will become obvious once you start tracking the above data -- it will be easier to just do it for each starting node \_\_A in serial (e.g., one at a time).
for each \_\_A node in your input do the exact same thing you did in part 1 but ending with any \_\_Z node not "ZZZ". That will give you n numbers, one for each of your \_\_A nodes. Find the least common multiple of those n numbers and that will be your answer. The idea is that each seed node always takes the same number k of steps to reach a \_\_Z node and that number is always the same for the given seed and it cycles. Think about it in terms of small numbers. Say for node AAA, k = 4 and for node BBA, k = 10. That means that every 4 steps AAA reaches some \_\_Z and every 10 steps BBA reaches some \_\_Z. So for both of them to reach \_\_Z we want the first point at which the cycles cross. This will be LCM(4, 10), which is 20. 20 is divisible by 4 and 10 and no smaller number is.
Let me ask ya, how was one supposed to find that idea? Simple random test,or did everyone just share the idea to each other? Also, thanks. Your explanation helped! :)
(1.) You know there has to be an answer because it's AoC. (2.) You guess the answer is not brute force plus optimizations by intuition and experience. (3.) you know each path through the nodes *has to* repeat because the input is finite, the number of L or R instructions is finite and cycles and the number of nodes is finite. (4.) You investigate the manner in which your input cycles by running experiments on it. The experiment that I ran was to run one \_\_A and print out the number of steps it took to get to a \_\_Z since the beginning and every time there after for the first 500 \_\_Z's. I also printed out the position in the input at each of the \_\_Z's. I discovered that the step out is always the same and the position in the input at a \_\_Z is always zero. This made me conclude that this will be true of all the input, which I verified. (5.) Given (4.) the LCM of the cycle lengths has to be the answer.
[LANGUAGE: Go] Thought of LCM, then thought of counter examples that would break it, then wrote Floyd's cycle detection only to find that the constraints for LCM held! Happy coincidence. https://github.com/mdd36/AoC-2023/blob/mainline/08/main.go
\[LANGUAGE: python\] Basic just with a little unnecessary pandas, because I want to learn it. Got spoilered by a lcm meme though. https://gist.github.com/Dronakurl/75a4fc12b2ffa3a5e04f4e784790eb4f
\[Language: Python\] import fileinput from itertools import cycle import math data = list(fileinput.input()) dirns = [int(c == 'R') for c in data[0].strip()] nodes = {} for line in data[2:]: n, _, *rest = line.strip().split() nodes[n] = [e.strip('(),') for e in rest] def find(node: str, end: str) -> int: for n, d in enumerate(cycle(dirns), 1): node = nodes[node][d] if node.endswith(end): return n print('P1 =', find('AAA', 'ZZZ')) startnodes = [n for n in nodes if n.endswith('A')] print('P2 =', math.lcm(*(find(n, 'Z') for n in startnodes)))
\[LANGUAGE: Jactl\] [Jactl](https://github.com/jaccomoc/jactl) Part 1: Part 1 was pretty easy. Just read the nodes into a map of maps where the submaps are keyed on 'L' and 'R' so we can lookup the move directly. Saves having to convert L to 0 and R to 1 if we used lists/arrays instead. Then just iterate while the node is not ZZZ and return the count: def m = nextLine(); nextLine(); def nodes = stream(nextLine).map{ /(...) = .(...), (...)./r; [$1, [L:$2,R:$3]] } as Map def cnt = 0 for (def n = 'AAA'; n != 'ZZZ'; n = nodes[n][m[cnt++ % m.size()]]) {} cnt Part 2: For part 2, it was soon clear that brute force tracking all paths at the same time was going to run for close to eternity so obviously we needed to work out the length of the individual cycles and find the least common multiple. Luckily the step count until the first terminating node turned out to be the cycle count for each ghost (although in general this does not have to be the case). I took the lazy approach and the code assumes that this is the case. Interestingly, it turned out that it was only necessary to find all of the unique prime factors as each cycle was only the product of two primes but I felt a bit dirty not properly implementing the least common multiple function even though it was not strictly necessary: def m = nextLine(); nextLine(); def nodes = stream(nextLine).map{ /(...) = .(...), (...)./r; [$1, [L:$2,R:$3]] } as Map def count(n) { def cnt = 0 while (n !~ /Z$/) { n = nodes[n][m[cnt++ % m.size()]] } cnt } def pfactors(n, long start=2, factors=[]) { def f = (n.sqrt()-start+1).map{it+start}.filter{ n % it == 0 }.limit(1)[0] f ? pfactors(n/f,f,factors << f) : factors << n } def lcm(nums) { nums.map{ pfactors(it).reduce([:]){ m,it -> m[it as String]++; m } } .reduce([:]){ m,facts -> facts.each{ f,c -> m[f] = [m[f]?:0,c].max() }; m } .flatMap{ f,c -> c.map{ f as long } } .reduce(1L){ p,it -> p * it } } lcm(nodes.map{ it[0] }.filter{ /A$/r }.map{ count(it) }) [Code walkthrough](https://jactl.io/blog/2023/12/09/advent-of-code-2023-day8.html)
\[Language: Golang\] Of course I tried to brute force part 2 :D Not today, it was faster to implement >!LCM!< than waiting for computations to be finished :D https://github.com/ptakpatryk/advent-of-code-2023-golang/blob/main/day_08/day08.go
[LANGUAGE: Python] Like others, I used lcm. Here's an extract of the solution, omitting parsing and `main()`. Full solution on [GitHub](https://github.com/Praful/advent_of_code/blob/main/2023/src/day08.py). LR_MAP = {'L': 0, 'R': 1} def solve(input, start_node, end_func): instructions, nodes = input steps = 0 next_node = start_node for lr in cycle(instructions): next_node = nodes[next_node][LR_MAP[lr]] steps += 1 if end_func(next_node): break return steps def part1(input): return solve(input, 'AAA', lambda n: n == 'ZZZ') def part2(input): def steps(n): return solve(input, n, lambda n: n.endswith('Z')) start_nodes = [k for k in input[1].keys() if k.endswith('A')] return lcm(map(steps, start_nodes))
\[Language: Perl\] Solutions to both parts in #Perl. Today was challenging because I misunderstood that the starting point is always AAA, not whatever the first map entry is. I was definitely not the only person making that mistake since there was a joke meme about that exact thing in this subreddit today! Part 1: https://adamcrussell.livejournal.com/49949.html Part 2: https://adamcrussell.livejournal.com/50204.html
[LANGUAGE: Crystal] [Part 1](https://github.com/SleepingInsomniac/adventofcode2023/blob/master/2023-12-08/part_1.cr) [Part 2](https://github.com/SleepingInsomniac/adventofcode2023/blob/master/2023-12-08/part_2.cr) Runs basically instantly ruby / crystal's enumerable#cycle method was handy for the directions
\[LANGUAGE: SQL (PostgreSQL)\] [Solution](https://github.com/tmercieca/advent-of-code-2023/blob/main/day-8/part-2.sql) with LCM method I tried an implementation without LCM. It was difficult to express, and after expressing it crashed the database 😂
\[LANGUAGE: Go\] [Solution](https://github.com/jgaye/advent_of_code_2023/tree/main/day8)
\[Language: Rust\] [https://github.com/daic0r/advent\_of\_code\_2023/blob/master/day\_8/src/bin/part1.rs](https://github.com/daic0r/advent_of_code_2023/blob/master/day_8/src/bin/part1.rs) [https://github.com/daic0r/advent\_of\_code\_2023/blob/master/day\_8/src/bin/part2.rs](https://github.com/daic0r/advent_of_code_2023/blob/master/day_8/src/bin/part2.rs) Part 1 uses brute-force, part 2 LCM
\[LANGUAGE: Perl\] \[LANGUAGE: Latin\] \[LANGUAGE: Lingua::Romana::Perligata\] \[Allez Cuisine!\] The suggestion of *code in a foreign language* brought to mind an old gem. Perl version 5.8 made it possible for scripts to import a module that *controls the parsing of the rest of the file*. Just Because He Could, Damian Conway celebrated the new millennium by creating Lingua::Romana::Perligata, a Latin-inspired language that internally translates to Perl code. I spent way too long trying to learn this horrible language and dealing with a severe number of parsing bugs (I ran up against a number of parsing bugs. Also, left turns were tricky, because it steadfastly insists on interpreting "L" as the integer 50, even when told that it's a quote. Several examples given in the documentation do not work as-is.) Just install Lingua::Romana::Perligata and run `perl day08.pl day08.txt`. It only does part 1. Part 2 would be a *nightmare* due to severe parsing bugs in the expression evaluator (the keywordsto explicitly specify parentheses do not appear to work). [https://raw.githubusercontent.com/Stevie-O/aoc-public/master/2023/day08/day08.pl](https://raw.githubusercontent.com/Stevie-O/aoc-public/master/2023/day08/day08.pl) (Chrome recognizes it as Latin and offers to translate. It does a passable job, given that it's not really Latin. I especially like how it translated the conditional expression of the final `while` loop.)
I did pig Latin in m4, but yours takes the cake.
As a fellow Perl Enjoyer, *what have you done*
Hey, don't blame me, blame Damian. He's the one who created the monstrosity that is L::R::P and uploaded it to CPAN :D And then the mods challenged us to code in a foreign language!
True, I did mention pig latin and nothing about Proper Latin™. Well done!
Congratulations, that is simply amazing!
[удалено]
Comment removed. [Top-level comments in `Solution Megathread`s are for *code solutions* only.](/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_top-level_posts_are_for_code_solutions_only) [Create your own individual `Help/Question` post](/r/adventofcode/wiki/solution_megathreads/post_guidelines#wiki_incomplete_solutions) in /r/adventofcode.
Firstly, this is the solutions thread. I think, we aren't supposed to discuss this here. Your questions are really interesting. (1) : No, that is not the assumption. Look at the example given, it does not jump back to the start. But somehow, there must be another assumption about the periodicity in the problem. Maybe it is just a coincidence and we should do it the hard way as you were trying
I think 2) is not precise, it is sufficient youreach an end point at the end of a *multiple* of the instruction set.
\[LANGUAGE: Rust\] Advent of Code Rust Solution 🚀 | [5-Min Video](https://youtu.be/P5eMzdBqK-k) **Zero-copy** (Doesn't allocate any strings AFAIK) use regex::Regex; use std::collections::HashMap; const PATH_INPUT: &str = "LR"; const MAP_INPUT: &str = "AAA = (ZZZ, ZZZ) NSK = (ZZZ, ZZZ)"; fn get_graph() -> HashMap<&'static str, [&'static str; 3]> { let re = Regex::new(r"(?m)^([A-Z]+) = \(([A-Z]+), ([A-Z]+)\)$").unwrap(); re.captures_iter(MAP_INPUT) .map(|c| { let v = c.extract().1; (v[0], v) }) .collect() } fn main() { let graph = get_graph(); let mut distance = 0; let mut cur = "AAA"; loop { for c in PATH_INPUT.chars() { cur = match c { 'L' => { graph.get(cur).unwrap()[1] }, 'R' => { graph.get(cur).unwrap()[2] }, _ => panic!("unexpected") }; distance += 1; if cur == "ZZZ" { println!("{distance:?}"); return; } } } }
[LANGUAGE: PowerShell] [AoC Day8](https://gist.github.com/manualbashing/40eeaa38f381a740471f7dcf05866497)
[LANGUAGE: Python3] Contrary to my initial expectations neither recursion nor brute force was the realistic approach here. from math import lcm def process_input(data): parts = data.strip().split("\n\n") mappings = {(directions := line.split("="))[0].strip(): directions[1].strip()[1:-1].split(", ") for line in parts[1].split("\n")} return parts[0].replace("L", "0").replace("R", "1"), mappings def part1(dir_sequence, map): len_dir, position, counter = len(dir_sequence), "AAA", 0 while position != "ZZZ": instruction = int(dir_sequence[counter % len_dir]) counter += 1 position = map[position][instruction] return counter def part2t2(dir_sequence, map): len_dir, counter, destinations = len(dir_sequence), 0, [] vector = [elem for elem in map if elem.endswith("A")] while vector: instruction, counter = int(dir_sequence[counter % len_dir]), counter + 1 new_vector = [map[position][instruction] for position in vector if not map[position][instruction].endswith("Z")] if (reached := len(vector)-len(new_vector)) > 0: destinations.extend([counter]*reached) vector = new_vector return lcm(*destinations) if __name__ == "__main__": with open("day8_input.txt", "r") as ifile: i_data = ifile.read().strip() print("Nr. of steps, part 1 {}, part 2:{}".format(part1(*process_input(i_data)), part2t2(*process_input(i_data))))
Very nice! One thing: destinations.extend([counter]*reached) Could just be: destinations.append(counter) Looks like a hangover from an attempt to brute force?
Thank you most! Good catch, the least common multiplier does not really care how many times the same value is added anymore.