DEV Community

loading...

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

kais_blog profile image Kai Originally published at kais.blog Updated on ・6 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 = [
  "FFFFFBFLLR",
  "FBFBFFBRLL",
  "BBFFBFBLRL",
  
];
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 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");
});
Enter fullscreen mode Exit fullscreen mode

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");
});
Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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();
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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");
});
Enter fullscreen mode Exit fullscreen mode

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

binaryLines.sort();
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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;
  }
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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!

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