VP 26: Bus Schedules (15 pts + 50 extra)

What You Need

Any computer with Python 3. You can also use an online Python environment, such as https://colab.research.google.com

Situation

You need to catch a bus. There are several buses running.

Each bus has a different schedule and ID number. All buses started at time=0 minutes, and their ID number indicates how often the bus leaves.

The bus with ID 5 departs at timestamps 0, 5, 10, 15, and so on.

The bus with ID 11 departs at 0, 11, 22, 33, and so on.

Your input data consists of two lines. The first line is the earliest timestamp you could depart on a bus. The second line lists the bus IDs that are in service; entries that show x are out of service.

Your goal is to figure out the earliest bus you can take. (There will be exactly one such bus.)

For example, consider this input data:

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

The departure times near timestamp 939 are shown below, marked "D":

time   bus 7   bus 13  bus 59  bus 31  bus 19
929      .       .       .       .       .
930      .       .       .       D       .
931      D       .       .       .       D
932      .       .       .       .       .
933      .       .       .       .       .
934      .       .       .       .       .
935      .       .       .       .       .
936      .       D       .       .       .
937      .       .       .       .       .
938      D       .       .       .       .
939      .       .       .       .       .
940      .       .       .       .       .
941      .       .       .       .       .
942      .       .       .       .       .
943      .       .       .       .       .
944      .       .       D       .       .
945      D       .       .       .       .
946      .       .       .       .       .
947      .       .       .       .       .
948      .       .       .       .       .
949      .       D       .       .       .

The earliest bus you could take is bus ID 59. It doesn't depart until timestamp 944, so you would need to wait 944 - 939 = 5 minutes before it departs.

VP 26.1: Earliest Bus (15 pts)
Use this input data:
1008141
17,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,523,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,13,19,x,x,x,23,x,x,x,x,x,x,x,787,x,x,x,x,x,37,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,29
Find the bus number of the earliest bus to take, and the number of minutes you need to wait. Multiply those values together to get the flag.

VP 26.2: Simultaneous Departures (5 pts extra)
Suppose there are only two buses running, IDs 5 and 7.
The bus with ID 5 departs at timestamps 0, 5, 10, 15, 20, and so on.
The bus with ID 7 departs at timestamps 0, 7, 14, 21, and so on.
What's the first time, after timestamp 0, when both buses depart simultaneously again?
That timestamp is the flag.

Two Buses Departing in Order

Suppose there are only two buses running, IDs 5 and 7.

We want to find a time when bus 5 departs, and bus 7 departs one minute later.

The first such time is timestamp 20.
The next time this happens is timestamp 55.

To find all times satisfying that condition, we can combine both routes into a single effective route with ID = 5*7 = 35.

VP 26.3: Three Buses in Order (5 pts extra)
There are three buses running, with IDs 7, 17, and 23.
Find the first timestamp at which bus 7 departs, then bus 17 departs one minute later, and bus 23 departs one minute after that.
Find the effective bus ID for the combination of these three buses.
Multiply the timestamp by the effective combined bus ID to form the flag.

Departures in Order

Find the earliest timestamp such that the first bus ID departs at that time and each subsequent listed bus ID departs at that subsequent minute. (The first line in your input is no longer relevant.)

For example, suppose you have the same list of bus IDs as above:

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

An x in the schedule means there are no constraints on what bus IDs must depart at that time.

This means you are looking for the earliest timestamp (called t) such that:

Bus ID 7 departs at timestamp t.
Bus ID 13 departs one minute after timestamp t.
There are no requirements or restrictions on departures at two or three minutes after timestamp t.
Bus ID 59 departs four minutes after timestamp t.
There are no requirements or restrictions on departures at five minutes after timestamp t.
Bus ID 31 departs six minutes after timestamp t.
Bus ID 19 departs seven minutes after timestamp t.

The only bus departures that matter are the listed bus IDs at their specific offsets from t. Those bus IDs can depart at other times, and other bus IDs can depart at those times. For example, in the list above, because bus ID 19 must depart seven minutes after the timestamp at which bus ID 7 departs, bus ID 7 will always also be departing with bus ID 19 at seven minutes after timestamp t.

In this example, the earliest timestamp at which this occurs is 1068781:

time     bus 7   bus 13  bus 59  bus 31  bus 19
1068773    .       .       .       .       .
1068774    D       .       .       .       .
1068775    .       .       .       .       .
1068776    .       .       .       .       .
1068777    .       .       .       .       .
1068778    .       .       .       .       .
1068779    .       .       .       .       .
1068780    .       .       .       .       .
1068781    D       .       .       .       .
1068782    .       D       .       .       .
1068783    .       .       .       .       .
1068784    .       .       .       .       .
1068785    .       .       D       .       .
1068786    .       .       .       .       .
1068787    .       .       .       D       .
1068788    D       .       .       .       D
1068789    .       .       .       .       .
1068790    .       .       .       .       .
1068791    .       .       .       .       .
1068792    .       .       .       .       .
1068793    .       .       .       .       .
1068794    .       .       .       .       .
1068795    D       D       .       .       .
1068796    .       .       .       .       .
1068797    .       .       .       .       .

In the above example, bus ID 7 departs at timestamp 1068788 (seven minutes after t). This is fine; the only requirement on that minute is that bus ID 19 departs then, and it does.

Representing the Buses

This situation can be represented by a list of tuples, (Bus ID, Delay):

[ (7, 0),
  (13, 1),
  (19, 7),
  (31, 6),
  (59, 4) ]

Combining Buses

Consider only the two bus IDs 7 and 13.

Buses (7, 0) and (13, 1) arrive correctly at t = 77--that is, but 7 arrives at t = 77, and bus 13 arrives at t = 77 + 1.

The combined bus has an ID = 7 * 13 = 91.

The delay of the combined bus is 91 - 77 = 14.

So the list of buses can be simplfied to:

[ (91, 14),
  (19, 7),
  (31, 6),
  (59, 4) ]

Repeating this process several times will eventually reduce the problem to a single bus line, which is easy to solve.

Here are some other examples:

The earliest timestamp that matches the list 17,x,13,19 is 3417.
67,7,59,61 first occurs at timestamp 754018.
67,x,7,59,61 first occurs at timestamp 779210.
67,7,x,59,61 first occurs at timestamp 1261476.
1789,37,47,1889 first occurs at timestamp 1202161486.

VP 26.4: Result (40 pts extra)
Use this input data:
1008141
17,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,523,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,13,19,x,x,x,23,x,x,x,x,x,x,x,787,x,x,x,x,x,37,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,29
What is the earliest timestamp such that all of the listed bus IDs depart at offsets matching their positions in the list? Hint: it is very large, larger than 100000000000000!
That timestamp is the flag.

Source

Adapted from the Advent of Code.

Posted 9-7-24
Explanation of combining bus routes added 9-26-24
Video added 10-9-24