Advent of Code 2020 Day 13
Try the simulator for Part 2
Task: Solve for X where...
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
X = Earliest timestamp where all buses arrive within minutes of one another
- 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)
- 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
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
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:
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 became elated when noticing their solution was a simple
whileloop 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)