## Advent of Code 2022, Day 1 -- Calorie Counting

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

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 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 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();

// 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.
Canonical URL