We are asked to figure out what bingo card will win first; the proof of finding the right card is in what numbers were not yet picked; you sum those, and multiply by the last number that matched.
We need to solve two problems:
If we model cards as a class with a 'marked' set we can trivially determine if a card has won every time we add another number to the card by intersecting each row or column with the marked set. That solves the second problem.
The first problem can be solved by keeping an index of number to a list of card indices. You map the number to the cards, mark those cards, checking for a winner.
from __future__ import annotations
from dataclasses import dataclass, field
from typing import Final
# Bingo cards are square grids of CARD_SIZE x CARD_SIZE numbers.
CARD_SIZE: Final[int] = 5
# Pre-computed slices for rows and columns
ROWS: Final[list[slice]] = [
slice(i, i + CARD_SIZE) for i in range(0, CARD_SIZE * CARD_SIZE, CARD_SIZE)
]
COLS: Final[list[slice]] = [
slice(col, CARD_SIZE * CARD_SIZE, CARD_SIZE) for col in range(CARD_SIZE)
]
@dataclass
class BingoCard:
numbers: list[int]
marked: set[int] = field(default_factory=set)
_lines: frozenset[frozenset[int]] = field(init=False)
def __post_init__(self) -> None:
# collect the sets of numbers forming the horizontal and vertical lines
# across the bingo card
self._lines = frozenset(
frozenset(self.numbers[row]) for row in ROWS
) | frozenset(frozenset(self.numbers[col]) for col in COLS)
@classmethod
def from_text(cls, text: str) -> BingoCard:
return cls([int(n) for n in text.split()])
@property
def unmarked_score(self) -> int:
return sum(set(self.numbers) - self.marked)
@property
def wins(self) -> bool:
# a bingo card wins if any of its lines is a subset of the marked numbers
marked = self.marked
return any(marked >= line for line in self._lines)
def mark(self, number: int) -> int:
"""Mark a number off on the card, and return a score
The score is 0 if there are still rows or columns with unmarked numbers.
"""
self.marked.add(number)
if self.wins:
return self.unmarked_score * number
return 0
@dataclass
class BingoSubsystem:
random_numbers: list[int]
cards: list[BingoCard] = field(default_factory=list)
number_index: dict[int, set[int]] = field(default_factory=dict)
def add_card(self, card: BingoCard) -> None:
card_index = len(self.cards)
self.cards.append(card)
for number in card.numbers:
self.number_index.setdefault(number, set()).add(card_index)
@classmethod
def from_text(cls, text: str) -> BingoSubsystem:
blocks = iter(text.split("\n\n"))
game = cls([int(n) for n in next(blocks).split(",")])
for block in blocks:
game.add_card(BingoCard.from_text(block))
return game
def find_winning_score(self):
empty = frozenset()
for number in self.random_numbers:
for card_index in self.number_index.get(number, empty):
if score := self.cards[card_index].mark(number):
return score
return 0
test_input = """\
7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1
22 13 17 11 0
8 2 23 4 24
21 9 14 16 7
6 10 3 18 5
1 12 20 15 19
3 15 0 2 22
9 18 13 17 5
19 8 7 25 23
20 11 10 24 4
14 21 16 12 6
14 21 17 24 4
10 16 15 9 19
18 8 23 26 20
22 11 13 6 5
2 0 12 3 7
"""
assert BingoSubsystem.from_text(test_input).find_winning_score() == 4512
import aocd
random_bingo_game = aocd.get_data(day=4, year=2021)
print("Part 1:", BingoSubsystem.from_text(random_bingo_game).find_winning_score())
Part 1: 8442
All we have to do now is continue to play Bingo until we run out of numbers or cards. We'll need to track:
class LastWinningBingoSubsystem(BingoSubsystem):
def find_last_winning_score(self) -> int:
last_score, remaining = 0, set(range(len(self.cards)))
empty = frozenset()
for number in self.random_numbers:
for card_index in self.number_index.get(number, empty) & remaining:
if score := self.cards[card_index].mark(number):
last_score = score
remaining.remove(card_index)
if not remaining:
break
return last_score
assert LastWinningBingoSubsystem.from_text(test_input).find_last_winning_score() == 1924
print(
"Part 2:",
LastWinningBingoSubsystem.from_text(random_bingo_game).find_last_winning_score(),
)
Part 2: 4590