85 lines
2.2 KiB
TypeScript
85 lines
2.2 KiB
TypeScript
import {anyCharOf, newline, uniDecimal, uniLetter, whitespace} from "parjs";
|
|
import {between, exactly, manySepBy, manyTill, or, stringify, then} from "parjs/combinators";
|
|
import fs from "fs";
|
|
|
|
const patternParser = anyCharOf("LR").pipe(manyTill(newline().pipe(exactly(2))));
|
|
|
|
const nodeNameParser = uniLetter().pipe(or(uniDecimal()), exactly(3), stringify());
|
|
const childParser = nodeNameParser.pipe(manySepBy(", "), exactly(2), between("(", ")"));
|
|
const nodeParser = nodeNameParser.pipe(then(childParser.pipe(between(" = ", whitespace()))))
|
|
|
|
const parser = patternParser.pipe(then(nodeParser.pipe(manySepBy(whitespace()))));
|
|
|
|
type Maybe<T> = T | undefined;
|
|
|
|
type Instruction = "L" | "R";
|
|
type NodeName = string;
|
|
type NodeChildren = [Maybe<NodeName>, Maybe<NodeName>];
|
|
|
|
const gcd = (a: number, b: number): number => {
|
|
if (b === 0) return a;
|
|
return gcd(b, a % b);
|
|
}
|
|
|
|
export const lcm = (a: number, b: number): number => {
|
|
const product = a * b;
|
|
return product / gcd(a, b);
|
|
}
|
|
|
|
export class DesertMap {
|
|
private readonly pattern: Instruction[];
|
|
|
|
private map: Record<NodeName, NodeChildren> = {};
|
|
|
|
constructor(input: string) {
|
|
const [pattern, nodes] = parser.parse(input).value;
|
|
|
|
this.pattern = pattern as Instruction[];
|
|
|
|
for (const [name, [[leftNode, rightNode]]] of nodes) {
|
|
if (!this.map[name]) {
|
|
this.map[name] = [undefined, undefined];
|
|
}
|
|
const children = [leftNode, rightNode];
|
|
this.map[name] = children as NodeChildren;
|
|
}
|
|
}
|
|
|
|
public stepsToZ(from: string): number {
|
|
let step = 0;
|
|
let curr = from;
|
|
|
|
while (!curr.endsWith('Z')) {
|
|
const instruction = this.pattern[step % this.pattern.length];
|
|
|
|
const [left, right] = this.map[curr];
|
|
|
|
if (instruction === "L" && left) {
|
|
curr = left;
|
|
} else if (instruction === "R" && right) {
|
|
curr = right;
|
|
}
|
|
|
|
if (!curr) return 0;
|
|
|
|
step++;
|
|
}
|
|
return step;
|
|
}
|
|
|
|
public ghostStepsToZ(): number {
|
|
let keys = Object.keys(this.map).filter(key => key.endsWith('A'));
|
|
|
|
return keys.map(key => this.stepsToZ(key)).reduce(lcm);
|
|
}
|
|
}
|
|
|
|
|
|
export const runDayEight = () => {
|
|
const input = fs.readFileSync('./inputs/day_eight_input.txt', 'utf-8').trimEnd();
|
|
|
|
const map = new DesertMap(input);
|
|
console.log(map.stepsToZ('AAA'));
|
|
|
|
console.log(map.ghostStepsToZ());
|
|
} |