Part 1

Day 5’s problem is all about cutting stuff in halves. The problem mentions an “airline [that] uses binary space partitioning to seat people”. On a ticket, there is 10 characters that are either F for front, B for back, L for left, R for right. The first seven characters help us determine the row (there are exactly 128 rows) while the last three are used to identify the exact seat in the row (there are exactly 8 seats in a row).

We are then told how each of this character help us to determine our seat in the plane. The example provided is FBFBBFFRLR, which means:

1. F means we take the front part, thus keeping rows 0 through 63
2. B means we take the back part, thus keeping rows 32 through 63.
3. F means we take the front part, thus keeping rows 32 through 47
4. B means we take the back part, thus keeping rows 40 through 47.
5. B means we take the back part, thus keeping rows 44 through 47.
6. F means we take the front part, thus keeping rows 44 through 45
7. The seventh F keeps the lower row: 44.
8. The first character for the actual seat is R, which means we take the upper half, thus keeping seats 4 to 7.
9. Then, L means we take the lower half, thus keeping seats 4 to 5.
10. Finally, R means we take the upper value: seat 5.

In the end, the expected output is a seat ID which is computed with the following formula: seat_id = row * 8 + seat.

The name is this problem is an indication of how we can solve it. Basically, we can represent the possible rows with an interval A = [I, J] that we are going to cut in half every time we look at a letter. The difficulty then consists of computing the new bounds correctly. Let’s take a closer look at our problem:

A = [0, 127]

|----------- ... ------------|
0                           127

The objective now is to shift the lower or upper bound so that the resulting interval is half the length of the former one. So the next step is either [0, 63] or [64, 127]. With these two intervals, we can start to see a pattern taking form:

• If we take the lower half, max = max - (length / 2);
• If we take the upper half, min = min + (length / 2).

If we follow the example, the first character on the ticket is an F, and so the interval becomes [0, 63], with a new length of 64. The second character is a B which means we have to take the upper half. So, if we apply the formula just above, we should get:

min = min + (length / 2) = 0 + 32, and so the interval becomes [32, 63] which is also the interval given by the problem statement. Our solution seems correct, and we can now implement it in Python (the objective is to find the highest seat ID):

seats = []
for ticket in tickets:
    row_min, row_max = 0, 127
    seat_min, seat_max = 0, 7
    for character in ticket:
        if character == "F":
            row_max -= int(len(range(row_min, row_max + 1)) / 2)
        elif character == "B":
            row_min += int(len(range(row_min, row_max + 1)) / 2)
        elif character == "R":
            seat_max -= int(len(range(seat_min, seat_max + 1)) / 2)
        elif character == "L":
            seat_minA += int(len(range(seat_min, seat_max + 1)) / 2)
    seat_id = row_min * 8 + seat_min    # It doesn't matter which value we chose
                                        # row_min == row_max and seat_min == seat_max
    seats.append(seat_id)
print(max(seats))

Part 2

In Part 2, we are told that our input data is a list of seat IDs that all have adjacent values except for our seat. Since all seat IDs are integers, we can very quickly sort the list of IDs produced in Part 1 and iterate through that list to find out the only missing value.

The solution is quite straightforward:

seats.sort()
for i, seat in enumerate(seats[:-1]):
    if seat + 1 != seats[i + 1]:
        print(seat + 1)
        break

Concepts and difficulties

In Day 5, the main difficulty is (as often) to model the problem appropriately. Once we figure out that the intervals are being cut in half at each pass, it is quite easy to conclude that the bounds need to be modified by half the length of the interval.

After that, Part 2 is probably simpler than Part 1. The trick is to see that sorting the list of seat_id will help us easily find the missing seat.