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
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)
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').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)
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
. 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
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
[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
bingo_cards, where each bingo card is
list of rows, where each row is a
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
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
We then create a
set to store any cards that have won.
# 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.
(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 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.
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