DEV Community

loading...

[Advent of Code 2020] Day 8 Step-by-Step Tutorial (TypeScript)

kais_blog profile image Kai Originally published at kais.blog ・9 min read

This post was originally published at kais.blog. It is part of a series of step-by-step tutorials about the Advent of Code 2020 event.

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!

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 = [
  "acc +17",
  "nop +150",
  "jmp +163",
  "acc +0",
  "acc +10",
  
];
Enter fullscreen mode Exit fullscreen mode

Solution

Puzzle

Just to make sure, you know what I'm talking about, take a look at today's puzzle:

Day 8: Handheld Halting

Part 1

This time, we are given the boot code of a kid's handheld game console. The boot code is represented by instructions. Each line of our puzzle input is one instruction. Every instruction consists of an operation and an argument.

The operation is either "acc", "jmp" or "nop. What they do, is explained in the puzzle description. Also, each operation is accompanied by an argument. The argument is a positive or negative integer.

With this knowledge, let's add a type definition for an instruction:

interface Instruction {
  operation: "acc" | "jmp" | "nop";
  argument: number;
}
Enter fullscreen mode Exit fullscreen mode

Okay, we have defined an interface for an instruction object. Now let's start with transforming our input into instruction objects.

First, let's initialize an array that will hold our instructions:

const instructions: Instruction[] = [];
Enter fullscreen mode Exit fullscreen mode

Now, let's populate the array. Basically, it comes down to this:

lines.forEach((line) => {
  // TODO: Parse the line.

  const instruction: Instruction = {
    operation: ,
    argument: ,
  };

  instructions.push(instruction);
});
Enter fullscreen mode Exit fullscreen mode

For each line we want to parse it, create an instruction object and then, add this object to our instructions array. Well, how do we parse the line. Let's look at the input again:

"acc +17",
"nop +150",
"jmp +163",
"acc +0",
"acc +10",

Enter fullscreen mode Exit fullscreen mode

Good. Remember, we have the operation and the argument. They are separated by a single space. We can use that information to extract the needed data from the line:

const [operation, argument] = line.split(" ");
Enter fullscreen mode Exit fullscreen mode

What is happening here? We are using the String#split method to split the string into an array. We use " " (a single space). Thus, we have an array containing two items. Then, we use array destructuring to extract the operation (first item), and the argument (second item) from the array.

Now we have extracted the data, let's create the instruction object:

const instruction: Instruction = {
  operation: operation as "acc" | "jmp" | "nop",
  argument: parseInt(argument),
};
Enter fullscreen mode Exit fullscreen mode

We told TypeScript that operation is one of "acc", "jmp", "nop". When using String#split TypeScript cannot know that operation is a very specific set of strings. We have to tell the compiler that operation is exactly one of "acc", "jmp", "nop". Also, the argument is of type string right now. Let's use parseInt to convert it to number.

Nice, our loop to populate the instructions array is now complete:

const instructions: Instruction[] = [];

lines.forEach((line) => {
  const [operation, argument] = line.split(" ");

  const instruction: Instruction = {
    operation: operation as "acc" | "jmp" | "nop",
    argument: parseInt(argument),
  };

  instructions.push(instruction);
});
Enter fullscreen mode Exit fullscreen mode

What's still left? We have to run the instructions until we reach an instruction we've already visited. While running the instructions, every acc operation changes an accumulator value. This accumulator value is important. As soon as we encounter an instruction that we have already visited, we should stop running the instructions. Then, the current accumulator value is our puzzle solution.

Let's try to implement all of this. What do we need? We need a variable to hold the current accumulator value.

let accumulator = 0;
Enter fullscreen mode Exit fullscreen mode

Easy. Now, we want to go through all instructions in order. However, a jmp operation may change our current position. So, we need to somehow remember what our current instruction is. Therefore, we can use two more variables:

let position = 0;
let instruction = instructions[position];
Enter fullscreen mode Exit fullscreen mode

Good! position holds our current position. instruction is the current instruction. We are using let instead of const because this will change after each instruction.

