Mary Knize

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

Jump to:

• Part 1
• Part 2
• What I learned

Since day 1 is pretty easy, I'll start off by showing you my completed code, and then I'll break it down:

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.