Discussion on: Advent of Code 2020 Solution Megathread - Day 13: Shuttle Search

[Shalvah]

Thanks for this. I was really stuck on this; came on here and saw folks mentioning a new theory (which bummed me out). I had been trying to figure something out with LCM, and your solution showed me what I'd been missing. Here's the core of mine:

current_timestamp = ids.first.first

ids.each_with_index do |(bus_id, offset), index|
  next if index == 0

  # At this point, we start off with a t that's valid for bus 1
  # Second iteration will add the period (bus 1's cycle) to t until it finds a valid t
  # Subsequent iterations will add the period (LCM of already found numbers)
  # Why does this work? Because the cycle repeats over the period.
  # So, if we've found a t that has b2 and b1 at certain positions,
  # Then using a period of lcm(b1, b2) will have them in the same positions again. (LCM == coinciding cycles)
  # So we just need to do this until we find where position(b3) = position(b2) + offset
  # Then update our period and go again for the next bus.
  period = ids[0..index - 1].reduce(1) { |acc, (id, _)| acc.lcm(id) }
  loop do
    difference = bus_id - (current_timestamp % bus_id)
    break if difference == (offset % bus_id)
    current_timestamp += period
  end
end

p current_timestamp