Advent of Code - 2021
This is a solution to Day 4 of Advent of Code 2021.
Day 4 - Giant Squid
You're already almost 1.5km (almost a mile) below the surface of the ocean, already so deep that you can't see any sunlight. What you can see, however, is a giant squid that has attached itself to the outside of your submarine.
Maybe it wants to play bingo?
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.)
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). 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,122 13 17 11 0
8 2 23 4 24
21 9 14 16 7
6 10 3 18 5
1 12 20 15 193 15 0 2 22
9 18 13 17 5
19 8 7 25 23
20 11 10 24 4
14 21 16 12 614 21 17 24 4
10 16 15 9 19
18 8 23 26 20
22 11 13 6 5
2 0 12 3 7The 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.
Custom function in utils.py
Since today's input didn't come in "one line == one input", I had to create a custom input reader in utils.py.
In the input, different sections (bingo numbers and individual bingo boards) are separated by empty lines, so I first split by double linebreak \n\n and then convert numbers into a list of integers.
I could parse the bingo board numbers into integers here as well but it would cause a lot of double processing so decided to pass that to the BingoBoard class's helper function (see class later).
from utils import read_bingo_input
import inspect
print(inspect.getsource(read_bingo_input))
def read_bingo_input():
try:
with open(os.path.join('..', 'inputs', 'day_4.txt')) as input_file:
data = input_file.read().split('\n\n')
numbers, boards = data[0], data[1:]
numbers = [int(n) for n in numbers.split(',')]
return numbers, boards
except FileNotFoundError as e:
print(e)
BingoBoard class
Let's build a class!
Every bingo board should know their own state: numbers in the board, what's marked, the internal score and what is the state of the game.
from_text is a helper constructor that allows us to read Advent of Code's input into BingoBoards.
Main logic happens inside mark function:
- We check if called number exists in this board
- If it does, we mark that slot as
None - If it does, we also reduce that from the score of the board
- And we check if marking that resulted in a winning board or not
For scoring the board, we keep track of two values: last_marked which is the latest number called by the bingo and score which is the sum of all unmarked numbers on the board.
Custom __repr__ also gives us a clean and readable output when we print a board. Nice both for presentation and for debugging!
class BingoBoard:
def __init__(self, board):
self.board = board or []
self.last_marked = None
self.finished = False
self.score = 0
for row in board:
for number in row:
self.score += number
def from_text(text):
text = text.strip()
rows = text.split('\n')
board = BingoBoard([[int(v) for v in row.split()] for row in rows])
return board
def mark(self, number):
marked = False
self.last_marked = number
for row in self.board:
if number in row:
row[row.index(number)] = None
marked = True
self.score -= number
return self.check_win()
return False
def check_win(self):
# check rows
for row in self.board:
unfinished = any([value is not None for value in row])
if not unfinished:
self.finished = True
return True
# check columns
for index in range(5):
col = [self.board[i][index] for i, _ in enumerate(self.board)]
unfinished = any([value is not None for value in col])
if not unfinished:
self.finished = True
return True
return False
def final_score(self):
return self.score * self.last_marked
def __repr__(self):
return '\n'.join('\t'.join(str(value if value is not None else "X") for value in row) for row in self.board)
Part 1
from utils import read_bingo_input
numbers, boards = read_bingo_input()
bingo_boards = []
for board in boards:
bingo_boards.append(BingoBoard.from_text(board))
def play_bingo(numbers, bingo_boards):
for number in numbers:
for board in bingo_boards:
finished = board.mark(number)
if finished:
return board
result = play_bingo(numbers, bingo_boards)
print(result)
print(f'Solution: {result.final_score()}')
assert result.final_score() == 11774 # Just here to help me notice if refactoring breaks stuff
60 X 37 X 73
80 X X 30 64
77 X X 1 45
79 X 11 12 51
25 X 68 67 61Solution: 11774
Part 2
On the other hand, it might be wise to try a different strategy: let the giant squid win.
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.
In the above example, the second board is the last to win, which happens after 13 is eventually called and its middle column is completely marked. If you were to keep playing until this point, the second board would have a sum of unmarked numbers equal to 148 for a final score of 148 * 13 = 1924.
Yay, a really straight-forward second part! All I need to do now is keep track of in which order the boards have won, pick the last one and let the squid win 🦑.
# Re-reading the inputs to avoid previous round affecting the results
numbers, boards = read_bingo_input()
bingo_boards = []
for board in boards:
bingo_boards.append(BingoBoard.from_text(board))
def play_bingo_last(numbers, boards):
winning_boards = []
for number in numbers:
for board in boards:
if not board.finished:
finished = board.mark(number)
if finished:
winning_boards.append(board)
return winning_boards[-1]
result = play_bingo_last(numbers, bingo_boards)
print(result)
print(f'Solution: {result.final_score()}')
assert result.final_score() == 4495 # Just here to help me notice if refactoring breaks stuff
X X X X X
X X X X 4
X X X X 0
X 54 X 82 X
5 X X X X
Solution: 4495
Wrap up
I really liked today's challenge. Parsing the board inputs and creating a structure for it was fun.
Reading through some other people's solutions for yesterday and today, I've noticed that people are able to use maths to really simplify the code. I've concluded two things from that:
- I'm not great at math, I could never come up with those solutions.
- It doesn't really matter, I can still write code that solves the puzzles.
You don't need to be a mathematician to be a developer!