This weekend was days 5 and 6. As always, all my solutions are available on https://git.sr.ht/~schnouki/advent-of-code.

Day 5: binary boarding

Today we are dealing with boarding passes, and parsing strings into seat numbers.

The description is pretty straightfoward: for each part of the boarding pass we have a lower and upper bound, and each new characters divides the search space in 2. Classic binary search!

def bisect(seq: str, up: str, hi: int) -> int:
    """Bisect using a string.

    >>> bisect("FBFBBFF", "B", 128)
    44
    >>> bisect("RLR", "R", 8)
    5
    """
    lo = 0
    for c in seq:
        mid = (hi + lo) // 2
        if c == up:
            lo = mid
        else:
            hi = mid
    return lo


def seat_id(data: str) -> int:
    """Compute the seat ID for a boarding pass.

    >>> seat_id("BFFFBBFRRR")
    567
    >>> seat_id("FFFBBBFRRR")
    119
    >>> seat_id("BBFFBBFRLL")
    820
    """
    row = bisect(data[:7], "B", 128)
    col = bisect(data[7:], "R", 8)

    return row * 8 + col

seats = set(seat_id(line) for line in raw_data.splitlines())

Very simple. Part 1 is just to search for the max of all values. This takes less than 1 ms. Alright.

…or is it? Is this really a good way to do it? Well, no!

These “boarding passes” are just numbers encoded in binary, with 0 replaced by “F” or “L” and 1 replaced by “B” or “R”… So we can remove these 2 functions and just use the equivalent, simpler and faster code:

data = raw_data.replace("B", "1").replace("F", "0").replace("R", "1").replace("L", "0")
seats = set(int(line, base=2) for line in data.splitlines())

Part 2 is also really simple:

first = min(seats)
last = max(seats)
for seat in range(first, last):
    if seat not in seats and (seat - 1) in seats and (seat + 1) in seats:
        print(seat)

Day 6: Custom Customs

Customs declaration forms. Who doesn’t love them?

Alright. In our input, each line is a set of answers for one person. Each group of person is separated by a blank line.

To make things easy to manipulate, we’ll use sets instead of plain strings, which makes it a bit easier (and faster) to check how answers correlate with each other. Parsing the input is pretty simple:

data: List[List[Set[str]]] = []
for group in raw_data.split("\n\n"):
    lines = [set(s.strip()) for s in group.split()]
    data.append(lines)

Part 1

We need to find all answers given by each group. In our parsed data, each list element is the list of answers for one group, so it’s pretty easy to do that using set operations:

total = 0
for group in data:
    answers = set()
    for line in group:
        answers.update(line)
    total += len(answers)
print(total)

That takes about 0.5 ms to run. Nice.

Part 2

Almost the same: now we need to find answers given by everyone in each group. Basically, same as before, except that we need to use a set union instead of a set intersection. Using sets was definitely a good idea!

total = 0
for group in data:
    answers = None
    for line in group:
        if answers is None:
            answers = line
        else:
            answers.intersection_update(line)
    total += len(answers)
print(total)

Same thing: about 0.5 ms.

That was nice. See you soon for day 7!