Giant Squid - Advent of Code 2021 Day 4

 

There were no Transformers to be found here today

StoneHenge

Day 4 of the Advent of Code problem is about facilitating an optimal solution via an optimal data structure. The problem gives us a list of 100 Bingo Boards along with the set of called numbers. We are asked to figure out which board will win first and last

We only need to scan the row and column containing the called number, in order to figure out if the board has won. Hence we need a data structure that will quickly give us the position of the cell containing the number. 

In this situation, a HashMap makes sense. This lookup table will quickly give us the x,y position of the number on the Bingo Board. We also need an easy way to figure out if the cell has already been marked. Since we already have a way to quickly lookup values in a cell, we can use a set containing the x,y positions of marked numbers.

The following code describe the construction of the data structures above. The generateLookup function below creates the tuple which contains two values -

• The lookup table table that contains the number as the key and the position as the value
• The set of numbers that have already been marked on this board.

# dict number to x,y
def generatelookup(board):
    d = {}
    for i in range(0,len(board)):
        for j,val in enumerate(board[i]):
            d[val] = (i,j)
    return d

boards = []

board = [] 
for i in lines[2:]:
    if len(i) == 0:
        boards.append((generatelookup(board),set()))
        board = []
        continue
    board.append(i.split())
boards.append((generatelookup(board),set()))

In the following processAndCheckIfWon function, for each called number -

• We first check if this number is contained in the board. 
• If the number exists we first mark it
• Then proceed to see if there is a win in either the row or the column. 

If there is a win, we return a tuple containing -

• The win Boolean, and,
• The sum of numbers that haven't been marked

def processAndCheckIfWon(board,calledNumber):

    lookup,marked = board

    if calledNumber in lookup:

        x,y = lookup[calledNumber]
        marked.add((x,y))

        columnWin = len([ 1 for posY in range(0,5) if (x,posY) in marked ]) == 5
        rowWin = len([ 1 for posX in range(0,5) if (posX,y) in marked ]) == 5

        if columnWin or rowWin:
            return (True,sum([ int(i) for i in lookup if lookup[i] not in marked]))

    return (False,None)

Finally, in the full source code , I proceed to iterate over the called numbers and call the processAndCheckWin function above. 

Part A requires the data from the first win, while Part B requires the data from the last win. We do need to track separately which boards have won, so that we eliminate them from consideration.