aoc2020/src/bin/day13.rs

const INPUT: &str = include_str!("../../data/day13");

struct Input {
	now: i128,
	bus_intervals: Vec<Option<i128>>,
}

impl Input {
	fn parse(data: &str) -> Self {
		let mut lines = data.lines();
		let now = lines.next().unwrap().parse::<i128>().unwrap();
		let bus_intervals = lines.next().unwrap().split(',').map(|part| {
			if part == "x" {
				None
			} else {
				Some(part.parse::<i128>().unwrap())
			}
		}).collect();
		Self { now, bus_intervals }
	}
}

fn extended_gcd(a: i128, b: i128) -> (i128, i128, i128) {
	// invariant: r == s*a + t*b
	// old: .0, current: .1
	let mut r = (a as i128, b as i128);
	let mut s = (1, 0);
	let mut t = (0, 1);

	while r.1 != 0 {
		let q = r.0 / r.1;
		r = (r.1, r.0 - q * r.1);
		s = (s.1, s.0 - q * s.1);
		t = (t.1, t.0 - q * t.1);
	}
	(r.0 as i128, s.0 as i128, t.0 as i128)
}


fn main() {
	let input = Input::parse(INPUT);
	let (wait, interval) = input.bus_intervals.iter().filter_map(|&interval| {
		let interval = interval?;
		let wait = interval - ((input.now - 1) % interval) - 1;
		Some((wait, interval))
	}).min().unwrap();
	println!("Waiting {} minutes for bus {}: {}", wait, interval, wait * interval);

	// searching T: T == offset (mod interval)
	let mut offs_interval: Vec<(i128, i128)> = input.bus_intervals.iter().enumerate().filter_map(|(ndx, &interval)| {
		let interval = interval?;
		// T + ndx == 0 (mod interval)
		// => offset == -ndx (mod interval)
		let offset = (interval - (ndx as i128) % interval) % interval;
		Some((offset, interval))
	}).collect();
	// println!("{:?}", offs_interval);
	let start = offs_interval.remove(0);
	let result = offs_interval.into_iter().fold(start, |(a_off, a_int), (b_off, b_int)| {
		let (g, s, t) = extended_gcd(a_int, b_int);
		assert_eq!(a_off % g, b_off % g);
		let ai = a_int / g;
		let bi = b_int / g;
		let next_int = ai * bi * g;
		let next_off = a_off * t * bi + b_off * s * ai;
		((next_off % next_int + next_int) % next_int, next_int)
	});
	println!("Requested pattern occurs at: {}", result.0);
}