From 15662865f0886209d871a7225bfc62cffd2e0783 Mon Sep 17 00:00:00 2001 From: blenovo Date: Tue, 4 Mar 2025 15:37:55 +0100 Subject: transfer from previous server --- 2018/aoc2018-d01.py | 32 +++++ 2018/aoc2018-d03.py | 77 +++++++++++ 2018/aoc2018-d04-1.py | 123 +++++++++++++++++ 2018/aoc2018-d05-1.py | 60 +++++++++ 2018/aoc2018-d05-2.py | 72 ++++++++++ 2018/aoc2018-d06.py | 140 ++++++++++++++++++++ 2018/aoc2018-d07-1.py | 116 ++++++++++++++++ 2018/aoc2018-d07-2.py | 190 ++++++++++++++++++++++++++ 2018/aoc2018-d08-1.py | 31 +++++ 2018/aoc2018-d08-2.py | 51 +++++++ 2018/aoc2018-d09.py | 50 +++++++ 2018/aoc2018-d10.py | 88 +++++++++++++ 2018/aoc2018-d11-1.py | 75 +++++++++++ 2018/aoc2018-d11-2.py | 108 +++++++++++++++ 2018/aoc2018-d12.py | 68 ++++++++++ 2018/aoc2018-d13.py | 195 +++++++++++++++++++++++++++ 2018/aoc2018-d14.py | 66 ++++++++++ 2018/aoc2018-d15-1.py | 324 +++++++++++++++++++++++++++++++++++++++++++++ 2018/aoc2018-d16.py | 359 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2018/aoc2018-d17.py | 144 ++++++++++++++++++++ 2018/aoc2018-d18.py | 131 ++++++++++++++++++ 2018/aoc2018-d19.py | 180 +++++++++++++++++++++++++ 2018/aoc2018-d20.py | 115 ++++++++++++++++ 2018/aoc2018-d21.py | 253 +++++++++++++++++++++++++++++++++++ 2018/aoc2018-d22.py | 136 +++++++++++++++++++ 2018/aoc2018-d23-1.py | 47 +++++++ 2018/aoc2018-d24.py | 211 +++++++++++++++++++++++++++++ 2018/aoc2018-d25.py | 69 ++++++++++ 28 files changed, 3511 insertions(+) create mode 100644 2018/aoc2018-d01.py create mode 100644 2018/aoc2018-d03.py create mode 100644 2018/aoc2018-d04-1.py create mode 100644 2018/aoc2018-d05-1.py create mode 100644 2018/aoc2018-d05-2.py create mode 100755 2018/aoc2018-d06.py create mode 100755 2018/aoc2018-d07-1.py create mode 100755 2018/aoc2018-d07-2.py create mode 100755 2018/aoc2018-d08-1.py create mode 100755 2018/aoc2018-d08-2.py create mode 100644 2018/aoc2018-d09.py create mode 100755 2018/aoc2018-d10.py create mode 100755 2018/aoc2018-d11-1.py create mode 100755 2018/aoc2018-d11-2.py create mode 100644 2018/aoc2018-d12.py create mode 100644 2018/aoc2018-d13.py create mode 100644 2018/aoc2018-d14.py create mode 100644 2018/aoc2018-d15-1.py create mode 100644 2018/aoc2018-d16.py create mode 100644 2018/aoc2018-d17.py create mode 100644 2018/aoc2018-d18.py create mode 100644 2018/aoc2018-d19.py create mode 100644 2018/aoc2018-d20.py create mode 100644 2018/aoc2018-d21.py create mode 100644 2018/aoc2018-d22.py create mode 100644 2018/aoc2018-d23-1.py create mode 100644 2018/aoc2018-d24.py create mode 100644 2018/aoc2018-d25.py (limited to '2018') diff --git a/2018/aoc2018-d01.py b/2018/aoc2018-d01.py new file mode 100644 index 0000000..ee8bab2 --- /dev/null +++ b/2018/aoc2018-d01.py @@ -0,0 +1,32 @@ +print(); +f = open("input"); + +part1 = 0; +results = []; +not_found = True; +loopcount = 0; +myinput = []; + +for i in f: + myinput.append(int(i)); + +while not_found: + for i in myinput: + #print(i, "endofline"); + part1 += i; + results.append(part1); + #for x in results: + if (results.count(part1) > 1): + part2 = part1; + print(part2); + not_found = False; + break; + loopcount += 1; + #print("loop", loopcount); + +#results.sort(); +#for i in results: +# print(i); + +print(part1); +print(part2); diff --git a/2018/aoc2018-d03.py b/2018/aoc2018-d03.py new file mode 100644 index 0000000..c304576 --- /dev/null +++ b/2018/aoc2018-d03.py @@ -0,0 +1,77 @@ +import numpy as np + +f = open("input"); + +GRIDSIZE = 1000; + +cloth = np.full((GRIDSIZE,GRIDSIZE),0, dtype=int); + + +part1 = np.count_nonzero(cloth); +print(part1); + +for i in f: + for l in range(len(i)): + if i[l] == "@": + claim_id = int(i[1:(l)]); + l_at = l+1; + if i[l] == ",": + claim_l = int(i[l_at:(l)]); + l_at = l+1; + if i[l] == ":": + claim_t = int(i[l_at:(l)]); + l_at = l+1; + if i[l] == "x": + claim_w = int(i[l_at:(l)]); + #l_at = l+1; + claim_h = int(i[l+1:]); + + for x in range(claim_l, claim_l+claim_w, 1): + for y in range(claim_t, claim_t+claim_h, 1): + cloth[y,x] +=1; + +part1 = np.count_nonzero(cloth); +#print(part1); +part1 = 0; +for i in range(GRIDSIZE): + for j in range(GRIDSIZE): + part1 += 1*(cloth[i,j] > 1); + + +print("part1", part1); + + +f = open("input"); +for i in f: + #print(i); + for l in range(len(i)): + #print(l, i[l]); + if i[l] == "@": + claim_id = int(i[1:(l)]); + l_at = l+1; + if i[l] == ",": + claim_l = int(i[l_at:(l)]); + l_at = l+1; + if i[l] == ":": + claim_t = int(i[l_at:(l)]); + l_at = l+1; + if i[l] == "x": + claim_w = int(i[l_at:(l)]); + #l_at = l+1; + claim_h = int(i[l+1:]); + + #checkclaim = "#" + str(claim_id) +" @ "+str(claim_l)+","+str(claim_t)+": "+str(claim_w)+"x"+str(claim_h); + #print("",i, checkclaim); + #print(); + is_overlap = False; + for x in range(claim_l, claim_l+claim_w, 1): + for y in range(claim_t, claim_t+claim_h, 1): + if (cloth[y,x] > 1): + is_overlap = True; + + if not is_overlap: + part2 = claim_id; + break; + +print("part2", part2); + diff --git a/2018/aoc2018-d04-1.py b/2018/aoc2018-d04-1.py new file mode 100644 index 0000000..6f28be5 --- /dev/null +++ b/2018/aoc2018-d04-1.py @@ -0,0 +1,123 @@ +import numpy as np + + +def datecompact(log): + d = log[1:5] + log[6:8] + log[9:11] + log[12:14] + log[15:17]; + return int(d); + +def action(log): + if (log[19] == "f"): + return 1; + elif (log[19] == "w"): + return 2; + else: + #return 3; + return int(log[24:].strip("\n # begins shift")); + return (log[24:].strip("\n # begins shift")); + #return int(log[24:].strip("#beginshft\n")); + +f = open("input"); +#f = open("testinput"); + +myinput = []; +guards = {}; + +for i in f: + #print(datecompact(i)); + myinput.append([datecompact(i),action(i)]); + if (action(i) != 1 and action(i) != 2 ): + try: + guards[action(i)] = 0; + except: + True; + + +for i in range(len(myinput)): + #print(i[0], " -- ", i[1]); + for j in range(len(myinput)): + if (myinput[i][0] < myinput[j][0]): + temp = myinput[i]; + myinput[i] = myinput[j]; + myinput[j] = temp; + + +#print(guards); + +#for i in range(len(myinput) -1): + #if (myinput[i][0] > myinput[i+1][0]): + #print("fuck"); +#for i in myinput: +# print(i[0], " -- ", i[1]); + +x1 = 0; + + +for l in myinput: + if l[1] == 2: + guards[g] += l[0] - x1 ; + elif l[1] == 1: + x1 = l[0]; + else: + g = l[1]; + + +tmax = 0; +bestg = ""; + +for g in guards.keys(): + print(g); + #''' + if (guards[g] >tmax): + tmax = guards[g]; + bestg = g; + #''' + +print("best guard ",bestg," - ", tmax); +#part1 = int(bestg)*tmax; +#print("part1", part1); + +#269357 too high +#256332 too high + + + +is_bestg = False; + +#timestat = np.array(60); +#timestat.fill(0); +timestat = np.full(60,0, dtype=int); + +#bestg = int(bestg); + +for l in myinput: + print("iterating", l[0], " ", l[1], " ", l[0]%100); + + if (is_bestg and (l[1] == 1 or l[1] == 2)): + print("yup"); + if l[1] == 1: + t1 = l[0]; + elif l[1] == 2: + t2 = l[0]; + for t in range(t1%100,t2%100,1): + timestat[t] += 1; + elif l[1] == bestg: + is_bestg = True; + elif l[1] != bestg: + print("not bestg"); + is_bestg = False; + +''' + guards[g] += l[0] - x1 ; + elif l[1] == 1: + x1 = l[0]; + else: + g = l[1]; +''' + +worsttime = (np.argmax(timestat)); + +part1 = int(bestg)*worsttime; + + +print("best guard ",bestg," - ", worsttime); +print("part1", part1); diff --git a/2018/aoc2018-d05-1.py b/2018/aoc2018-d05-1.py new file mode 100644 index 0000000..b1d8ebc --- /dev/null +++ b/2018/aoc2018-d05-1.py @@ -0,0 +1,60 @@ + +f = open("input"); +#f = open("testinput"); + +''' +test1 = ord("a") - ord("A"); +test2 = ord("b") - ord("B"); +test3 = ord("c") - ord("C"); + +print(test1, " ",test2, " ",test3, " ") + +''' + +cdiff = 32; + +def polymer_d(a,b): + return (cdiff == abs(ord(a) - ord(b))); + + +myinput = f.read(); +print(myinput); +print(len(myinput)); + +is_poly = True; +''' +while is_poly: + is_poly = False; + for x in range(1,len(myinput)): + x1 = myinput[x-1]; + x2 = myinput[x]; + if polymer_d(x1,x2): + #print((x1+x2)); + #myinput = myinput.replace((x1+x2),""); + myinput = myinput[ + is_poly = True; + break; + #is_poly = False; +''' + +while is_poly: + is_poly = False; + sub = ""; + for x in range(2,len(myinput)): + + x1 = myinput[x-2]; + x2 = myinput[x-1]; + if polymer_d(x1,x2): + myinput = sub + myinput[x:]; + is_poly = True; + break; + else: + sub += x1; +#print(myinput); +print(len(myinput)); +print(myinput); +myinput.rstrip("\n"); + +print("part 1", len(myinput) -1); +#9687 too high +#minus 1 helped lol, not sure why diff --git a/2018/aoc2018-d05-2.py b/2018/aoc2018-d05-2.py new file mode 100644 index 0000000..be01aa0 --- /dev/null +++ b/2018/aoc2018-d05-2.py @@ -0,0 +1,72 @@ + +f = open("input"); +#f = open("testinput"); + +''' +test1 = ord("a") - ord("A"); +test2 = ord("b") - ord("B"); +test3 = ord("c") - ord("C"); + +print(test1, " ",test2, " ",test3, " ") + +''' + +cdiff = 32; + +def polymer_d(a,b): + return (cdiff == abs(ord(a) - ord(b))); +''' +def polymer_strip(inp): + is_poly = True; + while is_poly: + is_poly = False; + sub = ""; + for x in range(2,len(inp)): + + x1 = inp[x-2]; + x2 = inp[x-1]; + if polymer_d(x1,x2): + inp = sub + inp[x:]; + is_poly = True; + break; + else: + sub += x1; + return inp; +''' +def polymer_strip(inp): + is_poly = True; + while is_poly: + is_poly = False; + for x in range(1,len(inp)): + x1 = inp[x-1]; + x2 = inp[x]; + if polymer_d(x1,x2): + #print((x1+x2)); + inp = inp.replace((x1+x2),""); + #myinput = myinput[ + is_poly = True; + break; + return inp; + #is_poly = False; + +myinput = f.read(); + +#print("A", ord("A"), "Z", ord("Z")); + +inp_max = 999999; +inp_c = ""; + +for c in range(ord("A"),ord("Z")+1,1): + #print(chr(c)); + subinput = myinput; + subinput = subinput.replace(chr(c),""); + subinput = subinput.replace(chr(c+cdiff),""); + subinput = polymer_strip(subinput); + if (len(subinput) < inp_max): + inp_max = len(subinput); + inp_c = c; + +print("part 2 ",inp_max -1); + +#again, needed minus 1 on answer +#not sure why is that but it works diff --git a/2018/aoc2018-d06.py b/2018/aoc2018-d06.py new file mode 100755 index 0000000..c3cf756 --- /dev/null +++ b/2018/aoc2018-d06.py @@ -0,0 +1,140 @@ +print("aoc 2018 day 06"); + +import numpy + + +f = open("input.txt", 'r'); +#f = open("testinput.txt", 'r'); + +myinput = {}; + +for l,line in enumerate(f): + myinput[chr(l+65)] = eval("[" + line + "]"); + print(myinput[chr(l+65)]); + +for p in myinput: + print(p); + +f.close(); + +Bounds = [0,0]; + +for p in myinput.keys(): + if myinput.get(p)[0] > Bounds[0]: + Bounds[0] = myinput.get(p)[0]; + if myinput.get(p)[1] > Bounds[1]: + Bounds[1] = myinput.get(p)[1]; + +Bounds[0] += 1; +Bounds[1] += 1; + +print("max x ", Bounds[0], "max y ", Bounds[1]); + + +class mappoint: + def __init__(self, cX, cY): + self.cords = [cX, cY]; + self.IsBoundary = False; + self.closest_point = []; #[cX, cY]; + self.closest_dist = 65000; + #closest_ID = ""; + def checkdistance(self, md, pname): #x, y, pname): + if md < self.closest_dist: + self.closest_dist = md; + self.closest_point.clear(); + self.closest_point.append(pname); # = #[x,y]; + #self.closest_ID = pname; + elif md == self.closest_dist: + self.closest_point.append(pname); + def sign(self): + s = self.closest_point[0]; + if ( len(self.closest_point) > 1): + s = "."; + return s; + #def setBounds(self, bounds): + #closest_point = [0,0]; + #closest_dist = 0; + +mymap = []; + +for x in range(Bounds[0]): + sublist = []; + for y in range(Bounds[1]): + sublist.append(mappoint(x,y)); + mymap.append(sublist); + +#for x in mymap: +# print(len(x)); + +#for x in mymap: +# print(x); + +for p in myinput.keys(): + for x in range(len(mymap)): + for y in range(len(mymap[x])): + manh_dist = abs(x - myinput[p][0] ) + abs( y - myinput[p][1] ); + mymap[x][y].checkdistance(manh_dist, p); + #if (manh_dist + #print(manh_dist); + +boundset = set(); + +for x in mymap: + for y in x: + print(y.sign(), end=""); + if (y.cords[0] == 0 or y.cords[1] == 0 or y.cords[0] == Bounds[0]-1 or y.cords[1] == Bounds[1]-1): + boundset.add(y.sign()); + print(end="\n"); + + +print("###########################################"); +print(boundset); + +finitepoints = set(); + +for p in myinput.keys(): + if not (p in boundset): + finitepoints.add(p); + + +print("###########################################"); +print(finitepoints); + +maxfp = ","; +maxfpscore = 0; + +for fp in finitepoints: + fpscore = 0; + print(fp); + for x in mymap: + for y in x: + if (y.sign() == fp): + fpscore += 1; + #print(x.count(fp)); + if (fpscore > maxfpscore): + maxfpscore = fpscore; + maxfp = fp; + +print("###"); +#print(maxfp, "\t part 1 =", maxfpscore); + + +###########PART 2 + +part2limit = 10000; +#part2limit = 32; #testinput + +regionsize = 0; + +for x in range(len(mymap)): + for y in range(len(mymap[x])): + localsum = 0; + for p in myinput.keys(): + d = abs(x - myinput[p][0] ) + abs( y - myinput[p][1] ); + localsum += d; + if localsum < part2limit: + regionsize += 1; + + +print("part 1 =", maxfpscore); +print("part 2 =", regionsize); diff --git a/2018/aoc2018-d07-1.py b/2018/aoc2018-d07-1.py new file mode 100755 index 0000000..b734e18 --- /dev/null +++ b/2018/aoc2018-d07-1.py @@ -0,0 +1,116 @@ +#class step: +# def __init__(self, name, unlocks): +# self.name = name; +# self.unlocks = unlocks; + + +def TransInstr (instruction): + return [instruction[5], instruction[36]]; + + +myinput = {}; + +currentfilename = "input.txt"; +#currentfilename = "testinput.txt"; + +f = open(currentfilename, 'r'); + +#list1 = []; +#list2 = {}; +list2 = set(); + +for line in f: + nowinstr = TransInstr(line); + #myinput[nowinstr[1]].append(nowinstr[0]); + list2.add(nowinstr[0]); + +#''' + try: + myinput[nowinstr[1]].append(nowinstr[0]); + #myinput[nowinstr[1]] = nowinstr[0]; + except: + myinput[nowinstr[1]] = []; + myinput[nowinstr[1]].append(nowinstr[0]); +#''' + +print(myinput.keys()); +print("##############"); +print(list2); +print("##############"); + +pr1 = list(myinput.keys()); +pr1.sort(); +pr2 = list(list2); +pr2.sort(); +print(pr1); +print(pr2); +print("##############"); + +print("##############"); +print("finding the first step"); + +CurrentStep = ''; + +AvailableSteps = []; +#AvailableSteps.append(CurrentStep); + +for l in list2: + IsUnique = True; + for k in myinput.keys(): + #print("L ", l, "\tK ",k, "\t",l == k); + if (l == k): + IsUnique = False; + break; + if IsUnique: + #CurrentStep = l; + #break; + AvailableSteps.append(l); + +print("Unique values are ", AvailableSteps); + +print("##############"); +print(myinput); +print("##############"); +part1 = ""; #CurrentStep; + +#list1 = myinput.keys(); +#list1.append(CurrentStep); +#print(list1); + + +while (len(AvailableSteps) != 0): + #input(); + AvailableSteps.sort(); + CurrentStep = AvailableSteps[0]; + part1 += CurrentStep; + print("now ", CurrentStep); + for step in myinput: + #x = myinput[step].index(CurrentStep); + #print(x, "\t",myinput[step]); + #myinput[step].pop(0); + #print(x, "\t",myinput[step]); + try: + #print("try worked"); + myinput[step].pop(myinput[step].index(CurrentStep)); + except: + #print("skip"); + pass; + if (len(myinput[step]) == 0 and part1.find(step) == -1): + AvailableSteps.append(step); + + AvailableSteps.pop(0); + +print("##################################"); + +def RemoveDupsOrder(TheString): + a = ""; + for letter in TheString: + if not (letter in a): + a += letter; + return a; + +print(part1); + +part1 = RemoveDupsOrder(part1); + +print(part1); diff --git a/2018/aoc2018-d07-2.py b/2018/aoc2018-d07-2.py new file mode 100755 index 0000000..2196e47 --- /dev/null +++ b/2018/aoc2018-d07-2.py @@ -0,0 +1,190 @@ +class elf: + #HasWork = False; + #WorkTime = 0; + #WorkStep = ''; + + def WorkAssign(self,s): + AocOffset = 60; #correct value + #AocOffset = 0; #example only + self.WorkStep = s; + self.WorkTime = ord(s) -64 + AocOffset; + self.HasWork = True; + + def WorkReset(self): + self.HasWork = False; + #self.WorkTime = 0; + self.WorkStep = ''; + def DoWork(self): + self.WorkTime += -1; + #if + # return + def __init__(self):#, name, unlocks): + self.HasWork = False; + self.WorkTime = 1; + self.WorkStep = ''; + + def __str__(self): + return f"{self.WorkStep}\t{self.WorkTime}\t{self.HasWork}"; + +def WorkInProgress(elflist): + w = False; + for e in elflist: + w += e.HasWork; + return w; + +def TransInstr (instruction): + return [instruction[5], instruction[36]]; + + +myinput = {}; + +currentfilename = "input.txt"; +numberofworkers = 5; +#currentfilename = "testinput.txt"; #example only +#numberofworkers = 2;#example only + +f = open(currentfilename, 'r'); + +#list1 = []; +#list2 = {}; +list2 = set(); + +for line in f: + nowinstr = TransInstr(line); + #myinput[nowinstr[1]].append(nowinstr[0]); + list2.add(nowinstr[0]); + +#''' + try: + myinput[nowinstr[1]].append(nowinstr[0]); + #myinput[nowinstr[1]] = nowinstr[0]; + except: + myinput[nowinstr[1]] = []; + myinput[nowinstr[1]].append(nowinstr[0]); +#''' + +print(myinput.keys()); +print("##############"); +print(list2); +print("##############"); + +pr1 = list(myinput.keys()); +pr1.sort(); +pr2 = list(list2); +pr2.sort(); +print(pr1); +print(pr2); +print("##############"); + +print("##############"); +print("finding the first step"); + +CurrentStep = ''; + +workers = []; + +for i in range(numberofworkers): + workers.append(elf()); + + +AvailableSteps = []; +#AvailableSteps.append(CurrentStep); + +for l in list2: + IsUnique = True; + for k in myinput.keys(): + #print("L ", l, "\tK ",k, "\t",l == k); + if (l == k): + IsUnique = False; + break; + if IsUnique: + #CurrentStep = l; + #break; + AvailableSteps.append(l); + +print("Unique values are ", AvailableSteps); + +print("##############"); +print(myinput); +print("##############"); +part1 = ""; #CurrentStep; + +#list1 = myinput.keys(); +#list1.append(CurrentStep); +#print(list1); +part2 = -1; +IsWork = False; +print("whileloop begins"); +while (len(AvailableSteps) != 0 or IsWork): + + part2 += 1;#input(); + #IsWork = False; + AvailableSteps.sort(); + #CurrentStep = AvailableSteps[0]; + print(part2, " - steps sorted:",AvailableSteps); + for worker in workers: + #print(worker); + #print(worker.WorkTime); + worker.DoWork(); + if (worker.WorkTime == 0): # and worker.WorkStep != ''): + part1 += worker.WorkStep; + #if (worker.WorkSte + if (worker.WorkStep != ''): + for step in myinput: + try: + myinput[step].pop(myinput[step].index(worker.WorkStep)); + except: + pass; + CurrentStepsCheck = "";# workers[0].WorkStep + workers[1].WorkStep + workers[2].WorkStep + workers[3].WorkStep; + for w in workers: + CurrentStepsCheck += w.WorkStep; + if (len(myinput[step]) == 0 and part1.find(step) == -1 and CurrentStepsCheck.find(step) == -1 ): #and AvailableSteps.find(step) == -1): + AvailableSteps.append(step); + worker.WorkReset(); + #worker.WorkStep() = ''; + #worker.HasWork() = False; + AvailableSteps = list(dict.fromkeys(AvailableSteps)); + + for worker in workers: + if not worker.HasWork: + if (len(AvailableSteps) > 0): + worker.WorkAssign(AvailableSteps[0]); + print("\tWorker begins step", AvailableSteps[0], "at second ", part2); + AvailableSteps.pop(0); + #else: + #worker.DoWork(); + #worker.WorkTime() += -1; + + #part1 += CurrentStep; + #print("now ", CurrentStep); + ''' + for step in myinput: + try: + myinput[step].pop(myinput[step].index(CurrentStep)); + except: + pass; + if (len(myinput[step]) == 0 and part1.find(step) == -1): #and AvailableSteps.find(step) == -1): + AvailableSteps.append(step); + ''' + + IsWork = WorkInProgress(workers); + #AvailableSteps.pop(0); + +print("whileloop finished"); +print("##################################"); + +def RemoveDupsOrder(TheString): + a = ""; + for letter in TheString: + if not (letter in a): + a += letter; + return a; + +print(part1); + +part1 = RemoveDupsOrder(part1); + +print(part1); +print("total time part2 = ", part2); +#207 too low (because I forgot to add 60secs per step, fixed now +#987 correct diff --git a/2018/aoc2018-d08-1.py b/2018/aoc2018-d08-1.py new file mode 100755 index 0000000..2d0110d --- /dev/null +++ b/2018/aoc2018-d08-1.py @@ -0,0 +1,31 @@ +currentfilename = "input.txt"; +#currentfilename = "testinput.txt"; #example only + +f = open(currentfilename, 'r'); +myinput = eval(f.read().replace(" ",",")); +f.close(); + +#for i in myinput: +# print(i); + +def NodeAnalysis(License, index): + NumberOfChilds = License[index[0]]; + index[0] += 1; + NumberofEntries = License[index[0]]; + index[0] += 1; + #print(index, " - this node has ", NumberOfChilds, " and ", NumberofEntries); + for child in range(NumberOfChilds): + NodeAnalysis(License, index); + + for entry in range(NumberofEntries): + index[1] += License[index[0]]; + index[0] += 1; + #print("\tcurrent index ", index[0]); + + +i = [0,0]; + +NodeAnalysis(myinput, i); +print("input length\t", len(myinput)); +print("final index\t", i[0]); +print("part1 answer\t", i[1]); diff --git a/2018/aoc2018-d08-2.py b/2018/aoc2018-d08-2.py new file mode 100755 index 0000000..17ce2cc --- /dev/null +++ b/2018/aoc2018-d08-2.py @@ -0,0 +1,51 @@ +currentfilename = "input.txt"; +#currentfilename = "testinput.txt"; #example only + +f = open(currentfilename, 'r'); +myinput = eval(f.read().replace(" ",",")); +f.close(); + +#for i in myinput: +# print(i); + +def NodeAnalysis(License, index): + NodeVal = 0; + NumberOfChilds = License[index[0]]; + index[0] += 1; + NumberofEntries = License[index[0]]; + index[0] += 1; + print(index, " - this node has ", NumberOfChilds, " and ", NumberofEntries); + ListOfEntries = []; + ListOfChilds = []; + for child in range(NumberOfChilds): + ListOfChilds.append(NodeAnalysis(License, index)); + + + for entry in range(NumberofEntries): + ListOfEntries.append(License[index[0]]); + #index[1] += License[index[0]]; + index[0] += 1; + #print("\tcurrent index ", index[0]); + if(NumberOfChilds == 0): + NodeVal = sum(ListOfEntries); + #for entry in range(NumberofEntries): + # NodeVal += License[index[0]]; + # index[0] += 1; + else: + for e in ListOfEntries: + if (e == 0 or e >NumberOfChilds): + continue; + NodeVal+= ListOfChilds[e-1]; + print("now ", NodeVal); + index.append(NodeVal); + return NodeVal; + + +i = [0,0]; + +part2 = NodeAnalysis(myinput, i); +print("input length\t", len(myinput)); +print("final index\t", i[0]); +print("part1 answer\t", i[1]); +print("part2 answer\t", i[1]); +print("part2 answer\t", i[-1]); diff --git a/2018/aoc2018-d09.py b/2018/aoc2018-d09.py new file mode 100644 index 0000000..3a300b9 --- /dev/null +++ b/2018/aoc2018-d09.py @@ -0,0 +1,50 @@ +#advent of code 2018 +#day 09 +#part 1 and part 2 + +from collections import deque +import time + +#parsing input is hardcoded for 1st and 7th word in text +f = open("input.txt", 'r'); +inputline = f.readline().split(); +playercount = int(inputline[0]); #input1 +lastmarble = int(inputline[6]); #input2 + +testinput = False; +if testinput: + playercount = 30; # 09 / 10 / 13 / 17 / 21 / 30 + lastmarble = 5807; # 25 / 1618 / 7999 / 1104 / 6111 / 5807 + # 32 / 8317 / 146373 / 2764 / 54718 / 37305 + +def MarbleGame(playercount, lastmarble): + playerlist = []; + player = 1; + for p in range(playercount+1): + playerlist.append(0); + + marblelist = deque([0]); + + for m in range(1, lastmarble+1): + if(m%23==0): + playerlist[player] += m; + marblelist.rotate(7); + playerlist[player] += marblelist.pop(); + marblelist.rotate(-1); + else: + marblelist.rotate(-1); + marblelist.append(m); + player +=1; + if (player > playercount): + player = 1; + + p1 = max(playerlist); + return p1; + +t1 = time.time(); +part1 = MarbleGame(playercount, lastmarble); +part2 = MarbleGame(playercount, lastmarble*100); +t2 = time.time(); +print("part 1 = ", part1); +print("part 2 = ", part2); +print("runtime ", round(t2-t1,3), " sec"); diff --git a/2018/aoc2018-d10.py b/2018/aoc2018-d10.py new file mode 100755 index 0000000..7bd2ae5 --- /dev/null +++ b/2018/aoc2018-d10.py @@ -0,0 +1,88 @@ +#advent of code 2018 +#day 10 + +#part 1 & part 2 + +class light: + def __init__(self, x,y,vx,vy): + self.Pos = [x,y]; + self.Vel = [vx,vy]; + def CalcNextPos(self, t): + return [self.Pos[0]+t*self.Vel[0],self.Pos[1]+t*self.Vel[1]]; + def __str__(self): + return f'<{self.Pos[0]},{self.Pos[1]}>'; + +def CalcArea(x1,x2,y1,y2): + return abs(x1-x2)*abs(y1-y2); + +f = open("input.txt",'r'); +Testing = False; +#Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); + +lights = []; + +for tl in f: + tl = tl.replace("position=<", ""); + tl = tl.replace("velocity=<", ""); + tl = tl.replace(">", ""); + tl = tl.replace(",", ""); + tl=tl.split(); + lights.append( light(int(tl[0]),int(tl[1]),int(tl[2]),int(tl[3])) ); +f.close(); + +Xmin = min(lights, key = lambda x: x.Pos[0]).Pos[0]; +Xmax = max(lights, key = lambda x: x.Pos[0]).Pos[0]; +Ymin = min(lights, key = lambda y: y.Pos[1]).Pos[1]; +Ymax = max(lights, key = lambda y: y.Pos[1]).Pos[1]; +#print(Xmin,Xmax,Ymin,Ymax); + +PrevArea = CalcArea(Xmin,Xmax,Ymin,Ymax); +ElapsedTime = 0; + +while True: + #print(ElapsedTime); + ElapsedTime += 1; + Xmin = min(lights, key = lambda L: L.CalcNextPos(ElapsedTime)[0]).CalcNextPos(ElapsedTime)[0]; + Xmax = max(lights, key = lambda L: L.CalcNextPos(ElapsedTime)[0]).CalcNextPos(ElapsedTime)[0]; + Ymin = min(lights, key = lambda L: L.CalcNextPos(ElapsedTime)[1]).CalcNextPos(ElapsedTime)[1]; + Ymax = max(lights, key = lambda L: L.CalcNextPos(ElapsedTime)[1]).CalcNextPos(ElapsedTime)[1]; + + CurrArea = CalcArea(Xmin,Xmax,Ymin,Ymax); + + if (CurrArea > PrevArea): + MessageTime = ElapsedTime-1; + break; + + PrevArea = CurrArea; + +pointlist = []; + +for l in lights: + xy = l.CalcNextPos(MessageTime); + pointlist.append((xy[0],xy[1])); + +Xmin = min(lights, key = lambda L: L.CalcNextPos(ElapsedTime)[0]).CalcNextPos(ElapsedTime)[0]; +Xmax = max(lights, key = lambda L: L.CalcNextPos(ElapsedTime)[0]).CalcNextPos(ElapsedTime)[0]; +Ymin = min(lights, key = lambda L: L.CalcNextPos(ElapsedTime)[1]).CalcNextPos(ElapsedTime)[1]; +Ymax = max(lights, key = lambda L: L.CalcNextPos(ElapsedTime)[1]).CalcNextPos(ElapsedTime)[1]; + + +print("###########"); +print("part1:"); + +for Y in range(Ymin,Ymax+1): + for X in range(Xmin,Xmax+1): + sign = " "; + if ((X,Y) in pointlist): + sign = "#"; + print(sign, end=""); + #print(end=""); + print(); + +part2 = MessageTime; + +print("###########"); +print("part2 ,", part2); diff --git a/2018/aoc2018-d11-1.py b/2018/aoc2018-d11-1.py new file mode 100755 index 0000000..2379c3c --- /dev/null +++ b/2018/aoc2018-d11-1.py @@ -0,0 +1,75 @@ +#advent of code 2018 +#day 11 +#part 1 + +#setup +GridSize = 300; +SquareSize = 3; +fcserialnumber = int(open("input.txt",'r').readline()); + +testing = False; +#testing = True; +if testing: + fcserialnumber = 42; #18=>33,45 ; 42 => 21,61; + +class fuelcell: + def __init__(self, x, y, serialnumber): + self.positionX = x; + self.positionY = y; + self.rackID = self.positionX + 10; + self.powerlevel = self.rackID * self.positionY; + self.powerlevel += serialnumber; + self.powerlevel *= self.rackID; + self.powerlevel = self.powerlevel//100; + self.powerlevel = self.powerlevel%10; + self.powerlevel -= 5; + def coords(self): + print(f'Fuel Cell coordinates (x,y): {self.positionX},{self.positionY} '); + def __str__(self): + return f'{self.powerlevel}'; + +''' +testinput = [[3,5,8],[122,79,57],[217,196,39],[101,153,71]]; + +for t in testinput: + dummycell = fuelcell(t[0],t[1],t[2]); + print(t, " -> ",dummycell.powerlevel); + dummycell.coords(); + +print("#############################"); +print(); +''' + +fcgrid = []; +gridline = []; + +for Y in range(GridSize): + gridline.clear(); + for X in range(GridSize): + gridline.append(fuelcell(X+1,Y+1,fcserialnumber)); + fcgrid.append(gridline.copy()); + +maxpower = -999; #negative power just to start the algorythm +maxX = 0; +maxY = 0; +powernow = 0; + +for Y in range(GridSize-SquareSize+1): + for X in range(GridSize-SquareSize+1): + powernow = 0; + for sy in range(SquareSize): + for sx in range(SquareSize): + powernow += fcgrid[Y+sy][X+sx].powerlevel; + if (powernow > maxpower): + maxpower = powernow; + maxX = X; + maxY = Y; + +#print(f'maximum found: {maxX},{maxY} => {maxpower}'); +print("part 1: "); +fcgrid[maxY][maxX].coords(); + +#10,300 wrong +#9,0 wrong +#0,9 wrong +#33,45 diff --git a/2018/aoc2018-d11-2.py b/2018/aoc2018-d11-2.py new file mode 100755 index 0000000..dbfafe7 --- /dev/null +++ b/2018/aoc2018-d11-2.py @@ -0,0 +1,108 @@ +#advent of code 2018 +#day 11 +#part 2 +#too lazy to clean up the code, might do it later (i.e. never) + +#setup +GridSize = 300; +SquareSize = 3; +fcserialnumber = int(open("input.txt",'r').readline()); + +testing = False; +#testing = True; +if testing: + fcserialnumber = 42; #18=>90,269,16 ; 42 => 21,61; + +class fuelcell: + def __init__(self, x, y, serialnumber): + self.positionX = x; + self.positionY = y; + self.rackID = self.positionX + 10; + self.powerlevel = self.rackID * self.positionY; + self.powerlevel += serialnumber; + self.powerlevel *= self.rackID; + self.powerlevel = self.powerlevel//100; + self.powerlevel = self.powerlevel%10; + self.powerlevel -= 5; + def coords(self): + print(f'Fuel Cell coordinates (x,y): {self.positionX},{self.positionY} '); + def __str__(self): + return f'{self.powerlevel}'; + +''' +testinput = [[3,5,8],[122,79,57],[217,196,39],[101,153,71]]; + +for t in testinput: + dummycell = fuelcell(t[0],t[1],t[2]); + print(t, " -> ",dummycell.powerlevel); + dummycell.coords(); + +print("#############################"); +print(); +''' + +fcgrid = []; +gridline = []; + +print("#############################"); +print("INITIATE BATTERY ARRAY"); +for Y in range(GridSize): + gridline.clear(); + for X in range(GridSize): + gridline.append(fuelcell(X+1,Y+1,fcserialnumber)); + fcgrid.append(gridline.copy()); + +print("#############################"); +print("CALCULATE SQUARE SUBSUMS"); +sumtable = []; + +gridline.clear(); +gridline.append(fcgrid[0][0].powerlevel); + +for X in range(1,GridSize): + SubSumFc = fcgrid[0][X].powerlevel + gridline[X-1]; + gridline.append(SubSumFc); +sumtable.append(gridline.copy()); + +currentsubsum = 0; + +for Y in range(1,GridSize): + gridline.clear(); + SubSumFc = sumtable[Y-1][0] + fcgrid[Y][0].powerlevel; + gridline.append(SubSumFc); + currentsubsum = fcgrid[Y][0].powerlevel; + for X in range(1,GridSize): + currentsubsum += fcgrid[Y][X].powerlevel; + gridline.append(sumtable[Y-1][X] + currentsubsum); + sumtable.append(gridline.copy()); + +print("#############################"); +print("SEARCH FOR HIGHEST SUBSUM SQUARE"); + +maxpower = -999; +maxX = 0; +maxY = 0; +powernow = 0; +maxsquare = 0; + +for Y in range(1,GridSize-3): + ssy = GridSize - Y; + for X in range(1,GridSize-3): + ssx = GridSize - X; + SquareSize = (ssx>=ssy)*ssy + ssx*(ssx maxpower): + maxX = X; + maxY = Y; + maxpower = powernow; + maxsquare = s; + #print("new max power: ", maxpower, " // ", powernow); + +print("#############################"); +print("Results:"); +print(maxX, "\t", maxY, "\t", maxsquare, "\t", maxpower); +fcgrid[maxY][maxX].coords(); +print("winrar part 2:\t", fcgrid[maxY][maxX].positionX,",",fcgrid[maxY][maxX].positionY,",",maxsquare+1,end=""); + diff --git a/2018/aoc2018-d12.py b/2018/aoc2018-d12.py new file mode 100644 index 0000000..9922c39 --- /dev/null +++ b/2018/aoc2018-d12.py @@ -0,0 +1,68 @@ +#advent of code 2018 +#day 12 +#part 1 & part 2 + +generationnumber1 = 20; #part1 +generationnumber2 = 10000; #steady state +generationnumber3 = 50000000000; #part2 + +f = open("input.txt", 'r'); + +testing = False; +#testing = True; +if testing: + f.close(); + f = open("testinput.txt", 'r'); + +PlantInitialState = f.readline(); +PlantInitialState = PlantInitialState.replace("initial state: ",""); +PlantInitialState = PlantInitialState.replace("\n",""); +f.readline(); + +Notes = {}; + +for l in f: + n1 = l[0:5]; + n2 = l[9]; + Notes[n1] = n2; + print(l, end=""); + +#append to the beginning and the end an a=4 amount of pots +#store the amount of appended pots + +PlantInitialState = "...." + PlantInitialState + "...."; +a = 4; +PlantCurrentState = PlantInitialState; + +part1 = 0; + +for g in range(generationnumber2): + substate = PlantCurrentState[0:2]; + substate += Notes.get(PlantCurrentState[0:5]); + for p in range(3,len(PlantCurrentState)-2): + substate += Notes.get(PlantCurrentState[p-2:p+3]); + substate += PlantCurrentState[-2:]; + if(substate[2] == '#'): + substate = ".." + substate; + a += 2; + if(substate[-3] == '#'): + substate = substate + ".."; + PlantCurrentState = substate; + if (g == generationnumber1 -1): + for pot in range(len(PlantCurrentState)): + if PlantCurrentState[pot] == '#': + part1 += pot - a; + + +SteadyState10k = 0; +for pot in range(len(PlantCurrentState)): + if PlantCurrentState[pot] == '#': + SteadyState10k += pot - a; + +gendiv = generationnumber3//generationnumber2; +part2 = SteadyState10k*(gendiv); + +print("part1: ", part1); +print("part2: ", part2); + +#2830 too low diff --git a/2018/aoc2018-d13.py b/2018/aoc2018-d13.py new file mode 100644 index 0000000..906ffa2 --- /dev/null +++ b/2018/aoc2018-d13.py @@ -0,0 +1,195 @@ +#advent of code 2018 +#day 13 +#part 1 and part 2 + +#I got it working the first time, but I was getting a wrong answer for actual input +#turns out I made a mistake in calculations for the crossroads for turn-left and turn-right +#i hastily scrambled a set of 2 equations for X and Y coordinates +#and it costed me time wasted on debugging +#for each round I was drawing the current layout of the map with a single cart +#I noticed that at crossroads it was doing a turn-left, straight, turn-left +#(instead of right for 3rd crossroads) +#I followed my equations by *slowly* calculating them on paper +#and found out that I had wrong signs for Y coordinate +#fun puzzle nonetheless +#comment for part2 +#i had a bit of an issue with getting it working properly +#at this moment, the part2 is calculated correctly, but part1 was off +#I cleaned up the code a bit and managed to solve this, so both parts are in the same file + +f = open("input.txt",'r'); +Testing = False; +#Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); + +class trackpoint: + def __init__(self, sign, x, y): + self.sign = sign; + self.positionX = x; + self.positionY = y; + def __str__(self): + return self.sign; + +class hline(trackpoint): + def __init__(self, sign, x, y): + trackpoint.__init__(self, sign, x, y); + def GiveSteps(self, cart_x, cart_y, cartid): + #left or right + x_next = self.positionX + (self.positionX - cart_x); + y_next = self.positionY + (self.positionY - cart_y); + return [x_next, y_next]; + +class vline(trackpoint): + def __init__(self, sign, x, y): + trackpoint.__init__(self, sign, x, y); + def GiveSteps(self, cart_x, cart_y, cartid): + #up or down + x_next = self.positionX + (self.positionX - cart_x); + y_next = self.positionY + (self.positionY - cart_y); + return [x_next, y_next]; + +class turnleft(trackpoint): + def __init__(self, sign, x, y): + trackpoint.__init__(self, sign, x, y); + def GiveSteps(self, cart_x, cart_y, cartid): + x_next = self.positionX - (cart_y - self.positionY); + y_next = self.positionY - (cart_x - self.positionX); + return [x_next, y_next]; + +class turnright(trackpoint): + def __init__(self, sign, x, y): + trackpoint.__init__(self, sign, x, y); + def GiveSteps(self, cart_x, cart_y, cartid): + x_next = self.positionX + (cart_y - self.positionY); + y_next = self.positionY + (cart_x - self.positionX); + return [x_next, y_next]; + +class crossroads(trackpoint): + def __init__(self, sign, x, y): + trackpoint.__init__(self, sign, x, y); + self.CartRegistry = {}; + def GiveSteps(self, cart_x, cart_y, cartid): + #number of crossroads is updated before this function is called, thats why it starts from 1 + if (cartid%3 == 1): + #turn left + x_next = self.positionX - (cart_y - self.positionY); + y_next = self.positionY + (cart_x - self.positionX); + elif (cartid%3 == 2): + #go straight + x_next = self.positionX + (self.positionX - cart_x); + y_next = self.positionY + (self.positionY - cart_y); + elif (cartid%3 == 0): + #turn right + x_next = self.positionX + (cart_y - self.positionY); + y_next = self.positionY - (cart_x - self.positionX); + return [x_next, y_next]; + +class minecart: + def __init__(self, sign, x, y, cart_id): + self.posX = x; + self.posY = y; + self.XroadsEncountered = 0; + self.nextstepX = x; + self.nextstepY = y; + self.Cart_ID = cart_id; + self.notHit = True; + if (sign == '>'): + self.prevX = x-1; + self.prevY = y; + if (sign == '<'): + self.prevX = x+1; + self.prevY = y; + if (sign == 'v'): + self.prevX = x; + self.prevY = y-1; + if (sign == '^'): + self.prevX = x; + self.prevY = y+1; + def cartmove(self, nextX, nextY): + self.nextstepX = nextX; + self.nextstepY = nextY; + self.prevX = self.posX; + self.prevY = self.posY; + self.posX = self.nextstepX; + self.posY = self.nextstepY; + def ReadCoords(self): + return [self.posX, self.posY]; + def CheckMatch(self, OtherCoords): + return (self.posX == OtherCoords[0] and self.posY == OtherCoords[1]); + def IsXroads(self, currentsign): + if (currentsign == "+"): + self.XroadsEncountered += 1; + +trackmap = []; + +for l in f: + subline = []; + l.replace("\n", ""); + for c in l: + subline.append(c); + trackmap.append(subline.copy()); + +cartlist = []; +cartid_counter = 10; + +TMSize_C = len(trackmap); +TMSize_R = len(trackmap[0]) -1; +#RETREIVING MINECARTS AND REPLACING SIGNS ON THE MAP +for c in range(TMSize_C): + for r in range(TMSize_R): + if (trackmap[c][r] == '^' or trackmap[c][r] == 'v' or trackmap[c][r] == '>' or trackmap[c][r] == '<'): + cartlist.append( minecart(trackmap[c][r], r, c, cartid_counter) ); + cartid_counter += 1; + if (trackmap[c][r] == '^' or trackmap[c][r] == 'v'): + trackmap[c][r] = '|'; + if (trackmap[c][r] == '>' or trackmap[c][r] == '<'): + trackmap[c][r] = '-'; + +cartlist = sorted(cartlist, key=lambda x: (x.posY, x.posX)); +newmap = []; + +for c in range(TMSize_C): + templine = []; + for r in range(TMSize_R): + if (trackmap[c][r] == ' '): + templine.append( trackpoint(trackmap[c][r], r, c) ); + elif (trackmap[c][r] == '-'): + templine.append( hline(trackmap[c][r], r, c) ); + elif (trackmap[c][r] == '|'): + templine.append( vline(trackmap[c][r], r, c) ); + elif (trackmap[c][r] == '/'): + templine.append( turnright(trackmap[c][r], r, c) ); + elif (trackmap[c][r] == '\\'): + templine.append( turnleft(trackmap[c][r], r, c) ); + elif (trackmap[c][r] == '+'): + templine.append( crossroads(trackmap[c][r], r, c) ); + newmap.append( templine.copy() ); + +roundcounter = 0; +part1 = None; +p1round = 0; + +while (len(cartlist) > 1): + roundcounter += 1; + cartlist = sorted(cartlist, key=lambda x: (x.posY, x.posX)); + for mc in cartlist: + NextSteps = []; + mc.IsXroads(newmap[mc.posY][mc.posX].sign); + NextSteps = newmap[mc.posY][mc.posX].GiveSteps(mc.prevX, mc.prevY, mc.XroadsEncountered); + mc.cartmove(NextSteps[0],NextSteps[1]); + MatchCounter = 0; + for mc2 in cartlist: + if mc.Cart_ID != mc2.Cart_ID: + mc.notHit = not mc.CheckMatch( mc2.ReadCoords() ); + mc2.notHit = not mc2.CheckMatch( mc.ReadCoords() ); + if part1 == None and mc.notHit == False: + part1 = mc.ReadCoords(); + p1round = int(roundcounter); + #print("part 1 = ",part1, "\t after", roundcounter, "rounds"); + cartlist = [c for c in cartlist if c.notHit]; + +part2 = cartlist[0].ReadCoords(); +print("part 1 = ",part1, "\t after", p1round, "rounds"); +print("part 2 = ",part2, "\t after", roundcounter, "rounds"); diff --git a/2018/aoc2018-d14.py b/2018/aoc2018-d14.py new file mode 100644 index 0000000..9e042d0 --- /dev/null +++ b/2018/aoc2018-d14.py @@ -0,0 +1,66 @@ +#advent of code 2018 +#day 14 +#part 1 & part 2 + +#there should be a faster way to compute the results +#no idea how to do it at the moment + +import time + +f = open("input.txt",'r'); +myinput = int(f.readline()); + +Testing = False; +#Testing = True; +if Testing: + f.close(); + #f = open("testinput.txt",'r'); + myinput = 9; + myinput = 5; + myinput = 18; + myinput = 2018; + +recipes = [3,7]; +elf1 = 0; +elf2 = 1; + +StillSearching = True; +part2 = ""; + +ElapsedTime = 0; +starttime = time.time(); + +while (StillSearching): + newrecipes = recipes[elf1] + recipes[elf2]; + newrecipes = str(newrecipes); + for r in newrecipes: + recipes.append(int(r)); + + move1 = 1 + recipes[elf1]; + move2 = 1 + recipes[elf2]; + elf1 = (move1 + elf1)%len(recipes); + elf2 = (move2 + elf2)%len(recipes); + + recipesstring = ""; + for n in range(-len(str(myinput))-1,0): + recipesstring += str( recipes[n%len(recipes)] ); + + if (recipesstring[:-1] == str(myinput)): + part2 = len(recipes) - len(str(myinput)) -1; + print("p2 ", part2); + elif (recipesstring[1:] == str(myinput)): + part2 = len(recipes) - len(str(myinput)); + print("p2 ", part2); + + if (len(recipes)>=myinput+10): + if (part2 != ""): + StillSearching = False; + +part1 = ""; +for i in range(myinput,myinput+10): + part1 += str(recipes[i]); + +endtime = time.time() - starttime; +print("FIN -- ", endtime, "sec"); +print("part 1: ", part1); +print("part 2: ", part2); diff --git a/2018/aoc2018-d15-1.py b/2018/aoc2018-d15-1.py new file mode 100644 index 0000000..6a2665d --- /dev/null +++ b/2018/aoc2018-d15-1.py @@ -0,0 +1,324 @@ +#advent of code 2018 +#day 13 +#part 1 +import heapq + +f = open("input.txt",'r'); +Testing = False; +Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); +Testing2 = False; +Testing2 = True; +if Testing2: + f.close(); + f = open("testinput2.txt",'r'); +Testing3 = False; +#Testing3 = True; +if Testing3: + f.close(); + f = open("testinput3.txt",'r'); +Testing4 = False; +#Testing4 = True; +if Testing4: + f.close(); + f = open("testinput4.txt",'r'); +Testing5 = False; +Testing5 = True; +if Testing5: + f.close(); + f = open("testinput5.txt",'r'); +Testing6 = False; +Testing6 = True; +if Testing6: + f.close(); + f = open("testinput6.txt",'r'); +Testing7 = False; +Testing7 = True; +if Testing7: + f.close(); + f = open("testinput7.txt",'r'); +NotTesting = False; +NotTesting = True; +if NotTesting: + f.close(); + f = open("input.txt",'r'); + #f = open("shit.txt",'r'); + +class thing: + def __init__(self, Pos, sign, currentID): + self.sign = sign; + self.PosX = Pos[1]; + self.PosY = Pos[0]; + self.IsAlive = False; + if (sign == "."): + self.IsPassable = True; + else: + self.IsPassable = False; + def __str__(self): + return self.sign; + + def SquaresInRange(self,bg): + squares = []; + p = (self.PosY-1,self.PosX); + if(bg[p].IsPassable): squares.append(p); + p = (self.PosY,self.PosX-1); + if(bg[p].IsPassable): squares.append(p); + p = (self.PosY,self.PosX+1); + if(bg[p].IsPassable): squares.append(p); + p = (self.PosY+1,self.PosX); + if(bg[p].IsPassable): squares.append(p); + return squares; + +class creature(thing): + def __init__(self, Pos, sign, currentID): + thing.__init__(self, Pos, sign, currentID); + self.ID = currentID; + self.health = 200; + self.damage = 3; + self.side = sign; + self.IsAlive = True; + if (self.side == "G"): + self.enemy = "E"; + if (self.side == "E"): + self.enemy = "G"; + + def death(self,bg): + self.IsPassable = True; + self.IsAlive = False; + self.health = 0; + unitcords[(self.PosY,self.PosX)] = None; + bg[(self.PosY,self.PosX)].IsPassable = True; + + + def movement(self,bg,PosNow,PosNew): + self.PosX = PosNew[1]; + self.PosY = PosNew[0]; + bg[PosNow].IsPassable = True; + bg[PosNew].IsPassable = False; + unitcords[PosNew] = self.ID; + unitcords[PosNow] = None; + + + def ScanProximity(self): + targets = []; + p = (self.PosY-1,self.PosX); + if p in unitcords and unitcords[p] in units and units[unitcords[p]].side == self.enemy and units[unitcords[p]].health >0: + targets.append(p); + p = (self.PosY,self.PosX-1); + if p in unitcords and unitcords[p] in units and units[unitcords[p]].side == self.enemy and units[unitcords[p]].health >0: + targets.append(p); + p = (self.PosY,self.PosX+1); + if p in unitcords and unitcords[p] in units and units[unitcords[p]].side == self.enemy and units[unitcords[p]].health >0: + targets.append(p); + p = (self.PosY+1,self.PosX); + if p in unitcords and unitcords[p] in units and units[unitcords[p]].side == self.enemy and units[unitcords[p]].health >0: + targets.append(p); + if targets: + targets.sort(key = lambda x: (units[unitcords[x]].health,units[unitcords[x]].PosY,units[unitcords[x]].PosX)); + return targets; + + + def IdentifyTargets_ALL(self,creaturelist,bg): + points = []; + for c in creaturelist: + if units[c].side == self.side or not units[c].IsAlive: continue; + points.extend(units[c].SquaresInRange(bg)); + return points; + + + def ShortestPaths(self, pointlist, bg): + paths = []; + pathlen = len(bg); + queue = []; + heapq.heappush(queue, (0,[(self.PosY,self.PosX)])); + visited = []; + while queue: + d, path = heapq.heappop(queue); + if d > pathlen: + return paths; + if path[-1] in pointlist: + if pathlen > len(path): + paths.append(path); + pathlen = len(path); + continue; + if path[-1] in visited: + continue; + else: + visited.append(path[-1]); + for a in bg[path[-1]].SquaresInRange(bg): + if a in visited: continue; + heapq.heappush(queue, (d+1, path + [a])); + return paths; + + def ChosenPath(self, pointlist, bg): + paths = self.ShortestPaths(pointlist, bg); + if len(paths) != 0: + pathends = min([p[-1] for p in paths]); + paths2= self.ShortestPaths([pathends], bg); + if len(paths2) != 0: + moves = []; + for p in paths: + moves.append(p[1]); + moves = sorted(moves, key = lambda m: (m[0],m[1])); + m = moves[0]; + self.movement(bg,(self.PosY,self.PosX),m); + + +def PathSearch(bg, Coordinates, Destination): + pass; + +def strike(attacker, target,bg): + target.health -= attacker.damage; + if (target.health <= 0): + target.death(bg); + +def armystrength(army): + strength = 0; + for soldier in army: + strength += units[unitcords[soldier]].health; + return strength; + +def armyscores(): + ElfScore = 0; + GobScore = 0; + for u in units: + if units[u].side == "G": GobScore += units[u].health; + if units[u].side == "E": ElfScore += units[u].health; + + return max(ElfScore,GobScore); + + + +def FindEnemies(team): + Enemies = 0; + for u in units: + if units[u].IsAlive and units[u].side != team: Enemies += 1; + + return Enemies; +############################################################################### + + +bgsizex = 0; +bgsizey = 0; +battleground = {}; +units = {}; +unitcords = {}; + +identifier = 11; + +for y, line in enumerate(f): + bgsizey += 1; + bgsizex = 0; + for x, c in enumerate(line): + bgsizex += 1; + if c == "G" or c == "E": + battleground[(y,x)] = thing((y,x),".",identifier); + units[identifier] = creature((y,x),c, identifier); + units[identifier].movement(battleground, (y,x), (y,x)); + identifier += 1; + else: + battleground[(y,x)] = thing((y,x),c,identifier); +''' +for y in range(bgsizey): + for x in range(bgsizex): + if (y,x) in unitcords: + print("X",end=""); + else: + print(battleground[(y,x)],end=""); #''' + + +unitcords = {}; +for u in units: + unitcords[(units[u].PosY,units[u].PosX)] = units[u].ID; + + +elfs = sum([1 for x in units if units[x].IsAlive and units[x].side=="E"]); +goblins = sum([1 for x in units if units[x].IsAlive and units[x].side=="G"]); + +ElapsedRounds = 0; + + +while goblins and elfs: + fighters = []; + for u in units: + if units[u].IsAlive: + fighters.append(units[u].ID); + + fighters = sorted(fighters, key = lambda u: (units[u].PosY,units[u].PosX)); + + for fighter in fighters: + if not units[fighter].IsAlive: continue; + if FindEnemies(units[fighter].side) <= 0: + print("loop broken FIGHTERS"); + break; + tars = units[fighter].ScanProximity(); + if tars: + tar = tars[0]; + strike(units[fighter],units[unitcords[tar]],battleground); + else: + CurrentPos = (units[fighter].PosY,units[fighter].PosX); + IdenTars = units[fighter].IdentifyTargets_ALL(fighters,battleground); + units[fighter].ChosenPath(IdenTars,battleground); + if CurrentPos == (units[fighter].PosY,units[fighter].PosX): + continue; + else: + tars = units[fighter].ScanProximity(); + if tars: + tar = tars[0]; + strike(units[fighter],units[unitcords[tar]],battleground); + + unitcords = {}; + for u in units: + unitcords[(units[u].PosY,units[u].PosX)] = units[u].ID; + + print("ROUND ", ElapsedRounds); + unitcords = {}; + for u in units: + unitcords[(units[u].PosY,units[u].PosX)] = units[u].ID; + + ElapsedRounds += 1; + elfs = sum([1 for x in units if units[x].IsAlive and units[x].side=="E"]); + goblins = sum([1 for x in units if units[x].IsAlive and units[x].side=="G"]); + ''' + for y in range(bgsizey): + for x in range(bgsizex): + if (y,x) in unitcords and unitcords[(y,x)] in units and units[unitcords[(y,x)]].IsAlive: + print(units[unitcords[(y,x)]].side,end=""); + else: + print(battleground[(y,x)],end=""); + print(); + ''' + + ''' + for y in range(bgsizey): + for x in range(bgsizex): + print((y,x), " - ", battleground[(y,x)].IsPassable); + print(); + print(); + ''' + + + +unitcords = {}; +for u in units: + unitcords[(units[u].PosY,units[u].PosX)] = units[u].ID; + print(u, f'({units[u].side} / ({units[u].PosY},{units[u].PosX})) ', units[u].health); + + +for y in range(bgsizey): + for x in range(bgsizex): + if (y,x) in unitcords and unitcords[(y,x)] in units and units[unitcords[(y,x)]].IsAlive: + print(units[unitcords[(y,x)]].side,end=""); + else: + print(battleground[(y,x)],end=""); +print(); + + +print("part 1 = ", ElapsedRounds, "*",armyscores(), "=",ElapsedRounds*armyscores()); +print("lil cheat = ", (ElapsedRounds-1), "*",armyscores(), "=",(ElapsedRounds-1)*armyscores()); +#I cant get the correct answer without implementing any short circuit logics +#thats why I print 2 outputs, for number of rounds and (number of rounds -1) + +#190777 p1 correct diff --git a/2018/aoc2018-d16.py b/2018/aoc2018-d16.py new file mode 100644 index 0000000..3bb0dc1 --- /dev/null +++ b/2018/aoc2018-d16.py @@ -0,0 +1,359 @@ +#advent of code 2018 +#day 16 +#part 1 and part 2 + +#when doing this puzzle I learned that I can make a list of functions and it just works +#code could use a bit of clean up, +#lots of multiple lines because of 16 functions +#(I could save ~32 lines just by modifying the functions) +#lots of work-arounds because I don't know to implement it efficently +#but still, I got the results + +f = open("input.txt",'r'); +Testing = False; +#Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); + +input_part1 = []; +input_part2 = []; +sublist = []; + +for l in f: + l = l.replace("\n",""); + if (len(l) == 0): + input_part1.append( sublist.copy() ); + sublist = []; + continue; + elif (l == "###"): + break; + elif (len(l) < 20): + sublist.append( [int(x) for x in l.split(" ")] ); + elif (l[6] == ":"): + sublist.append( eval(l[7:]) ); + elif (l[5] == ":"): + sublist.append( eval(l[7:]) ); +''' +for i in input_part1: + print(i[0], "\t", i[1], "\t", i[2], "\t") +''' + +for l in f: + l = l.replace("\n",""); + input_part2.append( [int(x) for x in l.split(" ")] ); + +''' +print(); +print(); +print(); +for i in input_part2: + print(i); +''' + +###opcode functions +def addr(before, op, aft): + bef = before.copy(); + C = bef[op[1]] + bef[op[2]]; + bef[op[3]] = C; + return bef; +def addi(before, op, aft): + bef = before.copy(); + C = bef[op[1]] + op[2]; + bef[op[3]] = C; + return bef; + +def mulr(before, op, aft): + bef = before.copy(); + C = bef[op[1]] * bef[op[2]]; + bef[op[3]] = C; + return bef; +def muli(before, op, aft): + bef = before.copy(); + C = bef[op[1]] * op[2]; + bef[op[3]] = C; + return bef; + +def banr(before, op, aft): + bef = before.copy(); + C = int(bef[op[1]] & bef[op[2]]); + bef[op[3]] = C; + return bef; +def bani(before, op, aft): + bef = before.copy(); + C = int(bef[op[1]] & op[2]); + bef[op[3]] = C; + return bef; + +def borr(before, op, aft): + bef = before.copy(); + C = int(bef[op[1]] | bef[op[2]]); + bef[op[3]] = C; + return bef; +def bori(before, op, aft): + bef = before.copy(); + C = int(bef[op[1]] | op[2]); + bef[op[3]] = C; + return bef; + +def setr(before, op, aft): + bef = before.copy(); + C = bef[op[1]]; + bef[op[3]] = C; + return bef; +def seti(before, op, aft): + bef = before.copy(); + C = op[1]; + bef[op[3]] = C; + return bef; + +def gtir(before, op, aft): + bef = before.copy(); + C = 0 + int( op[1] > bef[op[2]] ); + bef[op[3]] = C; + return bef; +def gtri(before, op, aft): + bef = before.copy(); + C = 0 + int( op[2] < bef[op[1]] ); + bef[op[3]] = C; + return bef; +def gtrr(before, op, aft): + bef = before.copy(); + C = 0 + int( bef[op[1]] > bef[op[2]] ); + bef[op[3]] = C; + return bef; + +def eqir(before, op, aft): + bef = before.copy(); + C = 0 + int( op[1] == bef[op[2]] ); + bef[op[3]] = C; + return bef; +def eqri(before, op, aft): + bef = before.copy(); + C = 0 + int( op[2] == bef[op[1]] ); + bef[op[3]] = C; + return bef; +def eqrr(before, op, aft): + bef = before.copy(); + C = 0 + int( bef[op[1]] == bef[op[2]] ); + bef[op[3]] = C; + return bef; + + +def threeormore(bef, op, aft): + fun = 1; + counter = 0; + out = aft.copy(); + counter += int( out == addr(bef,op,aft) ); + counter += int( out == addi(bef,op,aft) ); + counter += int( out == mulr(bef,op,aft) ); + counter += int( out == muli(bef,op,aft) ); + counter += int( out == banr(bef,op,aft) ); + counter += int( out == bani(bef,op,aft) ); + counter += int( out == borr(bef,op,aft) ); + counter += int( out == bori(bef,op,aft) ); + counter += int( out == setr(bef,op,aft) ); + counter += int( out == seti(bef,op,aft) ); + counter += int( out == gtir(bef,op,aft) ); + counter += int( out == gtri(bef,op,aft) ); + counter += int( out == gtrr(bef,op,aft) ); + counter += int( out == eqir(bef,op,aft) ); + counter += int( out == eqri(bef,op,aft) ); + counter += int( out == eqrr(bef,op,aft) ); + + return counter; + ''' + if (counter >= 3): + return 1; + else: + return 0; +''' + +part1 = 0; +for sample in input_part1: + before = sample[0]; + instruction = sample[1]; + after = sample[2]; + part1 += 1*(threeormore(before, instruction, after ) >=3); + +print("part 1 = ", part1); + +#776 yoo high +#588 correct +#my mistake - misunderstood bitwise AND and bitwise OR +#they dont return a boolean, just a normal integer +#my function was int(bool(value)), which was reducing the correct value to 1 + + + +#identifying single matches +''' +singles = []; +doubles = []; +triples = []; + +for sample in input_part1: + before = sample[0]; + instruction = sample[1]; + after = sample[2]; + if (threeormore(before, instruction, after ) == 1): + singles.append(instruction[0]); + if (threeormore(before, instruction, after ) == 2): + doubles.append(instruction[0]); + if (threeormore(before, instruction, after ) >= 3): + triples.append(instruction[0]); + #part1 += 1*(threeormore(before, instruction, after ) >=3); + +singles = list(dict.fromkeys(singles)); +doubles = list(dict.fromkeys(doubles)); +triples = list(dict.fromkeys(triples)); + +print("singles\t",len(singles), "\t", singles); +print("doubles\t",len(doubles), "\t", doubles); +print("triples\t",len(triples), "\t", triples); +''' + + + +def matchingfunctions(bef, op, aft): + functionlist = ""; + out = aft.copy(); + functionlist += "addr"*( out == addr(bef,op,aft) ); + functionlist += "addi"*( out == addi(bef,op,aft) ); + functionlist += "mulr"*( out == mulr(bef,op,aft) ); + functionlist += "muli"*( out == muli(bef,op,aft) ); + functionlist += "banr"*( out == banr(bef,op,aft) ); + functionlist += "bani"*( out == bani(bef,op,aft) ); + functionlist += "borr"*( out == borr(bef,op,aft) ); + functionlist += "bori"*( out == bori(bef,op,aft) ); + functionlist += "setr"*( out == setr(bef,op,aft) ); + functionlist += "seti"*( out == seti(bef,op,aft) ); + functionlist += "gtir"*( out == gtir(bef,op,aft) ); + functionlist += "gtri"*( out == gtri(bef,op,aft) ); + functionlist += "gtrr"*( out == gtrr(bef,op,aft) ); + functionlist += "eqir"*( out == eqir(bef,op,aft) ); + functionlist += "eqri"*( out == eqri(bef,op,aft) ); + functionlist += "eqrr"*( out == eqrr(bef,op,aft) ); + + return (op[0],functionlist); + +singles = []; +doubles = []; +triples = []; + +for sample in input_part1: + before = sample[0]; + instruction = sample[1]; + after = sample[2]; + if (threeormore(before, instruction, after ) == 1): + singles.append(matchingfunctions(before, instruction, after )); + if (threeormore(before, instruction, after ) == 2): + doubles.append(matchingfunctions(before, instruction, after )); + if (threeormore(before, instruction, after ) >= 3): + triples.append(matchingfunctions(before, instruction, after )); + #part1 += 1*(threeormore(before, instruction, after ) >=3); + +''' +print("singles\t",len(singles), "\t", singles); +print("doubles\t",len(doubles), "\t", doubles); +print("triples\t",len(triples), "\t", triples); +''' + +singles = list(dict.fromkeys(singles)); +doubles = list(dict.fromkeys(doubles)); +triples = list(dict.fromkeys(triples)); + +''' +for s in singles: + print(s); +print(); +print(); +for s in doubles: + print(s); +print(); +print(); +for s in triples: + print(s); +print(); +print(); +''' + +PossibleFunctions = {}; +total = singles + doubles + triples; + +for t in total: + PossibleFunctions.update({t[0] : t[1]}); + +''' +for pf in PossibleFunctions: + print(pf,"\t", PossibleFunctions[pf]); + ''' + +IdentifiedFunctions = {}; + + +while (len(IdentifiedFunctions) < 16): + for found in IdentifiedFunctions: + for possible in PossibleFunctions: + if (len(PossibleFunctions[possible]) > 4 ): + s = PossibleFunctions[possible]; + s = s.replace(IdentifiedFunctions[found], ""); + PossibleFunctions.update({possible : s}); + + for pf in PossibleFunctions: + if (len(PossibleFunctions[pf]) == 4 ): + IdentifiedFunctions.update({pf : PossibleFunctions[pf]}); + + ''' + for pf in PossibleFunctions: + print(pf,"\t", PossibleFunctions[pf]); + input(); + ''' + +''' +print(); +print(); +print(); +print("Identified Functions"); +for pf in IdentifiedFunctions: + print(pf,"\t", IdentifiedFunctions[pf]); +''' + +MatchFunctions = {}; +MatchFunctions.update({"addr":addr}); +MatchFunctions.update({"addi":addi}); +MatchFunctions.update({"mulr":mulr}); +MatchFunctions.update({"muli":muli}); +MatchFunctions.update({"banr":banr}); +MatchFunctions.update({"bani":bani}); +MatchFunctions.update({"borr":borr}); +MatchFunctions.update({"bori":bori}); +MatchFunctions.update({"setr":setr}); +MatchFunctions.update({"seti":seti}); +MatchFunctions.update({"gtir":gtir}); +MatchFunctions.update({"gtri":gtri}); +MatchFunctions.update({"gtrr":gtrr}); +MatchFunctions.update({"eqir":eqir}); +MatchFunctions.update({"eqri":eqri}); +MatchFunctions.update({"eqrr":eqrr}); + +for i in IdentifiedFunctions: + MatchFunctions.update({i:MatchFunctions[IdentifiedFunctions[i]]}); + +''' +print(); +print(); +print(); +print("Matched Functions"); +for pf in MatchFunctions: + print(pf,"\t", MatchFunctions[pf]); +''' + +reg = [0,0,0,0]; +for i in input_part2: + f_i = MatchFunctions[i[0]]; + reg = f_i(reg, i, [] ); + +part2 = reg[0]; +#print(reg); +print("part 2 = ", part2); diff --git a/2018/aoc2018-d17.py b/2018/aoc2018-d17.py new file mode 100644 index 0000000..30cd726 --- /dev/null +++ b/2018/aoc2018-d17.py @@ -0,0 +1,144 @@ +#advent of code 2018 +#day 17 +#part 1 and part 2 + +#for me this is one of the most time consuming puzzles for this year +#I got too cocky because I remembered a similar puzzle during 2022 edition +#unfortunately 2018 day 17 was more tricky +#I made 3 attempts, each time starting from scratch +#first time I just scrambled something, but there was no way to calculate when to stop the algo +#so the water was extremely overflowing +#for second attempt I wrote 2 functions, one for flowing downwards, second for spreading +#I spent a whole day "improving" the spreading function so it behaves correctly, to no avail +#I figured out the logic of the puzzle, but I kept getting weird errors +#such as water bursting through walls or flowing upwards +#I was adding more and more if-elses, but they weren't fixing these bugs: +#they were merely delaying them - after filling in the water correctly, the bugs were popping up again +#third and final attempt was successful - I already learned the logic of the algorithm, +#I just needed to implement it in bug-free way +#on the other hand, I managed to get a pretty good runtime. +#Every now and then I was looking up a solution for clues from others +#one of which Michael Fogleman, probably my most common resource for learning AoC 2018 +#while his code runs for almost a minute, mine just needs less than 0.05 secs +#it's really funny to "outperform" (in a way) someone whom you were constantly consulting for help +#one last thing I want to mention is that during the third attempt I kept getting wrong answer +#since I was only off by 3 and at the end there are only 3 waterfalls connecting to lowest point, +#I was convinced that I was calculating the solution for wrong range +#turns out I misunderstood the puzzle - you're supposed to calculate the amount of still +#and flowing water in range of highest wall point and the lowest wall point, +#while I kept calculating it in range from zero to lowest +#at least this time part2 was a freebee + +import time; + +f = open("input.txt",'r'); +Testing = False; +#Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); + +def parse_input(line): + line = line.replace("x=",""); + line = line.replace("y=",""); + line = line.replace("..",","); + line = "[" + line + "]"; + cords = eval(line); + return cords; #line coordinates: [x, y1, y2] or [y, x1, x2] + +Xmax = 500; #rightmost X coordinate, just for printing the area +Xmin = 500; #leftmost X coordinate, just for printing the area +Ymax = 0; #lowest Y coordinate, needed for solution +Ymin2 = 2000; #highest Y coordinate, needed for solution +LinesX = []; +LinesY = []; + +for l in f: + d = l[0]; #direction x or y + Cords = parse_input(l); + if d == "x": + Xmax = max(Cords[0], Xmax); + Xmin = min(Cords[0], Xmin); + Ymax = max(Cords[2], Ymax); + Ymin2 = min(Cords[1], Ymin2); + LinesX.append(Cords); + else: + Xmax = max(Cords[2], Xmax); + Xmin = min(Cords[1], Xmin); + Ymax = max(Cords[0], Ymax); + Ymin2 = min(Cords[0], Ymin2); + LinesY.append(Cords); + +Xmax += 1; +Xmin -= 1; +Ymin = 0; + +area = {}; +#initialize input into the area +for l in LinesX: + x = l[0]; + for y in range(l[1],l[2]+1): + area.update({(x,y):"#"}); +for l in LinesY: + y = l[0]; + for x in range(l[1],l[2]+1): + area.update({(x,y):"#"}); + +def wspread(cords, q): + r1 = 0; + r2 = 0; + x,y = cords; + while (area.get((x,y+1)," ") == "#" or area.get((x,y+1)," ") == "=") and area.get((x-1,y)," ") != "#": + r1 += 1; + x -= 1; + + x,y = cords; + while (area.get((x,y+1)," ") == "#" or area.get((x,y+1)," ") == "=") and area.get((x+1,y)," ") != "#": + r2 += 1; + x += 1; + + x,y = cords; + if area.get((x-r1-1,y)," ") == "#" and area.get((x+r2+1,y)," ") == "#": + for r in range(x-r1,x+r2+1): + area[(r,y)] = "="; + q.append((cords[0],cords[1]-1)); + else: + for r in range(x-r1,x+r2+1): + area[(r,y)] = "|"; + if area[(x-r1,y)] != "#" and area.get((x-r1,y+1)," ") == " ": + q.append((x-r1,y)); + if area[(x+r2,y)] != "#" and area.get((x+r2,y+1)," ") == " ": + q.append((x+r2,y)); + +def wfall(cords, q): + x,y = cords; + while area.get((x,y+1)," ")==" " and y < Ymax: + area[(x,y+1)] = "|"; + y += 1; + if area.get((x,y)," ")=="#" or area.get((x,y)," ")=="=": + q.append((x,y-1)); + elif y < Ymax: + q.append((x,y)); + +t1 = time.time(); +water = [(500,0)]; +area.update({(500,0):"|"}); + +while water: + w = water.pop(); + if area.get((w[0],w[1]+1)," ")==" ": + wfall(w, water); + else: + wspread(w, water); + +part1 = 0; +part2 = 0; +for a in area: + part1 += 1*(area[a]=="|" or area[a]=="=")*(a[1] >= Ymin2); + part2 += 1*(area[a]=="="); + +t2 = time.time(); + +print("part1 = ", part1); +print("part2 = ", part2); +print("runtime ", t2-t1); diff --git a/2018/aoc2018-d18.py b/2018/aoc2018-d18.py new file mode 100644 index 0000000..8d85635 --- /dev/null +++ b/2018/aoc2018-d18.py @@ -0,0 +1,131 @@ +#advent of code 2018 +#day 18 +#part 1 and part 2 + +#at first I thought I can find the loop by simply registering when a value "part2" is repeated once +#(kind of like in an earlier puzzle for that year) +#then I had a correct idea how to find the pattern, +#but didn't really know how to implement it efficently +#pattern recognition is an implementation of solution provided by Michael Fogleman +#adjusted to my current code +#another issue I had was that I resumed the calculations for part 2 from the state after 10 minutes (part1) +#I needed to save the initial state and then start over +#could probably reduce the code to single loop instead of two separate loops for each part + +f = open("input.txt",'r'); +Testing = False; +#Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); + +size = 50; +if Testing: size = 10; + +#part 1 + +CurrentState = {}; + +for r,l in enumerate(f): + #print(len(l)); + for c,a in enumerate(l): + CurrentState.update({(r,c):a}); +InitialState = CurrentState.copy(); +f.close(); + +for x in range(size): + for y in range(size): + print(CurrentState[(x,y)],end=""); + print(); + +#check if each adjacent position is still within grid range +def GetAdjacent(Cords): + Adjacent = []; + if (Cords[0] -1 >= 0 and Cords[1]-1 >=0): + Adjacent.append( (Cords[0] -1,Cords[1]-1) ); + if (Cords[0] -1 >= 0): + Adjacent.append( (Cords[0] -1,Cords[1]) ); + if (Cords[0] -1 >= 0 and Cords[1]+1 < size): + Adjacent.append( (Cords[0] -1,Cords[1]+1) ); + if (Cords[1]+1 < size): + Adjacent.append( (Cords[0],Cords[1]+1) ); + if (Cords[1]-1 >= 0): + Adjacent.append( (Cords[0],Cords[1]-1) ); + if (Cords[0] +1 < size and Cords[1]-1 >=0): + Adjacent.append( (Cords[0] +1,Cords[1]-1) ); + if (Cords[0] +1 < size): + Adjacent.append( (Cords[0] +1,Cords[1]) ); + if (Cords[0] +1 < size and Cords[1]+1 < size): + Adjacent.append( (Cords[0] +1,Cords[1]+1) ); + return Adjacent; + +def GetAcres(area, adj): + acres = []; + for c in adj: + acres.append(area[c]); + return acres; + +def ChangeState(area, Cords): + s = area[Cords]; + adj = GetAdjacent(Cords); + Acres = GetAcres(area, adj); + if (s == "." and Acres.count("|")>=3): + s = "|"; + elif (s == "|" and Acres.count("#")>=3): + s = "#"; + elif (s == "#" and Acres.count("#")>=1 and Acres.count("|")>=1): + s = "#"; + elif (s == "#"): + s = "."; + return s; + +SimTime = 10; #minutes + +InitialState = CurrentState.copy(); +for t in range(SimTime): + NextState = {}; + for x in range(size): + for y in range(size): + NextState.update({(x,y):ChangeState(CurrentState,(x,y))}); + CurrentState = NextState.copy(); + ''' + print("MINUTE ",t); + for x in range(size): + for y in range(size): + print(CurrentState[(x,y)],end=""); + print(); + print(); + ''' +summary = list(CurrentState.values()); + +woods = summary.count("|"); +lumbs = summary.count("#"); +part1 = woods*lumbs; +print("part 1 = ", part1); + +#part 2 + +SimTime2 = 1000000000; #minutes for part2 +values = {}; +prev = 0; + +CurrentState = InitialState.copy(); +for t in range(1,SimTime2): + NextState = {}; + for x in range(size): + for y in range(size): + NextState.update({(x,y):ChangeState(CurrentState,(x,y))}); + CurrentState = NextState.copy(); + summary = list(CurrentState.values()); + woods = summary.count("|"); + lumbs = summary.count("#"); + part2 = woods*lumbs; + loop = t - values.get(part2,0); + if (loop == prev): + if SimTime2%loop == t%loop: + break; + values[part2]=t; + prev = loop; + +print("part 2 = ", part2); + diff --git a/2018/aoc2018-d19.py b/2018/aoc2018-d19.py new file mode 100644 index 0000000..51ad39e --- /dev/null +++ b/2018/aoc2018-d19.py @@ -0,0 +1,180 @@ +#advent of code 2018 +#day 19 +#part 1 and part 2 + +#part 1 was very easy since it reused day 16 instructions +#for part 2 I was at first tricked by the maximum value stored in the register +#then I was tricked again by the value that was increasing by constant value +#which is really stupid on my part because I forgot that the answer to puzzle +#was value stored at register [0] - so none of the two above +#the value at reg[0] stores a sum of all divisors of +#the max value mentioned before +#it took me a while to understand it - that was a tricky part 2 (as usual) + +###opcode functions +#bit modified version of day 16 - removed 'after' list +def addr(before, op): + bef = before.copy(); + C = bef[op[1]] + bef[op[2]]; + bef[op[3]] = C; + return bef; +def addi(before, op): + bef = before.copy(); + C = bef[op[1]] + op[2]; + bef[op[3]] = C; + return bef; + +def mulr(before, op): + bef = before.copy(); + C = bef[op[1]] * bef[op[2]]; + bef[op[3]] = C; + return bef; +def muli(before, op): + bef = before.copy(); + C = bef[op[1]] * op[2]; + bef[op[3]] = C; + return bef; + +def banr(before, op): + bef = before.copy(); + C = int(bef[op[1]] & bef[op[2]]); + bef[op[3]] = C; + return bef; +def bani(before, op): + bef = before.copy(); + C = int(bef[op[1]] & op[2]); + bef[op[3]] = C; + return bef; + +def borr(before, op): + bef = before.copy(); + C = int(bef[op[1]] | bef[op[2]]); + bef[op[3]] = C; + return bef; +def bori(before, op): + bef = before.copy(); + C = int(bef[op[1]] | op[2]); + bef[op[3]] = C; + return bef; + +def setr(before, op): + bef = before.copy(); + C = bef[op[1]]; + bef[op[3]] = C; + return bef; +def seti(before, op): + bef = before.copy(); + C = op[1]; + bef[op[3]] = C; + return bef; + +def gtir(before, op): + bef = before.copy(); + C = 0 + int( op[1] > bef[op[2]] ); + bef[op[3]] = C; + return bef; +def gtri(before, op): + bef = before.copy(); + C = 0 + int( op[2] < bef[op[1]] ); + bef[op[3]] = C; + return bef; +def gtrr(before, op): + bef = before.copy(); + C = 0 + int( bef[op[1]] > bef[op[2]] ); + bef[op[3]] = C; + return bef; + +def eqir(before, op): + bef = before.copy(); + C = 0 + int( op[1] == bef[op[2]] ); + bef[op[3]] = C; + return bef; +def eqri(before, op): + bef = before.copy(); + C = 0 + int( op[2] == bef[op[1]] ); + bef[op[3]] = C; + return bef; +def eqrr(before, op): + bef = before.copy(); + C = 0 + int( bef[op[1]] == bef[op[2]] ); + bef[op[3]] = C; + return bef; + +MatchFunctions = {}; +MatchFunctions.update({"addr":addr}); +MatchFunctions.update({"addi":addi}); +MatchFunctions.update({"mulr":mulr}); +MatchFunctions.update({"muli":muli}); +MatchFunctions.update({"banr":banr}); +MatchFunctions.update({"bani":bani}); +MatchFunctions.update({"borr":borr}); +MatchFunctions.update({"bori":bori}); +MatchFunctions.update({"setr":setr}); +MatchFunctions.update({"seti":seti}); +MatchFunctions.update({"gtir":gtir}); +MatchFunctions.update({"gtri":gtri}); +MatchFunctions.update({"gtrr":gtrr}); +MatchFunctions.update({"eqir":eqir}); +MatchFunctions.update({"eqri":eqri}); +MatchFunctions.update({"eqrr":eqrr}); + +#end of day16 copy-paste +############################################### + +f = open("input.txt",'r'); +Testing = False; +#Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); + +ip = int(f.readline()[4:]); +instructions = []; + +for l in f: + l = l.split(); + i = []; + i.append(l[0]); + l_i = [int(x) for x in l[1:]]; + i += l_i; + instructions.append(i); + +instr_lim = len(instructions); +reg = [0,0,0,0,0,0]; +reg[ip] = 0; + +while True: + if( reg[ip] >= instr_lim): break; + instr = instructions[reg[ip]]; + fun = MatchFunctions[instr[0]]; + reg = fun(reg,instr); + + reg[ip] += 1; + +part1 = reg[0]; +print("part 1 = ", part1); + +reg = [1,0,0,0,0,0]; +reg[ip] = 0; +counter = 1; + +while True: + if( reg[ip] >= instr_lim): break; + instr = instructions[reg[ip]]; + fun = MatchFunctions[instr[0]]; + reg = fun(reg,instr); + + if (counter%1000 == 0): + print(reg); + y1 = reg[1]; + break; + + reg[ip] += 1; + counter += 1; + +maxval = max(reg); +part2 = 0; +for x in range(1,maxval+1): + if maxval%x == 0: part2 += x; + +print("part 2 = ", part2); diff --git a/2018/aoc2018-d20.py b/2018/aoc2018-d20.py new file mode 100644 index 0000000..06241f5 --- /dev/null +++ b/2018/aoc2018-d20.py @@ -0,0 +1,115 @@ +#advent of code 2018 +#day 20 +#part 1 and part 2 + +#I struggled with indexing when parsing the input +#I was getting more doors mapped than there really were +#the issue was that after parsing the content of a bracket +#I was retreiving a ")" sign instead of the following instruction like N or W +#+1 to the index did the work +#a bit disappointed with part 2, on which I spent more time reading it than coding + +f = open("input.txt",'r'); +Testing = False; +#Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); + +inputline = f.readline(); +inputline = inputline[1:-1]; +f.close(); +#split the contents of a bracket into separate strings, return a list of those strings +def parse_brackets(regex): + regex = regex[1:]; + close_brackets_sign = ")"; + close_brackets_count = 1; + subsets = []; + subset = ""; + for i, c in enumerate(regex): + if c == "(": + close_brackets_count += 1; + subset += c; + elif c == close_brackets_sign: + if close_brackets_count == 1: + subsets.append(subset); + break; + else: + close_brackets_count -= 1; + subset += c; + elif c == "|": + if close_brackets_count == 1: + subsets.append(subset); + subset = ""; + else: subset += c; + else: subset += c; + return i, subsets; +#fill up the "area" dictionary with rooms and doors based on provided instruction +#recursive function, the function is called again if the path is branching due to brackets +def parse_input(inputline, Cords, grid): + i = 0; + d = (0,0); + CurrentCords = Cords; + CurrentCords = (CurrentCords[0] +d[0],CurrentCords[1] +d[1]); + while i < len(inputline): + c = inputline[i]; + if c == "(": + x, subs = parse_brackets(inputline[i:]); + for s in subs: + parse_input(s, CurrentCords, grid); + i += x+1; + elif c == "$": + break; + else: + if c == "N": + d = (0,-1); + elif c == "S": + d = (0,1); + elif c == "W": + d = (-1,0); + elif c == "E": + d = (1,0); + CurrentCords = (CurrentCords[0] +d[0],CurrentCords[1] +d[1]); + grid.update({CurrentCords:"D"}); + CurrentCords = (CurrentCords[0] +d[0],CurrentCords[1] +d[1]); + grid.update({CurrentCords:"."}); + i += 1; + +area = {}; +p = (0,0); +area.update({p:"."}); + +parse_input(inputline, p, area); +#print the map of the area +''' +maxX = max([x[0] for x in area]); +minX = min([x[0] for x in area]); +maxY = max([y[1] for y in area]); +minY = min([y[1] for y in area]); + +for y in range(minY-1, maxY+1+1): + for x in range(minX-1, maxX+1+1): + cp = area.get((x,y),"#"); + if x==0 and y==0: cp = "X"; + print(cp, end=""); + print(); +''' + +distances = {}; +queue = [(0,0,0)]; + +while queue: + x,y,d = queue.pop(); + if ((x,y) in distances and distances.get((x,y)) <= d): + continue; + distances.update({(x,y):d}); + if (x+1,y) in area and (x+2,y) in area: queue.append((x+2,y,d+1)); + if (x-1,y) in area and (x-2,y) in area: queue.append((x-2,y,d+1)); + if (x,y+1) in area and (x,y+2) in area: queue.append((x,y+2,d+1)); + if (x,y-1) in area and (x,y-2) in area: queue.append((x,y-2,d+1)); + +part1 = max([distances[dist] for dist in distances]); +print("part1 = ", part1); + +part2 =len([distances[dist] for dist in distances if distances[dist]>=1000]); +print("part2 = ", part2); diff --git a/2018/aoc2018-d21.py b/2018/aoc2018-d21.py new file mode 100644 index 0000000..890b13d --- /dev/null +++ b/2018/aoc2018-d21.py @@ -0,0 +1,253 @@ +#advent of code 2018 +#day 21 +#part 1 and part 2 + +#this puzzle in my opinion was poorly worded, or I'm just overthinking +#part 1 was suprisingly simple since it only required running the solution for day 19 +#unfortunately, bruteforcing the answer for part 2 didn't go as well +#reading through input its possible to identify instruction jumps and determine what causes them +#I was stuck for like 2 days for part 2: I couldn't find a bug in my reverse-engineering +#I even run someone else's solution (modified for my input) to verify it +#only to get another wrong answer +#I found a second solution and I compared it to mine +#only to find out that the issue wasn't in logic, I simply entered wrong value in 1 line +#at least this reverse-engineering puzzle was for me more enjoyable than the 2021 one + +#part 1 bruteforce +#program halts if the value at register 0 matches the value at register X +#(register X is between 1 and 5, depends on the input) +#in one particular instruction near the end +#instruction 28 in my case +#calculating this value provides part 1 result + +#part 2 reverse engineering +#you can simplify the input program by reverse-engineering +#basically the first few lines are trash, then the program is initiated with starting values +#if condition 1 is met, program enters a loop until condition 1 is no longer true +#after this loop, program checks if the value at register 0 is equal to corresponding register X +#if true, program halts +#you can print out all values at register X, first printed message is part1, last one is part 2 + + +###opcode functions +#bit modified version of day 19 +def addr(before, op): + bef = before.copy(); + C = bef[op[1]] + bef[op[2]]; + bef[op[3]] = C; + return bef; +def addi(before, op): + bef = before.copy(); + C = bef[op[1]] + op[2]; + bef[op[3]] = C; + return bef; + +def mulr(before, op): + bef = before.copy(); + C = bef[op[1]] * bef[op[2]]; + bef[op[3]] = C; + return bef; +def muli(before, op): + bef = before.copy(); + C = bef[op[1]] * op[2]; + bef[op[3]] = C; + return bef; + +def banr(before, op): + bef = before.copy(); + C = int(bef[op[1]] & bef[op[2]]); + bef[op[3]] = C; + return bef; +def bani(before, op): + bef = before.copy(); + C = int(bef[op[1]] & op[2]); + bef[op[3]] = C; + return bef; + +def borr(before, op): + bef = before.copy(); + C = int(bef[op[1]] | bef[op[2]]); + bef[op[3]] = C; + return bef; +def bori(before, op): + bef = before.copy(); + C = int(bef[op[1]] | op[2]); + bef[op[3]] = C; + return bef; + +def setr(before, op): + bef = before.copy(); + C = bef[op[1]]; + bef[op[3]] = C; + return bef; +def seti(before, op): + bef = before.copy(); + C = op[1]; + bef[op[3]] = C; + return bef; + +def gtir(before, op): + bef = before.copy(); + C = 0 + int( op[1] > bef[op[2]] ); + bef[op[3]] = C; + return bef; +def gtri(before, op): + bef = before.copy(); + C = 0 + int( op[2] < bef[op[1]] ); + bef[op[3]] = C; + return bef; +def gtrr(before, op): + bef = before.copy(); + C = 0 + int( bef[op[1]] > bef[op[2]] ); + bef[op[3]] = C; + return bef; + +def eqir(before, op): + bef = before.copy(); + C = 0 + int( op[1] == bef[op[2]] ); + bef[op[3]] = C; + return bef; +def eqri(before, op): + bef = before.copy(); + C = 0 + int( op[2] == bef[op[1]] ); + bef[op[3]] = C; + return bef; +def eqrr(before, op): + bef = before.copy(); + C = 0 + int( bef[op[1]] == bef[op[2]] ); + bef[op[3]] = C; + return bef; + +MatchFunctions = {}; +MatchFunctions.update({"addr":addr}); +MatchFunctions.update({"addi":addi}); +MatchFunctions.update({"mulr":mulr}); +MatchFunctions.update({"muli":muli}); +MatchFunctions.update({"banr":banr}); +MatchFunctions.update({"bani":bani}); +MatchFunctions.update({"borr":borr}); +MatchFunctions.update({"bori":bori}); +MatchFunctions.update({"setr":setr}); +MatchFunctions.update({"seti":seti}); +MatchFunctions.update({"gtir":gtir}); +MatchFunctions.update({"gtri":gtri}); +MatchFunctions.update({"gtrr":gtrr}); +MatchFunctions.update({"eqir":eqir}); +MatchFunctions.update({"eqri":eqri}); +MatchFunctions.update({"eqrr":eqrr}); + +#end of day19 copy-paste +############################################### + +f = open("input.txt",'r'); +Testing = False; +#Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); + +ip = int(f.readline()[4:]); +instructions = []; + +for l in f: + l = l.split(); + i = []; + i.append(l[0]); + l_i = [int(x) for x in l[1:]]; + i += l_i; + instructions.append(i); + + +part1 = None; +instr_lim = len(instructions); + +while True: + reg = [0,0,0,0,0,0]; + reg[ip] = 0; + part1 = None; + + while True: + if( reg[ip] >= instr_lim): break; + if( reg[ip] >= 28): + #print(reg); + part1 = int(reg[5]); + break; + instr = instructions[reg[ip]]; + fun = MatchFunctions[instr[0]]; + reg = fun(reg,instr); + reg[ip] += 1; + + if part1 != None: + break; + +print("part 1 = ", part1, "(bruteforce)"); + +#part2 + +store1 = set(); #var ehich determines if the loop continues +store5 = set(); #var checked against the reg0 +part1 = None; +part2 = None; +p2 = None; + +reg5 = 10678677; +reg1 = 2**16; +while True: + reg4 = reg1%256; + reg5 += reg4; + reg5 = ((reg5%2**24)*65899)%(2**24); + + if reg1<256: + if not store5: + part1 = int(reg5); + if reg5 not in store5: + part2 = int(reg5); + store5.add(reg5); + #print("regs", reg1, reg5) + reg1 = reg5 | 2**16; + if reg1 in store1: + break; + store1.add(reg1); + reg5 = 10678677; + continue; + + reg1 = reg1//256; + +print("part 1 = ", part1); +print("part 2 = ", part2); + +#my input +''' +#ip 2 +seti 123 0 5 +bani 5 456 5 +eqri 5 72 5 +addr 5 2 2 +seti 0 0 2 +seti 0 4 5 +bori 5 65536 1 +seti 10678677 3 5 +bani 1 255 4 +addr 5 4 5 +bani 5 16777215 5 +muli 5 65899 5 +bani 5 16777215 5 +gtir 256 1 4 +addr 4 2 2 +addi 2 1 2 +seti 27 5 2 +seti 0 6 4 +addi 4 1 3 +muli 3 256 3 +gtrr 3 1 3 +addr 3 2 2 +addi 2 1 2 +seti 25 4 2 +addi 4 1 4 +seti 17 6 2 +setr 4 6 1 +seti 7 5 2 +eqrr 5 0 4 +addr 4 2 2 +seti 5 4 2 +''' diff --git a/2018/aoc2018-d22.py b/2018/aoc2018-d22.py new file mode 100644 index 0000000..7dd7a86 --- /dev/null +++ b/2018/aoc2018-d22.py @@ -0,0 +1,136 @@ +#advent of code 2018 +#day 22 +#part 1 and part 2 + +#at this point Im used to pathfinding problems, so I expected an easy 2-star +#I started with a recursive djikstra-algo function, but unfortunately +#for the actual input, I was reaching the maximum number of recurrences +#my plan B was a queue, which in general was correct, but I was missing one detail +#the problem isnt 2D pathfinding, but 4D (width, depth, time AND equipment) +#to discover this I needed to look up a solution on reddit +#said solution reminded me of heapq module which I already intended to learn +#the results were great - my initial no-heapq code needed almost 10 minutes to finish +#while with heapq whole program ran for less than half a second +#while I tried to compensate for the equipment variable with some +#"guess which equipment is probably the best choice when traversing" +#it didnt really help as much as heapq +#anyway, I still wasnt getting the correct answer +#This time the issue was in the design: +#in order to account for regions that are outside the initial scope +#(within target coordinates range) I simply scaled up the whole map by constant factor +#for factor = 2 the map still wasnt big enough to create the shortest path +#I needed to scale it up by factoer = 6 to get the correct result +#while this scale-up strategy isnt *that* bad for square-ish maps +#this map is extremely deep, but not very wide +#I really liked the idea to calculate the region type on the spot for part2 +#which I noticed only after struggling for 3 hours to fix my code +#might redo the part2 to fix this +#if the code doesnt provide correct results for part 2, try changing the SCALE variable +#to a bigger number +# + + +import time; +import heapq; + +f = open("input.txt",'r'); +Testing = False; +#Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); + +depth = eval(f.readline().replace("depth: ","")); +target = tuple(eval(f.readline().replace("target: ",""))); +f.close(); +#determine the type of region and other parameters +class region: + def __init__(self, pos, erosion1, erosion2): + self.Distance = 99999; #for when I tried to use djikstra + self.Equipped = None; + self.pos = pos; + if pos == (0,0) or pos == target: self.geo = 0; + elif pos[0] == 0: self.geo = pos[1]*48271; + elif pos[1] == 0: self.geo = pos[0]*16807; + else: self.geo = erosion1*erosion2; + self.erosion = (self.geo + depth)%20183; + self.risk = self.erosion%3; + if (self.risk == 0): + self.type = "R"; + self.Gear = ["T","C"]; + elif (self.risk == 1): + self.type = "W"; + self.Gear = ["C","N"]; + elif (self.risk == 2): + self.type = "N"; + self.Gear = ["T","N"]; + def GetAdjacent(self, grid): #hard to read, should remake this func, but not feeling like it + nextcords = []; + nx, ny = self.pos[0]-1, self.pos[1]; + if nx in range(SCALE*target[0] +1) and ny in range(SCALE*target[1] +1): nextcords.append((nx,ny)); + nx, ny = self.pos[0]+1, self.pos[1]; + if nx in range(SCALE*target[0] +1) and ny in range(SCALE*target[1] +1): nextcords.append((nx,ny)); + nx, ny = self.pos[0], self.pos[1]-1; + if nx in range(SCALE*target[0] +1) and ny in range(SCALE*target[1] +1): nextcords.append((nx,ny)); + nx, ny = self.pos[0], self.pos[1]+1; + if nx in range(SCALE*target[0] +1) and ny in range(SCALE*target[1] +1): nextcords.append((nx,ny)); + + return nextcords; + +area = {}; +mouth = (0,0); +part1 = 0; + +#for part 2: +#scale up the area with SCALE - wrong idea, see comment at the start +#SCALE is a variable in case it needs to be adjusted later +SCALE = 6; +#initiate area and calculate part 1 +for y in range(SCALE*target[1] +1): + for x in range(SCALE*target[0] +1): + ero1 = 0; + ero2 = 0; + r1 = area.get((x-1,y),None); + r2 = area.get((x,y-1),None); + if r1 != None: ero1 = r1.erosion; + if r2 != None: ero2 = r2.erosion; + area.update({(x,y):region((x,y),ero1,ero2)}); #brackets puke + if ( x in range(target[0] +1) and y in range(target[1] +1)): + part1 += area[(x,y)].risk; + +print("part 1 = ", part1); + +equip = "T"; +area[mouth].Distance = 0; +area[mouth].Equipped = equip; +gears = ["T","C","N"]; +queue = [(0, mouth, "T")]; +distances = {}; #obviously I meant time, but technically the same thing + +t1 = time.time(); +while queue: + d, p, e = heapq.heappop(queue); + if (p[0],p[1],e) in distances and distances[(p[0],p[1],e)] <= d: continue; + distances[(p[0],p[1],e)] = d; #update distances with the shorter path + #if the current region is the target and we're holding a torch - finish loop + if p == target and e == "T": + area[p].Equipped = e; + area[p].Distance = d; + break; + #push to queue the same region but with changed gear + for g in gears: + if g != e and g in area[p].Gear: + heapq.heappush(queue, (d+7,p,g)); + #push to queue the adjacent regions + neighbours = area[p].GetAdjacent(area); + for neighbour in neighbours: + if not e in area[neighbour].Gear: continue; + heapq.heappush(queue,(d+1,neighbour,e)); + +t2= time.time(); + +part2 = area[target].Distance; +print("part2 = ", part2); +print("\tpart 2 runtime ", t2-t1, "s"); + + diff --git a/2018/aoc2018-d23-1.py b/2018/aoc2018-d23-1.py new file mode 100644 index 0000000..a387337 --- /dev/null +++ b/2018/aoc2018-d23-1.py @@ -0,0 +1,47 @@ +#advent of code 2018 +#day 23 +#part 1 and part 2 + + +f = open("input.txt",'r'); +Testing = False; +#Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); + +def manhattan(pos1, pos2): + mx = abs(pos1[0] - pos2[0]); + my = abs(pos1[1] - pos2[1]); + mz = abs(pos1[2] - pos2[2]); + return mx + my + mz; + +class nanobot: + def __init__(self, pos, r): + self.pos = pos; + self.radius = r; + def __str__(self): + return f'pos={self.pos}, r={self.radius}'; + +bots = []; +for l in f: + l = l.replace("<","("); + l = l.replace(">",")"); + l = l.replace("r=",""); + l = l.replace("pos=",""); + p, r = eval(l); + bots.append(nanobot(p,r)); + +f.close(); + +strongest_radius = 0; +strongest_pos = None; +for bot in bots: + if bot.radius > strongest_radius: + strongest_radius = bot.radius; + strongest_pos = bot.pos; + +part1 = 0; +for bot in bots: + if (manhattan(strongest_pos, bot.pos) <= strongest_radius): part1 += 1; +print("part1 = ", part1); diff --git a/2018/aoc2018-d24.py b/2018/aoc2018-d24.py new file mode 100644 index 0000000..e5b45f5 --- /dev/null +++ b/2018/aoc2018-d24.py @@ -0,0 +1,211 @@ +#advent of code 2018 +#day 24 +#part 1 and part 2 + +#this was very fun to do +#easier version of 2018 day 15 due to no pathfinding +#part 1 no probs, but it took me way more time to finish part 2 than it should have +#at first I didn't account for a possible stalemate, but it was late at night +#(I read the input and didn't see any stalemate scenarios based on weaknesses +#but now that I think about it I was reading the testinput from the example lol) +#so I was trying to debug whats wrong with my current code +#instead of adding the few lines to resolve the stalemates +#the groups were simply refusing to fight +#but to be fair, there definitely were some bugs in a previous version, +#because I still wasn't getting the answer even when milk boost value was getting huge + +import copy; #library required for the deepcopy function + +f = open("input.txt",'r'); +Testing = False; +#Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); + +def readinput(group): + if group.find("(") != -1: + immu_weak = group[group.find("("):group.find(")")+1]; + group = group.replace(immu_weak, ""); + immu_weak = immu_weak.replace("(",""); + immu_weak = immu_weak.replace(")",""); + immu_weak = immu_weak.replace(", ",","); + if immu_weak.find(";") != -1: + if (immu_weak[0] == "i"): + i_i = 0; + w_i = 1; + elif (immu_weak[0] == "w"): + i_i = 1; + w_i = 0; + immu_weak = immu_weak.replace("weak to ",""); + immu_weak = immu_weak.replace("immune to ",""); + immu_weak = immu_weak.replace(" ",""); + iw = immu_weak.split(";"); + immu = iw[i_i].split(","); + weak = iw[w_i].split(","); + elif immu_weak[0] == "w": + immu_weak = immu_weak.replace("weak to ",""); + immu = []; + weak = immu_weak.split(","); + else: + weak = []; + immu_weak = immu_weak.replace("immune to ",""); + immu = immu_weak.split(","); + else: + immu = []; + weak = []; + group = group.replace("units each with", " "); + group = group.replace("hit points", " "); + group = group.replace("with an attack that does", " "); + group = group.replace("damage at initiative", " "); + g = group.split(); + gr = [int(x) for x in g[:-2]]; + gr.append(g[-2]); + gr.append(int(g[-1])); + gr.append(immu); + gr.append(weak); + return gr; + + +class army: + def __init__(self, side, ID, inputlist): + self.side = side; + self.id = ID; + self.units = inputlist[0]; + self.hp = inputlist[1]; + self.dmgVal = inputlist[2]; + self.dmgType = inputlist[3]; + self.initiative = inputlist[4]; + self.immune = inputlist[5]; + self.weak = inputlist[6]; + self.IsDead = False; + self.IsTargeted = False; + self.Target = None; + def __str__(self): + return f'<{self.side}>: {self.units} units each with {self.hp} hit points (immune to {self.immune}; weak to {self.weak}) with an attack that does {self.dmgVal} {self.dmgType} damage at initiative {self.initiative}'; + + def EffectivePower(self,TargetWeak,TargetImmune): + DamageDealt = self.units*self.dmgVal; + if self.dmgType in TargetWeak: + DamageDealt = DamageDealt*2; + elif self.dmgType in TargetImmune: + DamageDealt = 0; + return DamageDealt; + + def TakeDamage(self, DamageReceived): + UnitsKilled = DamageReceived//self.hp; + self.units -= UnitsKilled; + if self.units <= 0: + self.IsDead = True; + self.units = 0; + +############ +#parse input +groups = {}; +side = "imm"; +currentid = 11; +f.readline(); +for l in f: + if(l=="\n"): break; + groups.update({currentid:army(side,currentid,readinput(l))}); + currentid += 1; +f.readline(); +side = "inf"; +for l in f: + if(l=="\n"): break; + groups.update({currentid:army(side,currentid,readinput(l))}); + currentid += 1; +f.close(); + +immsys = 0; +infect = 0; +for g in groups: + if groups[g].side == "imm": immsys +=1; + if groups[g].side == "inf": infect +=1; + +milk = 0; +groupcopy = copy.deepcopy(groups); #deepcopy of groups to reset them + +winner = "inf"; #just to initiate the algo + +#keep doing battles until immune system wins +while winner == "inf": + groups = copy.deepcopy(groupcopy); + #count the initial number of groups for immune system and infection + #apply milk booster to immune system + immsys = 0; + infect = 0; + for g in groups: + if groups[g].side == "imm": immsys +=1; + if groups[g].side == "inf": infect +=1; + if groups[g].side == "imm": groups[g].dmgVal += milk; + groups[g].IsDead = False; + + #battle algorythm + while immsys > 0 and infect > 0: + kills = 0; + UnitsBefore = 0; + for g in groups: + UnitsBefore += groups[g].units; + #phase 1 target selection + TSqueue = [g for g in groups if groups[g].IsDead == False]; + TSqueue = sorted(TSqueue, key=lambda g: (groups[g].EffectivePower([],[]),groups[g].initiative), reverse = True); + for a in TSqueue: + groups[a].Target = None; + PossibleTargets = [g for g in groups if groups[g].IsDead == False and groups[g].side != groups[a].side]; + PossibleTargets = sorted(PossibleTargets, key=lambda g: (groups[a].EffectivePower(groups[g].weak,groups[g].immune),groups[g].EffectivePower([],[]),groups[g].initiative), reverse=True); + for t in PossibleTargets: + if groups[t].IsTargeted == False and groups[a].EffectivePower(groups[t].weak,groups[t].immune) > 0: + groups[a].Target = int(t); + groups[t].IsTargeted = True; + break; + + #phase 2 attacking + ATqueue = TSqueue.copy(); + ATqueue = sorted(ATqueue, key=lambda g: groups[g].initiative, reverse = True); + for a in ATqueue: + if groups[a].IsDead or groups[a].Target == None: continue; + t = groups[a].Target; + groups[t].TakeDamage( groups[a].EffectivePower(groups[t].weak,groups[t].immune) ); + + #reset the IsTargeted parameter for the next iteration of the battle + #count the groups of each side and calculate kills + immsys = 0; + infect = 0; + UnitsAfter = 0; + for g in groups: + groups[g].IsTargeted = False; + if groups[g].side == "imm" and groups[g].IsDead == False: immsys +=1; + if groups[g].side == "inf" and groups[g].IsDead == False: infect +=1; + UnitsAfter += groups[g].units; + + #if there were no kills in the current iteration of battle - finish the battle + kills = UnitsBefore - UnitsAfter; + if kills == 0: + break; + + #declare the winner (infection wins in case of a stalemate) + if kills == 0: + winner = "inf"; + elif immsys == 0: + winner = "inf"; + else: + winner = "imm"; + + #calculate part 1 + if milk == 0: + part1 = 0; + for g in groups: + if groups[g].side == winner and groups[g].IsDead == False: + part1 += groups[g].units; + + milk += 1; #raise milk booster for upcoming new battle + +#calculate part 2 +part2 = 0; +for g in groups: + if groups[g].side == winner and groups[g].IsDead == False: + part2 += groups[g].units; + +print("part 1 = ", part1); +print("part 2 = ", part2); diff --git a/2018/aoc2018-d25.py b/2018/aoc2018-d25.py new file mode 100644 index 0000000..37367df --- /dev/null +++ b/2018/aoc2018-d25.py @@ -0,0 +1,69 @@ +#advent of code 2018 +#day 25 +#part 1 + +#at first seemed really easy, then it got a bit more complex +#but then again it seemed easy again +#it just required a bit more thought to put into +#could probably be bit more optimized, especially with Constellations variable +#which could be a simple counter instead of a list, but w/e + +f = open("input.txt",'r'); +Testing = False; +#Testing = True; +if Testing: + f.close(); + f = open("testinput.txt",'r'); + +class spacepoint: + def __init__( self, coords ): + self.Coords = coords; + self.Adjacent = []; + self.Visited = False; + + def manh_dist(self, OtherPoint): #calculate manhattan distance from self to OtherPoint + m = 0; + m += abs(self.Coords[0] - OtherPoint[0]); + m += abs(self.Coords[1] - OtherPoint[1]); + m += abs(self.Coords[2] - OtherPoint[2]); + m += abs(self.Coords[3] - OtherPoint[3]); + return m; + #add all points from the grid that are within range to the "Adjacent" property + def get_adjacent(self, grid): + for g in grid: + if self == grid[g]: continue; + if (self.manh_dist(grid[g].Coords) <= 3): + self.Adjacent.append(g); + #recursive function(method) to make a list of all points that are in the same constellation + #"Visited" property prevents an infinite loop + def Find_Subset(self, grid, subset): + self.Visited = True; + subset.extend(self.Adjacent); + for n in self.Adjacent: + if grid[n].Visited: continue; + subset = grid[n].Find_Subset(grid, subset); + return subset; + + def __str__(self): + return f'{self.Coords}'; + +#parse input into the program +FixedPoints = {}; +for l in f: + l = "(" + l + ")"; + p = eval(l); + FixedPoints.update({p:spacepoint(p)}); +f.close(); + +#calculate neighbouring points for each point from input +for p in FixedPoints: + FixedPoints[p].get_adjacent(FixedPoints); + +#find all constellations +Constellations = []; +for p in FixedPoints: + if FixedPoints[p].Visited: continue; + Constellations.append(len(set(FixedPoints[p].Find_Subset(FixedPoints, [p])))); + +part1 = len(Constellations); +print("part 1 = ", part1); -- cgit v1.2.3