1 files changed, 110 insertions, 0 deletions
diff --git a/src/day_04.rs b/src/day_04.rs
new file mode 100644
index 0000000..77559e2
--- /dev/null
+++ b/src/day_04.rs
@@ -0,0 +1,110 @@
+use crate::{Problem, Solution};
+
+pub struct Day04;
+
+impl Problem for Day04 {
+    const DAY: u8 = 4;
+
+    const INPUT: &'static str = include_str!("../input/day_04.txt");
+}
+
+impl Solution for Day04 {
+    type Answer1 = usize;
+
+    type Answer2 = usize;
+
+    fn part_1(input: &str) -> anyhow::Result<Self::Answer1> {
+        let scores = input
+            .trim()
+            .split('\n')
+            .map(parse_score)
+            .collect::<Result<Vec<_>, _>>()?;
+
+        Ok(scores
+            .into_iter()
+            .filter(|n| n > &0)
+            .map(|n| 2usize.pow(n as u32 - 1))
+            .sum())
+    }
+
+    fn part_2(input: &str) -> anyhow::Result<Self::Answer2> {
+        let scores = input
+            .trim()
+            .split('\n')
+            .map(parse_score)
+            .collect::<Result<Vec<_>, _>>()?;
+
+        let cards = &mut vec![0usize; scores.len()];
+
+        for card in 0..scores.len() {
+            add_copy(cards, &scores, card)
+        }
+
+        Ok(cards.iter().sum())
+    }
+}
+
+fn add_copy(cards: &mut Vec<usize>, scores: &[usize], card: usize) {
+    cards[card] += 1;
+
+    for card in card + 1..cards.len().min(card + scores[card] + 1) {
+        add_copy(cards, scores, card);
+    }
+}
+
+fn parse_score(s: &str) -> anyhow::Result<usize> {
+    let (winning, numbers) = s
+        .trim()
+        .split_once(':')
+        .ok_or(anyhow::format_err!("Invalid card format: {s}"))?
+        .1
+        .trim()
+        .split_once('|')
+        .ok_or(anyhow::format_err!("Invalid card format: {s}"))?;
+
+    let winning_set = winning
+        .split_whitespace()
+        .map(std::str::FromStr::from_str)
+        .collect::<Result<Vec<usize>, _>>()?;
+
+    Ok(numbers
+        .split_whitespace()
+        .map(std::str::FromStr::from_str)
+        .collect::<Result<Vec<usize>, _>>()?
+        .into_iter()
+        .filter(|n| winning_set.contains(n))
+        .count())
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_part_1() -> anyhow::Result<()> {
+        const INPUT: &str = indoc::indoc! {"
+            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
+        "};
+
+        Ok(assert_eq!(13, Day04::part_1(INPUT)?))
+    }
+
+    #[test]
+    fn test_part_2() -> anyhow::Result<()> {
+        const INPUT: &str = indoc::indoc! {"
+            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
+        "};
+
+        Ok(assert_eq!(30, Day04::part_2(INPUT)?))
+    }
+}