Day 4: Giant Squid

Day #4 problem description │ Problem input

The game is represented as a list of boards and a list of drawn numbers. Each board has:

A dictionary grid that maps undrawn numbers on the board to their Cartesian coordinates (a pair (row, col)) on the board. When a number is drawn, its Cartesian coordinates are used to update progress (below), and then the number is removed from the dictionary.

The only reason drawn numbers are removed from a board’s dictionary is that Advent of Code asks for the sum of the board’s undrawn numbers to compute the answer, so we need to keep track of which numbers on a given board haven’t been drawn yet. Otherwise, we’d have had no reason to mutate the dictionary at all.
progress, which stores for each row and column the count of numbers in that row/column have not yet been drawn. If one of those counts hit zero, then every number in that row/column has been drawn, and so the board has a "Bingo" (i.e., has won).

The row and column indices have the same meaning as the Cartesian coordinates in the dictionary described above: if number 25 is drawn, and 25’s position on a particular board is (2, 3), then progress.rows[2] and progress.cols[3] each get decremented.

Setup

Reading the input text into a game (numbers and boards) is in read_input_into_game, whose (not particularly interesting) implementation should serve as its docs. get_answer_from_final_game_state is just used to prove to Advent of Code that we actually got the solution.

use crate::Answer;
use num::{integer::div_mod_floor, Integer};
use std::{
	collections::{BTreeMap as Map, BTreeSet as Set},
	str::FromStr,
};

#[derive(Debug)]
struct BoardProgress {
	rows: Vec<usize>,
	cols: Vec<usize>,
	has_won: bool,
}

impl BoardProgress {
	fn new(n_rows: usize, n_cols: usize) -> Self {
		let rows = vec![n_cols; n_rows];
		let cols = vec![n_rows; n_cols];
		Self {
			rows,
			cols,
			has_won: false,
		}
	}

	fn handle_entry(&mut self, row: usize, col: usize) {
		if self.has_won {
			return;
		}

		self.rows[row] -= 1;
		self.cols[col] -= 1;

		if self.rows[row] == 0 || self.cols[col] == 0 {
			self.has_won = true;
		}
	}
}

#[derive(Debug)]
struct Board<T: Integer> {
	grid: Map<T, (usize, usize)>,
	progress: BoardProgress,
}

impl<T: Integer + std::iter::Sum + Copy> Board<T> {
	fn new(nums: &[T], n_cols: usize) -> Self {
		let n_rows = nums.len() / n_cols;
		assert_eq!(n_rows * n_cols, nums.len());

		let mut grid = Map::new();
		for (i, &x) in nums.iter().enumerate() {
			let (r, c) = div_mod_floor(i, n_cols);
			grid.insert(x, (r, c));
		}
		Self {
			grid,
			progress: BoardProgress::new(n_rows, n_cols),
		}
	}

	fn play_number(&mut self, n: T) {
		let (r, c) = match self.grid.remove(&n) {
			Some(coords) => coords,
			None => return,
		};
		self.progress.handle_entry(r, c);
	}

	fn has_won(&self) -> bool {
		self.progress.has_won
	}

	fn get_ans(&self, winning_num: T) -> T {
		let unmarked_sum = self.grid.keys().copied().sum::<T>();
		winning_num * unmarked_sum
	}
}

struct Game<T: Integer> {
	boards: Vec<Board<T>>,
	numbers: Vec<T>,
}

impl<T: Integer + std::iter::Sum + Copy + FromStr + std::fmt::Debug> Game<T> {
	fn from_str(s: &str) -> Option<Self> {
		let mut lines = s.lines().chain(std::iter::once(""));
		let nums = lines
			.next()?
			.split(',')
			.map(|s| s.parse::<T>().ok())
			.collect::<Option<Vec<_>>>()?;

		let mut boards = vec![];
		let mut this_board = vec![];

		let mut n_cols = None;

		for line in lines {
			if line.is_empty() {
				if !this_board.is_empty() {
					let board = Board::new(this_board.as_slice(), n_cols.unwrap());
					boards.push(board);
					this_board.clear();
				}
			} else {
				for num in line.split_whitespace().map(|s| s.parse::<T>().ok()) {
					let num = num?;
					this_board.push(num);
				}
				if matches!(n_cols, None) {
					n_cols = Some(this_board.len());
				}
			}
		}

		Some(Self {
			boards,
			numbers: nums,
		})
	}
}

fn ans_for_input(input: &str) -> Answer<i32, i32> {
	let [game1, game2] = [0; 2].map(|_| Game::from_str(input).unwrap());
	(4, (pt1(game1), pt2(game2))).into()
}

pub fn ans() -> Answer<i32, i32> {
	ans_for_input(include_str!("input.txt"))
}

Part 1

We simply draw numbers until a board has won, then get the answer.

fn pt1(mut game: Game<i32>) -> i32 {
	for &num in &game.numbers {
		for board in &mut game.boards {
			board.play_number(num);
			if board.has_won() {
				return board.get_ans(num);
			}
		}
	}
	unreachable!();
}

Part 2

This time, we keep track of all of the boards that haven’t won yet. When the last un-won boards wins, we use it to compute the answer.

fn pt2(mut game: Game<i32>) -> i32 {
	let mut ongoing_game_idxs = (0..game.boards.len()).collect::<Set<_>>();

	for &num in &game.numbers {
		for (board_idx, board) in game.boards.iter_mut().enumerate() {
			let already_won = !ongoing_game_idxs.contains(&board_idx);
			if already_won {
				continue;
			}

			board.play_number(num);
			if board.has_won() {
				if ongoing_game_idxs.len() == 1 {
					return board.get_ans(num);
				}

				ongoing_game_idxs.remove(&board_idx);
			}
		}
	}
	unreachable!();
}