Day 13 starts out easy enough. We made it to an island (not our destination) and now need to take a bus to the local airport. The problem states:

Bus schedules are defined based on a timestamp that measures the number of minutes since some fixed reference point in the past. At timestamp 0, every bus simultaneously departed from the sea port. After that, each bus travels to the airport, then various other locations, and finally returns to the sea port to repeat its journey forever.

The time this loop takes a particular bus is also its ID number: the bus with ID 5 departs from the sea port at timestamps 0, 5, 10, 15, and so on. The bus with ID 11 departs at 0, 11, 22, 33, and so on. If you are there when the bus departs, you can ride that bus to the airport!

For part 1 we need to find out the first bus that will come after we arrive.
The input looks like:

939

7,13,x,x,59,x,31,19

Where 939 is when we arrive, and the list of numbers tell which buses are in service (x's seem to be out of service buses, but I’m guessing they will be important in part 2, so we can’t just toss them. For now I’ll turn them into -1s.).

I solve part 1 by taking the target time (939 in the example) dividing by each of the bus times, then rounding up and multiplying by the bus time. In short:

next_bus.append(bus * math.ceil(ourtime / bus))

Then I pick the minimum value and get my first star.

Part 2 is tough. We need to find a time when our given buses will arrive sequentially -- for the example, we want bus 7 to arrive, then 1 minute later bus 13, then nothing for 2 minutes, then at 4 minutes bus 59, etc. I was stumped on this for awhile. Here are my notes:

We could brute force it, but we have a clue that we need to be smarter. There should be a math solution.

In terms of brute forcing, I can make it easier by stepping through the length of my first bus (23) and only checking the other buses when it departs -- that helps.

Way too slow!

Least common denominator would show when they all arrive at the same time, but not sequentially. Is there a way to reduce our problem to LCD?

I tried to math my way out of the problem:

I thought about using modulo to quickly check the next buses.

def part2_fasterbutnotenough(busses):

    (my_code, my_bus) = find_my_code(busses)
    print("my code", my_code)
    print("my_bus", my_bus)

    step = -1

    while True:
        answer = True
        step+=1
        ourtime = step * my_bus[0]
        if step % 1000000 == 0:
           print("time stamp", ourtime)


        for (code, bus) in zip(my_code[1:], my_bus[1:]):

            if (ourtime + code) % bus != 0:
                answer = False
                break
        if answer == True:
            print('ourtime', ourtime)
            return(ourtime)

I let the code run.... and run...

I finally got a clue from a friend -- Chinese remainder theorem. https://en.wikipedia.org/wiki/Chinese_remainder_theorem. I read up. I still had no clue. But I felt like my modulo idea was definitely going in the right direction. I read a bit on reddit (this is now 30+ hours after the puzzle came out -- time to get some help.).

I found a solution that made sense to me and was easy to implement.

My solution is (pardon the mixing of 'busses' and 'buses' -- I'm an American living in Europe and my spelling is currently iterating between American and British spellings).

def part2(busses):

    (my_code, my_bus) = find_my_code(busses)

    #we start off knowing that we'll have to step in chunks of time equal to the first bus's loop
    step = my_bus[0]
    time = 0

    #now we step through the rest of the buses and find their associated factors
    for (code, bus) in zip(my_code[1:], my_bus[1:]):
        while (time + code) % bus != 0:
            time+=step
        #the above while loop finishes when we find the step size for bus n, so we increment our step size by that
        step *= bus
    return(time)

This code ran nearly instantaneously and got me my second star.

This puzzle was a hard one -- what more does Advent of Code have in store for us?