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.