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

View post

Only going to post my part 1 solution here, as I cheated and read through the thread in order to figure out part 2. Looking back, the brute force solution would have taken quite a while to show up; glad I didn't just "set and forget."

Anyway, part 1 in Rust. As always, on Github.

use aoc_runner_derive::{aoc, aoc_generator};

#[derive(Debug, Clone)]
struct Bus {
    interval: u128,
    last_pickup: u128,
}

#[derive(Clone)]
struct Timetable {
    depart: usize,
    buses: Vec<Option<Bus>>,
}

impl Bus {
    fn new(interval: u128) -> Bus {
        Bus {
            interval,
            last_pickup: 0,
        }
    }
}
impl Iterator for Bus {
    type Item = u128;
    fn next(&mut self) -> Option<u128> {
        self.last_pickup += self.interval as u128;
        Some(self.last_pickup)
    }
}

#[aoc_generator(day13)]
fn parse_input_day13(input: &str) -> Timetable {
    let lines: Vec<&str> = input.lines().collect();
    let approximate_departure = str::parse(lines.get(0).unwrap());
    let buses = lines.get(1).unwrap().split(",");
    Timetable {
        depart: approximate_departure.unwrap(),
        buses: buses
            .map(|b| {
                match b {
                    "x" => {
                        // Skip out-of-service buses
                        None
                    }
                    _ => Some(Bus::new(str::parse(b).unwrap())),
                }
            })
            .collect(),
    }
}

#[aoc(day13, part1)]
fn find_next_bus(root_input: &Timetable) -> u128 {
    let input = root_input.clone();
    let next_bus = input
        .buses
        .iter()
        .filter_map(|b| match b.as_ref() {
            None => None,
            Some(bus) => Some(Bus {
                interval: bus.interval,
                last_pickup: bus
                    .clone()
                    .take_while(|t| *t < input.depart as u128 + bus.interval)
                    .last()
                    .unwrap(),
            }),
        })
        .min_by(|bus1, bus2| bus1.last_pickup.cmp(&bus2.last_pickup))
        .unwrap();

    println!("{:?}", next_bus);
    next_bus.interval as u128 * (next_bus.last_pickup - input.depart as u128)
}