{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Playing Bingo\n", "\n", "- \n", "\n", "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.\n", "\n", "We need to solve two problems:\n", "\n", "- Identify what bingo cards have a given number\n", "- How to identify a card as 'done'\n", "\n", "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.\n", "\n", "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.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from __future__ import annotations\n", "\n", "from dataclasses import dataclass, field\n", "from typing import Final\n", "\n", "# Bingo cards are square grids of CARD_SIZE x CARD_SIZE numbers.\n", "CARD_SIZE: Final[int] = 5\n", "\n", "# Pre-computed slices for rows and columns\n", "ROWS: Final[list[slice]] = [\n", " slice(i, i + CARD_SIZE) for i in range(0, CARD_SIZE * CARD_SIZE, CARD_SIZE)\n", "]\n", "COLS: Final[list[slice]] = [\n", " slice(col, CARD_SIZE * CARD_SIZE, CARD_SIZE) for col in range(CARD_SIZE)\n", "]\n", "\n", "\n", "@dataclass\n", "class BingoCard:\n", " numbers: list[int]\n", " marked: set[int] = field(default_factory=set)\n", " _lines: frozenset[frozenset[int]] = field(init=False)\n", "\n", " def __post_init__(self) -> None:\n", " # collect the sets of numbers forming the horizontal and vertical lines\n", " # across the bingo card\n", " self._lines = frozenset(\n", " frozenset(self.numbers[row]) for row in ROWS\n", " ) | frozenset(frozenset(self.numbers[col]) for col in COLS)\n", "\n", " @classmethod\n", " def from_text(cls, text: str) -> BingoCard:\n", " return cls([int(n) for n in text.split()])\n", "\n", " @property\n", " def unmarked_score(self) -> int:\n", " return sum(set(self.numbers) - self.marked)\n", "\n", " @property\n", " def wins(self) -> bool:\n", " # a bingo card wins if any of its lines is a subset of the marked numbers\n", " marked = self.marked\n", " return any(marked >= line for line in self._lines)\n", "\n", " def mark(self, number: int) -> int:\n", " \"\"\"Mark a number off on the card, and return a score\n", "\n", " The score is 0 if there are still rows or columns with unmarked numbers.\n", "\n", " \"\"\"\n", " self.marked.add(number)\n", " if self.wins:\n", " return self.unmarked_score * number\n", " return 0\n", "\n", "\n", "@dataclass\n", "class BingoSubsystem:\n", " random_numbers: list[int]\n", " cards: list[BingoCard] = field(default_factory=list)\n", " number_index: dict[int, set[int]] = field(default_factory=dict)\n", "\n", " def add_card(self, card: BingoCard) -> None:\n", " card_index = len(self.cards)\n", " self.cards.append(card)\n", " for number in card.numbers:\n", " self.number_index.setdefault(number, set()).add(card_index)\n", "\n", " @classmethod\n", " def from_text(cls, text: str) -> BingoSubsystem:\n", " blocks = iter(text.split(\"\\n\\n\"))\n", " game = cls([int(n) for n in next(blocks).split(\",\")])\n", " for block in blocks:\n", " game.add_card(BingoCard.from_text(block))\n", " return game\n", "\n", " def find_winning_score(self):\n", " empty = frozenset()\n", " for number in self.random_numbers:\n", " for card_index in self.number_index.get(number, empty):\n", " if score := self.cards[card_index].mark(number):\n", " return score\n", " return 0\n", "\n", "\n", "test_input = \"\"\"\\\n", "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\n", "\n", "22 13 17 11 0\n", " 8 2 23 4 24\n", "21 9 14 16 7\n", " 6 10 3 18 5\n", " 1 12 20 15 19\n", "\n", " 3 15 0 2 22\n", " 9 18 13 17 5\n", "19 8 7 25 23\n", "20 11 10 24 4\n", "14 21 16 12 6\n", "\n", "14 21 17 24 4\n", "10 16 15 9 19\n", "18 8 23 26 20\n", "22 11 13 6 5\n", " 2 0 12 3 7\n", "\"\"\"\n", "\n", "assert BingoSubsystem.from_text(test_input).find_winning_score() == 4512" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Part 1: 8442\n" ] } ], "source": [ "import aocd\n", "\n", "random_bingo_game = aocd.get_data(day=4, year=2021)\n", "print(\"Part 1:\", BingoSubsystem.from_text(random_bingo_game).find_winning_score())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Part 2: continue the game and find the last score\n", "\n", "All we have to do now is continue to play Bingo until we run out of numbers or cards. We'll need to track:\n", "\n", "- The last winning score\n", "- What cards already won so we can skip those\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "class LastWinningBingoSubsystem(BingoSubsystem):\n", " def find_last_winning_score(self) -> int:\n", " last_score, remaining = 0, set(range(len(self.cards)))\n", " empty = frozenset()\n", " for number in self.random_numbers:\n", " for card_index in self.number_index.get(number, empty) & remaining:\n", " if score := self.cards[card_index].mark(number):\n", " last_score = score\n", " remaining.remove(card_index)\n", " if not remaining:\n", " break\n", " return last_score\n", "\n", "\n", "assert LastWinningBingoSubsystem.from_text(test_input).find_last_winning_score() == 1924" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Part 2: 4590\n" ] } ], "source": [ "print(\n", " \"Part 2:\",\n", " LastWinningBingoSubsystem.from_text(random_bingo_game).find_last_winning_score(),\n", ")" ] } ], "metadata": { "interpreter": { "hash": "8bb5fd587ebf4d90f905285c44a569046664a8863ee065ff2dd968491b671e06" }, "kernelspec": { "display_name": "Python 3.10.0 64-bit ('adventofcode-mOkh6lsX': pipenv)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.0" }, "orig_nbformat": 4 }, "nbformat": 4, "nbformat_minor": 2 }