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 have found the answer. Creating this array also performs a radix sort that will
12//! be used in part two.
13use crate::util::parse::*;
14
15type Input = (usize, [bool; 2020]);
16
17pub fn parse(input: &str) -> Input {
18 let mut numbers = [false; 2020];
19 let mut part_one = 0;
20
21 // Part one is determined as a side effect of the parse. Assume the input has no duplicates.
22 for number in input.iter_unsigned::<usize>() {
23 if numbers[2020 - number] {
24 part_one = number * (2020 - number);
25 }
26 numbers[number] = true;
27 }
28
29 // The parse performed a radix sort; numbers can now be used as an ordered sparse array.
30 (part_one, numbers)
31}
32
33pub fn part1(input: &Input) -> usize {
34 input.0
35}
36
37pub fn part2(input: &Input) -> usize {
38 let (_, numbers) = input;
39
40 // We know at least one of the three numbers is at least 2020/3.
41 for i in 674..2020 {
42 for j in 1..i {
43 let k = 2020 - i - j;
44 if numbers[i] && numbers[j] && numbers[k] {
45 return i * j * k;
46 }
47 }
48 }
49
50 unreachable!()
51}