year2018/
day01.rs

1use std::iter;
2use utils::prelude::*;
3
4/// Finding the first repeat.
5#[derive(Clone, Debug)]
6pub struct Day01 {
7    changes: Vec<i32>,
8    total: i32,
9}
10
11impl Day01 {
12    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
13        let changes = parser::i32().parse_lines(input)?;
14        Ok(Self {
15            total: changes.iter().sum(),
16            changes,
17        })
18    }
19
20    #[must_use]
21    pub fn part1(&self) -> i32 {
22        self.total
23    }
24
25    #[must_use]
26    pub fn part2(&self) -> i32 {
27        if self.total == 0 {
28            let mut frequencies = iter::once(0)
29                .chain(self.changes.iter().scan(0i32, |sum, &c| {
30                    *sum += c;
31                    Some(*sum)
32                }))
33                .enumerate()
34                .collect::<Vec<_>>();
35
36            frequencies.sort_unstable_by_key(|&(idx, freq)| (freq, idx));
37
38            frequencies
39                .array_windows()
40                .filter_map(|&[(_, freq1), (idx2, freq2)]| {
41                    if freq1 == freq2 {
42                        Some((idx2, freq1))
43                    } else {
44                        None
45                    }
46                })
47                .min()
48        } else {
49            let mut remainders = self
50                .changes
51                .iter()
52                .enumerate()
53                .scan(0i32, |freq, (t, &change)| {
54                    let curr = *freq;
55                    *freq += change;
56                    Some((curr.rem_euclid(self.total), curr, t))
57                })
58                .collect::<Vec<_>>();
59
60            remainders.sort_unstable();
61
62            remainders
63                .chunk_by(|&(r1, _, _), &(r2, _, _)| r1 == r2)
64                .flat_map(|chunk| {
65                    chunk.iter().enumerate().flat_map(|(i, &r1)| {
66                        chunk.iter().skip(i + 1).filter_map(move |&r2| {
67                            let ((_, freq1, t1), (_, freq2, _)) =
68                                if self.total > 0 { (r1, r2) } else { (r2, r1) };
69
70                            let freq_difference = freq2 - freq1;
71                            let iterations = freq_difference / self.total;
72                            if freq_difference.rem_euclid(self.total) == 0 && iterations >= 0 {
73                                let iterations = iterations as usize;
74                                Some((iterations * self.changes.len() + t1, freq2))
75                            } else {
76                                None
77                            }
78                        })
79                    })
80                })
81                .min()
82        }
83        .map(|(_, freq)| freq)
84        .expect("no solution found")
85    }
86}
87
88examples!(Day01 -> (i32, i32) [
89    {input: "+1\n-2\n+3\n+1", part1: 3, part2: 2},
90    {input: "+1\n+1\n+1", part1: 3},
91    {input: "+1\n+1\n-2", part1: 0},
92    {input: "-1\n-2\n-3", part1: -6},
93    {input: "+1\n-1", part2: 0},
94    {input: "+3\n+3\n+4\n-2\n-4", part2: 10},
95    {input: "-6\n+3\n+8\n+5\n-6", part2: 5},
96    {input: "+7\n+7\n-2\n-7\n-4", part2: 14},
97    // Negative versions of the above
98    {input: "-1\n+2\n-3\n-1", part1: -3, part2: -2},
99    {input: "-1\n+1", part2: 0},
100    {input: "-3\n-3\n-4\n+2\n+4", part2: -10},
101    {input: "+6\n-3\n-8\n-5\n+6", part2: -5},
102    {input: "-7\n-7\n+2\n+7\n+4", part2: -14},
103    // Custom examples
104    {input: "+2\n+3\n-8", part2: 2},
105    {input: "+0", part2: 0},
106    {input: "+1000000\n-999999", part2: 1000000},
107    {input: "+1\n-2\n+2\n-2\n+3", part2: 1},
108    {input: "+1\n-2\n+2\n-2\n-5", part2: 1},
109]);
year2018/day01.rs

year2018/
day01.rs
