Advent of Code 2023: Day 02

Code for solutions available on GitHub.

This day will make use of the nom crate to parse the input into some data structures.

Cube Conundrum

Today, the input is a list of games, where a game consists of an ID, and a set of rounds. Each rounds consists of pulling a number of red, green, and blue cubes out of a bag. Each line of the input has the following shape:

Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green

The first task is to determine which games of the input are possible if the bag only contained 12 red, 13 green, and 14 blue cubes. The answer is given by the sum of the possible games’ IDs.

To start, I just sketched out the types I would need to solve this problem.

#[derive(Debug, Default)]
struct Game {
    id: u32,
    sets: Vec<CubeSet>
}

#[derive(Debug, Default)]
struct CubeSet {
    red: u32,
    green: u32,
    blue: u32,
}

Parsing the input into a bunch of Games is the first step. It’s not all that interesting, just using the parsers and combinators from nom. Instead of chronicling all that, I’ll just say that the parsing code is here with the starting point being the parse_game function and move on to the actual problem solving.

After parsing each line into a Game, we need to somehow check that all rounds of the game are possible, given the maximum number of red, green, and blue cubes before summing up all IDs.

input
    .lines()
    .map(parse_game)
    .map(Result::unwrap) // AoC input is guaranteed to be valid
    .map(|game| {
        // if game is valid, return game ID,
        // else return 0
    })
    .sum()

This could be done by simply checking the number of red, green, and blue cubes in each round but where is the fun in that? Instead, I elected to implement PartialOrd for CubeSet. A CubeSet is “less” than another if all its counts are less than or equal to the other one. It’s equal if all counts are equal, and greater if any of its counts are greater.

impl PartialOrd for CubeSet {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        let orderings = [
            self.red.cmp(&other.red),
            self.green.cmp(&other.green),
            self.blue.cmp(&other.blue),
        ];
        Some(
            if orderings.iter().all(|o| o != &std::cmp::Ordering::Greater) {
                std::cmp::Ordering::Less
            } else if orderings.iter().all(|o| o == &std::cmp::Ordering::Equal) {
                std::cmp::Ordering::Equal
            } else {
                std::cmp::Ordering::Greater
            },
        )
    }
}

Why would I do this? Isn’t it just moving the code elsewhere? Well, yes! But look how pretty the solution becomes now:

let max_set = CubeSet {
    red: 12,
    green: 13,
    blue: 14,
};

input
    .lines()
    .map(parse_game)
    .map(Result::unwrap)
    .map(|game| {
        if game.sets.iter().all(|set| set <= max_set) {
            game.id
        } else {
            0
        }
    })
    .sum()

Short, sweet, and readable. Just the way I like it. ¹

Part 2

For part 2, the task is instead to determine the minimum number of cubes of each color needed for each game to be possible. Then for each game, multiply those numbers together (called the power of the set), then sum up these products for every game.

This is easily done by considering the pairwise solution. For two CubeSets, for the game to be possible, the total number of cubes in each set must be at least as large as largest of the two. A simple maximize method can be defined on CubeSet, along with a power method:

impl CubeSet {
    fn maximize(&self, other: &Self) -> Self {
        CubeSet {
            red: self.red.max(other.red),
            green: self.green.max(other.green),
            blue: self.blue.max(other.blue),
        }
    }

    fn power(&self) -> u32 {
        self.red * self.green * self.blue
    }
}

Now we can start with the template from part 1 to map things over each game:

input
    .lines()
    .map(parse_game)
    .map(Result::unwrap)
    .map(|game| {
        // Get minimum set to make game possible
        // Return power of minimum set
    })
    .sum()

Now the new methods can be utilized together with one of my favorite iterator concepts: fold!

input
    .lines()
    .map(parse_game)
    .map(Result::unwrap)
    .map(|game| {
        game.sets
            .into_iter()
            .fold(CubeSet::default(), |acc, set| {
                acc.maximize(&set)
            })
            .power()
    })
    .sum()

Short, sweet, readable once again. :)