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 std::array::from_fn;
16
17use crate::util::parse::*;
18
19const BOARD_SIZE: usize = 25;
20const ROWS_AND_COLS: [(usize, usize); 10] =
21    [(0, 1), (5, 1), (10, 1), (15, 1), (20, 1), (0, 5), (1, 5), (2, 5), (3, 5), (4, 5)];
22
23pub struct Board {
24    turn: usize,
25    score: usize,
26}
27
28pub fn parse(input: &str) -> Vec<Board> {
29    let (prefix, suffix) = input.split_once("\n\n").unwrap();
30    let boards: Vec<_> = suffix.iter_unsigned().collect();
31
32    let mut number_to_turn = [0; 100];
33    let mut turn_to_number = [0; 100];
34
35    for (i, n) in prefix.iter_unsigned().enumerate() {
36        number_to_turn[n] = i;
37        turn_to_number[i] = n;
38    }
39
40    boards
41        .chunks_exact(BOARD_SIZE)
42        .map(|board| {
43            let turns: [usize; BOARD_SIZE] = from_fn(|i| number_to_turn[board[i]]);
44            let max = |&(skip, step)| *turns.iter().skip(skip).step_by(step).take(5).max().unwrap();
45
46            let winning_turn = ROWS_AND_COLS.iter().map(max).min().unwrap();
47            let unmarked: usize = board.iter().filter(|&&n| number_to_turn[n] > winning_turn).sum();
48            let just_called = turn_to_number[winning_turn];
49
50            Board { turn: winning_turn, score: unmarked * just_called }
51        })
52        .collect()
53}
54
55pub fn part1(input: &[Board]) -> usize {
56    input.iter().min_by_key(|b| b.turn).unwrap().score
57}
58
59pub fn part2(input: &[Board]) -> usize {
60    input.iter().max_by_key(|b| b.turn).unwrap().score
61}
aoc/year2021/day04.rs

aoc/year2021/
day04.rs
