Discussion on: Advent of Code 2020 Solution Megathread - Day 13: Shuttle Search

[Benjamin Trent]

No way I could figure out part 2 without googling. I was playing around with least common divisor + gcd + clever looping. Finally googling around I found the chinese remainder theorem.

rust rust rust :)

use std::usize::MAX;
use std::collections::HashMap;

#[aoc(day13, part1)]
fn bus_wait_time(input: &(usize, HashMap<usize, usize>)) -> usize {
    let time = input.0;
    let busses = &input.1;
    let mut min_time = MAX;
    let mut best_bus_id = 0;
    for (&i, bus) in busses.iter() {
        let r = time % *bus;
        let waiting = *bus + time - r;
        if waiting < min_time {
            min_time = waiting;
            best_bus_id = i;
        }
    }
    busses[&best_bus_id] * (min_time - time)
}

#[aoc(day13, part2)]
fn magic_timestamp(input: &(usize, HashMap<usize, usize>)) -> usize {
    let mut buses:Vec<(usize, usize)> = input.1.iter().map(|(&pos, &id)| (pos, id)).collect();
    buses.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
    let mut timestamp = 0;
    let mut inc = buses[0].1;
    for &(i, bus) in &buses[1..] {
        // friggin CRT sieve garbage see: https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Computation
        while (timestamp + i) % bus != 0 {
            timestamp += inc;
        }
        // adjust for the next modulo
        inc *= bus;
    }
    timestamp
}

[Christopher Kruse]

Man, this turned out really concise. Also, thank you for letting me shamelessly steal your logic for part 2 :D