# Advent of Code 2020 Day 5 - 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 = [
"FFFFFBFLLR",
"FBFBFFBRLL",
"BBFFBFBLRL",
…
];
``````

## Solution

### Puzzle

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

Day 5: Binary Boarding

### Part 1

Ok, let's find out what the highest seat ID on the boarding pass is. First let's look at the puzzle again. A seat's column and row is described by a weird character sequence like this: `FFFFFBFLLR`.

F means Front, B means Back and describes whether we have to look at the lower or upper half of columns.

Very similar it goes for L and R. L means Left, R means Right and describes whether we have to look at the lower or upper half of rows.

The first 7 characters of the character sequence describe the column. It's always either the lower (F) or upper (B) half. The range is from 0 to 127.

WAIT A SECOND! I don't get rid of this weird feeling that I've seen stuff like that before. 7 characters, values from 0 to 127...

DING! It's 7 bits! So `FFFFFFF` could be translated to `0000000` and means column 0. That also means that `BBBBBBB` equals `1111111` equals 127. A combination of both like `FBFBFFB` = `0101001` and means 41. Easy!

Let's look at the 3 characters describing the row. How convenient! We can apply this bit (of) logic to the end of our character sequence too. It's equivalent to 3 bits. So, `LLL` = `000` = 0; `RRR` = `111` = 7 and `RLR` = `101` = 5.

So what does that mean? We can treat our input as binary! This leads us to the highest seat ID.

Somehow we've managed to almost solve the puzzle without even writing a single line of code. Great! The only thing that's left is now to find the highest seat ID. But first, let's write some code to convert our weird character sequences into binary:

``````const binaryLines = lines.map((line) => {
return line
.replaceAll("F", "0")
.replaceAll("B", "1")
.replaceAll("L", "0")
.replaceAll("R", "1");
});
``````

Here, we've just replaced all occurrences of the character with their matching binary value. Therefore, I've used the `String#replaceAll` method. This method is not available in general, I've used `babel` and `core-js` for the polyfill. However, you can also use this:

``````const binaryLines = lines.map((line) => {
return line
.replace(/F/g, "0")
.replace(/B/g, "1")
.replace(/L/g, "0")
.replace(/R/g, "1");
});
``````

It's basically the same but with regexes instead of the `String#replaceAll` method. It's up to you. I think most of you will already use a setup with `babel` and `core-js`.

So, now our lines look like this:

``````"0010001000",
"1010110101",
"0001001000",
…
``````

What now? Well, those are binary numbers. We simply have to find the highest number and then use some work to extract the column and row number. First, let's sort these, so the highest number is on top.

``````binaryLines.sort().reverse();
``````

Perfect! We've sorted in descending order, our highest number should be accessible with `binaryLines[0]`. The others aren't interesting for us anymore, because we are looking for the highest seat ID.

Let's extract the row and column:

``````const row = parseInt(binaryLines[0].slice(0, 7), 2);
const column = parseInt(binaryLines[0].slice(7, 10), 2);
``````

What happens here? Well, for the `row` we need the first 7 characters. For the `column` we need the last 3 characters. That's what we are doing there with the `String#slice` method. Then we want to get the decimal representation of our binary number. So we use `parseInt` and use a radix of `2`. That tells the function, that our input is in binary.

Now our `row` and `column` are just numbers, and we can use them to calculate our seat ID:

``````return row * 8 + column;
``````

Awesome! We've managed to solve the puzzle and find the highest seat ID.

To recap, here's the full solution:

``````const binaryLines = lines.map((line) => {
return line
.replaceAll("F", "0")
.replaceAll("B", "1")
.replaceAll("L", "0")
.replaceAll("R", "1");
});

binaryLines.sort().reverse();

const row = parseInt(binaryLines[0].slice(0, 7), 2);
const column = parseInt(binaryLines[0].slice(7, 10), 2);

return row * 8 + column;
``````

### Part 2

After solving part 1 like we did here in this tutorial, part 2 should be pretty easy.

The puzzle description says, that our seat ID is missing in the boarding pass. However, we know, that the seat IDs directly before and after (-1/+1) DO EXIST.

We can almost reuse our puzzle solution from part 1 to find the missing seat number. Let's turn those weird character sequences into binary again.

``````const binaryLines = lines.map((line) => {
return line
.replaceAll("F", "0")
.replaceAll("B", "1")
.replaceAll("L", "0")
.replaceAll("R", "1");
});
``````

Done. Now let's sort them, so we can easily spot if there is something missing.

``````binaryLines.sort();
``````

Great! Remember, our seat ID is calculated by using the column and row number. And we know, that there is no empty seat, except at the beginning and the end.

So, as soon as we find a seat ID and the next seat ID is NOT our previous seat ID + 1, we've found the missing seat ID. The seat must be the one between the previous and the next seat ID.

Let's initialize a variable to hold our `previousSeatId`!

``````let previousSeatId: number | null = null;
``````

We've set it to null, so we can check if there was a previous seat already.

Now, we just have to loop through our `binaryLines`, calculate the seat ID and check if it is too far off from the previous one.

``````for (const binaryLine of binaryLines) {
const row = parseInt(binaryLine.slice(0, 7), 2);
const column = parseInt(binaryLine.slice(7, 10), 2);

const seatId = row * 8 + column;

if (previousSeatId !== null && seatId !== previousSeatId + 1) {
return seatId - 1;
}

previousSeatId = seatId;
}
``````

Again, for each binary line we calculate the `seatId`. The parsing and calculation is done like we did it in part 1, so you might read the explanation there again.

Then, we have to check whether we've already found a `previousSeatId`. If yes, check if there is a seat missing in between. If there is a seat missing, that's our seat. If not, we have to assign our current seat ID as the previous seat ID and continue looping.

Nice, we've solved the puzzle. Here's the full solution again:

``````const binaryLines = lines.map((line) => {
return line
.replaceAll("F", "0")
.replaceAll("B", "1")
.replaceAll("L", "0")
.replaceAll("R", "1");
});

binaryLines.sort();

let previousSeatId: number | null = null;

for (const binaryLine of binaryLines) {
const row = parseInt(binaryLine.slice(0, 7), 2);
const column = parseInt(binaryLine.slice(7, 10), 2);

const seatId = row * 8 + column;

if (previousSeatId !== null && seatId !== previousSeatId + 1) {
return seatId - 1;
}

previousSeatId = seatId;
}
``````

## Conclusion

Did you spot that you can convert your input to binary? That made this puzzle pretty easy. Using the binary representation was a pretty straight-forward way to solve this. Maybe there's an even better way, but as always, we've solved the puzzle. For my tutorial series - that's what counts the most.

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

published

published

published

published

# How to Install Node.js and npm on Windows or macOS

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.