Now, one more thing is missing. We have to somehow determine if we've already visited an instruction. We could add a field visited: boolean to the instruction. Then, we could set this field to true after visiting an instruction. However, I'd say we create a set, that's holding each visited instruction:

const visitedInstructions = new Set<Instruction>();
Enter fullscreen mode Exit fullscreen mode

Ok, we are ready to go through the instructions. Remember, we should stop, as soon as we encounter any instruction
that has been visited already. It basically comes down to this:

while (!visitedInstructions.has(instruction)) {
  // TODO: Handle instruction.

  visitedInstructions.add(instruction);
  instruction = instructions[position];
}
Enter fullscreen mode Exit fullscreen mode

This while-loop will break, as soon as the current instruction has already been visited. To check this, we'll add the instruction to our visitedInstructions set, and use the Set#has method in the while-loop's condition. Also, after each iteration we have to update the current instruction.

Now, we still have to handle each instruction. There are three different operations. The current instruction's operation is accessible with instruction.operation. Also, its argument is accessible with instruction.argument. So, we just have to check the instruction's operation and update our accumulator and position accordingly.

We can make use of a switch statement. Let's go:

switch (instruction.operation) {
  case "acc":
    accumulator += instruction.argument;
    position++;
    break;
  case "jmp":
    position += instruction.argument;
    break;
  case "nop":
    position++;
    break;
}
Enter fullscreen mode Exit fullscreen mode

First, this checks the current operation. Then, according to the found operation, we handle different cases. acc updates the accumulator and advances to the next instruction. jmp changes our position by the given instruction.argument. And nop does nothing. So, we simply advance to the next instruction.

With this done, our loop is complete. Also, we've solved the puzzle. We just have to return the accumulator value. So, this is the full solution:

interface Instruction {
  operation: "acc" | "jmp" | "nop";
  argument: number;
}
Enter fullscreen mode Exit fullscreen mode
const instructions: Instruction[] = [];

lines.forEach((line) => {
  const [operation, argument] = line.split(" ");

  const instruction: Instruction = {
    operation: operation as "acc" | "jmp" | "nop",
    argument: parseInt(argument),
  };

  instructions.push(instruction);
});

let accumulator = 0;

let position = 0;
let instruction = instructions[position];

const visitedInstructions = new Set<Instruction>();

while (!visitedInstructions.has(instruction)) {
  switch (instruction.operation) {
    case "acc":
      accumulator += instruction.argument;
      position++;
      break;
    case "jmp":
      position += instruction.argument;
      break;
    case "nop":
      position++;
      break;
  }

  visitedInstructions.add(instruction);
  instruction = instructions[position];
}

return accumulator;
Enter fullscreen mode Exit fullscreen mode

Part 2

So, in part 1 we've encountered a situation, where an instruction is visited twice. This should not happen. According to the puzzle description we have to change ONE jmp or nop instruction. Then, the instructions should run without visiting any instruction twice.

Okay, like in part 1, let's parse our puzzle input:

interface Instruction {
  operation: "acc" | "jmp" | "nop";
  argument: number;
}
Enter fullscreen mode Exit fullscreen mode
const instructions: Instruction[] = [];

lines.forEach((line) => {
  const [operation, argument] = line.split(" ");

  const instruction: Instruction = {
    operation: operation as "acc" | "jmp" | "nop",
    argument: parseInt(argument),
  };

  instructions.push(instruction);
});
Enter fullscreen mode Exit fullscreen mode

Nothing has changed here. It's exactly the same code from part 1. If necessary, you can read the explanation there.

After that, in part 1, we've executed the instructions one-by-one until we've visited an instruction twice. However, this is faulty behaviour. Normally, our program should exit, as soon as there's no next instruction left.

This means, after running through our instructions like in part 1, the faulty jmp or nop instruction has to be in the set of visitedInstructions. Remember, we've created this set before running our while-loop. Let's extract our possibly faulty instructions from it:

const possiblyFaultyInstructions = [
...visitedInstructions,
].filter((instruction) => ["jmp", "nop"].includes(instruction.operation));
Enter fullscreen mode Exit fullscreen mode

