# Advent of Code 2020: Day 13 (Ruby solution)

·

Today's puzzle is not so easy.

The first task is about finding the closest arrival timestamp knowing how often each bus courses. This part is trivial:

``````file = File.read('inputs/day13.txt')
timestamp = file.lines.first.to_i
bus_lines = file.lines.last.split(',').map{|n| n.to_i if n.match(/\d+/)}
arrivals = bus_lines.compact.map do |line|
{line => (timestamp.to_f / line).ceil * line}
end.inject(:merge)

first_arrival = arrivals.min_by { |k, v| v }
``````

But the second one requires some non-elemental mathematical knowledge. Specifically, you should be aware about Chinese Remainder Theorem. I used this implementation. Here is the entire solution:

``````def extended_gcd(a, b)
last_remainder, remainder = a.abs, b.abs
x, last_x, y, last_y = 0, 1, 1, 0
while remainder != 0
last_remainder, (quotient, remainder) = remainder, last_remainder.divmod(remainder)
x, last_x = last_x - quotient * x, x
y, last_y = last_y - quotient * y, y
end
return last_remainder, last_x * (a < 0 ? -1 : 1)
end

def invmod(e, et)
g, x = extended_gcd(e, et)
if g != 1
raise 'Multiplicative inverse modulo does not exist!'
end
x % et
end

def chinese_remainder(mods, remainders)
max = mods.inject(:*) # product of all moduli
series = remainders.zip(mods).map { |r, m| (r * max * invmod(max / m, m) / m) }
series.inject(:+) % max
end

remainders_hash = bus_lines.each_with_index.map do |value, index|
{value.to_i => value.to_i - index} if value
end.compact.inject(:merge)