# Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

# Advent of Code 2021 - Day 4

## 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:

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!!

# 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!