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:
data = f.readlines()
drawn_numbers = [int(x) for x in data[0].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