127 lines
3.4 KiB
Rust
127 lines
3.4 KiB
Rust
use std::{collections::HashMap, str::FromStr};
|
|
|
|
use regex::Regex;
|
|
|
|
pub fn run() {
|
|
let input = include_str!("../input/day4.txt");
|
|
// let input = r#"Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53
|
|
// Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
|
|
// Card 3: 1 21 53 59 44 | 69 82 63 72 16 21 14 1
|
|
// Card 4: 41 92 73 84 69 | 59 84 76 51 58 5 54 83
|
|
// Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
|
|
// Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11"#;
|
|
|
|
let cards = input
|
|
.lines()
|
|
.filter(|s| !s.is_empty())
|
|
.map(|s| Card::parse(s.trim()))
|
|
.collect::<Vec<_>>();
|
|
let total_points = cards.iter().map(|c| c.points()).sum::<u32>();
|
|
dbg!(total_points);
|
|
|
|
let mut counts = cards.iter().map(|_| 1u32).collect::<Vec<_>>();
|
|
let mut to_process = cards.iter().map(|_| 1u32).collect::<Vec<_>>();
|
|
let total_cards = run_part2(&cards, &mut counts, &mut to_process);
|
|
dbg!(total_cards);
|
|
}
|
|
|
|
fn run_part2(cards: &[Card], counts: &mut [u32], to_process: &mut [u32]) -> u32 {
|
|
let orig_total = counts.iter().sum::<u32>();
|
|
|
|
for c in cards {
|
|
let card_index = c.id as usize - 1;
|
|
let card_count = to_process[card_index];
|
|
to_process[card_index] = 0;
|
|
let winning_numbers = c.winning_numbers();
|
|
for i in 1..(winning_numbers + 1) {
|
|
let duped_index = card_index + i;
|
|
if duped_index >= cards.len() {
|
|
break;
|
|
}
|
|
// println!("adding {} to card {}", card_count, duped_index + 1);
|
|
counts[duped_index] += card_count;
|
|
to_process[duped_index] += card_count;
|
|
}
|
|
}
|
|
|
|
// dbg!(counts);
|
|
// return 0;
|
|
|
|
if counts.iter().sum::<u32>() == orig_total {
|
|
return orig_total;
|
|
} else {
|
|
return run_part2(cards, counts, to_process);
|
|
}
|
|
}
|
|
|
|
#[derive(Debug, Clone, PartialEq)]
|
|
struct Card {
|
|
id: u32,
|
|
win: Vec<u32>,
|
|
have: Vec<u32>,
|
|
}
|
|
|
|
impl Card {
|
|
fn parse(value: &str) -> Self {
|
|
let (card, rest) = value.split_once(":").unwrap();
|
|
let id: u32 = card.split(" ").last().unwrap().parse().unwrap();
|
|
let (win, have) = rest.split_once("|").unwrap();
|
|
let mut win_vec = vec![];
|
|
let mut have_vec = vec![];
|
|
for s in win.split(" ") {
|
|
if s.is_empty() {
|
|
continue;
|
|
}
|
|
win_vec.push(s.parse().unwrap());
|
|
}
|
|
for s in have.split(" ") {
|
|
if s.is_empty() {
|
|
continue;
|
|
}
|
|
have_vec.push(s.parse().unwrap());
|
|
}
|
|
Self {
|
|
id,
|
|
win: win_vec,
|
|
have: have_vec,
|
|
}
|
|
}
|
|
|
|
fn winning_numbers(&self) -> usize {
|
|
self.win.iter().filter(|w| self.have.contains(w)).count()
|
|
}
|
|
|
|
fn points(&self) -> u32 {
|
|
let count = self.winning_numbers();
|
|
if count == 0 {
|
|
0
|
|
} else {
|
|
2u32.pow(count as u32 - 1) as u32
|
|
}
|
|
}
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
#[test]
|
|
fn test_card_from_str() {
|
|
assert_eq!(
|
|
Card::parse("Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53"),
|
|
Card {
|
|
id: 1,
|
|
win: vec![41, 48, 83, 86, 17],
|
|
have: vec![83, 86, 6, 31, 17, 9, 48, 53],
|
|
}
|
|
)
|
|
}
|
|
|
|
#[test]
|
|
fn test_points() {
|
|
assert_eq!(
|
|
Card::parse("Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53").points(),
|
|
8
|
|
)
|
|
}
|
|
}
|