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 1 and part1 are the
14//! first and last values respectively.
15use crate::util::parse::*;
16use std::array::from_fn;
17
18pub struct Input {
19    turn: usize,
20    score: usize,
21}
22
23pub fn parse(input: &str) -> Vec<Input> {
24    let mut to_turn = [0; 100];
25    let mut from_turn = [0; 100];
26
27    let mut chunks = input.split("\n\n");
28
29    for (i, n) in chunks.next().unwrap().iter_unsigned().enumerate() {
30        to_turn[n] = i;
31        from_turn[i] = n;
32    }
33
34    let score = |chunk: &str| {
35        let mut iter = chunk.iter_unsigned();
36        let board: [usize; 25] = from_fn(|_| iter.next().unwrap());
37        let turns: [usize; 25] = from_fn(|i| to_turn[board[i]]);
38
39        let row_and_cols = [
40            turns[0..5].iter().max().unwrap(),
41            turns[5..10].iter().max().unwrap(),
42            turns[10..15].iter().max().unwrap(),
43            turns[15..20].iter().max().unwrap(),
44            turns[20..25].iter().max().unwrap(),
45            turns.iter().step_by(5).max().unwrap(),
46            turns.iter().skip(1).step_by(5).max().unwrap(),
47            turns.iter().skip(2).step_by(5).max().unwrap(),
48            turns.iter().skip(3).step_by(5).max().unwrap(),
49            turns.iter().skip(4).step_by(5).max().unwrap(),
50        ];
51        let winning_turn = **row_and_cols.iter().min().unwrap();
52        let unmarked: usize = board.iter().filter(|&&n| to_turn[n] > winning_turn).sum();
53        let just_called = from_turn[winning_turn];
54
55        Input { turn: winning_turn, score: unmarked * just_called }
56    };
57
58    let mut scores: Vec<_> = chunks.map(score).collect();
59    scores.sort_unstable_by_key(|s| s.turn);
60    scores
61}
62
63pub fn part1(input: &[Input]) -> usize {
64    input.first().unwrap().score
65}
66
67pub fn part2(input: &[Input]) -> usize {
68    input.last().unwrap().score
69}
aoc/year2021/day04.rs

aoc/year2021/
day04.rs
