Learning Python with Advent of Code Walkthroughs
Dazbo's Advent of Code solutions, written in Python
Advent of Code 2021 - Day 4
Useful Links
Concepts and Packages Demonstrated
Problem Intro
A giant squid has attached itself to the sub. We’re going to play bingo with it!
Our input is a single comma-delimited line of numbers to be drawn, followed by multiple 5x5 bingo boards. As we draw numbres, they are marked off on the boards. The input data looks something like this…
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
Setup
Nothing special here. But we are going to use NumPy again.
import logging
import os
import time
from collections import deque
import numpy as np
SCRIPT_DIR = os.path.dirname(__file__)
INPUT_FILE = "input/input.txt"
# INPUT_FILE = "input/sample_input.txt"
logging.basicConfig(format="%(asctime)s.%(msecs)03d:%(levelname)s:%(name)s:\t%(message)s",
datefmt='%H:%M:%S')
logger = logging.getLogger(__name__)
logger.setLevel(level=logging.INFO)
Part 1
Determine which board will win, in order to beat squiddie. The winning board is the first board where all numbers in any row or any column are marked off. We also need to know the score of the winning board, which we’re told is the product of all the unmarked numbers, and the number that was last called.
First, let’s process the the input data:
input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:
data = f.read()
draw_numbers, bingo_cards = process_data(data)
def process_data(data: str) -> tuple[deque, np.ndarray]:
""" Takes raw str data. Converts first line to a list of int. Converts remaining blocks into a 3D Numpy array. """
# get the first line
draw_numbers = deque(map(int, data.partition('\n')[0].split(",")))
# Get list of cards, where each card is a list of 5 rows,
# which each row being a list of 5 ints
# E.g. one card = [[66, 78, 7, 45, 92], [39, 38, 62, 81, 77], [...], [...], [...]]
bingo_cards = [[list(map(int, row.split())) for row in card.splitlines()]
for card in data.split('\n\n')[1:]]
return draw_numbers, np.array(bingo_cards)
We first read() the data into one big str. Then we use partition() to split the data into three chunks: the bit before the first carriage return, the carriage return itself, and the bit after the carriage return. The three parts are returned as a tuple. Right now, we’re only interested in the first line, hence [0]. We then use split(",") to split the line at each comma, thus returning a list of numbers, each represented as a str. Then we use map to covert all these numbers into int values. And finally, we convert the list of int to a deque of int. (We don’t really need a deque, since the input data is small. But deques are very efficient at just popping numbers of the end, which is what we want to when drawing numbers.) So that’s our draw numbers sorted.
Now we need to process the bingo cards. First we split('\n\n') to split our input data at each empty line. This gives us blocks of data around each empty line. We’re not interested in the first block, since we’ve already dealt with the draw numbers. So, we use slice using [1:] to return every block of data apart from the first. At this point, we have a block of data for each bingo card. For each card, we use splitlines() to covert the block into a list of rows. And for each row, we split the data into int values using map. So now we have a list of bingo_cards, where each bingo card is list of rows, where each row is a list of int.
Finally, we convert this 3D list into a 3D numpy array and return the array.
The list of numbers, and the numpy array are both returned from this function, as a tuple.
Now the clever bit happens…
# Create a boolean np array of the same shape as bingo_cards, all False
# E.g. with 100 bingo cards, the shape would be (100, 5, 5)
card_completion = np.full(bingo_cards.shape, False)
cards_winning = set() # store each card that has won so far (just store the position ints)
We create a new numpy array, with exactly the same dimensions as the original array, but fill it with False elements. I.e. now we have an array that is itself composed of 5x5 arrays, with each value of the 5x5 array being False.
We then create a set to store any cards that have won.
Next…
# draw numbers until all cards have won
while draw_numbers and len(cards_winning) < len(bingo_cards):
num_drawn = draw_numbers.popleft()
# find all locations on the card where we've matched THIS number
# create a new np (bool) array accordingly
where_true = (bingo_cards == num_drawn) # where_true has same shape as cards
card_completion |= where_true # update card completion array
# Now determine which cards have won at this point
# Iterate through our boolean versions of each bingo card
for i, card in enumerate(card_completion):
if i in cards_winning:
continue # this card has already won; skip it
cols_complete = np.all(card, axis=0) # array of AND(cols), e.g. [True, False, False, True, True]
rows_complete = np.all(card, axis=1) # array of AND(rows)
if any(cols_complete) or any(rows_complete): # We got one!!
cards_winning.add(i)
# We're only interested in the first and last card that win...
if len(cards_winning) == 1 or len(cards_winning) == len(bingo_cards):
part_num = 1 if len(cards_winning) == 1 else 2
logger.info("Part %d:", part_num)
logger.info("Last number drawn: %d", num_drawn)
# Find all nums in this card where the card completion state is False
card_unmarked_nums = bingo_cards[i][~card]
sum_unmarked_nums = sum(card_unmarked_nums)
logger.info("Sum of remaining: %d", sum(card_unmarked_nums))
logger.info("Product=%d\n", num_drawn*sum_unmarked_nums)
We draw numbers from the number deque, one at a time. We use popleft() to do this, which removes and returns the left-most (i.e. first) number that was put on the deque.
We use (bingo_cards == num_drawn) to check each value in the numpy array against the number just drawn. This returns a new array - where_true - with exactly the same shape (i.e. same dimensions) as the bingo_cards array. The values in the new array will be False wherever the number is not a match, but True wherever it was. Thus, the where_true array will only be True whever that number was drawn and wherever that number is present in the bingo boards.
We then use | to perform an or between the where_true array, and the card_completion array. If either array is True in a given position, the new value will be True in that position. Otherwise, the value will be False. Thus, this allows us to track all the number positions that have been marked so far.
We then use np.all(card, axis=0) and np.all(card, axis=1) to establish which columns and which rows have all positions True, respectively. Finaly, we use any(cols_complete) or any(rows_complete) to evaluate if any of the columns or any of the rows are complete. The first time this evaluation is True we’ve found our winning board.
We then index our bingo cards with complement of the array of marked numbers. I.e the numbers that have NOT yet been marked off. This gives us all the unmarked numbers. We can then use sum to add up all the unmarked numbers, as required.
Part 2
Part 1 was solved by returning the first card that wins.
But it’s time for a new strategy: let the squiddie win! We do that by determining which is the last card that will win. We can easily do that by counting the number of cards in the cards_winning set, and establishing if this is equal to the total number of bingo cards. If they do match, then the last card must have just won.
Output:
20:28:07.769:INFO:__main__: Part 1:
20:28:07.770:INFO:__main__: Last number drawn: 54
20:28:07.771:INFO:__main__: Sum of remaining: 639
20:28:07.772:INFO:__main__: Product=34506
20:28:07.836:INFO:__main__: Part 2:
20:28:07.836:INFO:__main__: Last number drawn: 42
20:28:07.837:INFO:__main__: Sum of remaining: 183
20:28:07.837:INFO:__main__: Product=7686
Onwards!