Confused? Check out my Day 1 post to read all about Advent of Code here: https://galaxyinferno.com/how-to-solve-advent-of-code-2021-day-1/
GitHub
https://github.com/GalaxyInfernoCodes/Advent_Of_Code_2021
This is where I will upload all of my Python Notebooks where I solve the challenges. I’m solving them on Google Colab, because that allows me to just quickly throw something together in the Browser on any machine I’m on. Since I’m lazy, that’s my go-to for quick and small projects. Otherwise I code in VSCode 🙂
Day 4 Puzzle
Here is the challenge, if you want to read the full puzzle: https://adventofcode.com/2021/day/4
On Day 4 we are playing Bingo with a Squid 🙂 The squid is kind of irrelevant, except we assume it has many arms and can play multiple bingo boards at once.
The input looks 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 6At first we get a line of numbers that will be called during the game. And below that – separated by an empty line each are several 5×5 bingo boards with entries separated by one or more whitespaces.
Part 1
At first, we are concerned with winning. So we want to find the board that will win first, so no matter which boards the squid chooses, we will win. After determining the board, we also need to compute a score which is the sum of all unmarked entries on the board after winning by completing a vertical or horizontal row.
Before we can do any of that, we have to read in the data from the text file though.
with open(file_name, 'r') as f:
lines = [entry.strip() for entry in f.readlines()]
called_numbers = [int(entry) for entry in lines[0].split(',')]
print(called_numbers)
number_of_boards = (len(lines)-1)//6
print(number_of_boards)
boards = dict()
for j in range(number_of_boards):
boards[j] = Board()
boards[j].read_from_lines(lines[(2 + j*6):(2+5+(j+1)*6)])
Now that is a bunch of code all at once and I haven’t even defined the Board class yet 😮
At first we just read in the lines from a text file as on all previous days. The first line is also very easy to convert into a list of integers that will be the numbers called during the bingo game.
Then we have to split the lines, so we can read each board separately. For that we calculate the number of boards by dividing the number of lines (minus 1, because we already dealt with the first line) by 6 – because each board has 5 lines and an empty line above it. For this, it is important that in your text file, there are no empty lines after the last bingo board.
So we can loop through all the boards and with this
(2 + j*6):(2+5+(j+1)*6)we can determine the first and last row we need to look at for each board. We have an offset of 2, because we ignore the first two lines (one are the numbers, one is empty) and then we always add 6. The end is then 5 lines down (in python the upper end of an interval is never included).
Right now let’s look at the Board class. At first I thought a class was a bit much, but after considering that we need to save the entries and also keep track of which numbers are already marked/crossed off on the board, a class seemed easier. So we have two numpy arrays, each 5×5.
class Board:
def __init__(self):
self.board = np.zeros((5,5), dtype=int)
self.marked = np.zeros((5,5))
def read_from_lines(self, lines):
for i in range(5):
line_entries = [int(entry) for entry in lines[i].split(' ') if entry != '']
self.board[i] = line_entries
def check_called_number(self, called_number):
if called_number in self.board:
indices = np.where(self.board == called_number)
self.marked[indices[0], indices[1]] = 1
def check_win(self):
return self.marked.all(axis=0).any() or self.marked.all(axis=1).any()
def calculate_score(self, called_number):
return (self.board * (self.marked==0)).sum() * called_numberAt first we only use the read_from_lines method in my above code, which splits the line at a whitespace and converts each entry to an integer. We also ignore empty entries that arise during this because the number-entries in the text can also be separated by multiple whitespaces.
The other two methods are used in the following function:
def find_first_winner(called_numbers, boards):
for called_number in called_numbers:
for j in range(len(boards)):
boards[j].check_called_number(called_number)
if boards[j].check_win():
print(f"Board {j+1} won!")
print(boards[j].marked)
return j, called_numberHere, we loop through all called numbers and for each number, we take each of the boards and check if the number is present on that board. If it is present we use numpy.where to find the position on the board and set the entry on the marked array to 1/True. Afterwards we check if the board has won, because once the first board has one, we need to stop marking numbers so we can calculate the score. If we would continue marking numbers, the score would be smaller since it is the sum of all unmarked numbers.
Checking for win: This is very easy if you use the .all(axis=0) method that numpy arrays come with. This can be used for arrays with True/False or equivalent values. Depending on the axis you provide, it tells you for each row/column if all entries in that row/column are True. It’s like a logical AND. We then also use the .any() method, which is like the logical OR: it tells us if that condition is true of any of the rows/columns which is enough for a board to win.
So we perform this function and and then calculate the score of the winner board, which we return from the function:
winner_index, called_number = find_first_winner(called_numbers, boards)
print('score', boards[winner_index].calculate_score(called_number))Part 2
Now, we want to let the squid win, which involved adjusting the find_first_winner function, so it’s now a find_last_winner function:
def find_last_winner(called_numbers, boards):
winners = []
winner_call = 0
for called_number in called_numbers:
for j in range(len(boards)):
if j not in winners:
boards[j].check_called_number(called_number)
if boards[j].check_win():
winners.append(j)
print(f"Board {j+1} won!")
winner_call = called_number
return winners[-1], winner_callThere are a few things to keep in mind here. Mostly concerning the calculation of the score.
First, we keep track of all boards that have already won by using a list and appending the winners index each time a board wins. Furthermore, to avoid marking any numbers on a board that has already won (which would alter the score) by checking if we already noted that board in the winners list.
To compute the score of the board, we need to multiple the sum of all unmarked entries with the last number that was marked on the board before it won, so we always keep track of the last number that made a board win. In the end we will have the value that is relevant for the last winner – which is all we need.
So this function gives us the board index of the last winner and the number we need to multiply with, so the total score can be found by calling:
winner_index, called_number = find_last_winner(called_numbers, boards)
print('score', boards[winner_index].calculate_score(called_number))The End
So this concludes Day 4. It was definitely a bit trickier than before and I am not 100% happy with how I saved and managed the boards, but it did the job *shrug*.