What happens here? First, by using the spread-operator (...) we are creating an array from our visitedInstructions set. Then, we filter through this array and keep only the "jmp" and "nop" instructions.

Okay, let's think about what should happen now:

We can run through all instructions. We know, when we've visited any instruction twice. We also know all potential suspects. Our offender is in possiblyFaultyInstructions. Strange. I mean, the faulty instruction is in possiblyFaultyInstructions.

Now that we have come so far, we have to check each possibly faulty instruction. We'll change their operation from "jmp" to "nop" or vice versa. Then, we can run our program again to check, whether the program runs through the instructions without visiting any instruction twice.

Before doing that, let's recap how we've run through the instructions in part 1:

let accumulator = 0;

let position = 0;
let instruction = instructions[position];

const visitedInstructions = new Set<Instruction>();

while (!visitedInstructions.has(instruction)) {
  switch (instruction.operation) {
    case "acc":
      accumulator += instruction.argument;
      position++;
      break;
    case "jmp":
      position += instruction.argument;
      break;
    case "nop":
      position++;
      break;
  }

  visitedInstructions.add(instruction);
  instruction = instructions[position];
}
Enter fullscreen mode Exit fullscreen mode

That's our code from part 1. Nothing has changed for now. We exit the while-loop as soon as any instruction is visited twice. However, this time, let's rewrite our while-loop. First, note that visiting any instruction twice is faulty behaviour. Second, I'd like to introduce you to exit codes. Many programs use exit codes to determine whether the run terminated successfully. Only if the returned exit code is 0, the run was successful. We can take advantage of this to check our possibly faulty instructions.

Let's first write a run function. Then, we can pass our instructions and see, how it terminates.

function run(instructions: Instruction[]): RunResult {
  // TODO: Implement the function.
}
Enter fullscreen mode Exit fullscreen mode

Okay, so our run function will return a RunResult. This result will give us information about the exitCode, the current accumulator and all visitedInstructions. Its type definition looks like this:

interface RunResult {
  exitCode: number;
  accumulator: number;
  visitedInstructions: Set<Instruction>;
}
Enter fullscreen mode Exit fullscreen mode

Now back to implementing our run function. Let's reuse our code from part 1:

function run(instructions: Instruction[]): RunResult {
  let accumulator = 0;

  let position = 0;
  let instruction = instructions[position];

  const visitedInstructions = new Set<Instruction>();

  while (!visitedInstructions.has(instruction)) {
    switch (instruction.operation) {
      case "acc":
        accumulator += instruction.argument;
        position++;
        break;
      case "jmp":
        position += instruction.argument;
        break;
      case "nop":
        position++;
        break;
    }

    visitedInstructions.add(instruction);
    instruction = instructions[position];
  }

  return accumulator;
}
Enter fullscreen mode Exit fullscreen mode

Great. With a few modifications, this should give us the correct result. Remember, we want to use an exit code of 0, if there was NO problem. Also, we want to use an exit code of 1, if an instruction was visited twice. Let's change our code accordingly:

function run(instructions: Instruction[]): RunResult {
  // THIS IS NEW!
  let exitCode = 0;

  let accumulator = 0;

  let position = 0;
  let instruction = instructions[position];

  const visitedInstructions = new Set<Instruction>();

  // THIS HAS CHANGED!
  while (instruction) {
    // THIS IS NEW!
    if (visitedInstructions.has(instruction)) {
      exitCode = 1;
      break;
    }

    switch (instruction.operation) {
      case "acc":
        accumulator += instruction.argument;
        position++;
        break;
      case "jmp":
        position += instruction.argument;
        break;
      case "nop":
        position++;
        break;
    }

    visitedInstructions.add(instruction);
    instruction = instructions[position];
  }

  // THIS HAS CHANGED!
  return { exitCode, accumulator, visitedInstructions };
}
Enter fullscreen mode Exit fullscreen mode

