Advent of Code 2020 Day 13

Today's puzzle for Advent of Code was a rough one if you weren't able to iteratively improve the performance of your solution in part two. Part one was pretty easy to brute-force to find a solution since you were only going through each valid bus one time to figure out when it would be available at the platform after the provided time.  You can pretty easily simply loop through all buses and do the following kind of action Math.ceil((double) bus.id/(double) earliestTime) * bus.id which would give the NEXT time the bus with the given id would be set to depart the stop AFTER the earliestTime (the first input in the file). Since Math.ceil provides the rounded-up value of the input (which is required to be a double to get proper division rules) you know the values that are integers (bus id evenly divides the time) would not be changed but those that are decimals would round up.

For part two the goal was to provide the time at which the first bus in the list departed, the second bus in the list arrived at the next minute, the third bus in the list arrived at the next minute, etc. This problem stated that if the bus in the list was of bus id "x" you could ignore its arrival, but not the index going forward, so looking at the second example list, 17,x,13,19 you need bus 17 to arrive on the time, bus 13 to arrive 2 timepoints after bus 17, and bus 19 to arrive 3 timepoints after bus 19.  Like in part one, the buses only arrive when the time is evenly divisible by their bus id, so in this example, we can illustrate this below in the table:

time  bus 17   bus 13   bus 19
3414    .        .        .
3415    .        .        .
3416    .        .        .
3417    D        .        .
3418    .        .        .
3419    .        D        .
3420    .        .        D
3421    .        .        .
3422    .        .        .
3423    .        .        .
3424    .        .        .
3425    .        .        .
3426    .        .        .
3427    .        .        .

This was provided as an example where the earliest timestamp that matches the list is 3417 (as you can see above in the graphical representation). We are warned in the problem statement that the answer for our input is likely to be larger than 100000000000000 (that's 100 trillion). I already knew to use longs because I figured I should just default to longs now, but this is a situation where a brute-force solution might take too much time, which is likely an even bigger problem. The fortunate situation is that we were provided with enough examples to do some iterative improvements.

I started with brute force (just to see how bad my input was) and found that the brute-force approach was able to get all of the examples without an issue, which meant that any change I made would be able to be tested iteratively. Brute force for this part basically meant that I was incrementing the interval of searches by the id of the 0-index in the bus list. The approach that I took to accomplish this was to take one of the buses, which has an id (the value of the bus in the list) and an offset (index in the list of buses). For part one we were concerned with if the bus arrives at a given time, for part two we are concerned with if at a given time for the FIRST bus in the list, our bus arrives with the specified offset. Part one uses time % bus.id == 0, part two uses (time + bus.offset) % bus.id == 0 for validation. To improve performance, you can change your interval of search by taking the previous interval times the latest found bus in the list of buses and removing that bus from the list as you know all future values increased by the previously working interval times the matched bus id. See the following example for bus with ids 2,9,14.

time   bus 2   bus 9   bus 14
0        D       D       D
1        .       .       .
2        D       .       .
3        .       .       .
4        D       .       .
5        .       .       .
6        D       .       .
7        .       .       .
8        D       .       .
9        .       D       .
10       D       .       .
11       .       .       .
12       D       .       .
13       .       .       .
14       D       .       D
15       .       .       .
16       D       .       .
17       .       .       .
18       D       D       .
19       .       .       .
20       D       .       .
21       .       .       .
22       D       .       .
23       .       .       .
24       D       .       .
25       .       .       .
26 *     D       .       .
27       .       D       .
28       D       .       D
29       .       .       .
30       D       .       .
31       .       .       .

In this example, The following work will happen within the loop:

buses[{id: 2, offset: 0}, {id: 9, offset: 1}, {id: 14, offset: 2}]

time  interval  bus bus_check              action
0     1         2   Yes (0+2)  % 2  is 0   interval = interval * 2
0     2         9   No  (0+1)  % 9  is 1   time = time + interval
2     2         9   No  (2+1)  % 9  is 3   time = time + interval
4     2         9   No  (4+1)  % 9  is 5   time = time + interval
6     2         9   No  (6+1)  % 9  is 7   time = time + interval
8     2         9   Yes (8+1)  % 9  is 0   interval = interval * 9
8     18        14  No  (8+2)  % 14 is 10  time = time + interval
26    18        14  Yes (26+2) % 14 is 0   end loop, time = 26

Had we used the 0-offset bus as the interval, this would take 13 iterations to complete (but could take even longer), however with this work of multiplying the interval continually once a bus is found and using that going forward really reduces the number of iterations completed. Looking at the number of iterations for all of my 6 examples with this methodology:

• Example 1: Got timestamp: 1068781 in 34 loop iterations
• Example 2: Got timestamp: 3417 in 22 loop iterations
• Example 3: Got timestamp: 754018 in 47 loop iterations
• Example 4: Got timestamp: 779210 in 41 loop iterations
• Example 5: Got timestamp: 1261476 in 85 loop iterations
• Example 6: Got timestamp: 1202161486 in 423 loop iterations

For a comparison, the brute force method took the following number of iterations for each example:

• Example 1: Got timestamp: 1068781 in 152684 loop iterations
• Example 2: Got timestamp: 3417 in 202 loop iterations
• Example 3: Got timestamp: 754018 in 11255 loop iterations
• Example 4: Got timestamp: 779210 in 11631 loop iterations
• Example 5: Got timestamp: 1261476 in 18829 loop iterations
• Example 6: Got timestamp: 1202161486 in 671975 loop iterations

For reference, if I were to take my answer for my final input and calculate the number of iterations it would take to calculate properly, it would be 47,236,766,515,393 iterations. (that's 47 trillion iterations).  My current computer's processor is a 8-core 4.22 GHz processor (Ryzen 7 3800X) which means it can do 4,220,000,000 tasks per second, so conservatively, 47 trillion iterations would take 11,200 seconds if it was just doing super simple tasks (typically each logical operation takes multiple clock cycles) so a REAL conservative estimate would probably be 1,120,000 seconds (100 tasks per loop iteration). With the number of seconds it would take to complete that with the brute-force approach, 1.12 million seconds that would be my computer STILL PROCESSING this solution for 13 days. This is why iterative approaches can help, and also why when you first start the first attempt of it with brute force, you know when to stop and change your strategy. My updated strategy only took 507 loop iterations to find the final correct answer of 803,025,030,761,664 for the time, which is a significant improvement, if you ask me.

If you want to join my Advent of Code leaderboard, feel free to join with the code: 699615-aae0e8af.