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                .windows(2)
40                .filter_map(|w| {
41                    let (_, freq1) = w[0];
42                    let (idx2, freq2) = w[1];
43                    if freq1 == freq2 {
44                        Some((idx2, freq1))
45                    } else {
46                        None
47                    }
48                })
49                .min()
50        } else {
51            let mut remainders = self
52                .changes
53                .iter()
54                .enumerate()
55                .scan(0i32, |freq, (t, &change)| {
56                    let curr = *freq;
57                    *freq += change;
58                    Some((curr.rem_euclid(self.total), curr, t))
59                })
60                .collect::<Vec<_>>();
61
62            remainders.sort_unstable();
63
64            remainders
65                .chunk_by(|&(r1, _, _), &(r2, _, _)| r1 == r2)
66                .flat_map(|chunk| {
67                    chunk.iter().enumerate().flat_map(|(i, &r1)| {
68                        chunk.iter().skip(i + 1).filter_map(move |&r2| {
69                            let ((_, freq1, t1), (_, freq2, _)) =
70                                if self.total > 0 { (r1, r2) } else { (r2, r1) };
71
72                            let freq_difference = freq2 - freq1;
73                            let iterations = freq_difference / self.total;
74                            if freq_difference.rem_euclid(self.total) == 0 && iterations >= 0 {
75                                let iterations = iterations as usize;
76                                Some((iterations * self.changes.len() + t1, freq2))
77                            } else {
78                                None
79                            }
80                        })
81                    })
82                })
83                .min()
84        }
85        .map(|(_, freq)| freq)
86        .expect("no solution found")
87    }
88}
89
90examples!(Day01 -> (i32, i32) [
91    {input: "+1\n-2\n+3\n+1", part1: 3, part2: 2},
92    {input: "+1\n+1\n+1", part1: 3},
93    {input: "+1\n+1\n-2", part1: 0},
94    {input: "-1\n-2\n-3", part1: -6},
95    {input: "+1\n-1", part2: 0},
96    {input: "+3\n+3\n+4\n-2\n-4", part2: 10},
97    {input: "-6\n+3\n+8\n+5\n-6", part2: 5},
98    {input: "+7\n+7\n-2\n-7\n-4", part2: 14},
99    // Negative versions of the above
100    {input: "-1\n+2\n-3\n-1", part1: -3, part2: -2},
101    {input: "-1\n+1", part2: 0},
102    {input: "-3\n-3\n-4\n+2\n+4", part2: -10},
103    {input: "+6\n-3\n-8\n-5\n+6", part2: -5},
104    {input: "-7\n-7\n+2\n+7\n+4", part2: -14},
105    // Custom examples
106    {input: "+2\n+3\n-8", part2: 2},
107    {input: "+0", part2: 0},
108    {input: "+1000000\n-999999", part2: 1000000},
109    {input: "+1\n-2\n+2\n-2\n+3", part2: 1},
110    {input: "+1\n-2\n+2\n-2\n-5", part2: 1},
111]);
year2018/day01.rs

year2018/
day01.rs
