aoc/year2021/
day04.rs

1//! # Giant Squid
2//!
3//! We use a trick to immediately calculate the winning turn and score for each board.
4//!
5//! First we create a bidirectional map between each number and turn that it's drawn. Since the
6//! numbers are at most 2 digits we can use a fixed size array instead of a `HashMap` for speed.
7//!
8//! Then for each column and row within a board, map each number to a turn and take the maximum
9//! value. This is the turn that the row or column will win. Then take the *minimum* of
10//! these maximum values. This is the turn that the entire board will win.
11//!
12//! Filtering the board numbers by turn and a reverse lookup from turn to number gives the
13//! score for each board. Sort each result by turn and the answers for part one and two are the
14//! first and last values respectively.
15use crate::util::parse::*;
16use std::array::from_fn;
17
18const BOARD_SIZE: usize = 25;
19const ROWS_AND_COLS: [(usize, usize); 10] =
20    [(0, 1), (5, 1), (10, 1), (15, 1), (20, 1), (0, 5), (1, 5), (2, 5), (3, 5), (4, 5)];
21
22pub struct Board {
23    turn: usize,
24    score: usize,
25}
26
27pub fn parse(input: &str) -> Vec<Board> {
28    let (prefix, suffix) = input.split_once("\n\n").unwrap();
29    let boards: Vec<_> = suffix.iter_unsigned().collect();
30
31    let mut number_to_turn = [0; 100];
32    let mut turn_to_number = [0; 100];
33
34    for (i, n) in prefix.iter_unsigned().enumerate() {
35        number_to_turn[n] = i;
36        turn_to_number[i] = n;
37    }
38
39    boards
40        .chunks_exact(BOARD_SIZE)
41        .map(|board| {
42            let turns: [usize; BOARD_SIZE] = from_fn(|i| number_to_turn[board[i]]);
43            let max = |&(skip, step)| *turns.iter().skip(skip).step_by(step).take(5).max().unwrap();
44
45            let winning_turn = ROWS_AND_COLS.iter().map(max).min().unwrap();
46            let unmarked: usize = board.iter().filter(|&&n| number_to_turn[n] > winning_turn).sum();
47            let just_called = turn_to_number[winning_turn];
48
49            Board { turn: winning_turn, score: unmarked * just_called }
50        })
51        .collect()
52}
53
54pub fn part1(input: &[Board]) -> usize {
55    input.iter().min_by_key(|b| b.turn).unwrap().score
56}
57
58pub fn part2(input: &[Board]) -> usize {
59    input.iter().max_by_key(|b| b.turn).unwrap().score
60}
aoc/year2021/day04.rs

aoc/year2021/
day04.rs
