Advent of Code is a yearly programming challenge involving 25 puzzles, released daily in December. I published all my solutions for 2021 on GitHub. I’m featuring some of the more interesting or odd ones in a series of posts.

For some reason I committed to writing solutions to the first few problems in one-line quasi-functional Python (which, incidentally, is Turing complete). Day 4’s one-liner is the most hideous of the bunch.

The problem asks us to simulate a gaggle of bingo-playing grannies: given a sequence of draws and a set of bingo boards, we submit the score of whoever wins first.

Here’s the code, annotated with pointers to explanations below.

( # (1)
    lambda draws, boards: reduce( # (2)
        lambda score_and_boards, draw: (
            ( # (3)
                lambda boards: (
                    reduce( # (4)
                        lambda score, board: sum(
                            n for row in board for (n, seen) in row if not seen
                        )
                        * draw
                        if score is None
                        and any(
                            all(seen for (_, seen) in row)
                            for b in [board, zip(*board)] # (5)
                            for row in b
                        )
                        else score,
                        boards,
                        None,
                    ),
                    boards,
                )
            )( # (6)
                lmap( # (7)
                    lambda board: lmap(
                        lambda row: lmap(
                            lambda e: (e[0], draw == e[0] or e[1]), row
                        ),
                        board,
                    ),
                    score_and_boards[1],
                )
            )
            if score_and_boards[0] is None
            else score_and_boards # (8)
        ),
        draws,
        (None, boards),
    )[0]
)(*read("input.txt"))

  1. The form (lambda t: f(t))(g(x)) allows us to write f(g(x)) more concisely when f(t) has a lot of ts. Here, this lets me avoid writing read("input.txt")[1] multiple times when I mean boards. This pattern is like a less elegant form of let ... in or where from Haskell.

    read is just boilerplate. It returns (draws, boards), where draws is the list of numbers drawn and boards is a list of bingo board states, represented by 5x5 listlists of tuples (n, seen) with seen initially False.

  2. This is functools.reduce, which is just a fold in FP lingo; reduce(f, [x] + xs, a) == reduce(f, xs, f(a, x)).

    In our case f is the lambda at (3), which maps tuples score_and_boards := (winning score: Maybe int, current board states: [[[(int, bool)]]]) and the current draw to a new score_and_boards tuple. The iterable to be reduced is draws, and the initial value of score_and_boards is (None, boards), which indicates that there is initially no winning score and all boards are unmarked.

    At the end of the reduction, we pluck off the score from the final tuple.

  3. We use the composition trick from (1) again here.
  4. This reduce searches the updated board states for a winning board, returning the score of the first board with a complete row or column of seen entries, or None if none exists. We assume that there is no tie for first.
  5. zip(*board) is the transpose of board; its rows are columns of board.
  6. To update board states, for each board we flip the seen bit of each entry if matches the current draw.
  7. Our lmap is just the composition list . map. These lines would be less obnoxious as a list comprehension.
  8. We stop searching for a win if someone has already won.

Here’s the equivalent procedural code:

draws, boards = read("input.txt") # (1)
for draw in draws: # (2)
    for i, board in enumerate(boards): # (4)
        boards[i] = [ # (6)
            [(n, draw == n or seen) for (n, seen) in row]
            for row in board
        ]
        if any(
            all(seen for (_, seen) in row)
            for b in [boards[i], zip(*boards[i])] # (5)
            for row in b
        ):
            return draw * sum(
                n for row in boards[i] for (n, seen) in row if not seen
            )

A third as many lines as the “one-liner” (according to black, at least), and perhaps a bit more readable.