Toast is in Beta!Big news! Toast is in Beta!Learn more →

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.

for-loops.rs

rust

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.

combinations.rs

rust

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. `map`

ing 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)`

.

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.

cartesian-product-clone.rs

rust

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

cartesian-product-iter.rs

rust

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)}

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.