From 7a15d394d4cbac2827ce621e58f9c267f3a20df8 Mon Sep 17 00:00:00 2001
From: Tomasz Kramkowski <tk@the-tk.com>
Date: Sat, 4 Dec 2021 18:31:12 +0000
Subject: day 4: final rewrite, best performance

---
 4.py | 89 +++++++++++++++++++++++---------------------------------------------
 1 file changed, 30 insertions(+), 59 deletions(-)

diff --git a/4.py b/4.py
index 0c7cf4f..4ee51be 100644
--- a/4.py
+++ b/4.py
@@ -1,68 +1,39 @@
-from collections import defaultdict
+from typing import NamedTuple
 from utils import open_day
 
-class Board:
-    col_hits: list[int]
-    row_hits: list[int]
-    has_bingo: bool
-    nums: dict[int, tuple[int, int]]
-    def __init__(self, cells: list[list[int]]) -> None:
-        width: int = len(cells[0])
-        height: int = len(cells)
-        self.col_hits = [height] * width
-        self.row_hits = [width ] * height
-        self.nums = dict()
-        for y, row in enumerate(cells):
-            for x, cell in enumerate(row):
-                self.nums[cell] = (x, y)
-        self.has_bingo = False
-    def call(self, num: int) -> None:
-        pos: tuple[int, int] | None = self.nums.pop(num, None)
-        if pos is None: return
-        x, y = pos
-        self.col_hits[x] -= 1
-        self.row_hits[y] -= 1
-        self.has_bingo = (
-            self.has_bingo or
-            not self.col_hits[x] or
-            not self.row_hits[y]
-        )
-    @property
-    def unmarked_sum(self) -> int:
-        return sum(self.nums.keys())
-    @staticmethod
-    def from_string(s: str) -> 'Board':
-        return Board([[int(n) for n in l.split()] for l in s.split('\n')])
+class Win(NamedTuple):
+    index: int | None
+    round: int
 
-def solve(nums: list[int], boards: list[Board]) -> tuple[int, int]:
-    indices: set[int] = { i for i in range(len(boards)) }
-    nums_indices: defaultdict[set[int]] = defaultdict(set)
-    i: int
-    board: Board
-    for i, board in enumerate(boards):
-        for n in board.nums:
-            nums_indices[n].add(i)
-    wins: list[int] = []
-    num: int
-    for num in nums:
-        i: int
-        board: Board
-        winners: set[int] = set()
-        num_indices: set[int] = nums_indices.get(num)
-        for i in indices & num_indices:
-            boards[i].call(num)
-            if boards[i].has_bingo:
-                wins.append(num * boards[i].unmarked_sum)
-                winners.add(i)
-        indices.difference_update(winners)
-    return wins[0], wins[-1]
+Board = list[list[int]]
+
+def board_from_string(s: str) -> Board:
+    return [[numidxs[int(cell)] for cell in row.split()] for row in s.split('\n')]
+
+def resolve(nums: list[int], boards: list[Board], index: int, round: int) -> int:
+    board: Board = boards[index]
+    count: int = sum(nums[cell] for row in board for cell in row if cell > round)
+    return count * nums[round]
 
 nums: str | list[int]
 boards: list[str] | list[Board]
 nums, *boards = open_day(4).read().rstrip().split('\n\n')
 nums = list(map(int, nums.split(',')))
-boards = [Board.from_string(b) for b in boards]
+numidxs = { n: i for i, n in enumerate(nums) }
+boards = [board_from_string(board) for board in boards]
+
+first: Win = Win(None, max(nums))
+last: Win = Win(None, 0)
+for i, board in enumerate(boards):
+    row: int = min(max(row) for row in board)
+    col: int = min(
+        max(board[y][x] for y in range(len(board)))
+        for x in range(len(board[0]))
+    )
+    win: Win = Win(i, min(row, col))
+    if win.round < first.round: first = win
+    if win.round > last.round: last = win
 
-part1, part2 = solve(nums, boards)
-print(part1)
-print(part2)
+assert(first.index is not None and last.index is not None)
+print(resolve(nums, boards, first.index, first.round))
+print(resolve(nums, boards, last.index, last.round))
-- 
cgit v1.2.3-54-g00ecf