« Advent of Code 2020 - Day 4
Advent of Code 2020 - Day 6 »

Advent of Code 2020 - Day 5

in   code   ,

Day 5 of AoC 2020 (Binary Boarding) is a bit of a trick problem. However, once you understand the pattern inherent in the problem description, this is extremely straightforward. As always, spoilers ahead.

The problem description describes the use of binary space partitioning, in essence splitting the search space in half at every step, then picking one of the halves and proceeding with the search. A naive implementation would take the upper and lower bounds and recalculate the bounds after each character.

But, this is unnecessary, and can be solved by simply mapping the characters to 0 and 1, and converting the binary string into an integer. Why does this work? Let’s take a simple example FBFBBFFRLR, as given in the problem description. Let’s just take the seat column (RLR).

  • Start by considering the whole range 0-7
  • The first R tells us to take the upper half of this range (4-7)
  • The second letter (L) means take the lower half of the now restricted range (4-5)
  • The last letter (R) means to take the upper half - giving us the seat column 5

Let’s use the binary encoding to visualize this further.

Step Character Binary Encoding Range
0 - XXX 0 - 7
1 R 1XX 4 - 7
2 L 10X 4 - 5
3 R 101 5

As you can see from the binary encoding column, the X characters are essentially floating values, which means that they could take either 0 or 1, and the range is found by setting them to all 0 or all 1. But, once we have all the positions resolved, we are down to a single value in the range.

In the same way, by replacing F with 0 and B with 1, we can compute the seat row. However, we don’t actually need the row and column, we only need the seat ID, which is, conveniently, row * 8 + column, or the value by just converting all characters to 0 or 1 and converting from binary to integer.

With the above example (FBFBBFFRLR), we can compute the result as 0101100101, or 357, as shown in the table below:

Step Character Binary Encoding Range
0 - XXXXXXXXXX 0 - 1023
1 F 0XXXXXXXXX 0 - 511
2 B 01XXXXXXXX 256 - 511
3 F 010XXXXXXX 256 - 383
4 B 0101XXXXXX 320 - 383
5 B 01011XXXXX 352 - 383
6 F 010110XXXX 352 - 367
7 F 0101100XXX 352 - 359
8 R 01011001XX 356 - 359
9 L 010110010X 356 - 357
10 R 0101100101 357

Now, we have all we need to compute the seat ID using the character to bit mapping defined above.

def seat_id(seat):
    mapping = {'F': '0', 'B': '1', 'L': '0', 'R': '1'}
    return int(''.join(mapping[c] for c in seat), 2)

with open('input') as datafile:
    data = datafile.read().splitlines()

seats = sorted(seat_id(seat) for seat in data)

max_seat = seats[-1]

With the above snippet, we have the solution for part 1. For part 2, we know that the plane is full, and the only missing seat in the sorted list is our seat. The problem states tht we are somewhere in the middle, so we can just walk through the list, comparing the current seat with the previous seat, and when the difference is not 1, we have found our missing seat.

last = seat[0]
for seat in seats[1:]:
    if seat != last+1:
        print(last+1)
        break
    last = seat

 

 Recent Posts

 Tags

 Categories