Advent of Code 2020 day 13
This was a struggle for me. Part one was easy enough (haven’t even bothered to include my code for that below), but I chipped away at part two for several hours before getting a solution.
The subreddit was full of people talking about Chinese Remainder Theorem which has a Wikipedia page that might as well be smeared across my wall in custard. The acronym “LCM” kept coming up as well, which I now know stands for “lowest common multiple”, and does a much better job of describing itself than the Chinese remainder theorem does.
Many sheets of paper later I realised how LCM could be used, basically to keep increasing the “period” whenever more than one of the buses were in sync.
No fun - all mathematics and pattern recognition. As a result the code you see below is crap because I can’t face looking at this puzzle any more now I have my answer.
As I type day 14’s puzzle has been out for 20 minutes as well, so I’m going to post this and see what the next one brings.
def low_com_mul(i)
return i.reduce(1, :lcm)
end
buses = INPUT.strip.lines.last.split(',').map { |e| e == 'x' ? nil : e.to_i }
departures = Array.new(buses)
max_bus = buses.compact.max
max_bus_index = buses.index(max_bus)
period = max_bus
time = max_bus - max_bus_index
synced_buses = []
while departures.compact.any? { |e| e != 0 }
if low_com_mul(synced_buses) > period
period = low_com_mul(synced_buses)
puts "Period changed to #{period}"
end
time += period
synced_buses.clear
departures = buses.each_with_index.map do |e, i|
unless e == nil
bus_offset = ((time + i) % e) # 0 if the bus is in the right place at the right time
synced_buses << e if bus_offset == 0
bus_offset
end
end
end
puts time