Advent of Code 2023: Day 04

Code for solutions available on GitHub.

Scratchcards

Time to play the lottery! This day, the input has the following shape:

Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53

Every line represents a scratchcard with an ID, a list of winning numbers, and the list of numbers the card has. A card has a score, calculated from the amount of numbers that match the winning numbers. One match is worth one point, and each additional match doubles the score. So essentially the score is two to the power of the number of matches minus one, if there is at least one match.

As always, let’s get started with a struct, defining a Card:

struct Card {
    id: i32,
    winning_numbers: Vec<i32>,
    numbers: Vec<i32>,
}

And a couple methods to calculate the score:

impl Card {
    fn score(self) -> u32 {
        if self.count_winning_numbers() == 0 {
            0
        } else {
            2_u32.pow(self.count_winning_numbers() - 1)
        }
    }

    fn count_winning_numbers(self) -> u32 {
        self.winning_numbers
            .iter()
            .filter(|n| self.winning_numbers.contains(n))
            .count() as u32
    }
}

And now it’s parsing time again. Blah blah blah, parser combinators, and the code is here. This time I elected to implement the parsing by implementing TryFrom<&'a str> for Card. Why? Because it makes the solution look like this:

input
    .lines()
    .map(Card::try_from)
    .map(Result::unwrap)
    .map(Card::score)
    .sum()

And that’s it! Pretty satisfying. Have I said that I love iterators?

Part 2

Turns out that you don’t win points as described in part 1. What actually happens if you have matching numbers is that you get a copy of the n following cards, where n is the number of matching numbers. Each of those cards have the same ID as their original, and are played at the same time as the original when iterating. The solution to the problem is the count of how many total cards were generated by this process plus the original cards given in the input. How many cards do you end up with?

Since we need to keep track of a number for every card ID, I elected to use a hashmap to store the counts. But I used the IntMap type from the nohash-hasher crate instead of the standard library’s HashMap type. I did this simply because we’re mapping numbers to numbers, and there is no real need to do any hashing. I just wanted a simple mapping, and by not using hashing, we regain some performance.

So basically, for each card in the input, we get how many instances are already in the map (or 1 if it’s not in the map), and add that count to the following n cards in the map. Again, n is the number of winning numbers.

let mut card_map = IntMap::<u32, u32>::default();
input
    .lines()
    .map(Card::try_from)
    .map(Result::unwrap)
    .for_each(|card| {
        let instances = *card_map.entry(card.id).or_insert(1);
        let start = card.id + 1;
        let end = start + card.count_winning_numbers();
        for i in start..end {
            card_map
                .entry(i)
                .and_modify(|v| *v += instances)
                .or_insert(1 + instances);
        }
    });
card_map.into_values().sum::<u32>()

And that’s the whole thing!