advent_of_code/year2020/
day01.rs

1use crate::common::parser::parse_lines;
2use crate::input::Input;
3use core::cmp::Ordering::{Equal, Greater, Less};
4
5fn subsequence_summing_to(sorted_sequence: &[u32], desired_sum: u32) -> Option<u32> {
6    if sorted_sequence.is_empty() || sorted_sequence.len() < 2 {
7        return None;
8    }
9
10    let (mut left, mut right) = (0, sorted_sequence.len() - 1);
11
12    while left != right {
13        let (left_value, right_value) = (sorted_sequence[left], sorted_sequence[right]);
14        let candidate_sum = left_value + right_value;
15
16        match candidate_sum.cmp(&desired_sum) {
17            Equal => {
18                return Some(left_value * right_value);
19            }
20            Less => {
21                left += 1;
22            }
23            Greater => {
24                right -= 1;
25            }
26        }
27    }
28
29    None
30}
31
32pub fn solve(input: &Input) -> Result<u32, String> {
33    const DESIRED_SUM: u32 = 2020;
34
35    let mut expenses = parse_lines::<u32>(input.text)?;
36    expenses.sort_unstable();
37
38    let result = if input.is_part_one() {
39        subsequence_summing_to(&expenses, DESIRED_SUM)
40    } else {
41        expenses
42            .iter()
43            .enumerate()
44            .find_map(|(left_index, &left_value)| {
45                let desired_sub_sum = DESIRED_SUM.checked_sub(left_value)?;
46                subsequence_summing_to(&expenses[(left_index + 1)..], desired_sub_sum)
47                    .map(|value| value * left_value)
48            })
49    };
50
51    result.ok_or_else(|| {
52        format!(
53            "No {} expenses sum to {}",
54            input.part_values(2, 3),
55            DESIRED_SUM
56        )
57    })
58}
59
60#[test]
61pub fn tests() {
62    use crate::input::{test_part_one, test_part_one_error, test_part_two, test_part_two_error};
63
64    test_part_one!("1721\n979\n366\n299\n675\n1456" => 514_579);
65    test_part_one_error!("" => "No 2 expenses sum to 2020");
66    test_part_one_error!("1" => "No 2 expenses sum to 2020");
67    test_part_one_error!("1\n2" => "No 2 expenses sum to 2020");
68    test_part_one_error!("1\n2\n3" => "No 2 expenses sum to 2020");
69
70    test_part_two!("1721\n979\n366\n299\n675\n1456" => 241_861_950);
71    test_part_two_error!("asdf" => "Line 1: Not a valid integer");
72    test_part_two_error!("12\nasdf" => "Line 2: Not a valid integer");
73    test_part_two_error!("" => "No 3 expenses sum to 2020");
74    test_part_two_error!("1" => "No 3 expenses sum to 2020");
75    test_part_two_error!("1\n2" => "No 3 expenses sum to 2020");
76    test_part_two_error!("1\n2\n3" => "No 3 expenses sum to 2020");
77
78    let real_input = include_str!("day01_input.txt");
79    test_part_one!(real_input => 138_379);
80    test_part_two!(real_input => 85_491_920);
81}
advent_of_code/year2020/day01.rs

advent_of_code/year2020/
day01.rs
