search

andreiz / advent-of-code-2023-swift

Copilot and ChatGPT assisted Advent of Code 2023 to learn Swift.
0 stars 0 forks source link

Day 8: Haunted Wasteland #8

Open andreiz opened 10 months ago

andreiz commented 10 months ago

https://adventofcode.com/2023/day/8

Input: https://adventofcode.com/2023/day/8/input

andreiz commented 10 months ago

Seems like a straightforward binary tree traversal, repeating the instructions on a cycle and counting the steps.

First thing we need is a function to parse the input into a data structure. I chose to keep it simple use a dictionary maping from one node to the left and right nodes it's connected to, representing the graph. A couple of typealiases for readability.

https://github.com/andreiz/advent-of-code-2023-swift/blob/dc7abce16a1bf6af677cfbfd2159386ddc53698e/day-08/wasteland.swift#L3-L21

andreiz commented 10 months ago

Traversal is pretty trivial. Initialize current node to "AAA", then loop the instructions continuously until we reach "ZZZ".

https://github.com/andreiz/advent-of-code-2023-swift/blob/7797cdd5ed8279cdd4d8692ac7c5ac05caaeb872/day-08/wasteland.swift#L23-L43

andreiz commented 10 months ago

Parsing and calling is trivial too.

https://github.com/andreiz/advent-of-code-2023-swift/blob/7797cdd5ed8279cdd4d8692ac7c5ac05caaeb872/day-08/wasteland.swift#L45-L49

andreiz commented 10 months ago

Part 2. Now we have a set of start nodes (all the ones ending in "A") and end nodes (ending in "Z"). We go from all the start nodes simultaneously until all paths reach end nodes. If only some of paths reach end, they act like any other node and we continue as normal.

The trick part here is that in order for all the paths to finish at the same time (lengh) some of them will have to be repeated several times until other paths catch up (paths have different periodicities). But we don't actually need to repeat them. We calculate path for each start node, then compute the least common multiple of all the path lengths, giving us the one encompassing path length.

andreiz commented 10 months ago

traverseGraph now has a parameter for starting node and an updated stopping condition and also returns the path length.

https://github.com/andreiz/advent-of-code-2023-swift/blob/d2f2c840e9fb4a90ac3bc21cbe42a016a8f35ad5/day-08/wasteland-ghost.swift#L23-L43

andreiz commented 10 months ago

And then we just find all starting nodes, get path length for each one, and calculate least common multiple of them.

https://github.com/andreiz/advent-of-code-2023-swift/blob/d2f2c840e9fb4a90ac3bc21cbe42a016a8f35ad5/day-08/wasteland-ghost.swift#L45-L60