As you can see, some lines have changed. Why and what happened? Okay, let's reiterate. By default, we assume everything is going smooth. So, we initialize an exitCode of 0. Then, we want to keep looping as long as there are instructions left. However, if we've already visited this instruction, something went wrong. So we can set the exitCode to 1 and break the loop. In the end, we have to return a bit more than only the accumulator. We also need the exitCode and the visitedInstructions. Thus, the return value matches our defined interface RunResult.

Phew, we are almost done. Now, for each possibly faulty instruction we just have to change the operation from "jmp" to "nop" or vice versa. Then, we can run the program and check the exit code. If it's 0 we've found the successful run, and our puzzle is solved. If the exit code is 1 we must try another possibly faulty instruction.

Here's the implementation for that:

for (const possiblyFaultyInstruction of possiblyFaultyInstructions) {
  // Temporarily save the initial operation. We use this to reset the instruction later.
  const initialOperation = possiblyFaultyInstruction.operation;

  // Change the operation. (jmp -> nop | nop -> jmp)
  possiblyFaultyInstruction.operation =
    initialOperation === "jmp" ? "nop" : "jmp";

  // Run the program with the changed instruction.
  const { exitCode, accumulator } = run(instructions);

  // This run was successful. Return the value of `accumulator`.
  if (exitCode === 0) {
    return accumulator;
  }

  // This instruction was not faulty. Reset to its initial operation.
  possiblyFaultyInstruction.operation = initialOperation;
}
Enter fullscreen mode Exit fullscreen mode

I've added comments to the implementation above. I hope it's comprehensible enough.

Adding everything together, we've solved our puzzle. Here's the full solution:

interface Instruction {
  operation: "acc" | "jmp" | "nop";
  argument: number;
}
Enter fullscreen mode Exit fullscreen mode
const instructions: Instruction[] = [];

lines.forEach((line) => {
  const [operation, argument] = line.split(" ");

  const instruction: Instruction = {
    operation: operation as "acc" | "jmp" | "nop",
    argument: parseInt(argument),
  };

  instructions.push(instruction);
});

const { visitedInstructions } = run(instructions);

const possiblyFaultyInstructions = [
...visitedInstructions,
].filter((instruction) => ["jmp", "nop"].includes(instruction.operation));

for (const possiblyFaultyInstruction of possiblyFaultyInstructions) {
  const initialOperation = possiblyFaultyInstruction.operation;

  possiblyFaultyInstruction.operation =
    initialOperation === "jmp" ? "nop" : "jmp";

  const { exitCode, accumulator } = run(instructions);

  if (exitCode === 0) {
    return accumulator;
  }

  possiblyFaultyInstruction.operation = initialOperation;
}
Enter fullscreen mode Exit fullscreen mode
interface RunResult {
  exitCode: number;
  accumulator: number;
  visitedInstructions: Set<Instruction>;
}
Enter fullscreen mode Exit fullscreen mode
function run(instructions: Instruction[]): RunResult {
  let exitCode = 0;
  let accumulator = 0;

  let position = 0;
  let instruction = instructions[position];

  const visitedInstructions = new Set<Instruction>();

  while (instruction) {
    if (visitedInstructions.has(instruction)) {
      exitCode = 1;
      break;
    }

    switch (instruction.operation) {
      case "acc":
        accumulator += instruction.argument;
        position++;
        break;
      case "jmp":
        position += instruction.argument;
        break;
      case "nop":
        position++;
        break;
    }

    visitedInstructions.add(instruction);
    instruction = instructions[position];
  }

  return { exitCode, accumulator, visitedInstructions };
}
Enter fullscreen mode Exit fullscreen mode

We did it! By the way, we can reuse our run function in our initial program run.

Solution

This puzzle required us to implement three simple instructions. We might revisit this post multiple times in the next days. Maybe more Advent of Code puzzles build upon these simple instructions. We'll see!

Again, writing this tutorial took quite some time. I'm not sure whether I can keep up with publishing these daily. I'll try my best!

Thanks a lot for reading this post. Please consider sharing it with your friends and colleagues. See you tomorrow!

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!

This post was originally published at kais.blog.

Discussion (0)

pic
Editor guide