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
- using
- 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 alist 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
andcheck_win
andget_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.
- I started with writing down the
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 thenum
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()))
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Furthest Building You Can Reach | LeetCode | Solution Explained
January 20, 2022
Burst Balloons | LeetCode | Solution Explained
January 1, 2022