Advent of Code: Day #13 - Shuttle Search

Today we need to find the right shuttle bus to get to the airport!

Find the earliest time you can depart given a time which you must depart after and a list of services and how often they run.

Reading in the data

The first line in the input.txt was the earliest time we can depart and the second line is a comma separated list.

def read_data(path):
    with open(path) as f:
        lines = f.readlines()
        time = int(lines[0].rstrip())
        dataset = lines[1].strip().split(",")

    return time, dataset

The Solution

To solve this i decided to do an integer division of the earliest time we can depart and how often the bus runs. This will give us a value, when multiplied by how often the bus runs, close to the time we desire. We then just increment this multiplier until we reach a time that is latter than the earliest time. We repeat this for all busses until we have found the first possible bus we can catch.

def task_one(time, dataset):
    bus_timetable = sorted([int(i) for i in dataset if i != "x"])

    time_waiting = {}

    for bus in bus_timetable:
        # No point starting at 0, by taking the integer
        # remainder we will always be bellow time bu a little
        mutli = time // bus
        sum = 0
        while sum <= time:
            sum = bus * mutli
            mutli += 1
        time_waiting[bus] = sum - time

    # Find the smallest wait
    sort = {k: v for k, v in sorted(time_waiting.items(), key=lambda item: item[1])}
    key = list(sort.keys())[0]

The Solution

For task two we are tasked with finding the first time that all busses depart sequentially. To start I removed the * from the dataset and transformed it to be pairs of (index, bus_id) from there we loop through every bus and see if the time stamp + the index is a multiple of the bus ID (If so a bus will depart at that time stamp). We then multiply the 'jump' value by the current bus_id to keep the ratio correct. Once we have gone through all busses we have our time stamp.

def task_two(data):
    # Generate array of tuple (index, bus_id)
    data = [(i, int(bus_id)) for i, bus_id in enumerate(data) if bus_id != 'x']
    # First Bus ID
    jump = data[0][1]
    time_stamp = 0
    # For busses after the first
    for delta, bus_id in data[1:]:
        while (time_stamp + delta) % bus_id != 0:
            time_stamp += jump
        jump *= bus_id
    return time_stamp