Tinkering with code and algorithms for fun
input = (await FileAttachment("Avent of Code 2020 - Day 18.txt").text()).trim()
parseInput = input => {
let tree = [];
let stack = [];
for (let i = 0; i < input.length; i++) {
let token = input[i];
if (token === " ") {
continue;
} else if (token === "*" || token === "+") {
tree = [token, tree];
} else if (token === "(") {
stack.push(tree);
tree = [];
} else if (token === ")") {
const tree0 = stack.pop();
if (tree0.length) {
tree0.push(tree);
tree = tree0;
}
} else {
// number
let j = i + 1;
while (
j < input.length &&
input.charCodeAt(j) > 47 &&
input.charCodeAt(j) < 58
) {
j++;
}
token = input.slice(i, j);
tree.push(+token);
i = j - 1;
}
}
return tree;
}
testInput = [
"1 + 2 * 3 + 4 * 5 + 6 ", // 71
"1 + (2 * 3) + (4 * (5 + 6))", // 51
"2 * 3 + (4 * 5)", // 26
"5 + (8 * 3 + 9 + 3 * 4 * 3)", // 437
"5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))", // 12240
"((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2" // 13632
]
parseInput("(1 + 2) * (3 + 4)")
testInput.map(parseInput)
// The worst part is that it probably would have taken me less time to relearn how to
// use any type of parsing tool out there than to hand-roll this from scratch.
// Also less buggy
function q1(input) {
const lines = input.trim().split('\n');
const calcExpr = line => {
let ast = parseInput(line);
const walkTree = ast => {
const [op, ast1, ast2] = ast;
if (Number.isFinite(op)) {
// op is a number
return op;
}
const v1 = Number.isFinite(ast1) ? ast1 : walkTree(ast1);
const v2 = Number.isFinite(ast2) ? ast2 : walkTree(ast2);
if (op === "+") return v1 + v2;
return v1 * v2;
};
return walkTree(ast);
};
const results = lines.map(calcExpr);
let sum = 0;
for (const v of results) sum += v;
return sum;
}
testInput.map(q1)
answer1 = q1(input)
testInput.map(q2)
// (Heh, whoops, that's a bit excessive)
// q2(input)
answer2 = {
const lines = input.trim().split('\n');
let sum = 0n;
for (const line of lines) sum += q2(line).res;
return sum;
}
q2 = input => {
let tree = [];
let stack = [];
input = input.split('');
// parse nrs and strip spaces
const input2 = [];
for (let i = 0; i < input.length; i++) {
let nr = input[i].charCodeAt() - 48;
if (nr >= 0 && nr < 10) {
while (
++i < input.length &&
input[i].charCodeAt() > 47 &&
input[i].charCodeAt() < 58
) {
nr = nr * 10 + input[i].charCodeAt() - 48;
}
input2.push(BigInt(nr));
i--;
} else if (input[i] === " ") {
continue;
} else {
input2.push(input[i]);
}
}
input = input2;
// parenthesis
for (let i = 0; i < input.length; i++) {
let token = input[i];
if (token === "(") {
stack.push(tree);
tree = [];
} else if (token === ")") {
const tree0 = stack.pop();
tree0.push(tree);
tree = tree0;
} else {
tree.push(token);
}
}
// *
const walkTreeMul = ast => {
let mul = [];
for (let i = 0; i < ast.length; i++) {
if (Array.isArray(ast[i])) ast[i] = walkTreeMul(ast[i]);
else if (ast[i] === "*") mul.push(i);
}
if (!mul.length) return ast;
let out = ["*"];
let j = 0;
for (let i = 0; i < mul.length; i++) {
const k = mul[i];
out.push(ast.slice(j, k));
j = k + 1;
}
out.push(ast.slice(j));
return out;
};
tree = walkTreeMul(tree);
// +
const walkTreePlus = ast => {
let sum = [];
for (let i = 0; i < ast.length; i++) {
if (Array.isArray(ast[i])) ast[i] = walkTreePlus(ast[i]);
else if (ast[i] === "+") sum.push(i);
}
if (!sum.length) return ast;
let out = ["+"];
let j = 0;
for (let i = 0; i < sum.length; i++) {
const k = sum[i];
out.push(ast.slice(j, k));
j = k + 1;
}
out.push(ast.slice(j));
return out;
};
tree = walkTreePlus(tree);
// I could try to remember why I end up with
// nested arrays and handroll my parser better
// or I can inline
const inline = ast => {
if (Array.isArray(ast[0])) return inline(ast[0]);
for (let i = 1; i < ast.length; i++) {
ast[i] = inline(ast[i]);
}
return ast;
};
tree = inline(tree);
// return tree;
const calc = ast => {
let prefix = ast[0];
if (typeof prefix === "bigint") return prefix;
else {
let acc = calc(ast[1]);
if (prefix === "*") {
for (let i = 2; i < ast.length; i++) {
acc *= calc(ast[i]);
}
} else if (prefix === "+") {
for (let i = 2; i < ast.length; i++) {
console.log({ i, acc });
acc += calc(ast[i]);
}
} else {
return "there be either bugs or bad input here";
}
return acc;
}
};
return { tree, res: calc(tree) };
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
