From 12f551dbfef138880b29ba6abe4576714ae942cb Mon Sep 17 00:00:00 2001 From: blenovo Date: Sat, 2 Aug 2025 03:13:50 +0200 Subject: summer warmup sesh part 2 --- 2020/aoc2020-d13.py | 46 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 46 insertions(+) create mode 100644 2020/aoc2020-d13.py (limited to '2020/aoc2020-d13.py') diff --git a/2020/aoc2020-d13.py b/2020/aoc2020-d13.py new file mode 100644 index 0000000..dd0d0d1 --- /dev/null +++ b/2020/aoc2020-d13.py @@ -0,0 +1,46 @@ +#advent of code 2020 +#day 13 +#kinda cheated, the chinese remainder theorem (CRT) was copy-pasted from google search results +#the source where I was reading how it works didn't really provide a good example +#will definitely look it up later :) + +def gcd_extended(a, b): + if a == 0: + return b, 0, 1 + gcd, x1, y1 = gcd_extended(b % a, a) + x = y1 - (b // a) * x1 + y = x1 + return gcd, x, y + +def find_min_x(num, rem): + prod = 1 + for n in num: + prod *= n + result = 0 + for i in range(len(num)): + prod_i = prod // num[i] + _, inv_i, _ = gcd_extended(prod_i, num[i]) + result += rem[i] * prod_i * inv_i + return result % prod + +PuzzleInput = open("13.in","r").read().split("\n"); +timestamp = int(PuzzleInput[0]); +buses = PuzzleInput[1].split(",");f b != "x"]; + +times = dict(); +BusList = []; +OffsetList = []; +for index, bus in enumerate(buses): + if bus == "x": continue; + bus = int(bus); + BusList.append(bus); + OffsetList.append(bus-index); + d = timestamp%bus; + NextStop = timestamp-d+bus; + times[NextStop] = (bus,bus-d); + +busID, WaitTime = times[min(times)]; +p1 = busID * WaitTime; +p2 = find_min_x(BusList,OffsetList); #CRT +print("part 1 =",p1); +print("part 2 =",p2); -- cgit v1.2.3