Advent of Code 2022 - Day 01

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Rust. I’ll post my solutions and code to GitHub as well. After finishing last year (and 2015-2019) in Julia, I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!

Day 01 - Calorie Counting

Find the problem description HERE.

The Input - The Elves Go Marching…

Our input for day one consists of groups of numbers, each on an individual line, with groups separated by an empty line. Each group represents the caloric value of the snacks being carted around by an individual elf, and, I must say, these elves either have the metabolism of hummingbirds or they aren’t going to make it too far into the jungle…

const INPUT: &str = include_str!("../../input/01/input.txt");

/// The input type for today's puzzles.
pub type Input = Vec<u32>;

/// Read and parse the input file
pub fn read() -> Input {
    // Iterate over each empty-line separated "chunk", parsing each chunk into 
    // a total calorie count per Elf, returning the list of total calories per
    // Elf.
    INPUT
        .trim()
        .split("\n\n")
        .map(try_parse_elf_calories)
        .collect::<Result<_, _>>()
        .expect("Could not parse input!")
}

/// Parse a "chunk" of lines representing an individual Elf's snacks into the 
/// total calories for that Elf.
fn try_parse_elf_calories(value: &str) -> Result<u32, std::num::ParseIntError> {
    // Iterate over each line, convert it to a u32, and sum the results
    let mut total = 0;
    for line in value.lines() {
        total += line.parse::<u32>()?;
    }
    Ok(total)
}

No sweat here! While actually solving the puzzle at first, I was keeping up with each elf’s snacks in a Vec<u32>, but it turns out that I only needed the total calories carried per Elf for parts 1 and 2, so it got re-factored out.

Part One - The Biggest Loser

Sooo… let me get this right: The most prepared elf who packed the most snacks and lugged them out into the jungle is about to get his stash raided by all the other elves? Way to be popular, I guess. For this part, we just need to identify the elf with the most caloric goodness squirreled away. I sure that elf won’t mind being identified in this way…

/// Solve Day 01, Part 01
pub fn solve(input: &Input) -> Output {
    // Get the maximum calorie count for an Elf and return it as an Output::U32.
    input.iter().copied().max().unwrap_or_default().into()
}

Simple, and straight to the point. We copy each number in the input because we’re iterating over a borrowed Input, this way we can re-use it for part 2. If for some reason our input were empty, we’d get zero for the most calories carried and a whole bunch of sad elves.

Part Two - Spread the Love

I guess the chief snack-packer got wind of our plot and decided to share the attention with the two next-most-gluttonous elves. Now we need to identify the top three elves (by caloric provision, of course) and return the combined caloric payload they’re lugging about.

/// Solve Day 01, Part 02
pub fn solve(input: &Input) -> Output {
    // A running total of the top three values for total
    // Elf calories found so far, descending from left to
    // right.
    let mut top_three = [u32::MIN; 3];

    // For each Elf's total snack calories...
    for calories in input.iter() {
        // Need a local (mutable) copy of the calories value
        let mut calories = *calories;

        // For each value in the current top three...
        for top_value in top_three.iter_mut() {
            // If the current Elf's total calories are greater than
            // the current top value, then swap the values. `calories`
            // now contains the previous `top_value` and the previous
            // value for `calories` is in `top_three`. Repeat for all
            // values in `top_three` until `top_three` contains the
            // largest three values of `top_three` and `calories`.
            if calories > *top_value {
                std::mem::swap(top_value, &mut calories);
            }
        }
    }

    // Return the sum of the top three calorie counts
    top_three.iter().sum::<u32>().into()
}

Not too much more complicated than part 1. While I technically could have just sorted the list of elf snack impact and returned the sum of the top three, I opted to take the time complexity of this solution down from O(n log n) down to O(n) by storing the top three calorie counts in an array. Then, for every elf I check, I’m shuffling that array so that it contains the top 3 values out of the 4 under consideration (the 3 already there plus the new one in calories). This way, I’m iterating over the input at most three times, which is still linear time complexity!

Wrap-Up

Ah, Advent of Code, how I have missed thee! Well, not too much, honestly. After last year I decided I needed to go back and grab all the stars from previous years, which was a fun 5-month (or so) project. One of the things I learned from that experience was the value of setting up a decent project template ahead of time to make the process of actually solving the puzzles as focused as possible. Given how verbose Rust can be, this seemed like an especially good idea this year, and today’s puzzle gave me a chance to test drive that setup. Now, while the number one on the leaderboard finished this puzzle (both parts) in less than a minute (what!?), I was happy to be done writing and re-factoring in under thirty minutes. I’m claiming it as a win! Plus, my solution runs in 39_microseconds_, 38 of which are spent parsing the input. I’m looking forward to tomorrow!