Solution in Python for the day 4 puzzle of the 2021 edition of the Advent of Code annual programming challenge.
Bingo is played on a set of boards each consisting of a 5x5 grid of numbers. Numbers are chosen at random, and the chosen number is marked on all boards on which it appears. (Numbers may not appear on all boards.) If all numbers in any row or any column of a board are marked, that board wins. (Diagonals don't count.)
Only rows and columns must be considered. Following sorting this leaves ten sets of integers per each grid.
The submarine has a bingo subsystem to help passengers (currently, you and the giant squid) pass the time. It automatically generates a random order in which to draw numbers and a random set of boards (your puzzle input).
The input contents are a set consisting of a list of integers, followed by a number of 5x5 grids with each cell being an integer.
For example:
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
The input contents decoder is a little more involved than previously. It must return two elements of distinct type.
The score of the winning board can now be calculated. Start by finding the sum of all unmarked numbers on that board; in this case, the sum is 188. Then, multiply that sum by the number that was just called when the board won, 24, to get the final score, 188 * 24 = 4512.
The calculation of the sum requires keeping track of uncalled numbers on the grid. Each grid must keep the state of called numbers.
The first part of the contents is a list of integers separated by a comma. Building this list a matter of splitting a string then mapping each member in the appropriate type.
lines = iter(open(filename).readlines())
called_numbers:Iterator[int] = (int(token) for token in next(lines).split(','))The following part consists in iterating over the remaining lines building a list of bingo grids.
for line in lines:
short_line = len(line) < BINGO_GRID_SIZE
if short_line:
continue
row_numbers = {int(token) for token in line.strip().split()}
bingo_grid.append(row_numbers)
grid_complete = len(bingo_grid) == BINGO_GRID_SIZE
if grid_complete:
bingo_grids.append(bingo_grid)
bingo_grid = []The complete load_contents() method being:
def load_contents(filename: Path) -> tuple[Iterator, list]:
"""Load and convert contents from file
:param filename: input filename
:return: called numbers and bingo grids
"""
lines = iter(open(filename).readlines())
called_numbers:Iterator[int] = (
int(token) for token in next(lines).split(','))
bingo_grids = []
bingo_grid = []
for line in lines:
short_line = len(line) < BINGO_GRID_SIZE
if short_line:
continue
row_numbers = {int(token) for token in line.strip().split()}
bingo_grid.append(row_numbers)
grid_complete = len(bingo_grid) == BINGO_GRID_SIZE
if grid_complete:
bingo_grids.append(bingo_grid)
bingo_grid = []
log.debug(f'Reached end of {filename=}')
return called_numbers, bingo_gridsWorking from the end, the answer is the product of the called numbered by the sum of all the unmarked numbers.
def solve_part_one(contents: tuple[Iterator, list]) -> int:
"""Solve the first part of the challenge
:param diagnostic_report: called numbers and bingo grids
:return: expected challenge answer
"""
called_numbers, grids = contents
called_numbers = 0
unmarked_numbers = {0}
for called_number in called_numbers:
...
sum_unmarked_numbers = sum(unmarked_numbers)
answer = called_number * sum_unmarked_numbers
return answerThe inner loop must iterate over all grids. These grids must contain columns and rows which are updated by removing called numbers.
for called_number in called_numbers:
for i, grid in enumerate(processed_grids):
bingo = False
for j, row in enumerate(grid):
if called_number not in row:
continue
processed_grids[i][j] = row - {called_number}
if not processed_grids[i][j]:
processed_grids[i].pop(j)
bingo = True
if bingo:
unmarked_numbers = {n for row in processed_grids[i] for n in row}
break
else:
continue
break| Contents | Command | Answer | Time |
|---|---|---|---|
input.txt |
./day_4.py input.txt -p 1 |
35711 |
62.5 ms |
You aren't sure how many bingo boards a giant squid could play at once, so rather than waste time counting its arms, the safe thing to do is to figure out which board will win last and choose that one. That way, no matter which boards it picks, it will win for sure.
Goal is to find the last board to win.
Instead of stopping on the first bingo call, the goal is to keep continuing and keeping track of the last card that did bingo, and the corresponding called number.
def solve_part_two(contents: Iterator[tuple]) -> int:
"""Solve the first part of the challenge
:param diagnostic_report: binary numbers
:return: expected challenge answer
"""
"""Solve the first part of the challenge
:param contents: called numbers and bingo grids
:return: expected challenge answer
"""
called_numbers, grids = contents
processed_grids = []
for grid in grids:
rows = [set(row) for row in grid]
rows.extend((set(row) for row in list(zip(*grid))))
processed_grids.append(rows)
unmarked_numbers:set[int] = {0}
for called_number in called_numbers:
for i, grid in enumerate(processed_grids):
bingo = False
for j, row in enumerate(grid):
if called_number not in row:
continue
processed_grids[i][j] = row - {called_number}
if not processed_grids[i][j]:
processed_grids[i].pop(j)
bingo = True
break
if bingo:
unmarked_numbers = {n for row in processed_grids[i] for n in row}
processed_grids.pop(i)
last_called_number = called_number
sum_unmarked_numbers = sum(unmarked_numbers)
answer = last_called_number * sum_unmarked_numbers
return answerThis implementation turned out to be flawed. Two issues were present:
- Using a set for the rows is correct in the sense that no duplicates are expected, however this storage type does not preserve the order. As a result the rotatation of the array using
list(zip(*grid)))no longer produces correct results. - The iteration of the
processed_gridscontains an operation which affect its contents by deleting an entry after a bingo event.
The correct implementation ending up being:
def solve_part_two(contents: tuple[list, list]) -> int:
"""Solve the second part of the challenge
:param contents: called numbers and bingo grids
:return: expected challenge answer
"""
called_numbers, grids = contents
processed_grids = {}
for i, grid in enumerate(grids):
rows = [set(row) for row in grid]
rows.extend((set(row) for row in list(zip(*grid))))
processed_grids[i] = rows
unmarked_numbers:set[int] = {0}
for called_number in called_numbers:
for i, egrid in enumerate(grids):
if i not in processed_grids:
continue
bingo = False
for j, row in enumerate(processed_grids[i]):
if called_number not in row:
continue
processed_grids[i][j] = row - {called_number}
if not len(processed_grids[i][j]):
processed_grids[i].pop(j)
bingo = True
break
if bingo:
unmarked_numbers = {n for row in processed_grids[i] for n in row}
processed_grids.pop(i)
last_called_number = called_number
sum_unmarked_numbers = sum(unmarked_numbers)
answer = last_called_number * sum_unmarked_numbers
return answer| Contents | Command | Answer | Time |
|---|---|---|---|
input.txt |
./day_4.py input.txt -p 2 |
5586 |
101.0 ms |