31:T797,md`# Day 18 - Operation Order As you look out the window and notice a heavily-forested continent slowly appear over the horizon, you are interrupted by the child sitting next to you. They're curious if you could help them with their math homework. Unfortunately, it seems like this "math" follows different rules than you remember. The homework (your puzzle input) consists of a series of expressions that consist of addition (+), multiplication (*), and parentheses ((...)). Just like normal math, parentheses indicate that the expression inside must be evaluated before it can be used by the surrounding expression. Addition still finds the sum of the numbers on both sides of the operator, and multiplication still finds the product. However, the rules of operator precedence have changed. Rather than evaluating multiplication before addition, the operators have the same precedence, and are evaluated left-to-right regardless of the order in which they appear. For example, the steps to evaluate the expression \`1 + 2 * 3 + 4 * 5 + 6\` are as follows: \`\`\`text 1 + 2 * 3 + 4 * 5 + 6 3 * 3 + 4 * 5 + 6 9 + 4 * 5 + 6 13 * 5 + 6 65 + 6 71 \`\`\` Parentheses can override this order; for example, here is what happens if parentheses are added to form \`1 + (2 * 3) + (4 * (5 + 6))\`: \`\`\`text 1 + (2 * 3) + (4 * (5 + 6)) 1 + 6 + (4 * (5 + 6)) 7 + (4 * (5 + 6)) 7 + (4 * 11 ) 7 + 44 51 \`\`\` Here are a few more examples: \`\`\`text 2 * 3 + (4 * 5) becomes 26. 5 + (8 * 3 + 9 + 3 * 4 * 3) becomes 437. 5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4)) becomes 12240. ((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2 becomes 13632. \`\`\` Before you can help with the homework, you need to understand it yourself. Evaluate the expression on each line of the homework; what is the sum of the resulting values?`32:Tadb,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) }; }33:[{"id":"e4dc4bc5c3efaa17f22a7f04d28964234fe49003710888a16469e864582d9692bc36c0a4c0404889f4fba2c2fd55c1e05728f5e85449703b21c2a54221ec0909","href":"https://static.observableusercontent.com/files/e4dc4bc5c3efaa17f22a7f04d28964234fe49003710888a16469e864582d9692bc36c0a4c0404889f4fba2c2fd55c1e05728f5e85449703b21c2a54221ec0909","name":"Avent of Code 2020 - Day 18.txt","type":"text/plain","lastModified":1608278812859.897,"size":19762}] 2f:{"title":"Day 18 - Operation Order","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"input = (await FileAttachment(\"Avent of Code 2020 - Day 18.txt\").text()).trim()","pinned":true,"hidden":false,"mode":"ojs"},{"id":17,"value":"parseInput = input => {\n let tree = [];\n let stack = [];\n for (let i = 0; i < input.length; i++) {\n let token = input[i];\n if (token === \" \") {\n continue;\n } else if (token === \"*\" || token === \"+\") {\n tree = [token, tree];\n } else if (token === \"(\") {\n stack.push(tree);\n tree = [];\n } else if (token === \")\") {\n const tree0 = stack.pop();\n if (tree0.length) {\n tree0.push(tree);\n tree = tree0;\n }\n } else {\n // number\n let j = i + 1;\n while (\n j < input.length &&\n input.charCodeAt(j) > 47 &&\n input.charCodeAt(j) < 58\n ) {\n j++;\n }\n token = input.slice(i, j);\n tree.push(+token);\n i = j - 1;\n }\n }\n return tree;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":13,"value":"testInput = [\n \"1 + 2 * 3 + 4 * 5 + 6 \", // 71\n \"1 + (2 * 3) + (4 * (5 + 6))\", // 51\n \"2 * 3 + (4 * 5)\", // 26\n \"5 + (8 * 3 + 9 + 3 * 4 * 3)\", // 437\n \"5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4))\", // 12240\n \"((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2\" // 13632\n]","pinned":true,"hidden":false,"mode":"ojs"},{"id":75,"value":"parseInput(\"(1 + 2) * (3 + 4)\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":88,"value":"testInput.map(parseInput)","pinned":true,"hidden":false,"mode":"ojs"},{"id":72,"value":"// The worst part is that it probably would have taken me less time to relearn how to\n// use any type of parsing tool out there than to hand-roll this from scratch.\n// Also less buggy\nfunction q1(input) {\n const lines = input.trim().split('\\n');\n\n const calcExpr = line => {\n let ast = parseInput(line);\n const walkTree = ast => {\n const [op, ast1, ast2] = ast;\n if (Number.isFinite(op)) {\n // op is a number\n return op;\n }\n const v1 = Number.isFinite(ast1) ? ast1 : walkTree(ast1);\n const v2 = Number.isFinite(ast2) ? ast2 : walkTree(ast2);\n if (op === \"+\") return v1 + v2;\n return v1 * v2;\n };\n return walkTree(ast);\n };\n\n const results = lines.map(calcExpr);\n let sum = 0;\n for (const v of results) sum += v;\n return sum;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":90,"value":"testInput.map(q1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":103,"value":"answer1 = q1(input)","pinned":true,"hidden":false,"mode":"ojs"},{"id":116,"value":"md`---\n\n## Part Two\nYou manage to answer the child's questions and they finish part 1 of their homework, but get stuck when they reach the next section: advanced math.\n\nNow, addition and multiplication have different precedence levels, but they're not the ones you're familiar with. Instead, addition is evaluated before multiplication.\n\nFor example, the steps to evaluate the expression \\`1 + 2 * 3 + 4 * 5 + 6\\` are now as follows:\n\n\\`\\`\\`text\n1 + 2 * 3 + 4 * 5 + 6\n 3 * 3 + 4 * 5 + 6\n 3 * 7 * 5 + 6\n 3 * 7 * 11\n 21 * 11\n 231\n\\`\\`\\`\n\nHere are the other examples from above:\n\n\\`\\`\\`text\n 1 + (2 * 3) + (4 * (5 + 6)) still becomes 51.\n 2 * 3 + (4 * 5) becomes 46.\n 5 + (8 * 3 + 9 + 3 * 4 * 3) becomes 1445.\n 5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4)) becomes 669060.\n ((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2 becomes 23340.\n\\`\\`\\`\n\nWhat do you get if you add up the results of evaluating the homework problems using these new rules?`","pinned":false,"hidden":false,"mode":"ojs"},{"id":252,"value":"testInput.map(q2)","pinned":true,"hidden":false,"mode":"ojs"},{"id":257,"value":"// (Heh, whoops, that's a bit excessive)\n// q2(input)","pinned":true,"hidden":false,"mode":"ojs"},{"id":264,"value":"answer2 = {\n const lines = input.trim().split('\\n');\n let sum = 0n;\n for (const line of lines) sum += q2(line).res;\n return sum;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":121,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":2,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}