## DEV Community is a community of 700,827 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 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'

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:
# 
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
``````