Advent of Code: Day #05 - Binary Boarding

Now we're through passport control we need to board the plane. And we've forgotten our boarding pass. Never mind through process of elimination we can discover which seat is ours.

The airline uses binary space partitioning (BSP) to refer to seats. BSP continuously subdivides a space by half until only one possibility remains. Their are 127 rows and 7 columns on the plane. An example seat specifier could be FBFBBFFRLR where F means we take the lower half of the row subdivision and B the upper half. L is the lower half of rows and R is upper half. For task 1 we must find the highest seat ID.

Reading in the data

When I read in the data I split the row and column information of each line (row information is the first 7 digits, row the last 3) and created a [row, column] array from each specifier.

def read_data(path):
    passes = []
    with open(path, "r") as file:
        for line in file.readlines():
            tmp = line.rstrip()
            passes.append([tmp[0:-3], tmp[-3:]])
    return passes

The Solution

We simply subdivide the row space of 0, 127 and the column space of 0, 7 until we are left with only one possible row and column then calculate the seat ID and see if it's the highest we've seen.

def bsp(limits):
    return limits[1] - (limits[1] - limits[0]) // 2


def task_one(passes):
    highest = -1
    for row_data, column_data in passes:
        rows = [0, 127]
        cols = [0, 7]

        for instruction in row_data:
            switch = {"B": 0, "F": 1}
            rows[switch[instruction]] = bsp(rows)

        for instruction in column_data:
            switch = {"R": 0, "L": 1}
            cols[switch[instruction]] = bsp(cols)

        seat_id = (rows[0] * 8) + cols[0]
        highest = seat_id if seat_id > highest else highest

    return highest

The Solution

For task two we actually have to find out which boarding pass is ours. To do this we borrow the code from part 1 to calculate the seat ID's and add them all to a list. Then to find ours we generate a list of all the seat ID's then take the difference of the two lists.

def bsp(limits):
    return limits[1] - (limits[1] - limits[0]) // 2


def task_two(passes):
    seat_ids = []

    for row_data, column_data in passes:
        rows = [0, 127]
        cols = [0, 7]

        for instruction in row_data:
            switch = {"B": 0, "F": 1}
            rows[switch[instruction]] = bsp(rows)

        for instruction in column_data:
            switch = {"R": 0, "L": 1}
            cols[switch[instruction]] = bsp(cols)

        seat_ids.append((rows[0] * 8) + cols[0])

    sorted_seats = sorted(seat_ids)
    all_seats = set(range(sorted_seats[0], sorted_seats[-1]))
    sorted_seats = set(sorted_seats)

    my_seat = all_seats - sorted_seats
    return my_seat.pop()