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 }
puts "First task answer: #{(first_arrival.last - timestamp) * first_arrival.first}"

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)

puts "Second task answer: #{chinese_remainder(remainders_hash.keys, remainders_h