binary boarding

approach

each boarding pass is split into a 7-letter row part and a 3-letter column part. bisect narrows a range for each part: B or R keeps the upper half, anything else keeps the lower half. the seat id is row * 8 + column.

part 1 is the largest id. part 2 sorts the ids and returns the first gap between consecutive ones; a comment notes it could be done in O(n) but sorting was good enough.

the trick

the letters are a binary search spelled out, so halving a range per character gives the row and column.

def bisect(s):
    l, r = 0, 2**len(s) - 1
    for c in s:
        mid = (l + r) // 2
        if c in ['B', 'R']:
            l = mid + 1
        else:
            r = mid
    return r