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) };
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.