## DEV Community is a community of 892,765 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Kai

Posted on • Originally published at kais.blog

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

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.

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",
…
];
``````

## 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;
}
``````

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[] = [];
``````

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);
});
``````

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",
…
``````

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(" ");
``````

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),
};
``````

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);
});
``````

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;
``````

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];
``````

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>();
``````

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.

instruction = instructions[position];
}
``````

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;
}
``````

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;
}
``````
``````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;
}

instruction = instructions[position];
}

return accumulator;
``````

## 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;
}
``````
``````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);
});
``````

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));
``````

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;
}

instruction = instructions[position];
}
``````

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.
}
``````

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>;
}
``````

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;
}

instruction = instructions[position];
}

return accumulator;
}
``````

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;
}

instruction = instructions[position];
}

// THIS HAS CHANGED!
return { exitCode, accumulator, visitedInstructions };
}
``````

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;
}
``````

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;
}
``````
``````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;
}
``````
``````interface RunResult {
exitCode: number;
accumulator: number;
visitedInstructions: Set<Instruction>;
}
``````
``````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;
}

instruction = instructions[position];
}

return { exitCode, accumulator, visitedInstructions };
}
``````

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!