Advent of Code 2020 Day 18 - Solution + Tutorial (TypeScript)
- [ 1 ]
- [ 2 ]
- [ 3 ]
- [ 4 ]
- [ 5 ]
- [ 6 ]
- [ 7 ]
- [ 8 ]
- [ 9 ]
- [ 10 ]
- [ 11 ]
- [ 12 ]
- [ 13 ]
- [ 14 ]
- [ 15 ]
- [ 16 ]
- [ 17 ]
- [ 18 ]
I'll try to update asap. Please bear in a mind that I'll probably lag one or multiple days behind.
Prerequisites
I assume you've put your puzzle input into an array called lines
where each array item is a line of the input text file.
It's up to you to either parse the text file or create an array by hand.
const lines = [
"3 * (9 + 5 * (8 * 9 * 6)) * 5 * 6",
"5 + (5 + (6 + 8 * 6 * 9 + 7 + 4) + 2 * 3 * (7 * 5 * 5 * 4 + 2)) * 3 + 5 * 6 * 8",
"4 + 3 + 4 + (2 * 9 + 3 + 9 + 7) + 9",
…
];
Solution
Preface
Starting with Day 10, I'll just publish my solution for both parts without explaining every single step. Unfortunately, I can't continue providing full step-by-step tutorials for each day. The concepts used get more difficult day by day. So, I've concluded that it's better if I wrote separate blog posts about these concepts later.
Also, it's holiday season. This makes it much more difficult creating well-thought-out tutorials. However, I'll try to annotate my code examples a little. This way, you might understand what I've done.
I will now move on to sharing useful tips for web developers regularly. These should help you become a better developer. Also, the shared tips should help with solving problems like those we encounter in Advent of Code. Here's my first post: 14 Awesome JavaScript Array Tips You Should Know About
Puzzle
Just to make sure, you know what I'm talking about, take a look at today's puzzle:
Part 1
TODO: The code is ready, I'm working on the description.
const postfixNotations = lines.map(parse);
const solutions = postfixNotations.map(solve);
return solutions.reduce((previous, current) => previous + current);
function parse(expression: string) {
const tokens = [...expression.replaceAll(" ", "")];
const operatorStack: string[] = [];
const outputQueue: string[] = [];
tokens.forEach((token) => {
if (["+", "*"].includes(token)) {
while (
operatorStack.length > 0 &&
["+", "*"].includes(operatorStack.slice().pop()!)
) {
const operator = operatorStack.pop()!;
outputQueue.push(operator);
}
operatorStack.push(token);
return;
}
if (token === "(") {
operatorStack.push(token);
return;
}
if (token === ")") {
while (operatorStack.length > 0 && operatorStack.slice().pop() !== "(") {
const operator = operatorStack.pop()!;
outputQueue.push(operator);
}
operatorStack.pop();
return;
}
outputQueue.push(token);
});
while (operatorStack.length > 0) {
const operator = operatorStack.pop()!;
outputQueue.push(operator);
}
return outputQueue;
}
function solve(postfixNotation: string[]) {
const stack: number[] = [];
postfixNotation.forEach((value) => {
const number = Number(value);
if (!Number.isNaN(number)) {
stack.push(number);
return;
}
const a = stack.pop();
const b = stack.pop();
switch (value) {
case "+":
stack.push(Number(a) + Number(b));
break;
case "*":
stack.push(Number(a) * Number(b));
break;
}
});
return stack.pop()!;
}
Part 2
TODO: The code is ready, I'm working on the description.
const postfixNotations = lines.map(parse);
const solutions = postfixNotations.map(solve);
return solutions.reduce((previous, current) => previous + current);
const precedenceLevels: Record<string, number> = {
"+": 3,
"*": 2,
};
function parse(expression: string) {
const tokens = [...expression.replaceAll(" ", "")];
const operatorStack: string[] = [];
const outputQueue: string[] = [];
tokens.forEach((token) => {
if (["+", "*"].includes(token)) {
while (
operatorStack.length > 0 &&
["+", "*"].includes(operatorStack.slice().pop()!)
) {
if (
precedenceLevels[token] >
precedenceLevels[operatorStack.slice().pop()!]
) {
break;
}
const operator = operatorStack.pop()!;
outputQueue.push(operator);
}
operatorStack.push(token);
return;
}
if (token === "(") {
operatorStack.push(token);
return;
}
if (token === ")") {
while (operatorStack.length > 0 && operatorStack.slice().pop() !== "(") {
const operator = operatorStack.pop()!;
outputQueue.push(operator);
}
operatorStack.pop();
return;
}
outputQueue.push(token);
});
while (operatorStack.length > 0) {
const operator = operatorStack.pop()!;
outputQueue.push(operator);
}
return outputQueue;
}
function solve(postfixNotation: string[]) {
const stack: number[] = [];
postfixNotation.forEach((value) => {
const number = Number(value);
if (!Number.isNaN(number)) {
stack.push(number);
return;
}
const a = stack.pop();
const b = stack.pop();
switch (value) {
case "+":
stack.push(Number(a) + Number(b));
break;
case "*":
stack.push(Number(a) * Number(b));
break;
}
});
return stack.pop()!;
}
Conclusion
TODO: I'm working on it.