aoc/year2023/
day04.rs

1//! # Scratchcards
2//!
3//! Part two is a dynamic programming problem. Starting with 1 copy of each card we add the extra
4//! number of copies to the number of following cards equal to the number of winning numbers.
5use crate::util::parse::*;
6
7pub fn parse(input: &str) -> Vec<usize> {
8    input
9        .lines()
10        .map(|line| {
11            // Numbers are at most 99 so we can use a fixed size array instead of a HashSet.
12            let mut found = [false; 100];
13            let (win, have) = line.split_once('|').unwrap();
14            win.iter_unsigned::<usize>().skip(1).for_each(|i| found[i] = true);
15            have.iter_unsigned::<usize>().filter(|&i| found[i]).count()
16        })
17        .collect()
18}
19
20pub fn part1(input: &[usize]) -> u32 {
21    input.iter().map(|&n| (1 << n) >> 1).sum()
22}
23
24pub fn part2(input: &[usize]) -> u32 {
25    // Start with a single copy of each card.
26    let mut copies = vec![1; input.len()];
27
28    for (i, &n) in input.iter().enumerate() {
29        (1..=n).for_each(|j| copies[i + j] += copies[i]);
30    }
31
32    copies.iter().sum()
33}
aoc/year2023/day04.rs

aoc/year2023/
day04.rs
