generated from eric/adventofcode2023
90 lines
2.1 KiB
JavaScript
90 lines
2.1 KiB
JavaScript
import { readFileSync } from 'node:fs';
|
|
|
|
let sampleMode = true;
|
|
|
|
const sampleArray1 = readFileSync('sample.txt').toString().split("\n");
|
|
const sampleArray2 = readFileSync('sample2.txt').toString().split("\n");
|
|
const inputArray = readFileSync('input.txt').toString().split("\n");
|
|
|
|
const usedArray1 = sampleMode ? sampleArray1 : inputArray;
|
|
const usedArray2 = sampleMode ? sampleArray2 : inputArray;
|
|
|
|
// Part One
|
|
|
|
console.time("part1");
|
|
|
|
// Parse the graph
|
|
const graph = new Map();
|
|
|
|
for (const element of usedArray1) {
|
|
const [node, targets] = element.split(': ');
|
|
graph.set(node, targets.split(' '));
|
|
}
|
|
|
|
// Count paths from 'you' to 'out' using memoization
|
|
const memo = new Map();
|
|
|
|
function countPaths(node) {
|
|
if (node === 'out') return 1n;
|
|
if (memo.has(node)) return memo.get(node);
|
|
if (!graph.has(node)) return 0n;
|
|
|
|
let total = 0n;
|
|
for (const next of graph.get(node)) {
|
|
total += countPaths(next);
|
|
}
|
|
|
|
memo.set(node, total);
|
|
return total;
|
|
}
|
|
|
|
const part1 = countPaths('you');
|
|
|
|
console.timeEnd("part1");
|
|
console.log(part1.toString());
|
|
|
|
|
|
// Part Two
|
|
|
|
console.time("part2");
|
|
|
|
// Re-parse graph for part 2 (may use different sample file)
|
|
const graph2 = new Map();
|
|
for (const element of usedArray2) {
|
|
const [node, targets] = element.split(': ');
|
|
graph2.set(node, targets.split(' '));
|
|
}
|
|
|
|
// Count paths between any two nodes using memoization
|
|
const memo2 = new Map();
|
|
|
|
function countPathsBetween(from, to) {
|
|
const key = `${from}->${to}`;
|
|
if (memo2.has(key)) return memo2.get(key);
|
|
|
|
if (from === to) return 1n;
|
|
if (!graph2.has(from)) return 0n;
|
|
|
|
let total = 0n;
|
|
for (const next of graph2.get(from)) {
|
|
total += countPathsBetween(next, to);
|
|
}
|
|
|
|
memo2.set(key, total);
|
|
return total;
|
|
}
|
|
|
|
// Paths from svr to out visiting both dac and fft:
|
|
// Either: svr -> dac -> fft -> out
|
|
// Or: svr -> fft -> dac -> out
|
|
|
|
const path1 = countPathsBetween('svr', 'dac') * countPathsBetween('dac', 'fft') * countPathsBetween('fft', 'out');
|
|
const path2 = countPathsBetween('svr', 'fft') * countPathsBetween('fft', 'dac') * countPathsBetween('dac', 'out');
|
|
|
|
const part2 = path1 + path2;
|
|
|
|
console.timeEnd("part2");
|
|
console.log(part2.toString());
|
|
|
|
// functions
|