year2016/
day15.rs

Help
1use std::cell::RefCell;
2use std::collections::HashSet;
3use std::iter;
4use utils::number::{chinese_remainder, is_prime};
5use utils::prelude::*;
6
7/// Finding when discs align.
8///
9/// This puzzle is a system of linear simultaneous congruences which can be solved using
10/// <https://en.wikipedia.org/wiki/Chinese_remainder_theorem>.
11#[derive(Clone, Debug)]
12pub struct Day15 {
13    discs: Vec<Disc>,
14}
15
16#[derive(Copy, Clone, PartialEq, Eq, Debug)]
17struct Disc {
18    size: u32,
19    position: u32,
20}
21
22impl Day15 {
23    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
24        let seen_positions: RefCell<HashSet<u32>> = Default::default();
25        Ok(Self {
26            discs: parser::u32()
27                .with_prefix(" has ".with_prefix(parser::u32()).with_prefix("Disc #"))
28                .then(parser::u32().with_prefix(" positions; at time=0, it is at position "))
29                .with_suffix(".")
30                .map_res(|(size, position)| {
31                    if position >= size {
32                        Err("current position should be less than number of positions")
33                    } else if !is_prime(size) {
34                        Err("number of positions should be prime")
35                    } else if !seen_positions.borrow_mut().insert(size) {
36                        Err("number of positions should be unique")
37                    } else {
38                        Ok(Disc { size, position })
39                    }
40                })
41                .parse_lines(input)?,
42        })
43    }
44
45    #[must_use]
46    pub fn part1(&self) -> i64 {
47        Self::earliest_alignment(self.discs.iter())
48    }
49
50    #[must_use]
51    pub fn part2(&self) -> i64 {
52        Self::earliest_alignment(self.discs.iter().chain(iter::once(&Disc {
53            size: 11,
54            position: 0,
55        })))
56    }
57
58    #[inline]
59    fn earliest_alignment<'a>(discs: impl Iterator<Item = &'a Disc> + Clone) -> i64 {
60        let residues = discs
61            .clone()
62            .enumerate()
63            .map(|(i, disc)| -(disc.position as i64) - (i as i64 + 1));
64        let moduli = discs.map(|disc| disc.size as i64);
65
66        chinese_remainder(residues, moduli).expect("sizes are all prime")
67    }
68}
69
70examples!(Day15 -> (i64, i64) [
71    {
72        input: "Disc #1 has 5 positions; at time=0, it is at position 4.\n\
73            Disc #2 has 2 positions; at time=0, it is at position 1.",
74        part1: 5
75    },
76]);
year2016/day15.rs

year2016/
day15.rs
