Advent of Code 2020 - Day 1: finding 2 or 3 numbers that add up to 2020

Question

Next: Advent of Code 2020 - Day 2: validating passwords

Problem statement

I decided to take a shot at Advent of Code 2020 to exercise my Rust knowledge. Here's the task for Day 1:

Day 1: Report Repair

[...]

Specifically, they need you to find the two entries that sum to 2020 and then multiply those two numbers together.

For example, suppose your expense report contained the following:

1721
979
366
299
675
1456

In this list, the two entries that sum to 2020 are 1721 and 299. Multiplying them together produces 1721 * 299 = 514579, so the correct answer is 514579.

[...]

Part Two

[...] They offer you a second one if you can find three numbers in your expense report that meet the same criteria.

Using the above example again, the three entries that sum to 2020 are 979, 366, and 675. Multiplying them together produces the answer, 241861950.

The full story can be found on the website.

My solution

src/day_1.rs

use {anyhow::Result, std::io::prelude::*};

pub type Number = u64;

pub fn parse_data<R: BufRead>(reader: R) -> Result<Vec<Number>> {
    reader.lines().map(|line| Ok(line?.parse()?)).collect()
}

// Finds a pair of numbers in `data` that add up to `sum`
pub fn find_pair(mut data: Vec<Number>, sum: Number) -> Option<(Number, Number)> {
    data.sort_unstable();

    find_pair_in_sorted(&data, sum)
}

// Finds a triple of numbers in `data` that add up to `sum`.
pub fn find_triple(mut data: Vec<Number>, sum: Number) -> Option<(Number, Number, Number)> {
    data.sort_unstable();

    while let Some(number) = data.pop() {
        let sub_sum = match sum.checked_sub(number) {
            Some(sub_sum) => sub_sum,
            None => continue,
        };

        if let Some((a, b)) = find_pair_in_sorted(&data, sub_sum) {
            return Some((a, b, number));
        }
    }

    None
}

// Finds a pair of numbers in `data` that add up to `sum`
// by binary searching for `sum - n` for each number `n` in `data`.
// `data` must be sorted in ascending order.
pub fn find_pair_in_sorted(mut data: &[Number], sum: Number) -> Option<(Number, Number)> {
    while let Some((&number, new_slice)) = data.split_last() {
        data = new_slice;

        let target = match sum.checked_sub(number) {
            Some(target) => target,
            None => continue,
        };

        if data.binary_search(&target).is_ok() {
            return Some((target, number));
        }
    }

    None
}

src/bin/day_1_1.rs

use {
    anyhow::{anyhow, Result},
    aoc_2020::day_1::{self as lib, Number},
    std::{fs::File, io::BufReader},
};

const PATH: &str = "./data/day_1/input";
const SUM: Number = 2020;

fn main() -> Result<()> {
    let file = BufReader::new(File::open(PATH)?);
    let data = lib::parse_data(file)?;

    let (a, b) = lib::find_pair(data, SUM)
        .ok_or_else(|| anyhow!("cannot find pair that adds up to {}", SUM))?;
    println!("{} * {} = {}", a, b, a * b);

    Ok(())
}

src/bin/day_1_2.rs

use {
    anyhow::{anyhow, Result},
    aoc_2020::day_1::{self as lib, Number},
    std::{fs::File, io::BufReader},
};

const PATH: &str = "./data/day_1/input";
const SUM: Number = 2020;

fn main() -> Result<()> {
    let file = BufReader::new(File::open(PATH)?);
    let data = lib::parse_data(file)?;

    let (a, b, c) = lib::find_triple(data, SUM)
        .ok_or_else(|| anyhow!("cannot find triple that adds up to {}", SUM))?;
    println!("{} * {} * {} = {}", a, b, c, a * b * c);

    Ok(())
}

Crates used: anyhow 1.0.37

cargo fmt and cargo clippy have been applied.

Answer 1

Your code is well done and shows familiarity with Rust.

The best I can do is comment on some parts of the code and provide two small, concrete pieces of advice. There is very little room for improvement in the code.

I see your Vecs in function parameters are well motivated. The one in find_triple is motivated by the need to do pop, and the one in find_pair just follows the other for consistency between parts of the task.

The decision to introduce Number as a type alias is ok, and works and looks fine, but keep in mind that it adds an extra mental hop for the reader.

Return types

Acting by intuition I'd change the return types to have const-length arrays instead of tuples. This brings attention to the fact that the array/tuple is homogeneous. I would change:

-> Option<(Number, Number, Number)> and return Some((a, b, number));
to
-> Option<[Number; 3]> and return Some([a, b, number]);

Typo?

It's good to be correct and consistent in naming. The function name is find_triple - but 'triple' is not a noun, 'triplet' is.