Advent of Code 2020: Day 13 (Ruby solution)

Subscribe to my newsletter and never miss my upcoming articles

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
Tags:#ruby

No Comments Yet