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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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