Created
December 10, 2023 01:21
-
-
Save jjclxrk/b0c208753c6e19ca7edabba54c3c0940 to your computer and use it in GitHub Desktop.
[aoc2023] - 08.mjs
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import fs from "fs"; | |
| import readline from "readline"; | |
| const fileStream = fs.createReadStream("input.txt"); | |
| const rl = readline.createInterface({ | |
| input: fileStream, | |
| crlfDelay: Infinity, | |
| }); | |
| let instructions = null; | |
| const graph = {}; | |
| /** | |
| * Parse a node and its left and right edges from the puzzle input. | |
| */ | |
| const parseEdges = (line) => { | |
| const match = /([A-Z]{3}) = \(([A-Z]{3}), ([A-Z]{3})\)/.exec(line); | |
| if (!match) { | |
| console.error("Unparseable line:", line); | |
| process.exit(1); | |
| } | |
| return { node: match[1], left: match[2], right: match[3] }; | |
| }; | |
| /** | |
| * Calculate the number of steps from the starting node to a node which | |
| * satisfiies the `isDestination` predicate by following the set of left and | |
| * right instructions. | |
| */ | |
| const solve1 = ( | |
| startNode = "AAA", | |
| isDestination = (dst) => dst === "ZZZ", | |
| ) => { | |
| let curr = startNode; | |
| let steps = 0; | |
| while (!isDestination(curr)) { | |
| if (instructions.charAt(steps % instructions.length) === "L") { | |
| curr = graph[curr].left; | |
| } else { | |
| curr = graph[curr].right; | |
| } | |
| steps++; | |
| } | |
| return steps; | |
| }; | |
| /** Greatest common divisor via Euclid's algorithm. */ | |
| const gcd = (a, b) => b ? gcd(b, a % b) : a; | |
| /** | |
| * Least common multiple for a list of numbers calculated via the greatest | |
| * common divisor. | |
| */ | |
| const lcm = (nums) => nums.reduce( | |
| (accum, curr) => (Math.abs(accum * curr) / gcd(accum, curr)), | |
| ); | |
| /** | |
| * Calculate the number of steps it takes to simultaneously proceed from all | |
| * starting nodes (nodes ending with 'A') to a state of all destination nodes | |
| * (nodes ending with 'Z'). | |
| */ | |
| const solve2 = () => { | |
| // Find the number of steps before reaching a destination node (ends with | |
| // 'Z') for each starting node (ends with 'A'). | |
| const steps = Object.keys(graph) | |
| .filter((node) => /A$/.test(node)) | |
| .map((node) => solve1(node, (dst) => /Z$/.test(dst))); | |
| // Find the number of steps before the above cycles all align on a | |
| // destination by calculating the least common multiple of all of the cycle | |
| // lengths. | |
| return lcm(steps); | |
| }; | |
| rl.on("line", (line) => { | |
| // If we haven't initialised instructions, we must be reading the first | |
| // line of the input. | |
| if (!instructions) { | |
| instructions = line; | |
| return; | |
| } | |
| // The second line is blank, skip it. | |
| if (!line) { | |
| return; | |
| } | |
| // Otherwise this is a graph edge entry, parse it and add to the graph. | |
| const { node, ...edges } = parseEdges(line); | |
| graph[node] = edges; | |
| }); | |
| rl.on("close", () => { | |
| console.log("part 1 result:", solve1()); | |
| console.log("part 2 result:", solve2()); | |
| }); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment