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 preserve the relative offset at each step
10//! in the next search.
11use crate::util::iter::*;
12use crate::util::parse::*;
13
14type Disc = [usize; 2];
15
16pub fn parse(input: &str) -> Vec<Disc> {
17    input.iter_unsigned().skip(1).step_by(2).chunk::<2>().collect()
18}
19
20pub fn part1(input: &[Disc]) -> usize {
21    solve(input)
22}
23
24pub fn part2(input: &[Disc]) -> usize {
25    let mut modified = input.to_vec();
26    modified.push([11, 0]);
27    solve(&modified)
28}
29
30fn solve(discs: &[Disc]) -> usize {
31    let mut time = 0;
32    let mut step = 1;
33
34    for (offset, &[size, position]) in discs.iter().enumerate() {
35        while (time + offset + 1 + position) % size != 0 {
36            time += step;
37        }
38
39        step *= size;
40    }
41
42    time
43}
aoc/year2016/day15.rs

aoc/year2016/
day15.rs
