aoc/year2020/
day13.rs

1//! # Shuttle Search
2//!
3//! Part two is the [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem).
4//! The integers n₁, n₂, ... nₖ map to the bus ids 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::parse::*;
12
13pub struct Input {
14    timestamp: usize,
15    buses: Vec<(usize, usize)>,
16}
17
18pub fn parse(input: &str) -> Input {
19    let lines: Vec<_> = input.lines().collect();
20    let timestamp = lines[0].unsigned();
21    let buses: Vec<_> = lines[1]
22        .split(',')
23        .enumerate()
24        .filter(|&(_, id)| id != "x")
25        .map(|(offset, id)| (offset, id.unsigned()))
26        .collect();
27    Input { timestamp, buses }
28}
29
30pub fn part1(input: &Input) -> usize {
31    let (id, next) = input
32        .buses
33        .iter()
34        .map(|(_, id)| (id, id - input.timestamp % id))
35        .min_by_key(|&(_, next)| next)
36        .unwrap();
37
38    id * next
39}
40
41pub fn part2(input: &Input) -> usize {
42    let (mut time, mut step) = input.buses[0];
43
44    for (offset, id) in &input.buses[1..] {
45        let remainder = id - offset % id;
46
47        while time % id != remainder {
48            time += step;
49        }
50
51        step *= id;
52    }
53
54    time
55}
aoc/year2020/day13.rs

aoc/year2020/
day13.rs
