DEV Community

Cover image for Shuttle Search
Robert Mion
Robert Mion

Posted on

Shuttle Search

#adventofcode #programming #algorithms #computerscience

Advent of Code 2020 Day 13

Try the simulator for Part 2

Simulator of NullDev's algorithm 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
Enter fullscreen mode Exit fullscreen mode

Part 2

X = Earliest timestamp where all buses arrive within minutes of one another
Enter fullscreen mode Exit fullscreen mode

Example input 

939
7,13,x,x,59,x,31,19
Enter fullscreen mode Exit fullscreen mode

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

  1. Formulating an equation to identify the bus arriving soonest
  2. Solving it manually for my puzzle input
  3. 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       .       .       .
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Confirmed:

  Earliest departure time 
- (Earliest departure time modulo Bus ID)
-----------------------------------------
Bus ID's just-missed departure time
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Confirmed:

  Bus ID
- (Earliest departure time modulo Bus ID)
--------------------------------------
Bus ID's next departure time
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Here's a visualization of that algorithm:
Algorithm for Part 1

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
Simulator of 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)

Read next

dm8ry profile image

The Strength of Vertica DB: A Case Study in Sales Analytics

Dmitry Romanoff -

mdarifulhaque profile image

1545. Find Kth Bit in Nth Binary String

MD ARIFUL HAQUE -

zanepearton profile image

Rust + WASI: Application Monitoring

Zane -

mikeyoung44 profile image

A beginner's guide to the Stable-Diffusion-Xl-Base-1.0 model by Stabilityai on Huggingface

Mike Young -