75 lines
2.5 KiB
Rust
75 lines
2.5 KiB
Rust
use std::io::BufRead;
|
|
|
|
fn first_bus<F: BufRead> (input: F) -> u32 {
|
|
let lines: Vec<_> = input.lines().flat_map(|l| l.ok()).collect();
|
|
let ts: u32 = lines[0].parse().unwrap();
|
|
lines[1].split(',')
|
|
.flat_map(|id| id.parse::<u32>().ok())
|
|
.map(|id| (id, id - (ts % id)))
|
|
.min_by_key(|item| item.1).map(|item| item.0 * item.1).unwrap()
|
|
}
|
|
|
|
|
|
pub fn part1<F: BufRead> (input: F) {
|
|
println!("{}", first_bus(input));
|
|
}
|
|
|
|
// Voir https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_restes_chinois#Exemple
|
|
fn solver(mods: Vec<u64>, remainders: Vec<u64>) -> (u64, u64) {
|
|
let product = mods.iter().fold(1, |acc, m| acc * m);
|
|
let mut mods_products = Vec::new();
|
|
for current_mod in mods.iter() {
|
|
let mod_product = mods.iter().filter(|m| *m != current_mod).fold(1, |acc, m| acc * m);
|
|
let mut multiple_prod = mod_product;
|
|
while multiple_prod % current_mod != 1 {
|
|
multiple_prod += mod_product;
|
|
}
|
|
mods_products.push(multiple_prod);
|
|
}
|
|
let solution = mods_products.iter().zip(remainders.iter()).fold(0, |acc, (m, r)| acc + m * r);
|
|
(solution % product , product)
|
|
}
|
|
|
|
fn find_first_timestamp(buses: Vec<Option<u64>>) -> u64 {
|
|
let mods = buses.iter().filter_map(|x| *x).collect();
|
|
let remainders = buses.iter().enumerate().filter_map(|(i, bus_id)| bus_id.map(|id| id - (i as u64 % id))).collect();
|
|
solver(mods, remainders).0
|
|
}
|
|
|
|
pub fn part2<F: BufRead> (input: F) {
|
|
let schedule = input.lines().skip(1).flat_map(|l| l.ok()).next().unwrap();
|
|
println!("{}", find_first_timestamp(schedule.split(',').map(|id| id.parse().ok()).collect()));
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
#[test]
|
|
pub fn test_parse() {
|
|
let input = "939\n7,13,x,x,59,x,31,19".as_bytes();
|
|
assert_eq!(first_bus(input), 295);
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_first_timestamp() {
|
|
let test_cases = [
|
|
(1068781, "7,13,x,x,59,x,31,19"),
|
|
(3417, "17,x,13,19"),
|
|
(754018, "67,7,59,61"),
|
|
(779210, "67,x,7,59,61"),
|
|
(1261476, "67,7,x,59,61"),
|
|
(1202161486, "1789,37,47,1889"),
|
|
];
|
|
for (res, input) in test_cases.iter() {
|
|
assert_eq!(*res, find_first_timestamp(input.split(',').map(|id| id.parse().ok()).collect()));
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_solver() {
|
|
let mods = vec![3, 5, 7];
|
|
let remainders = vec![2, 3, 2];
|
|
assert_eq!(solver(mods, remainders), (23, 105));
|
|
}
|
|
}
|