kais.blog

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

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

Conclusion

TODO: I'm working on it.

If you like my content and you want to see more, please follow me on Twitter!
Questions, feedback or just wanna chat? Come and join my Discord!
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.