13b.md

Day 13 - Shuttle Search - Part 2

You're given a bus schedule like such:

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

Which means:

• Bus ID 7 arrives at time t. It repeats every 7t's. So It'll arrive again at t + 7, and t + 14, and so on. All buses repeat based on their ID.
• Bus ID 13 arrives at t + 1. Just like 7, this would repeat every 13t. So t + 14, t + 27, etc.
• Bus ID 59 arrives at t + 4.
• Bus ID 31 arrives at t + 6.
• Bus ID 19 arrives at t + 7.

The x are bus schedules as well, but they don't have any constraint on the problem we're going to give.

We're trying to figure out the smallest value of t that satisfies the schedule above.

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    .       .       .       .       .

The fact that bus 7 and bus 19 both depart at the same time at the very end is not relevant. Just a coindence for this example.

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.

What is the earliest timestamp such that all of the listed bus IDs depart at offsets matching their positions in the list?

Solution

One solution is to just find the largest number in our bus schedule, and make sure t - idx is divisible by that large number, where idx is the index where the largest number is in the array. Whenever we increment t, we increment by that largest number, because t always has to be divisible by the largest number. In this scenario, our step is largest number.

export function getEarliestTimestamp({ busSchedule }: Simulation) {
  const [maxNumId, maxNum] = busSchedule.reduce(
    (max, curr, idx) => (curr > max[1] ? [idx, curr] : max),
    [-1, 0]
  );

  // Say the max number is at index 4, and it's 97.
  // Say the first number is 13 (at index 0 obv).
  // Any timestamp we have must be divisible by 97, which allows us to use that
  // as our increment (see end of while loop) below.
  // We start our timestamp at maxNum - maxNumId (or 93) because we'll add idx
  // back to it in the if statement inside for-loop. So it'll be checking if 93
  // + 4 + 97x is divisible by 97 when it gets to 97, which must always be true.
  let timestamp = maxNum - maxNumId;
  while (timestamp < Number.MAX_SAFE_INTEGER) {
    let solutionFound = true;
    for (let i = 0; i < busSchedule.length; i++) {
      if (isNaN(busSchedule[i])) {
        continue;
      }
      if ((timestamp + i) % busSchedule[i] !== 0) {
        solutionFound = false;
        break;
      }
    }
    if (solutionFound) {
      break;
    }
    timestamp += maxNum;
  }
  return timestamp;
}

This solution took 50mins to solve the input given.

Better Solution (took single-digit milliseconds)

Say our input is [7, 13, 19, 23].

1. Set our step to 7 and timestamp to 7 (because it's the first element in the array). Whenever we change timestamp, it must ALWAYS be divisible by 7. So we add by 7 or some multiple of 7. E.g., step += 7, or step += 7*4.
2. Start a for-loop, iterating over the rest of the elements in our array 13, 19, 23.
   • In each iteration of this for-loop, add step (7 atm) to the timestamp until timestamp + 1 is divisible by 13.
   • Once we do find such a number, we need to make sure timestamp + 1 continues to stay divisible by 13. In our step now, we need to add 13 to it always or some multiple of 13.
   • But we also need to make sure timestamp stays divisible by 7.
   • We can solve both of these problems by making our step = 7 * 13. Recall that as long as we add 7 or some multiple of 7, we're good. That multiple is 13. Likewise, as long as we add 13 or some multiple of 13, we're good. That multiple is 7.
   • Now we increase the timestamp by 7 * 13, which is a much bigger number!
   • As soon as we find a timestamp that causes timestamp + 2 to be divisible by 19, we can increase our step to step = 7 * 13 * 19, making our loop even faster.

export function getEarliestTimestamp({ busSchedule }: Simulation) {
  let timestamp = busSchedule[0];
  let step = busSchedule[0];

  for (let i = 1; i < busSchedule.length; i++) {
    if (isNaN(busSchedule[i])) {
      continue;
    }
    while ((timestamp + i) % busSchedule[i] !== 0) {
      timestamp += step;
    }
    step = step * busSchedule[i];
  }
  return timestamp;
}

This took a handful of milliseconds to solve the input, as opposed to 50 minutes like the previous one.

Non-prime Input Array

If the numbers in our input array weren't all prime numbers, we'd have to use LCM to make sure we find the smallest timestamp. E.g., if our input array was [7, 14, 19, 23], when we got to 14, we couldn't change our step to 7 * 14. We'd just change it to 14 because LCM(7, 14) = 14. In simple terms, by increasing our timestamp by 14, we're also increasing the timestamp by 7 * 2, so it is guaranteed to be divisible by 7 as well.

Whenever we were ready to move on to the next input, we could just do LCM with all the previous inputs. E.g., if we just got done with 19, we'd do LCM(7, 14, 19). OR We could just do step = LCM(step, 19). Both would achieve the same thing.