Advent of Code 2021: Day 4

# Advent of Code 2021 - Day 4

## Day 4 puzzle description

Day 4 puzzle description can be found on my Github.

## My solution in Python

``````from dataclasses import dataclass
from typing import Iterable, List, Sequence, Set, Tuple

Row = List[int]
Column = List[int]

EMPTY_LINE = "\n"

BOARD_LENGTH = 5

@dataclass(frozen=True)
class BingoBoard:
rows: List[Row]

def __post_init__(self):
board_length = len(self.rows)
for row in self.rows:
if len(row) != board_length:
raise ValueError("Board dimensions must be the same (i.e. 5 x 5).")

@property
def board_length(self) -> int:
return len(self.rows)

@property
def columns(self) -> List[Column]:
return [[row[i] for row in self.rows] for i in range(self.board_length)]

@property
def are_numbers_unique(self) -> bool:
"""
Making sure that all numbers in particular board are unique.
"""
return (
len(set([num for row in self.rows for num in row]))
== self.board_length ** 2
)

@property
def all_numbers(self) -> Set[int]:
return set([num for row in self.rows for num in row])

def get_unmarked_numbers(self, drawn_numbers: Iterable[int]) -> Set[int]:
return self.all_numbers - set(drawn_numbers)

def has_won(self, drawn_numbers: List[int]) -> bool:
drawn_numbers_set = set(drawn_numbers)
has_winning_row = any(set(row) <= drawn_numbers_set for row in self.rows)
has_winning_column = any(
set(column) <= drawn_numbers_set for column in self.columns
)
return has_winning_row or has_winning_column

def get_board_score(self, drawn_numbers: List[int]) -> int:
return sum(self.get_unmarked_numbers(drawn_numbers)) * drawn_numbers[-1]

@classmethod
def from_sequence_of_strings(cls, string_sequence: Sequence[str]):
rows = [[int(x) for x in line.split(" ")] for line in string_sequence]
return cls(rows)

def parse_game_data(path: str) -> Tuple[List[int], List[BingoBoard]]:
with open(path, "rt") as f:
drawn_numbers = [int(x) for x in data.split(",")]

boards = []
board_buffer = []
for line in data[1:]:
if line == EMPTY_LINE:
continue
board_buffer.append(line.replace("\n", "").strip().replace("  ", " "))
if len(board_buffer) == BOARD_LENGTH:
board = BingoBoard.from_sequence_of_strings(board_buffer)
boards.append(board)
board_buffer.clear()

return drawn_numbers, boards

def calculate_first_winning_board_score_from_file(path: str) -> int:
all_drawn_numbers, boards = parse_game_data(path)

for i in range(5, len(all_drawn_numbers)):
for board in boards:
drawn_numbers = all_drawn_numbers[:i]
if board.has_won(drawn_numbers):
return board.get_board_score(drawn_numbers)

def calculate_last_winning_board_score_from_file(path: str) -> int:
all_drawn_numbers, boards = parse_game_data(path)

winning_boards = []
winning_drawn_numbers = []
last_winning_board_found = False

# TODO: it works, but feels complicated? Refactor candidate
while not last_winning_board_found:
for i in range(5, len(all_drawn_numbers)):
for board in boards:
drawn_numbers = all_drawn_numbers[:i]
if board.has_won(drawn_numbers):
if board not in winning_boards:
winning_boards.append(board)
winning_drawn_numbers.append(drawn_numbers)
else:
last_winning_board_found = True

last_winning_board = winning_boards[-1]
last_winning_drawn_numbers = winning_drawn_numbers[-1]
return last_winning_board.get_board_score(last_winning_drawn_numbers)

if __name__ == "__main__":
input_path = "input.txt"
first_winning_board_score = calculate_first_winning_board_score_from_file(
input_path
)
last_winning_board_score = calculate_last_winning_board_score_from_file(input_path)
print(first_winning_board_score)
print(last_winning_board_score)
``````

## Quick recap

This one is pretty verbose.

I really liked how Python's builtin `set()` data structure was useful for this kind problem - you could simply use set arithmetic to determine if particular row/column is a winning one (must be a subset of drawn numbers so far).

I'm not satisfied with part 2 solution - feels a bit convoluted, maybe I'll try refactoring it some day.

That's it for day 4 of Advent of Code 2021 :-).

Take care,
Kuba