Advent of Code 2020: Day 5

, 8 min read
advent of code 2020

Part 1

You board your plane only to discover a new problem: you dropped your boarding pass! You aren’t sure which seat is yours, and all of the flight attendants are busy with the flood of people that suddenly made it through passport control.

Instead of zones or groups, this airline uses binary space partitioning to seat people. A seat might be specified like FBFBBFFRLR, where F means “front”, B means “back”, L means “left”, and R means “right”.

The first 7 characters will either be F or B; these specify exactly one of the 128 rows on the plane (numbered 0 through 127). Each letter tells you which half of a region the given seat is in. Start with the whole list of rows; the first letter indicates whether the seat is in the front (0 through 63) or the back (64 through 127). The next letter indicates which half of that region the seat is in, and so on until you’re left with exactly one row.

For example, consider just the first seven characters of FBFBBFFRLR:
Start by considering the whole range, rows 0 through 127.
F means to take the lower half, keeping rows 0 through 63.
B means to take the upper half, keeping rows 32 through 63.
F means to take the lower half, keeping rows 32 through 47.
B means to take the upper half, keeping rows 40 through 47.
B keeps rows 44 through 47.
F keeps rows 44 through 45.
The final F keeps the lower of the two, row 44.

Every seat also has a unique seat ID: multiply the row by 8, then add the column. In this example, the seat has ID 44 * 8 + 5 = 357.

As a sanity check, look through your list of boarding passes. What is the highest seat ID on a boarding pass?

You can read the full text here. In summary, today’s puzzle input requires us to decode a binary search in string format.

I’m quite actually reasonably familiar with this process as space-filling curves are used a lot in astronomy. They are typically used to encode the location of a particle with a key such that they are rapidly queried. In general, this involves a lot of binary understanding and bit twiddling, which is hard to read so I’ll skip this approach here. See the EAGLE paper for more detail on this usage in astronomy.

For this problem the data ingestion process is straight forward. As each line stores the information for a single boarding pass we can just loop over the file and store the boarding pass as a string, in a vector. In C++ this looks like this,

1
2
3
4
5
6
7
8
// Load the boarding passes into a vector of strings
std::vector<std::string> boarding_passes;
std::fstream myfile("input", std::ios_base::in);
std::string line;
while(std::getline(myfile, line)){
    boarding_passes.push_back(line);
}
myfile.close();

Great, the boarding passes are now loaded into memory! We now need to write a function that can process the position encoded location and return the row and column of each seat. For this, we are following a binary search pattern,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
std::pair<int, int> find_seat(std::string boarding_pass){
    std::pair<int, int> seat;
    int rowl = 0;
    int rowh = 127;
    int coll = 0;
    int colh = 7;
    // Now we loop through the boarding pass
    for (int i=0; i<boarding_pass.size(); i++){
        if (boarding_pass[i] == 'F')
            rowh = (rowl + rowh) / 2;
        if (boarding_pass[i] == 'B')
            rowl = (rowl + rowh) / 2 + 1;
        if (boarding_pass[i] == 'L')
            colh = (coll + colh) / 2;
        if (boarding_pass[i] == 'R')
            coll = (coll + colh) / 2 + 1;
    }
    seat.first = rowl;
    seat.second = coll;
    return seat;
}

The function above might look complicated, but it’s not so bad. We start by knowing we are on any row between 0 and 127. If the first character in ur string is an “F”, then this tells us we are in the front half of our current range. The range 0-127 becomes, 0-63. Assume the next character is a “B” it means we are at the back of our current range, so 0-63 becomes 32-63. As the range we are considering is halved each time we just need 7 “F"s or “B"s to identify which row we are sat on. We repeat this process for the column of our seat once we have found the correct row.

We now loop over all of the boarding passes in our input, turn them into seat IDs, and store the largest value.

1
2
3
4
5
6
7
8
// Loop through and calculate the seat ids from the boarding passes
std::pair<int, int> seat;
int id;
for(auto bp : boarding_passes){
    seat = find_seat(bp);
    id = seat.first*8+seat.second;
    ans1 = std::max(ans1, id);
}

Woo, we have the first ⭐, halfway there!

The full code can be found on github

Part 2

Ding! The “fasten seat belt” signs have turned on. Time to find your seat. It’s a completely full flight, so your seat should be the only missing boarding pass in your list. However, there’s a catch: some of the seats at the very front and back of the plane don’t exist on this aircraft, so they’ll be missing from your list as well.

Your seat wasn’t at the very front or back, though; the seats with IDs +1 and -1 from yours will be in your list.

What is the ID of your seat?

You can read the full text here.

Well, it’s Saturday, so I’m very glad that part 2 doesn’t require too much extra work. We need to find the missing seat from the list of seat IDs. We know that every other seat should be filled, so if our seat was N, then N-1 and N+1 must be in the list, however, N would be missing.

I decided to implement this by storing the seat ID’s from part 1 and then sorting them. I can loop through and quickly identify our missing seat.

1
2
3
4
5
6
// Sort the seat ids
std::sort(seat_ids.begin(), seat_ids.end());
// Look for missing seat ids
for(int i=1; i<seat_ids.size(); i++)
    if (seat_ids[i]-2 == seat_ids[i-1])
        ans2 = seat_ids[i]-1;

That’s the stars ⭐⭐ earned!

The full code can be found on github

Reflections

I don’t think the first part of today’s problem can’t really be optimised too much. The solution will be O(N) where N is the number of boarding passes in the input.

We have to read in all of the inputs, which is O(N)-time, but we don’t have to store them. We could have easily just stored the maximum boarding pass, thus this could be O(1)-space. For part 2, my solution is far from optimal. I decided to sort the array which is O(N logN)-time and I’ve stored all the boarding passes so code O(N)-space.

A more optimal solution would never store the boarding passes in memory. Instead, we could loop through the file and calculate the seat ID for each boarding pass. In this loop we keep track of the maximum and minimum seat ID’s, and also the sum of all seat ID’s we have seen.

We can then calculate the expected sum if every seat was present using the partial sum of natural numbers. We then subtract the actual sum from the expected sum and the difference will be the seat ID for the missing seat; our seat!

The code for this is the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
std::pair<int, int> seat;
int sum = 0, maxv = 0, minv = 100000, id = 0;
std::fstream myfile("input", std::ios_base::in);
std::string line;
while(std::getline(myfile, line)){
    seat = find_seat(line);
    id = seat.first*8+seat.second;
    // store min, max and sum
    minv = std::min(minv, id);
    maxv = std::max(maxv, id);
    sum += id;
}
myfile.close();
// Expected sum
ans1 = maxv;
int expected = (maxv*(maxv+1)) / 2 - ((minv)*(minv-1)) / 2;
ans2 = expected - sum;

An O(N)-time and O(1)-space solution; my work here is done!

Updates (13:00, 05/12/20)

Corentin Cadiou pointed out on twitter that I could update my boarding pass processing to the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
std::pair<int, int> find_seat(std::string boarding_pass){
    int row = 0, col = 0;
    // Now we loop through the boarding pass
    for (int i=0; i<boarding_pass.size(); i++){
        if (boarding_pass[i] == 'F')
            row <<= 1;
        if (boarding_pass[i] == 'B'){
            row <<= 1;
            row += 1;
        }
        if (boarding_pass[i] == 'L')
            col <<= 1;
        if (boarding_pass[i] == 'R'){
            col <<= 1;
            col += 1;
        }
    }
    return {row, col};
}

which uses bit shifting and thus will be slightly faster than my original approach which is neat.

. . . .

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Back to my advent calendar

Comments

Back to all posts