Advent of Code 2020 Day 18 - Solution + Tutorial (TypeScript)

published 2020-12-20T13:40:23.000Z

All TypeScript Solutions for Advent of Code 2020

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:

Day 18: Operation Order

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()!;
}