Advent of Code 2021 | Day 4 | Solution Explained in Python3

I explain the solution for the Advent of Code 2021 Day 4 problem in Python3. Answer explained in detail.

Part 1: Logic

Here’s all you need to know to understand the solution better:

  • The first thing we did was to extract the list of numbers from the first line of the input:
    • using data[0].split(',') splits the first line by ,s
    • then we have a list of strings with us
    • using the map(int, list_of_strings) we can map each element in the list of strings to an integer
    • finally we have a list of numbers
  • Then we want to extract out the boards
    • I iterate over each line
    • if the line is of length == 1, meaning its a line with just the ‘\n’ character, we can store the board we saw up till now
    • else, we append the line, using the map logic as we already saw
    • NOTE: the board is laid out as a list of list of list of integer && bool
    • Where we have board[i][j] pointing to one cell and board[i][j][0] pointing to the actual number and the board[i][j][1] telling whether the number has been marked or not
  • Pro tip: Its always a good idea to write down the names of the functions you are going to use, before actually writing their function bodies.
    • I started with writing down the mark_in_board and check_win and get_score function names where I needed them
    • then created all of them one by one
    • check_win is the most interesting one, because I used list(zip(*board)) to get its transpose. We basically zip the iterators and then convert the zipped tuples to a list.

Part 1: Code

def get_input():
    data = []
    with open("input.txt") as f:
        data = f.readlines()
    return data


def mark_in_board(board, num):
    m, n = len(board), len(board[0])
    for i in range(m):
        for j in range(n):
            if board[i][j][0] == num:
                board[i][j][1] = True


def check_win(board):
    m, n = len(board), len(board[0])
    for i in range(m):
        if sum(item[1] for item in board[i]) == n:
            return True

    transpose_board = list(zip(*board))
    for j in range(n):
        if sum(item[1] for item in transpose_board[j]) == m:
            return True

    return False


def get_score(board):
    m, n = len(board), len(board[0])
    ans = 0
    for i in range(m):
        for j in range(n):
            if not board[i][j][1]:  # we want unmarked
                ans += board[i][j][0]

    return ans


def solve(data):
    nums = list(map(int, data[0].split(",")))
    boards = []
    board = None
    for line in data[1:]:
        if len(line) == 1:
            boards.append(board)
            board = []
        else:
            line_nums = list(map(int, line.split()))
            board.append([[line_num, False] for line_num in line_nums])

    boards = boards[1:]  # first one is a None board

    for num in nums:
        for board in boards:
            mark_in_board(board, num)
            if check_win(board):
                return get_score(board) * num

    return 0


print(solve(get_input()))

Part 2: Logic

  • We keep a track of the board statuses – the scores of the boards, according to the get_score and the num values – to get the final score
  • We also want to know which board is the last one modified – so we have a last_index

Part 2: Code

def get_input():
    data = []
    with open("input.txt") as f:
        data = f.readlines()
    return data


def mark_in_board(board, num):
    m, n = len(board), len(board[0])
    for i in range(m):
        for j in range(n):
            if board[i][j][0] == num:
                board[i][j][1] = True


def check_win(board):
    m, n = len(board), len(board[0])
    for i in range(m):
        if sum(item[1] for item in board[i]) == n:
            return True

    transpose_board = list(zip(*board))
    for j in range(n):
        if sum(item[1] for item in transpose_board[j]) == m:
            return True

    return False


def get_score(board):
    m, n = len(board), len(board[0])
    ans = 0
    for i in range(m):
        for j in range(n):
            if not board[i][j][1]:  # we want unmarked
                ans += board[i][j][0]

    return ans


def solve(data):
    nums = list(map(int, data[0].split(",")))
    boards = []
    board = None
    for line in data[1:]:
        if len(line) == 1:
            boards.append(board)
            board = []
        else:
            line_nums = list(map(int, line.split()))
            board.append([[line_num, False] for line_num in line_nums])

    boards = boards[1:]  # first one is a None board

    board_won_status = [None] * len(boards)
    last_index = -1
    for num in nums:
        for i, board in enumerate(boards):
            if not board_won_status[i]:  # board hasn't won yet
                mark_in_board(board, num)
                if check_win(board):
                    board_won_status[i] = get_score(board) * num  # save score
                last_index = i  # save index

    return board_won_status[last_index]


print(solve(get_input()))

Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.