AoC Day 2: Cube Conundrum

Day 2 continues the Advent of Code story.

To be honest, I think the Advent of Code is nothing more than a way for Eric to flex his creative writing muscles in the most sadistic "Choose Your Own Adventure" book ever…

Anyway, today you find yourself playing a game with the elves, and one brings a bag filled with different colored cubes. He pulls out a handful of cubes and shows them to you, then puts them back in the bag. He does this several more times for each game you play, and the results are recorded for you in the input file. Here’s a sample:

Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green

Each game is numbered, as you can see. Each handful of cubes the elf shows you is separated by a semi-colon (;). For the first game, there are three different handfuls of cubes — for the last, only two.

Your task is to figure out which of these games are possible if the bag only contained:

12 red cubes,
13 green cubes, and
14 blue cubes

Add up the ID numbers of those games for the answer.

Approach

This one is an exercise in reading and parsing the input, as the algorithm itself appears relatively easy:

For each game played
- For each set of cubes pulled
  - If red_pulled>12 or green_pulled>13 or blue_pulled>14
    - Continue to the next game
- Add the game ID to the final answer
Return the final answer

Why two nested loops? I need one to get each separate game, and a second inner loop to get each set of cubes (there is a third in the actual code as well). Each game is only valid if all the sets in the game meet the criteria listed. Stated another way, if any set of cubes for a game don’t satisfy our requirements, the game is invalid and we can move to the next game.

This means I need to figure out two things:

How to read the data into the right internal format, and
How to get out of the inner cube loop and to the next game.

When I write "internal format", I mean how the data in the input file will be stored in my program. I can’t leave it as it is, a big string with punctuation and labels and such. I can’t even leave little pieces as strings — I need to get the numbers associated with each game stored as usize integers to add up. I also need the number of each type of cube in each set as usize integers so I can compare them to the constant values 12, 13, or 14. Getting the data from the input file into an internal format suitable for solving the problem is 90% of solving these problems.

Let’s work backward, though. To break out of the inner for loop, I use a boolean flag called possible, which is set to true at the start of each game. It gets set to false if any of the above conditions are not met. I check it at the bottom of each loop:

for game_set in game_sets{
    // Split off each kind of ball
    let balls = game_set.trim().split(',');

    // Check each kind of ball pulled
    for ball in balls{
        let ball_info = ball.trim().split(' ').collect::<Vec<&str>>();
        let count = ball_info[0].trim().parse::<usize>().unwrap();
        match ball_info[1]{
            "red" => possible = possible & (count <= RED),
            "green" => possible = possible & (count <= GREEN),
            "blue" => possible = possible & (count <= BLUE),
            &_ => panic!()
        }
        if !possible{
            break;
        }
    }
    if !possible{
        break;
    }
}

if possible{
    sum += game_num;
}

By checking the flag at the bottom of each loop, I can break out of the inner loops (one for the set, and one for each of the ball colors), and know when I get out whether the checks were successful.

The internal data format is handled as simply as possible, by reading everything with a bunch of .split() calls. I did it this way mainly because, at this point in my Rust learning, I didn’t know any other way to get the data I needed out of the larger string:

for line in lines{
    // Assume this game satisfies the requirements
    let mut possible = true;

    // Split off the game identifier from the rest of the game
    let game = line.split(':').collect::<Vec<&str>>();

    // Get the game number
    let game_num = game[0].split(' ').collect::<Vec<&str>>();
    let game_num = game_num[1].trim().parse::<usize>().unwrap();

    // Split off all the individual sets
    let game_sets = game[1].split(';');

It works well, and I was able to move on to the complication.

Part 2

In part 1, you were told how many red, green and blue cubes there in total and asked to figure out if a game was possible. For part 2, you twist it around — assume each game is possible, and figure out the lowest number of each color cube that must be in the bag. Once you know those numbers, multiply them together, then add each game’s total for the final score.

Reading the data happens the same way, but now instead of comparing each number to a constant, I figure out what the maximum of each cube is shown in each game. That number represents the minimum number of each cube that could be in the bag.

Sound counter-intuitive? Assume I am shown two sets, one with 3 blue cubes, and a second with 6 blue cubes. For these sets to be possible, there have to be at least 6 blue cubes in the bag. There could be 7 blue cubes, or 10, or 235, but the minimum number that have to be in the bag to show me a maximum of 6 cubes is 6.

Here’s what this looks like in code, with the same reading code as above:

for game_set in game_sets{

    // Split off each kind of ball
    let balls = game_set.trim().split(',');

    // Check each kind of ball pulled
    for ball in balls{
        let ball_info = ball.trim().split(' ').collect::<Vec<&str>>();
        let count = ball_info[0].trim().parse::<usize>().unwrap();
        match ball_info[1]{
            "red"   => red   = std::cmp::max(red, count),
            "green" => green = std::cmp::max(green, count),
            "blue"  => blue  = std::cmp::max(blue, count),
            &_      => panic!()
        }
    }
}

At least I learned how to use std::cmp::max().

Note that I don’t care about the game number anymore, nor is there a flag — I need to process every set of cubes for every game. Once I have the maximum number of each color cube, I simply multiply them together and add them to my final sum for the answer.

Summary

My code can be viewed here, and input is always welcome.

This puzzle was mostly about parsing input properly. I dropped back to a Python technique I know to get the job done, although I’m sure there are better ways to do it in Rust. In fact, below are some raw notes I took as I was working on this puzzle, as well as some notes for learning and improvement — enjoy seeing the sausage making.

TBD: Check https://github.com/manhunto/advent-of-code-rs/blob/master/src/solutions/day02.rs for some interesting parsing code.

https://github.com/dzerium/advent_of_code_23/blob/main/src/cube_conondrum.rs uses sscanf — is that Rusty enough?

Most of the solutions I’m seeing use a lot of .map() and other calls to do the splitting in one shot. Look into .nth() and definitely start replacing .expect() for the .unwrap() calls to better handle errors.

Cogito Coders

I think (like a coder), therefore I am (a coder).

AoC Day 2: Cube Conundrum