This is a write-up of the first challenge of this year's Advent Of Code. At the end of the year the Advent Of Code starts on December 1st, publishing daily coding challenges until Christmas. Ths events runs annually for a few years now. It is an excellent opportunity to learn a new programming language, to improve one's own skills or see what other participants come up with. Each day consists of two parts, the solution of the 1st is required to unlock the 2nd. Challenges will usually grow in difficulty & require of participants to implement a range of algorithms or apply in order to find a solution. For each daily challenge a text input file is provided on the website. For each participant this input is somewhat randomly generated that adheres to the same rules but solutions from participants will differ.

The last few years I also took part (see aoc2020 & aoc2021). This year I want to see how much I've learnt in Rust & to see which crates can be used to solve some of these puzzles.

Let's start with day 01. Today a group of elves take inventory of their supplies.

The example input looks:

1000
2000
3000

4000

5000
6000

7000
8000
9000

10000

Successive lines with numbers represent the inventory of a single elf. All these groups are separated by blank lines to mark different inventories, e.g. 1000, 2000, 3000 belong to the first elf, 4000 to the second etc. A line with a number represents the calories of a single snack. In the example above the first elf has a total of 6000 calories, the 2nd one has 4000.

The task is to find the elf that carries the highest number of calories.

Setup

I'm using Rust 1.65, my code editor is VS Code. All is running in Ubuntu using WSL2 on Windows 10. My recommendation is to use a code editor that supports the Rust Analyzer, the most popular language server protocol for Rust. It's available for example in Visual Studio Code & provides a number of useful features, e.g. inlay type hints, diagnostics, shortcuts to run tests.

The daily project is built as follows:

cd aoc-2022
cargo new day01

This generates a Cargo.toml & src/main.rs files in folder day01. The Cargo.toml looks like

# Cargo.toml
[package]
name = "aoc-2022-day-01"
version = "0.1.0"
edition = "2021"

[dependencies]

A basic version of src/main.rs could look as follows:

fn parse(input: &str) -> () {
    todo!("Parse the input")
}

fn main() {
    let input = parse(include_str!("input.txt"));
    // use the input to run both parts
}

#[cfg(test)]
mod tests {
    // Add tests from daily challenge to see if code works.
}

Generally I like to have a test module with the sample data from the daily challenge as it helps to figure out how to parse the data.

First the input text file has to be read, we copy the input file available from the daily challenge into a file input.txt inside the src folder. To keep things simple for now I chose the parse function to group the calories into a nested Vec, the calories number is put into a u32.

The interface of the parse function looks then

fn parse(input: &str) -> Vec<Vec<u32>> {}

Apart from the return type this is basically what I'll use for all challenges, as nearly all input comes from a provided text file. Let's see how the content can be parsed to group all calories for each elf.

fn parse(input: &str) -> Vec<Vec<u32>> {
    input
        .split("\n\n")
        .map(|group| {
            group
                .lines()
                .map(str::trim)
                .filter_map(|s| s.parse::<u32>().ok())
                .collect::<Vec<_>>()
        })
        .collect::<Vec<_>>()
}

fn main() {
    let input = parse(include_str!("input.txt"));
}

The include_str! macro in main includes a text file relative to the current file as a String during compilation. This has the advantage that the input file is part of the final binary. The parse function splits the input by a blank line (sequence "\n\n"). For each group all calories are converted using str::parse to parse all &str into u32 values. Any possible conversion error is ignored by using filter_map, as we can expect all lines in the input file that is not an empty line contains a valid single number.

Lastly the iterator of the group is turned into a Vec using collect. An alternative could be to use itertools's convenient helper collect_vec. Then instead of .collect::<Vec<_>>() the iterator can be collected via collect_vec.

Each group consists of a number of lines that make up the calories for one elf. In general I like to use str::trim during the parse step to remove any leading or trailing whitespace characters from each line.

Note Using str::trim is not strictly necessary for the given input, but it makes it easier to use sample input in the test module. These usually follow default formatting rules to improve readability but may contain leading whitespaces.

Part 1

Now that we have a representation of the input data as a Vec<Vec<u32>> let's solve the first part. For that we will add a new function named part1 & set up a test for it.

#[cfg(test)]
mod tests {
    use crate::*;

    const INPUT: &str = r#"
        1000
        2000
        3000

        4000

        5000
        6000

        7000
        8000
        9000

        10000
    "#;

    #[test]
    fn test_part1() {
        assert_eq!(24_000, part1(&parse(INPUT)));
    }
}

