Juha-Matti Santala
Community Builder. Dreamer. Adventurer.

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:


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

14 21 17 24 4
10 16 15 9 19
18 8 23 26 20
22 11 13 6 5
2 0 12 3 7

The 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

def read_bingo_input():
        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:

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:

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(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	61

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

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:
    return winning_boards[-1]

result = play_bingo_last(numbers, bingo_boards)

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

  1. I'm not great at math, I could never come up with those solutions.
  2. 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!