Advent of Code 2022, Day 1 -- Calorie Counting

Mary Knize

Dec 1st, 2022

3 min read

Advent Of Code

Rust solutions to Advent of Code 2022, day 1.

Another December, another Advent of Code!

This year, I'm going to try using Rust as much as possible, but I might fall back to Python or JavaScript at times.

In 2020, I made it 16 days into December before giving up (although I only did write-ups for nine days that year). Last year, I only got through three days using Rust, and didn't write down anything. ☹️

This year's goal is to go beyond my record of 16 days, and to also write a little something about my problem solving process each day.

Full code for Day 1 can be found on Github.

The Day 1 problem can be found at adventofcode.com/2022/day/1

use std::fs;
use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    let contents = fs::read_to_string("input.txt").unwrap();
    let arr = contents
        .split("\n\n")
        .collect::<Vec<&str>>();
    for elf in arr {
        let cals: i32 = elf
            .split("\n")
            .map(|val| val.parse::<i32>().unwrap_or(0))
            .sum();
        heap.push(cals);
    }
    println!("{}", heap.peek().unwrap());

    let mut top3 = 0;
    for _ in 0..3 {
        top3 += heap.pop().unwrap();
    }
    println!("{}", top3);
}

Part 1

The way I initially solved part 1, which asks for the highest sum from the list, was to split the input into an array of arrays, as I've done above. Then, I would have a mutable variable that I would update with the maximum sum. I would then print that sum as my answer.

use std::fs;
use std::cmp;

fn main() {
    let contents = fs::read_to_string("input.txt").unwrap();
    let mut maximum = 0;

    // Split by double newlines to create a per-elf vector.
    let arr = contents
        .split("\n\n")
        .collect::<Vec<&str>>();

    // Iterate over each elf's snacks.
    for elf in arr {
        // Split the remaining string by newline, cast to integer, and sum.
        let cals: i32 = elf
            .split("\n")
            .map(|val| val.parse::<i32>().unwrap_or(0))
            .sum();
        // Update the maximum value.
        maximum = cmp::max(maximum, cals);
    }
    println!("{}", maximum);
}

However, after seeing part 2 of the question, I realized that the whole problem could be better solved with a max heap. I've used heapq in Python before, but I've never used a heap in Rust before. Luckily, I found that Rust has BinaryHeap in the standard library. As a bonus, BinaryHeap creates a max heap by default, as opposed to heapq's default min heap.

Rewriting the part 1 to use BinaryHeap looks like this:

use std::fs;
use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    let contents = fs::read_to_string("input.txt").unwrap();

    // Split by double newlines to create a per-elf vector.
    let arr = contents
        .split("\n\n")
        .collect::<Vec<&str>>();
    // Iterate over each elf's snacks.
    for elf in arr {
        // Split the remaining string by newline, cast to integer, and sum.
        let cals: i32 = elf
            .split("\n")
            .map(|val| val.parse::<i32>().unwrap_or(0))
            .sum();
        // Push the total value to the heap.
        heap.push(cals);
    }

    // Peek at the heap and print the largest value.
    println!("{}", heap.peek().unwrap());
}

Part 2

Since part 2 just asks for a sum of the top three totals, and we already have a max heap, it's trivial to pop the top three amounts off of the heap and add them together. I've added a mutable variable to sum the values, and simply loop three times to pop off the top values.

let mut top3 = 0;
for _ in 0..3 {
    top3 += heap.pop().unwrap();
}
println!("{}", top3);

An earlier iteration had me using:

let top3 = heap
    .into_sorted_vec()
    .rev()
    .iter()
    .take(3)
    .sum()

It seems inefficient. Why use a heap when you're just going to transform it into a vector, reverse it, and then turn it into an iterable? Also, into_sorted_vec returns the items sorted in ascending order, as opposed to the descending order that is the max heap. In that case I would've just pushed each sum to a vector, sorted it, then taken the top three and summed those.

Perhaps there's a better way than using a mutable to hold the running total, but it's in the nightly Rust build.

rustup update
rustup default nightly

Then, at the very top of main.rs, use this flag:

#![feature(binary_heap_into_iter_sorted)]

Now, into_iter_sorted will return an iterable from the heap, that's in descending order, and then I can take the top three items and sum them.

let top3: i32 = heap
    .into_iter_sorted()
    .take(3)
    .sum();
println!("{}", top3);

Quite helpful if you can use experimental methods!

What I learned

BinaryHeap - A max heap data structure.
Rust nightly - Nightly build of Rust with cutting-edge features.
.into_iter_sorted() - A Rust nightly method for BinaryHeap that allows you to turn a heap into a sorted iterable.

mary.codes