aoc/year2016/
day15.rs

1//! # Timing is Everything
2//!
3//! Part one is the [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem).
4//! The integers n₁, n₂, ... nₖ map to the disc sizes which happen to be prime. This satisfies the
5//! requirement that the integers are [pairwise coprime](https://en.wikipedia.org/wiki/Coprime_integers#Coprimality_in_sets).
6//!
7//! For simplicity we use the "search by sieving" method. We start at zero with a step the size of
8//! the first integer. Then we search for each subsequent integer located at the correct offset of
9//! minutes and multiply the step by the new integer. This preserves the relative offset at each step
10//! in the next search.
11use crate::util::iter::*;
12use crate::util::parse::*;
13
14type Pair = [usize; 2];
15
16pub fn parse(input: &str) -> Pair {
17    let disks: Vec<Pair> = input.iter_unsigned().skip(1).step_by(2).chunk::<2>().collect();
18    let (part1, step) = solve(&disks, 0, 0, 1);
19    let (part2, _step) = solve(&[[11, 0]], disks.len(), part1, step);
20    [part1, part2]
21}
22
23pub fn part1(results: &Pair) -> usize {
24    results[0]
25}
26
27pub fn part2(results: &Pair) -> usize {
28    results[1]
29}
30
31fn solve(discs: &[Pair], offset: usize, mut time: usize, mut step: usize) -> (usize, usize) {
32    for (o, &[size, position]) in discs.iter().enumerate() {
33        while !(time + offset + o + 1 + position).is_multiple_of(size) {
34            time += step;
35        }
36        step *= size;
37    }
38
39    (time, step)
40}
aoc/year2016/day15.rs

aoc/year2016/
day15.rs