This declares the const variable INPUT with the input from the given example. We know that the result for this sample data is 24000, therefore we will check the returned value from part1 with it. This also kind of informs us to what the function interace for part1 needs to look like.

To make the code compile let's declare the part1 function for now.

fn part1(elves: &[Vec<u32>]) -> u32 {
    unimplemented!()
}

Note the function parameter elves has a types of &[Vec<u32>] instead of &Vec<Vec<u32>>. Running cargo clippy will issue a warning "warning: writing &Vec instead of &[_] involves a new object where a slice will do". It's recommended to use a slice rather than a type with a specific size. It also allows callers to pass in other types where a slice can be obtained from.

Running cargo test should now compile the code, but the test test_part1 will fail. As the next step we will calculate the sum of calories for each elf in function part1. There are multiple ways to implement this, but this is a good opportunity to use iterators for these of calculations.

fn part1(elves: &[Vec<u32>]) -> u32 {
    elves.iter().map(|elf| elf.iter().sum()).max().unwrap()
}

fn main() {
    let elves = parse(include_str!("input.txt"));
    println!("Max calories: {}", part1(&elves));
}

The part1 function uses map for each group of Vec<u32> to calculate their sum. The code elves.iter().map(|elf| elf.iter().sum()) results in an iterator over u32 values. The max method finds the highest u32 value by iterating over all values. The unwrap at the end is to unpack the value, the list is expected not to be empty.

There is one technique that I sometimes use to check the state inbetween iterator methods. It's not the most ideal way to debug things, but to check intermediate states in iterators it's quite useful.

fn part1(elves: &[Vec<u32>]) -> u32 {
    elves
        .iter()
        .map(|elf| elf.iter().sum())
        .inspect(|v| println!("{}", v)) // <- 'print current state
        .max()
        .unwrap()
}

The method inspect takes a reference to the output from the previous iterator call (map) and runs some code, without interrupting the iterator chain. In this case we println the content of variable v which is a u32. Running the test test_part1 with the included inspect call outputs:

running 1 test
6000
4000
11000
24000
10000
test tests::test_part1 ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 1 filtered out; finished in 0.00s

Running the project with cargo run should output the desired number for the full input.

Part 2

The second part adds a constraint to not rely on the single elf with the maximum number of calories, but to find the top three elves with the highest calories to provide snack backups. The task is to find the top three elves and sum their calories.

Often times the solution for part 1 is not necessarily applicable for the 2nd part. It's also not necessarily useful to anticipate in advance what the 2nd part may look like. Usually the code can be refactored in a way that it accommodate both solutions to some degree. In this case it seems quite easy to refactor the current logic to also apply for the 2nd part.

One option is to sort the list of sums in descending order, then it becomes quite easy to just take the first N items, either 1 or 3. Let's refactor the part1 function first & extract shared logic:

/// Returns the summed calories for each elf, sorted by biggest sum first
fn sorted_sums(elves: &[Vec<u32>]) -> impl Iterator<Item = u32> + '_ {
    elves.iter().map(|elf| elf.iter().sum()).sorted().rev()
}

fn part1(elves: &[Vec<u32>]) -> u32 {
    sorted_sums(elves).next().unwrap()
}

The new function sorted_sums takes the nested Vec<u32> of calories & returns an Iterator. It could also have returned a collected Vec for example. The advantage is that sorted_sums itself does not do much on its own, it's creating an Iterator over the elves variable. The part1 actually runs the iterator by calling .next() that invokes the full iterator calls. At the end it gets the first item from the iterator. The unwrap call is fine here, as it's not expected to have an empty elves slice. Generally I'm not a fan of calling unwrap, as it's often better to propagate the Option to the caller and let it handle Some & None.

Running cargo test should still pass the test as before. Implementing the 2nd part now should be straightforward.

fn part2(elves: &[Vec<u32>]) -> u32 {
    sorted_sums(elves).take(3).sum()
}

fn main() {
    // .. as before
    println!("Top three calories: {}", part2(&elves));
}

#[cfg(test)]
mod tests {
    // .. as before

    #[test]
    fn test_part2() {
        assert_eq!(45_000, part2(&parse(INPUT)));
    }
}

There is a new test test_part2 that checks the outcome of the test sample. Function part2 also calls sorted_sums and calculates the top three calories. Chaining iterator calls like this is really convenient. The method take on Iterator yields at most n elements from the iterator. If there are less, then fewer items will be returned. Lastly the sum method will take each element & adds them together. It returns a single result of type u32 due to type inference of the function return type.

Running the program outputs the 2nd number, the sum of calories of the top three elves.