Sean McLemon | Advent of Code

2020-12-05 - Binary Boarding

(original .ipynb)

Day 5 puzzle input is a list of 10-character strings (mine is here) representing a Boarding Pass, which can be processed to calculate a "seat id" through a calculation neatly described in the link but which I can't be bothered repeating here. Part 1 involves calculating the seat ids for all boarding passes and finding the largest one. Part 2 involves finding a gap in the sequence of seat ids which turns out to be "my" seat.

puzzle_input_str = open("puzzle_input/day5.txt").read()

def parse_boarding_pass_section(elements, upper_str, lower_str):
    lower = 0
    upper = (2 ** len(elements)) - 1
    step = (2 ** len(elements)) // 2

    for e in elements:
        if e == lower_str:
            upper = upper - step
        elif e == upper_str:
            lower = lower + step
        else:
            raise Exception(f"invalid element detected: {e}")
        
        step = step // 2

    assert upper == lower
    return upper

def seat_id(boarding_pass):
    rows = boarding_pass[:7]
    cols = boarding_pass[7:]
    
    row = parse_boarding_pass_section(rows, "B", "F")
    col = parse_boarding_pass_section(cols, "R", "L")
    
    return (row * 8) + col    

# So, decoding FBFBBFFRLR reveals that it is the seat at row 44, column 5.
# ...
# 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.
assert 357 == seat_id("FBFBBFFRLR")

#     BFFFBBFRRR: row 70, column 7, seat ID 567.
#     FFFBBBFRRR: row 14, column 7, seat ID 119.
#     BBFFBBFRLL: row 102, column 4, seat ID 820.
assert 567 == seat_id("BFFFBBFRRR")
assert 119 == seat_id("FFFBBBFRRR")
assert 820 == seat_id("BBFFBBFRLL")

seat_ids = [ seat_id(b.strip()) for b in puzzle_input_str.strip().split("\n") ]    
print("part 1 - highest seat id =", max(seat_ids))

def find_my_seat(seat_ids):
    all_seats = set(seat_ids)

    # assume the first unoccupied seat is mine
    for row in range(0, 128):
        for col in range(0, 8):
            sid = (row * 8) + col       
            prev_sid = sid - 1
            next_sid = sid - 1

            if (not (sid in all_seats)) and (prev_sid in all_seats) and (next_sid in all_seats):
                return sid
    return -1

print("part 2 - my seat id =", find_my_seat(seat_ids))

part 1 - highest seat id = 933
part 2 - my seat id = 711