aoc-2020-zig

Advent of Code 2020 Solutions in Zig
git clone https://git.sinitax.com/sinitax/aoc-2020-zig
Log | Files | Refs | README | sfeed.txt

part2 (3645B)

      1--- Part Two ---
      2
      3The shuttle company is running a contest: one gold coin for anyone that can find the earliest
      4timestamp such that the first bus ID departs at that time and each subsequent listed bus ID departs
      5at that subsequent minute. (The first line in your input is no longer relevant.)
      6
      7For example, suppose you have the same list of bus IDs as above:
      8
      97,13,x,x,59,x,31,19
     10An x in the schedule means there are no constraints on what bus IDs must depart at that time.
     11
     12This means you are looking for the earliest timestamp (called t) such that:
     13
     14
     15 - Bus ID 7 departs at timestamp t.
     16 - Bus ID 13 departs one minute after timestamp t.
     17 - There are no requirements or restrictions on departures at two or three minutes after timestamp
     18t.
     19 - Bus ID 59 departs four minutes after timestamp t.
     20 - There are no requirements or restrictions on departures at five minutes after timestamp t.
     21 - Bus ID 31 departs six minutes after timestamp t.
     22 - Bus ID 19 departs seven minutes after timestamp t.
     23
     24
     25The only bus departures that matter are the listed bus IDs at their specific offsets from t. Those
     26bus IDs can depart at other times, and other bus IDs can depart at those times.  For example, in the
     27list above, because bus ID 19 must depart seven minutes after the timestamp at which bus ID 7
     28departs, bus ID 7 will always also be departing with bus ID 19 at seven minutes after
     29timestamp t.
     30
     31In this example, the earliest timestamp at which this occurs is 1068781:
     32
     33time     bus 7   bus 13  bus 59  bus 31  bus 19
     341068773    .       .       .       .       .
     351068774    D       .       .       .       .
     361068775    .       .       .       .       .
     371068776    .       .       .       .       .
     381068777    .       .       .       .       .
     391068778    .       .       .       .       .
     401068779    .       .       .       .       .
     411068780    .       .       .       .       .
     421068781    D       .       .       .       .
     431068782    .       D       .       .       .
     441068783    .       .       .       .       .
     451068784    .       .       .       .       .
     461068785    .       .       D       .       .
     471068786    .       .       .       .       .
     481068787    .       .       .       D       .
     491068788    D       .       .       .       D
     501068789    .       .       .       .       .
     511068790    .       .       .       .       .
     521068791    .       .       .       .       .
     531068792    .       .       .       .       .
     541068793    .       .       .       .       .
     551068794    .       .       .       .       .
     561068795    D       D       .       .       .
     571068796    .       .       .       .       .
     581068797    .       .       .       .       .
     59
     60In the above example, bus ID 7 departs at timestamp 1068788 (seven minutes after t). This is fine;
     61the only requirement on that minute is that bus ID 19 departs then, and it does.
     62
     63Here are some other examples:
     64
     65
     66 - The earliest timestamp that matches the list 17,x,13,19 is 3417.
     67 - 67,7,59,61 first occurs at timestamp 754018.
     68 - 67,x,7,59,61 first occurs at timestamp 779210.
     69 - 67,7,x,59,61 first occurs at timestamp 1261476.
     70 - 1789,37,47,1889 first occurs at timestamp 1202161486.
     71
     72
     73However, with so many bus IDs in your list, surely the actual earliest timestamp will be larger than
     74100000000000000!
     75
     76What is the earliest timestamp such that all of the listed bus IDs depart at offsets
     77matching their positions in the list?
     78
     79