Advent of Code Rust day 1 for loops vs iterators

Spoilers ahead for Advent of Code 2020 day 1. The full code is on GitHub.

Given a list of newline-separated numbers, return the multiplication of the two numbers that add up to 2020.

Coming from other languages, one may be tempted to reach for for loops. This results in some more manual work with respect to ownership and borrowing, so you might end up just cloning instead.

fn process(input: &str) -> Option<u64> {
    let mut nums = vec![];
    for line in input.lines() {
        let num = line.parse::<u64>().unwrap();
        nums.push(num);
    }

    for num in nums.clone() {
        for num2 in nums.clone() {
            for num3 in nums.clone() {
                if num + num2 + num3 == 2020 {
                    return Some(num * num2 * num3);
                }
            }
        }
    }
    return None;
}

So we have a mutable nums vec that we parse numbers into, and a loop for every combination of numbers. So refactoring our code from part 1 to part 2 means: adding a third for loop, remembering to add a third number and remembering to multiply a third number. The latter two being actions the type system doesn't help us remember to do: it will accept num + num2 just as easily as num + num2 + num3.

We can rectify the cloning, reduce our ownership battles, and make refactoring less error prone by using iterators.

fn process(input: &str) -> Option<u64> {
    input
        .lines()
        .map(|string_num| string_num.parse::<u64>().unwrap())
        .combinations(3)
        .find(|perm| perm.iter().sum::<u64>() == 2020)
        .map(|v| v.iter().product())
}

input.lines() hands us an iterator we can keep using. maping over the string to parse it, then producing the set of combinations of all numbers using itertools and .combinations. Note that in the for loop example we were also producing more pairs than we needed to, because for just the combinations we'd want to start each nested for loop at an offset.

This .combinations approach allows us to more easily pass in configuration to our function, such as the number of items to pair in a combination. Combined with the usage of .sum() and .product(), we no longer have to manually maintain the list of added or multiplied numbers, reducing the possibility for human error when refactoring. In fact, refactoring from part 1 to part two only requires changing .combinations(2) to .combinations(3).

Alternates

While I like the combinations approach the best for code maintainability and refactoring ease, itertools also offers cartesian_product, which can be used as follows without worrying about borrowing.

use itertools::Itertools;

pub fn process(input: &str) -> Option<u64> {
    let list = input
        .lines()
        .map(|string_num| string_num.parse::<u64>().unwrap());

    list.clone()
        .cartesian_product(list.clone())
        .cartesian_product(list.clone())
        .find(|((a, b), c)| a + b + c == 2020)
        .map(|((a, b), c)| a * b * c)
}

or with a vec allocation

use itertools::Itertools;

pub fn process(input: &str) -> Option<u64> {
    let list = input
        .lines()
        .map(|string_num| string_num.parse::<u64>().unwrap())
        .collect::<Vec<u64>>();

    list.iter()
        .cartesian_product(list.iter())
        .cartesian_product(list.iter())
        .find(|((a, b), c)| **a + **b + **c == 2020)
        .map(|((a, b), c)| a * b * c)
}

On Performance

We have four examples above,

• for-loops.rs
• combinations.rs
• cartesian-product-clone.rs
• cartesian-product-iter.rs

Here are the criterion benches for each, sorted.

| example | lower bound | best guess | upper bound | | ----------------------- | ----------- | ---------- | ----------- | | for-loops | 1.0216 ms | 1.0239 ms | 1.0263 ms | | cartesian-product-iter | 2.5539 ms | 2.5596 ms | 2.5658 ms | | cartesian-product-clone | 21.010 ms | 21.059 ms | 21.111 ms | | combinations | 32.727 ms | 32.832 ms | 32.948 ms |

As shown, for loops are the fastest with the cartesian-product-iter example being second at a little over ~2.5x time (1ms vs 2.5ms). The clone version performs dramatically worse and the combinations example being the worst at 32ms.

note that we're really talking milliseconds here and unless you've measured and it matters, I'd still opt for the combinations approach, with the cartesian-product-iter a close second.