year2020/
day13.rs

1use utils::number::{chinese_remainder, gcd};
2use utils::prelude::*;
3
4/// Finding when cycles first align.
5///
6/// Part 2 is similar to [2016 Day 15](../year2016/struct.Day15.html).
7#[derive(Clone, Debug)]
8pub struct Day13 {
9    earliest: u64,
10    buses: Vec<Bus>,
11}
12
13#[derive(Copy, Clone, Debug)]
14struct Bus {
15    id: u32,
16    offset: i64,
17}
18
19impl Day13 {
20    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
21        let (earliest, buses) = parser::u64()
22            .with_eol()
23            .then(
24                parser::one_of((parser::nonzero_u32().map(Some), b'x'.map(|_| None)))
25                    .repeat_fold(b',', 1, (Vec::new(), 0i64), |(mut buses, offset), id| {
26                        if let Some(id) = id {
27                            buses.push(Bus {
28                                id: id.get(),
29                                offset,
30                            });
31                        }
32                        (buses, offset + 1)
33                    })
34                    .map(|(buses, _)| buses),
35            )
36            .parse_complete(input)?;
37
38        if buses.is_empty() {
39            return Err(InputError::new(input, 0, "expected at least one id"));
40        }
41
42        let mut period = 1i64;
43        for bus in &buses {
44            let id = i64::from(bus.id);
45            if gcd(period, id) != 1 {
46                return Err(InputError::new(input, 0, "ids must be pairwise coprime"));
47            }
48            period = period
49                .checked_mul(id)
50                .ok_or_else(|| InputError::new(input, 0, "combined period is too large"))?;
51        }
52
53        Ok(Self { earliest, buses })
54    }
55
56    #[must_use]
57    pub fn part1(&self) -> u64 {
58        let (id, wait) = self
59            .buses
60            .iter()
61            .map(|bus| {
62                let id = u64::from(bus.id);
63                let wait = (id - self.earliest % id) % id;
64                (id, wait)
65            })
66            .min_by_key(|&(_, wait)| wait)
67            .unwrap();
68        id * wait
69    }
70
71    #[must_use]
72    pub fn part2(&self) -> u64 {
73        chinese_remainder(
74            self.buses.iter().map(|bus| -bus.offset),
75            self.buses.iter().map(|bus| i64::from(bus.id)),
76        )
77        .expect("ids are pairwise coprime") as u64
78    }
79}
80
81examples!(Day13 -> (u64, u64) [
82    {input: "939\n7,13,x,x,59,x,31,19", part1: 295, part2: 1068781},
83    {input: "0\n17,x,13,19", part2: 3417},
84    {input: "0\n67,7,59,61", part2: 754018},
85    {input: "0\n67,x,7,59,61", part2: 779210},
86    {input: "0\n67,7,x,59,61", part2: 1261476},
87    {input: "0\n1789,37,47,1889", part2: 1202161486},
88]);
year2020/day13.rs

year2020/
day13.rs
