aoc/year2020/
day01.rs

1//! # Report Repair
2//!
3//! The straightforward approach is to compare every possible pair of elements for part one and
4//! every possible triple for part two. This would have `O(n²)` and `O(n³)` time complexity respectively.
5//!
6//! We can do better with `O(n)` complexity for part one and `O(n²)` for part two.
7//!
8//! For part one we use an implicit hash table in an array, since values are constrained to between
9//! 0 and 2020 and each value is already perfectly hashed. For each entry we check the index
10//! at its value. If this is marked then we have seen the reciprocal `2020 - value` before
11//! so we can return the product. If not then we mark the reciprocal value in the array.
12//!
13//! Part two reuses the pair finding logic, finding the third element by stepping through the slice
14//! one by one and adjusting the target total. To reuse the array without reallocating
15//! (which is slow) we use a `round` value instead of `bool`.
16use crate::util::parse::*;
17
18pub fn parse(input: &str) -> Vec<usize> {
19    input.iter_unsigned().collect()
20}
21
22pub fn part1(input: &[usize]) -> usize {
23    let mut hash = [0; 2020];
24    two_sum(input, 2020, &mut hash, 1).unwrap()
25}
26
27pub fn part2(input: &[usize]) -> usize {
28    let mut hash = [0; 2020];
29
30    (0..input.len() - 2)
31        .find_map(|i| {
32            let first = input[i];
33            let round = i + 1;
34            let target = 2020 - first;
35            two_sum(&input[round..], target, &mut hash, round).map(|product| first * product)
36        })
37        .unwrap()
38}
39
40fn two_sum(slice: &[usize], target: usize, hash: &mut [usize], round: usize) -> Option<usize> {
41    for &i in slice {
42        if i < target {
43            let complement = target - i;
44            if hash[i] == round {
45                return Some(i * complement);
46            }
47            hash[complement] = round;
48        }
49    }
50
51    None
52}
aoc/year2020/day01.rs

aoc/year2020/
day01.rs
