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

[Derk-Jan Karrenbeld]

I don't know about those theorems. It's a prime factorisation problem (and evidently all bus numbers are prime numbers, so that makes it even easier). My Ruby solution is general purpose (so also non-prime busses) but 🤷

require 'prime'
require 'benchmark'

source = 'input.txt'

timestamp, schedule_line = File.readlines(source)
schedule = schedule_line.split(',').map { |x| x.chomp }

busses = schedule
  .each_with_index
  .map { |bus, offset| bus != 'x' ? [bus.to_i, offset] : nil }
  .compact

current_timestamp = 0

# This is unnecessary because all bus numbers are prime numbers, but this more
# general solution works for busses that are non-prime!
#
# In this exercise, the result is an array with one element: the first bus number:
# [7]
timestamp_factors = busses.shift.first.prime_division.map(&:first)

Benchmark.bm do |x|
  x.report do
    busses.each do |(bus, offset)|
      # The first bus will depart at t + 0 every t = bus * i. In fact, for any bus it's
      # true that once you find a valid t where t + offset = bus * i, the next
      # valid t for that bus is (t + bus).
      #
      # So you can skip all the ts inbetween.
      skip_factor = timestamp_factors.inject(&:*)

      # Find the next t for which [t + offset = bus * i].
      loop do
        minutes_to_departure = bus - (current_timestamp % bus)
        break if minutes_to_departure == offset % bus
        current_timestamp += skip_factor
      end

      # If all busses are prime numbers (they are in AoC), the prime-only
      # solution would be:
      #
      # timestamp_factors.push(bus)
      #
      # The general purpose solution looks like this:
      timestamp_factors.push(*bus.prime_division.map(&:first))
      timestamp_factors.uniq!
    end
  end
end

puts current_timestamp

[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