53 lines
1.3 KiB
TypeScript
53 lines
1.3 KiB
TypeScript
|
type Node = { name: string, left: string, right: string };
|
||
|
|
|
||
|
|
const input = await Deno.readTextFile("input.txt");
|
||
|
|
|
||
|
|
const lines = input.split("\n").map(x => x.trim()).filter(x => x.length > 0);
|
||
|
|
const instructions = lines[0];
|
||
|
|
const nodes = lines.splice(1).map(x=> {
|
||
|
|
const m = /(\w+)\s*=\s*\(\s*(\w+)\s*,\s*(\w+)\s*\)/.exec(x);
|
||
|
|
if (!m){
|
||
|
|
throw new Error("Invalid line: " + x);
|
||
|
|
}
|
||
|
|
return {name: m[1], left: m[2], right: m[3]};
|
||
|
|
});
|
||
|
|
|
||
|
|
|
||
|
|
console.log(instructions, nodes);
|
||
|
|
|
||
|
|
const map = new Map<string, Node>();
|
||
|
|
for (const node of nodes){
|
||
|
|
map.set(node.name, node);
|
||
|
|
}
|
||
|
|
|
||
|
|
function stepInst(node: Node, instruction: string){
|
||
|
|
if (instruction === "R"){
|
||
|
|
return node.right
|
||
|
|
} else {
|
||
|
|
return node.left
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
let step = 0;
|
||
|
|
let current = nodes.filter(x => x.name.endsWith("A"));
|
||
|
|
if (!current){
|
||
|
|
throw new Error("Invalid input");
|
||
|
|
}
|
||
|
|
|
||
|
|
// brute force
|
||
|
|
while (!current.every(x => x.name.endsWith("Z"))){
|
||
|
|
const instruction_index = step % instructions.length;
|
||
|
|
const instruction = instructions[instruction_index];
|
||
|
|
|
||
|
|
//execute
|
||
|
|
current = current.map(x => {
|
||
|
|
const next = stepInst(x, instruction);
|
||
|
|
return map.get(next)!
|
||
|
|
})
|
||
|
|
step++;
|
||
|
|
|
||
|
|
if (step % 1000000 === 0){
|
||
|
|
console.log(step, current);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
console.log(step);
|