Advent of Code 2020 Day 13
Try the simulator for Part 2
Task: Solve for X where...
Part 1
X = Product of two numbers: Id of the next bus to arrive, and the minutes between earliest departure time and that bus's arrival time
Part 2
X = Earliest timestamp where all buses arrive within minutes of one another
Example input
939
7,13,x,x,59,x,31,19
It represents
- Earliest departure time
- List of bus IDs that doubles as each bus's arrival time intervals (e.g. 7 is Bus ID 7 which arrives every 7 minutes)
Part 1
- Formulating an equation to identify the bus arriving soonest
- Solving it manually for my puzzle input
- Solving it with an algorithm
Formulating an equation to identify the bus arriving soonest
The puzzle offers this helpful diagram:
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 . . .
What this shows me:
Using 939 as a baseline
For Bus ID 7:
Last departure was 938
1 minute ago
The remainder after 939/7 = 1 -> 939 - 1 = 938
For Bus ID 13:
Last departure was 936
3 minutes ago
The remainder after 939/13 = 3 -> 939 - 3 = 936
For Bus ID 31:
Last departure was 930
9 minutes ago
The remainder after 939/31 = 9 -> 939 - 9 = 930
For Bus ID 19:
Last departure was 931
8 minutes ago
The remainder after 939/19 = 8 -> 939 - 8 = 931
Confirmed:
Earliest departure time
- (Earliest departure time modulo Bus ID)
-----------------------------------------
Bus ID's just-missed departure time
Now, how do I determine each Bus's next departure time?
Using 939 as a baseline
For Bus ID 7:
Next departure is 945
6 minute from now
(7 - The remainder after 939/7) = 6
For Bus ID 13:
Next departure is 949
10 minutes from now
(13 - The remainder after 939/13) = 10
For Bus ID 59:
Next departure is 944
5 minutes from now
(59 - The remainder after 939/59) = 5
Confirmed:
Bus ID
- (Earliest departure time modulo Bus ID)
--------------------------------------
Bus ID's next departure time
Solving it manually for my puzzle input
- Since my input only had <10 bus ids, I used my browser's console to perform each of these equations, subbing in each bus id
- As expected - and hoped - I got the correct answer
Solving it with an algorithm
Process the input:
Split the input at the new line character to create an array of two elements
Convert the first element into a number
Split the second element at the comma character to create an array of elements
Filter out all 'x' elements
Convert each remaining element into a number
Determine which bus arrives soonest:
For each number
Update an accumulating 2-element array - starting from an array with two elements that are both the earliest departure time - according to the following steps:
If the number generated from subtracting (the remainder after dividing the earliest departure time by the bus ID) from the bus ID is less than the current number stored as the second element in the accumulating array
Updated the accumulating array such that the first item is the bus ID and the second item is the result of the equation above
Calculate the product of bus ID and minutes spent waiting:
For each number in the 2-element array
Accumulate the product of each number
Return the product
Here's a visualization of that algorithm:
Part 2
I knew the x
's would play a role eventually!
The journey that followed:
- I read, re-read, and understood the instructions
- I recognized that I didn't know where to start in creating an algorithm that could solve this puzzle and NOT run over 10 billion times
- I turned to my go-to JavaScript solver, NullDev
- I became elated when noticing their solution was a simple
while
loop inside an array iterator function - I was determined to understand how it worked
- I seized upon the opportunity to build a simulator that leveraged NullDev's algorithm...so I could visualize how it worked
- I built it, saw how it worked, and marveled at its elegance
Here is the simulator using NullDev's algorithm for Part 2
I opted not to finish watching the simulator run on my input.
I left this puzzle with one proudly-earned gold star.
And one more notch on my belt of simulators.
Top comments (0)