diff options
56 files changed, 5509 insertions, 0 deletions
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<ssy);
+ for s in range(SquareSize):
+ powernow = 0;
+ powernow = sumtable[Y+s][X+s] - sumtable[Y-1][X+s] - sumtable[Y+s][X-1] + sumtable[Y-1][X-1];
+ if (powernow > 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); diff --git a/2020/aoc2020-d01-1.py b/2020/aoc2020-d01-1.py new file mode 100644 index 0000000..23d2abb --- /dev/null +++ b/2020/aoc2020-d01-1.py @@ -0,0 +1 @@ +print("hello"); diff --git a/2024/aoc2024-d01.py b/2024/aoc2024-d01.py new file mode 100644 index 0000000..034e170 --- /dev/null +++ b/2024/aoc2024-d01.py @@ -0,0 +1,37 @@ +#advent of code 2024 +#day 01 p1 & p2 +#heapq was slower than manually sorting the lists +import time +t1 = time.time(); + +part1 = 0; +part2 = 0; +ListA = []; +ListB = []; +DictA = {}; + +f = open("01.in"); +for l in f: + n1,n2 = l.split(" "); + ListA.append(int(n1)); + ListB.append(int(n2)); + DictA[int(n1)] = 0; +f.close(); + +ListA = sorted(ListA); +ListB = sorted(ListB); + +for i,x1 in enumerate(ListA): + x2 = ListB[i]; + d = abs(x1-x2); + part1 += d; + if x2 in DictA: + DictA[x2] = DictA[x2] + 1; + +for x in DictA: + part2 += x*DictA[x]; + +t2 = time.time(); +print("part 1 = ", part1); +print("part 2 = ", part2); +print("time ", t2-t1); diff --git a/2024/aoc2024-d02.py b/2024/aoc2024-d02.py new file mode 100644 index 0000000..655fdc1 --- /dev/null +++ b/2024/aoc2024-d02.py @@ -0,0 +1,41 @@ +#advent of code 2024 +#day 02 +part1 = 0; +ToCheck = []; + +f = open("02.in","r"); +for l in f: + levels = [int(lvl) for lvl in l.split()]; + if (levels[1]-levels[0]) < 0: + levels.reverse(); + dMin = 4; + dMax = 0; + for i in range(1,len(levels)): + d = levels[i] - levels[i-1]; + dMin = min(dMin,d); + dMax = max(dMax,d); + if dMax <=3 and dMin >= 1: + part1 += 1; + else: + ToCheck.append(levels); +f.close(); + +correction = 0; +for levels in ToCheck: + isOK = False; + for x in range(len(levels)): + NewLevels = [levels[y] for y in range(len(levels)) if y !=x] + for _ in ["n","r"]: #normal and reversed, reverse and the end of first iteration + dMin = 4; + dMax = 0; + for i in range(1,len(NewLevels)): + d = NewLevels[i] - NewLevels[i-1]; + dMin = min(dMin,d); + dMax = max(dMax,d); + if dMax <=3 and dMin >= 1: isOK = True; + NewLevels.reverse(); + if isOK: correction += 1; + +part2 = part1 + correction; +print("part 1 = ", part1); +print("part 2 = ", part2); diff --git a/2024/aoc2024-d03.py b/2024/aoc2024-d03.py new file mode 100644 index 0000000..ed1bd2b --- /dev/null +++ b/2024/aoc2024-d03.py @@ -0,0 +1,36 @@ +#advent of code 2024 +#day 03 +#could be improved to match only numbers of lengths 1-3 +#instead of if statements in mul function +import re + +def mul(foundmatch): + foundmatch = foundmatch[4:-1]; + v1, v2 = [int(val) for val in foundmatch.split(",")]; + if v1 > 999: v1 = 0; + if v2 > 999: v2 = 0; + return v1*v2; + +part1 = 0; +part2 = 0; +instr = []; + +f = open("03.in","r") +for line in f: + regmatch = r'(mul\(\d+,\d+\))|(don\'t\(\))|(do\(\))'; + for m in re.findall(regmatch,line): + instr.append(m); +f.close(); + +ok = True; +for i in instr: + m, dn, do = i; #mul() / dont() / do() + if dn: ok = False; + elif do: ok = True; + if m: + v = mul(m); + part1 += v; + part2 += v*ok; + +print("part 1 =", part1); +print("part 2 = ", part2); diff --git a/2024/aoc2024-d04.py b/2024/aoc2024-d04.py new file mode 100644 index 0000000..c999c83 --- /dev/null +++ b/2024/aoc2024-d04.py @@ -0,0 +1,62 @@ +#advent of code 2024 +#day 04 +#the issue with 1st version of part 2 was that I didn't account for +#a cross of words "MAM" and "SAS" +#counting the letters gave a false positive (number of "m" and "s" was the same +#but it wasn't a cross of 2 "MAS" words +#now it check independently each word (dirs1 and dirs2) + +part1 = 0; +part2 = 0; +word = "XMAS"; +dirs = ((1,0),(-1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,1),(1,-1)); +Alist = []; +grid = {}; +xm = 0; +ym = 0; + +f = open("04.in","r") +for y,l in enumerate(f): + ym = y +1; + l = l[:-1]; + for x,c in enumerate(l): + xm = x +1; + grid[(x,y)] = c; +f.close(); + +for y in range(ym): + for x in range(xm): + if grid[(x,y)] == "A": Alist.append((x,y)); + for d in dirs: + dx, dy = d; + IsWord = True; + for i in range(len(word)): + nx = x + dx*i; + ny = y + dy*i; + nc = grid.get((nx,ny),"q"); + if nc != word[i]: + IsWord = False; + break; + if IsWord: part1 += 1; + +dirs1 = ((-1,-1),(1,1)); +dirs2 = ((-1,1),(1,-1)); +dirs0 = [dirs1,dirs2]; +for A in Alist: + x,y = A; + xcount = 0; + for d0 in dirs0: + cross = {}; + for d in d0: + dx,dy = d; + nx = x + dx; + ny = y + dy; + c = grid.get((nx,ny),"q"); + v = cross.get(c,0); + cross[c] = v + 1; + if cross.get("S",0) == 1 and cross.get("M",0) ==1: + xcount += 1; + if xcount == 2: part2 += 1; + +print("part 1 =", part1); +print("part 2 =", part2); diff --git a/2024/aoc2024-d05.py b/2024/aoc2024-d05.py new file mode 100644 index 0000000..2f8490a --- /dev/null +++ b/2024/aoc2024-d05.py @@ -0,0 +1,57 @@ +#advent of code 2024 +#day 05 +#cool, but seemed harder on first glance +#part1: keep looking up the rules for each page in an update +#if any of the pages in rules are present before the current page +#then the update is incorrect, else add the middle page to part1 score +#part2: keep correcting the order until each rule is satisfied +#popping the incorrectly placed page, then inserting it at the index +#of the page violating the rule +#edit: apparently there's a cycle in the rules which may lead to inifite +#corrections, but in my solution, or at least for my input, that isnt the case + +f = open("05.in","r"); +r, u = f.read().split("\n\n"); #rules and updates +f.close(); +rules, updates = {}, []; +part1 = 0; +part2 = 0; + +for l in r.split("\n"): + v1, v2 = [int(x) for x in l.split("|")]; + if not v1 in rules: rules[v1] = []; + rules[v1].append(v2); + +for l in u.split("\n")[:-1]: #skipping last line because its reading an empty line + updates.append([int(x) for x in l.split(",")]); + +def Verify(update): + ok = True; + for x, page in enumerate(update): + if page in rules: + for rule in rules[page]: + if rule in update[0:x]: ok = False; + return ok*update[len(update)//2]; + +def correction(update): + NewUpdate = update.copy(); + ok = False; + while not ok: + ok = True; + for x, page in enumerate(NewUpdate): + if page in rules: + for y in range(x,-1,-1): + if NewUpdate[y] in rules[page]: + ok = False; + NewUpdate.pop(x); + NewUpdate.insert(y, page); + break; + return NewUpdate[len(NewUpdate)//2]; + +for update in updates: + score = Verify(update); + part1 += score; + if score == 0: part2 += correction(update); + +print("part 1 =", part1); +print("part 2 =", part2); diff --git a/2024/aoc2024-d06.py b/2024/aoc2024-d06.py new file mode 100644 index 0000000..e5da9b4 --- /dev/null +++ b/2024/aoc2024-d06.py @@ -0,0 +1,63 @@ +#advent of code 2024 +#day 06 +#cleaned up + + +grid = {}; +xMin, yMin, xMax, yMax = 0, 0, 0, 0; +dirs = [(0,-1),(1,0),(0,1),(-1,0)]; +d = 0; #starting direction of the guard + +f = open("06.in","r"); +for y, l in enumerate(f): + yMax = max(yMax,y); + for x, c in enumerate(l[:-1]): + xMax = max(xMax,x); + if c == "^": + guard1 = (x,y); #guard position + guard2 = (x,y); #guard pos for part 2 + c = "."; + grid[(x,y)] = c; +f.close(); + +visited = set(); +while True: + gx, gy = guard1; #split guard coordinates + dx, dy = dirs[d]; + if not (xMin <= gx <= xMax)*(yMin <= gy <= yMax): break; + if grid.get((gx+dx,gy+dy),".") == "#": + d = (d+1)%4; + dx, dy = dirs[d]; + visited.add(guard1); + guard1 = (gx+dx,gy+dy); + +#definition of loop: if the guard meets the same obstacle twice, then he's looping +def bruteforce(NewPos,guard): #check if inserting in NewPos position an obstacle will create a loop + d = 0; + obstacles = set(); + #register in set "obstacles" encountered obstacles in format: x,y,d, + #where d is the direction from which guard encountered the obstacle + ok = True + while True: + gx, gy = guard; + dx, dy = dirs[d]; + if not (xMin <= gx+dy <= xMax)*(yMin <= gy+dy <= yMax): + ok = False; #if the guard left the grid then the new obstacle didnt work + break; + if grid.get((gx+dx,gy+dy),".") == "#" or (gx+dx,gy+dy)==NewPos: + d = (d+1)%4; + dx, dy = dirs[d]; + if (guard,d) in obstacles: break; + obstacles.add((guard,d)); + else: + guard = (gx+dx,gy+dy); + return ok; + +NewPlaces = set(); #store the correct possibilites in a set just in case to prevent duplicates +for v in visited: #simulate another guard patrol for each possible new position v + if bruteforce(v,guard2): NewPlaces.add(v); #if he loops, +1 to score + +part1 = len(visited); +part2 = len(NewPlaces); +print("part 1 =", part1); +print("part 2 =", part2); diff --git a/2024/aoc2024-d07.py b/2024/aoc2024-d07.py new file mode 100644 index 0000000..46a594d --- /dev/null +++ b/2024/aoc2024-d07.py @@ -0,0 +1,40 @@ +#advent of code 2024 +#day 07 +#rewritten to do both parts at the same time +#very slow solution (roughly 10 mins of runtime) +#it generates all possible arrangements of operators +#to fill in the empty spaces in the equation +#on top of that, it utilizes eval() +#however, the solution works and that's the important part + +import itertools + +def calculate(test,nums,ops): + N = [n for n in nums.split(" ")]; + ValidAnswerP1 = False; + ValidAnswerP2 = False; + for prod in itertools.product(ops,repeat=nums.count(" ")): + score = ''+N[0]; + for i,p in enumerate(prod): + if p == "||": p = ""; + teststring = str(score) + p + N[i+1]; + score = eval(teststring); + if score == test: + ValidAnswerP2 = True; + if "||" not in prod: ValidAnswerP1 = True; + if ValidAnswerP1 and ValidAnswerP2: break; + return ValidAnswerP1, ValidAnswerP2; + +part1 = 0; +part2 = 0; +ops = ["+","*","||"]; +f = open("07.ex","r"); +for l in f: + TestValue, numbers = l[:-1].split(": "); + TestValue = int(TestValue); + valid_p1, valid_p2 = calculate(TestValue, numbers,ops); + part1 += valid_p1*TestValue; + part2 += valid_p2*TestValue; +f.close(); +print("part 1 = ", part1); +print("part 2 = ", part2); diff --git a/2024/aoc2024-d08.py b/2024/aoc2024-d08.py new file mode 100644 index 0000000..b977a26 --- /dev/null +++ b/2024/aoc2024-d08.py @@ -0,0 +1,41 @@ +#advent of code 2024 +#day 08 +#cool +xMin, yMin, xMax, yMax = 0,0,0,0; #map bounds +antennas = {}; #dictionary of antennas +antinodes1 = set(); #antinodes for part 1 +antinodes2 = set(); #anitnodes for part 2 + +f = open("08.in","r"); +for y,l in enumerate(f): + yMax = max(yMax,y); + for x, c in enumerate(l[:-1]): + xMax = max(xMax,x); + if c != ".": + if antennas.get(c,None) == None: + antennas[c] = []; + antennas[c].append((x,y)); +f.close(); + +for antenna in antennas: #for each antenna + for a1 in antennas[antenna]: #for each instance of that antenna + for a2 in antennas[antenna]: #for each counterpart of that instance + if a1 == a2: continue; #antenna can't have the antinode on its own + a1x, a1y = a1; + a2x, a2y = a2; + dx = a2x-a1x; + dy = a2y-a1y; + if (xMin <= a1x-dx <= xMax) and (yMin <= a1y-dy <= yMax): + antinodes1.add((a1x-dx,a1y-dy)); + antinodes2.add((a1x,a1y)); + while True: + ax = a1x-dx; + ay = a1y-dy; + if not ((xMin <= ax <= xMax) and (yMin <= ay <= yMax)): + break; + antinodes2.add((ax,ay)); + a1x = ax; + a1y = ay; + +print("part 1 =", len(antinodes1)); +print("part 2 =", len(antinodes2)); diff --git a/2024/aoc2024-d09-1.py b/2024/aoc2024-d09-1.py new file mode 100644 index 0000000..3a3e1e6 --- /dev/null +++ b/2024/aoc2024-d09-1.py @@ -0,0 +1,56 @@ +#advent of code 2024 +#day 09 - part 1 +#I'll rewrite it to include both parts in the same file one day +#tbh I'm not even reviewing this shit +#very slow part 1, part 2 relatively fast + +part1 = 0; +disk = open("09.in","r").readline().strip(); +files = {}; +freespace = {}; +NewDisk = {}; +fid = 0; +sid = 0; +ind = 0; +for i in range (0,len(disk)): + if i%2 == 0: + files[fid] =[int(x)+ind for x in range(int(disk[i]))]; + ind += int(disk[i]); + fid += 1; + else: + freespace[sid] = [int(x)+ind for x in range(int(disk[i]))]; + ind += int(disk[i]); + sid +=1; + +si = 0; #space index +fi = fid -1; #file index +originalSize = len(files[fi]); +while sum([len(freespace[x]) for x in freespace]) > 0: + #empty list of freespaces - change to another one + if len(freespace[si]) == 0: + si += 1; + continue; + + #clear freespace that is after the fileblock with biggest index + FileMax = max([max(files[x]) for x in files]); + if FileMax < freespace[si][-1]: + freespace[si].pop(-1); + continue; + + #switch places between last fileblock and first freespace + files[fi].pop(); + originalSize -= 1; + NewSpace = freespace[si].pop(0); + files[fi].insert(0,NewSpace); + + #if that was the last fileblock, switch to second to last file + if originalSize == 0: + fi -= 1; + originalSize = len(files[fi]); + +#checksum calculation +for file in files: + for f in files[file]: + part1 += file*f; + +print("part 1 =", part1); diff --git a/2024/aoc2024-d09-2.py b/2024/aoc2024-d09-2.py new file mode 100644 index 0000000..483388e --- /dev/null +++ b/2024/aoc2024-d09-2.py @@ -0,0 +1,41 @@ +#advent of code 2024 +#day 09 - part 2 +#I'll rewrite it to include both parts in the same file one day +#tbh I'm not even reviewing this shit +#very slow part 1, part 2 relatively fast + +part2 = 0; +disk = open("09.in","r").readline().strip(); +files = {}; +freespace = {}; +NewDisk = {}; +fid = 0; +sid = 0; +ind = 0; +for i in range (0,len(disk)): + if i%2 == 0: + files[fid] =[int(x)+ind for x in range(int(disk[i]))]; + ind += int(disk[i]); + fid += 1; + else: + freespace[sid] = [int(x)+ind for x in range(int(disk[i]))]; + ind += int(disk[i]); + sid +=1; + +for fi in range(fid-1,-1,-1): #file index, from last to first + CurrentLimit = min(files[fi]); + for si in range(0, len(freespace)): #space index, from first to last + if len(freespace[si]) <= 0: continue; + if max(freespace[si]) > CurrentLimit: break; + if len(freespace[si]) >= len(files[fi]): + OriginalSize = 0 + len(files[fi]); + for o in range(OriginalSize): + files[fi].pop(); + NewSpace = freespace[si].pop(0); + files[fi].insert(0,NewSpace); + break; + +for file in files: + for f in files[file]: + part2 += file*f; +print("part 2 =", part2); diff --git a/2024/aoc2024-d10.py b/2024/aoc2024-d10.py new file mode 100644 index 0000000..4f51a0d --- /dev/null +++ b/2024/aoc2024-d10.py @@ -0,0 +1,55 @@ +#advent of code 2024 +#day 10 +#tbh I don't think I even understood the task correctly +#but the first idea for part 2 +#that came up to my head worked so i'll take it +#all I did was switch a set into a list +#rewritten so the code does both parts now + +grid = {}; +xMin, yMin, xMax, yMax = 0,0,0,0; +dirs = [(1,0),(-1,0),(0,1),(0,-1)]; +starts = []; + +f = open("10.in","r"); +for y,l in enumerate(f): + yMax = max(y,yMax); + for x,c in enumerate(l.strip()): + grid[(x,y)]=int(c); + if c == "0": starts.append((x,y)); + xMax = max(xMax,x); +f.close(); + +def getAdjacent(pos,h): + adj = []; + xp, yp = pos; + for i,d in enumerate(dirs): + dx,dy = d; + if grid.get((xp+dx,yp+dy),-1)-h == 1: + adj.append((xp+dx,yp+dy,i)); + return adj; + +def pathfinding(starts): + score1 = 0; + score2 = 0; + for start in starts: + subscore1 = set(); + subscore2 = list(); + x0,y0 = start; + queue = [(x0,y0,0)]; + while queue: + px,py,pd = queue.pop(); + CurrentHeight = grid.get((px,py),-1); + if CurrentHeight == 9: + subscore1.add((px,py)); + subscore2.append((px,py,pd)); + else: + NextValid = getAdjacent((px,py),CurrentHeight); + queue.extend(NextValid); + score1 += len(subscore1); + score2 += len(subscore2); + return score1, score2; + +part1, part2 = pathfinding(starts); +print("part 1 =", part1); +print("part 2 =", part2); diff --git a/2024/aoc2024-d11.py b/2024/aoc2024-d11.py new file mode 100644 index 0000000..0d6fea4 --- /dev/null +++ b/2024/aoc2024-d11.py @@ -0,0 +1,50 @@ +#advent of code 2024 +#day 11 +#I liked it. what I did was: +#store current stones in dictionary in format stonenumber:amount of these stones +#iterate the changes in time +#if the given stone is split up for the first time, the result is memorized +#in the changes dictionary +#during iteration, the UpdateStones function tries to read the results of splitting +#if there are none, the stone is getting split up for the first time +#repeat for given steps +stones = {}; +changes = {}; +f = open("11.in","r"); +for s in f.readline().strip().split(" "): + si = int(s); + if si not in stones: stones[si] = 0; + stones[si] += 1; +f.close(); + +def SplitStones(stone): + NewStones = []; + if stone == 0: + NewStones.append(1); + elif len(str(stone))%2==0: + stonestring = str(stone); + sm = len(stonestring)//2; + s1,s2 = stonestring[0:sm], stonestring[sm:]; + NewStones.append(int(s1)); + NewStones.append(int(s2)); + else: + NewStones.append(stone*2024); + return NewStones; + +def UpdateStones(prevStones): + Updated = {}; + for s in prevStones: + if s not in changes: changes[s] = SplitStones(s); + for c in changes[s]: + if c not in Updated: Updated[c] = 0; + Updated[c] += prevStones[s]; + return Updated; + +steps1 = 25; #for part 1 +steps2 = 75; #for part 2 +for step in range(1,steps2+1): + stones = UpdateStones(stones); + if step == steps1: part1 = sum([stones[x] for x in stones]); +part2 = sum([stones[x] for x in stones]); +print("part 1 =", part1); +print("part 2 =", part2); diff --git a/2024/aoc2024-d12.py b/2024/aoc2024-d12.py new file mode 100644 index 0000000..b7ac378 --- /dev/null +++ b/2024/aoc2024-d12.py @@ -0,0 +1,83 @@ +#advent of code 2024 +#day 12 +#we needed area of the plot and its perimiter +#we floodfill given plot and store the coordinates of the plants +#then, on the borders, we register the coordinates of the plants +#that are adjacent to our plot and the direction from which it was +#registered during floodfill. the length of this set (perim) is the perimiter +#then, for part 2, we group the points in perim set by their direction +#(3rd parameter), then we sort each group based on the coordinate +#that is changing, that is: if the fence was registered from the north, +#then it is part of the north-facing fence, so we sort it by the x-axis +#identical for southern and similar for east/west (y-axis) +#iterate over every fence point, if the gap is greater 1 then increment +#the amount of sides. I probably should make a drawing because +#I'll forget what it does in the future despite writing this comment +grid = {}; +f = open("12.in","r"); +for y,l in enumerate(f): + for x,c in enumerate(l.strip()): + grid[(x,y)]=c; +f.close(); + +dirs = [(1,0),(0,1),(-1,0),(0,-1)]; +visited = set(); + +def getAdjacent(pos,l): + adj = []; + vis = set(); + xp, yp = pos; + for di,d in enumerate(dirs): + dx,dy = d; + if grid.get((xp+dx,yp+dy),".") == l: + adj.append((xp+dx,yp+dy)); + else: + vis.add((xp+dx,yp+dy,di)); + return adj, vis; + +def sides(perimiter): + SidesTotal = 0; + NumberOfSides = {}; + PerimsGrouped = {}; + for di in range(4): + NumberOfSides[di] = 0; + PerimsGrouped[di] = [m for m in perimiter if m[2]==di]; + PerimsGrouped[di] = sorted(PerimsGrouped[di], key=lambda m: (m[di%2],m[(di+1)%2])); + if len(PerimsGrouped[di]) == 0: + continue; + else: + NumberOfSides[di] += 1; + prevx,prevy,prevd = PerimsGrouped[di][0]; + for PerPos in PerimsGrouped[di][1:]: + x,y,d = PerPos; + if not(abs(x-prevx)==di%2 and abs(y-prevy) ==(di+1)%2): + NumberOfSides[di] += 1; + prevx,prevy,prevd = x,y,d; + SidesTotal += NumberOfSides[di]; + return SidesTotal; + +def fill(startpos, letter): + queue = [startpos]; + perim = set(); #add points that aren't part of the area but are adjacent + v = set(); #visited points, that is: the area + while queue: + px,py = queue.pop(); + if (px,py) in v: continue; + visited.add((px,py)); + v.add((px,py)); + NextValid, NextBorders = getAdjacent((px,py),letter); + queue.extend(NextValid); + perim = perim.union(NextBorders); + return len(v), len(perim), sides(perim); + +part1 = 0; +part2 = 0; +for g in grid: + if g in visited:continue; + L = grid[g]; + LandArea, LandPerim, LandSides = fill(g,L); + part1 += LandArea*LandPerim; + part2 += LandArea*LandSides; + +print("part 1 =", part1); +print("part 2 =", part2); diff --git a/2024/aoc2024-d13.py b/2024/aoc2024-d13.py new file mode 100644 index 0000000..8eaff25 --- /dev/null +++ b/2024/aoc2024-d13.py @@ -0,0 +1,31 @@ +#advent of code 2024 +#day 13 +#similar problem was last year +#rewritten to include both parts, could get rid of second for loop but w/e +import re + +def formula(machinevalues,p2): + xa,ya,xb,yb,XP,YP = machinevalues; + XP += p2; + YP += p2; + pusha = (yb*XP - xb*YP)/(yb*xa - xb*ya); #number of pushes - button A + pushb = (XP - xa*pusha)/xb; #number of pushes - button B + Valid = (pusha%1 == 0)*(pushb%1==0); #check if solution is an integer + cost = 3*int(pusha) + int(pushb); + return Valid*cost; + +machines = []; +f = open("13.in","r"); +for l in f.read().split("\n\n"): + values = re.findall(r'\d+',l); + machines.append([int(v) for v in values]); +f.close(); + +part1, part2 = 0, 0; +for machine in machines: + part1 += formula(machine,0); + part2 += formula(machine,10000000000000); + +print("part 1 =",part1); +print("part 2 =",part2); + diff --git a/2024/aoc2024-d14.py b/2024/aoc2024-d14.py new file mode 100644 index 0000000..c824d96 --- /dev/null +++ b/2024/aoc2024-d14.py @@ -0,0 +1,87 @@ +#advent of code 2024 +#day 14 +#correctly assumed that the picture will show up +#if the robots don't overlap +#doing previous years with online help paid off +#NOTE: I learned that it's not recommended to +#take modulo of a negative value +#however there was no problem with that in python + +import re + +class robot: + def __init__(self,rx,ry,rvx,rvy): + self.posx = rx; + self.posy = ry; + self.startx = rx; #useless, no need to reset + self.starty = ry; #useless, no need to reset + self.velx = rvx; + self.vely = rvy; + def move(self,steps): + self.posx = (self.posx + steps*self.velx)%xMax; + self.posy = (self.posy + steps*self.vely)%yMax; + def currentpos(self): + return (self.posx,self.posy); + def resetpos(self): #useless, no need to reset + self.posx = self.startx; + self.posy = self.starty; + +robots = []; +xMin = 0; #from part 1 description, grid range +yMin = 0; #from part 1 description, grid range +xMax = 101; #from part 1 description, grid range +yMax = 103; #from part 1 description, grid range + +f = open("14.in","r"); +for l in f: + nums = re.findall(r'-?\d+',l) + robots.append(robot(*[int(n) for n in nums])); +f.close(); + +RobotPositions = {}; +TimeElapsed = 100; #from part 1 description, time of simulation + +for r in robots: + r.move(TimeElapsed); + robx,roby = r.currentpos(); + if RobotPositions.get((robx,roby),None) == None: + RobotPositions[(robx,roby)] = 0; + RobotPositions[(robx,roby)] += 1; + +part1 = 1; #Safety Factor to multiply +qlim = [(0,xMax//2,0,yMax//2),(1+xMax//2,xMax+1,0,yMax//2),(0,xMax//2,1+yMax//2,yMax+1),(1+xMax//2,xMax+1,1+yMax//2,yMax+1)]; +#qlim = ranges of each quadrant in format: x_min,x_max,y_min,y_max +#not to be confused with xMin,xMax,yMin,yMax of the total grid +#could probably change it a bit and check which quadrant given robot +#belongs to after calculating its position at TimeElapsed +#and count them during "r in robots" for loop +for qx1,qx2,qy1,qy2 in qlim: + robotcountq = 0; #number of robots for each quadrant + for y in range(qy1,qy2): + for x in range(qx1,qx2): + robotcountq += RobotPositions.get((x,y),0); + part1 *= robotcountq; + +print("part 1 = ", part1); +TotalRobots = len(robots); +#I assume (in hindsight: correctly) that the picture doesn't show up before the 100s mark from part 1 +#in general robots' positions should be reset and then start the timer from t = 0 +while True: + TimeElapsed += 1; + RobotSpots = set(); + for r in robots: + r.move(1); + robx,roby = r.currentpos(); + RobotSpots.add((robx,roby)); + if len(RobotSpots)==TotalRobots: break; +part2 = TimeElapsed; +print("part 2 = ", part2); +#commented out the print of the tree itself +#for y in range(yMax): +# for x in range(xMax): +# c = "."; +# if (x,y) in RobotSpots: c = "#"; +# #c = RobotPositions.get((x,y),"."); +# print(c,end=""); +# print(); + diff --git a/2024/aoc2024-d15.py b/2024/aoc2024-d15.py new file mode 100644 index 0000000..a6bb5a0 --- /dev/null +++ b/2024/aoc2024-d15.py @@ -0,0 +1,157 @@ +#advent of code 2024 +#day 15 +#could probably reduce the length of code even more +#if I were to index the part2 box +#instead of hardcoding the left and right part of the box +#but w/e, I don't feel like doing it +#the code is ~110 lines of code shorter after cleaning up +#explanation: +#given: picture of the grid (fg) and robots movement list (movement) +#create 2 grids: grid1 and grid2 for part 1 and part 2 respectively +#for part 2 the grid is made wider x2: the grid2 is created with +#resizing dictionary to know what to insert where +#there are 3 functions: GPS, movebox, stackbox +#GPS calculates the result required by puzzle after simulating +#the movement of the robot +#the box variable is a list of characters that are considered a box +#for each part of a puzzle: O for part 1, [ and ] for part 2 +#the thing is that by making it into a list, I don't need +#separate functions for each part: the logic checks if +#the current tile is equal to the last or the first element of this list +#to determine whether or not it's a box +#for list of length 1, element with index 0 and -1 are the same +#next it iterates over each step of the robot's movement in movement list +#before the robot moves, it checks what is in it's way +#if it's a floor ("."), then it takes a step +#if it's a wall ("#"), it stands in the same spot +#if it's a box, it runs the movebox or stackbox function +#to determine if it's viable or not +#stackbox is a function that is run only for part2 if the robot +#wants to push boxes up or down. if it's part 1 or it moves left or right +#it uses movebox function +#movebox function scans the grid in the provided direction +#(accordingly with robots desired movement) as long as it meets +#a wall tile or floor tile. if it's a wall: can't move +#if it's a floor, then for each tile in the path, from last tile to the first +#move each tile in given direction +#stackbox function queues each tile with a box +#and checks if something is above or below (depending on the robots direction) +#if there's another box, it queues up that tile and it's counterpart +#(left or right) to check it again recursively +#if at any moment there's a wall in the path, the robot can't move +#if the final tiles don't have only floor tiles above or below them, +#then each box tile is moved one step in correct direction, +#leaving behind a free space +#this comment is as long as solutions for days 1-13 +#but I just fucking know that I'll look this up one day and will +#not remember anything +grid1 = {}; +grid2 = {}; +dirs = {}; +dirs["^"] = (0,-1); +dirs["v"] = (0,1); +dirs["<"] = (-1,0); +dirs[">"] = (1,0); +resizing = {}; +resizing["#"] = "##"; +resizing["O"] = "[]"; +resizing["."] = ".."; +resizing["@"] = "@."; + +f = open("15.in","r"); +fg, movement = f.read().split("\n\n"); +movement = movement.replace("\n",""); +for y,l in enumerate(fg.split("\n")): + for x,c in enumerate(l.strip()): + if c == "@": + robot1 = (x,y); + robot2 = (2*x,y); + c = "."; + grid1[(x,y)] = c; + for offset in range(2): + grid2[(2*x+offset,y)] = resizing[c][offset]; +f.close(); + +def movebox(BoxPos,direction,grid,box,p2): + valid = True; + bx, by = BoxPos; #coordinates of 1st box to push + dirx,diry = direction; + distance = 1; #python ranges are exclusive on outside + NextTile = grid.get((bx+distance*dirx,by+distance*diry),"#"); + while NextTile == box[0] or NextTile == box[-1]: + distance += 1; + NextTile = grid.get((bx+distance*dirx,by+distance*diry),"#"); + LastTile = grid.get((bx+distance*dirx,by+distance*diry),"#"); + if LastTile == "#": #if wall, can't move + valid = False; + else: #replace each box in the way step by step in reversed order + for dist in range(distance): + NewPosition = (bx+distance*dirx -dist*dirx,by+distance*diry -dist*diry); + PrevPosition = (bx+distance*dirx -dist*dirx -dirx,by + distance*diry - dist*diry - diry); + grid[NewPosition] = grid[PrevPosition]; + grid[PrevPosition] = "."; + return valid; + +def stackbox(BoxPos,direction,grid,box,p2): + valid = True; + bx,by = BoxPos; + dirx,diry = direction; + if grid[BoxPos] == box[0]: BoxPos2 = (bx+1,by,box[-1]); + else: BoxPos2 = (bx-1,by,box[0]); + queue = [(bx,by,grid[BoxPos]),BoxPos2]; #each part of the box is a separate entry in queue + BoxesToMove = queue.copy(); + while queue: + PosToCheck = []; + for queuedpos in queue: + BX,BY,dummy = queuedpos; #dummy not needed for queue loop, needed later + NextTile = grid[(BX,BY+diry)]; + if NextTile == box[0]: + PosToCheck.append((BX,BY+diry,NextTile)); + PosToCheck.append((BX+1,BY+diry,grid[(BX+1,BY+diry)])); + elif NextTile == box[-1]: + PosToCheck.append((BX,BY+diry,NextTile)); + PosToCheck.append((BX-1,BY+diry,grid[(BX-1,BY+diry)])); + elif NextTile == "#": + valid = False; + break; + if valid: + queue = PosToCheck.copy(); + BoxesToMove.extend(PosToCheck); + else: + BoxesToMove = []; + queue = []; + BoxesToMove = sorted(BoxesToMove, key = lambda k: k[1],reverse=diry>0); + for BoxToMove in BoxesToMove: + boxx,boxy,prevtile = BoxToMove; + grid[(boxx,boxy+diry)] = prevtile; + grid[(boxx,boxy)] = "."; + return valid; + +def GPS(grid,robot,p2): + box = ["O"]; + if p2: box = ["[","]"]; + for d in movement: + dx,dy = dirs[d]; + rx,ry = robot; + NextPos = (rx+dx,ry+dy); + tile = grid.get(NextPos,"#"); + if tile == "#": #if wall, dont move + ok = False; + elif tile == box[0] or tile == box[-1]: #if boxes in the way, move boxes first + if p2 and dy != 0: + ok = stackbox(NextPos,dirs[d],grid,box,p2); + else: + ok = movebox(NextPos,dirs[d],grid,box,p2); + else: #if nothing in the way, then move + ok = True; + robot = (rx+ok*dx,ry+ok*dy); + score = 0; + for g in grid: + if grid[g] == box[0]: score += 100*g[1] + g[0]; + return score; + +part1 = GPS(grid1,robot1,False); +part2 = GPS(grid2,robot2,True); +print("part 1 =", part1); +print("part 2 =", part2); + diff --git a/2024/aoc2024-d16-dangerously_unwashed.py b/2024/aoc2024-d16-dangerously_unwashed.py new file mode 100644 index 0000000..710a3e5 --- /dev/null +++ b/2024/aoc2024-d16-dangerously_unwashed.py @@ -0,0 +1,170 @@ +#advent of code 2024 +#day 16 +#version 1 - not cleaned up +#don't know anymore, can't explain - keeping the unrevised version because it's hilariously dogshit +#part 1: simple shortest path search +#part 2: keep the path searching function running until all paths with distance equal to the shortest path are registered +#keep track of distance for each node, kinda like djikstra, distance to each node is stored in a dictionary +#with only exception that it stores all of the possible +#in short: linked list, in format: node_1:set_of_previous_nodes, previous nodes have shortest possible path to that node +#keep a map of previous steps, that is Position_now:set of positions that could be used to reach +#I also commented out a check to prevent going backwards (take step north, then take step south) +#but I guess that was taken care of during other checks like how big is the distance so it didnt matter +#the entries in queues with distance greater than registered shortest path are discarded +#the check is repeated (probably unnecessarily) before queuepush +#my other issue: there could be more than 1 directions from which I could reach the E +#while I registered all of them, durign testing I used only one of them +#turns out there weren't multiple ends (all valid paths reach E from the same direction) +#sidenote: i think i solved that earlier, because I was getting similar values, but I didn't bother to check + +#assumptions: +#only 1 starting position + +import heapq + +grid = {}; +xMin, yMin, xMax, yMax = 0,0,0,0; #just for printout +dirs = [(1,0),(0,1),(-1,0),(0,-1)]; #east, south, west, north + +f = open("16.in","r"); +for y,l in enumerate(f): + yMax = max(y,yMax); + for x,c in enumerate(l.strip()): + if c == "S": + start = (x,y); + c = "." + grid[(x,y)]=c; + xMax = max(xMax,x); +f.close(); + +''' +for y in range(yMax+1): + for x in range(xMax+1): + print(grid[(x,y)], end=""); + print(); #''' + +#print(start); + +def getAdjacent(coordinates): + adj = []; + xp, yp, dp = coordinates; + for i,d in enumerate(dirs): + dx,dy = d; + if grid.get((xp+dx,yp+dy),"#") != "#": + adj.append((xp+dx,yp+dy,i)); + return adj; + +BigNumber = xMax*yMax*100000000000; + +def pathfinding(startingpos): + ends = set(); + visited = set(); + x0,y0 = startingpos; + queue = []; + heapq.heappush(queue,(0,(x0,y0,0))); + ShortestPath = BigNumber; + pathmap = {}; + pathdis = {}; + pathmap[(x0,y0,0)] = set(); + + while queue: + distance, coords = heapq.heappop(queue); + #if coords in visited: continue; + if distance > ShortestPath: continue; + visited.add(coords); + px,py,pd = coords; + + #pathmap[(coords,prevs)] = min(distance, pathmap.get((coords,prevs),float('inf'))); + CurrentTile = grid.get((px,py),"#"); + if CurrentTile == "E": + ShortestPath = min(ShortestPath,distance); + if distance == ShortestPath: + ends.add(coords); + + #else: + NextValid = getAdjacent((px,py,pd)); + for NV in NextValid: + #print("NV", distance+1+1000*(NV[2]!=pd),NV); + next_dist = distance+1+1000*(NV[2]!=pd); + prev_dist = pathdis.get(NV,BigNumber); + if next_dist > prev_dist: + continue; + if next_dist < prev_dist: + pathmap[NV] = set(); + pathdis[NV] = next_dist; + pathmap[NV].add(coords); + #if NV[2] == (pd+2)%4: continue; + heapq.heappush(queue,(distance+1+1000*(NV[2]!=pd),NV)); + + return ShortestPath, pathmap, pathdis, ends; + + +part1, PathMap,PathDis, PathEnds = pathfinding(start); +part2 = len(PathMap); +newtotal = set(); +#for shit in tv: +# shit1,shit2,shit2 +print("part 1 =", part1); + +#print(PathMap); +for pm in PathMap: + if len(PathMap[pm]) > 1: + print(pm, PathMap[pm]); +#input(); + +#print(PathDis); +#input(); +#print(PathEnds); + +def FindSpots(startpos,end,pathmap,pathdis,prevpaths): + #sx,sy,_ = + validpaths = set(); + print(end); + #for end in endpos: + #queue = [end]; + #scorereversed = 0 + pathdis[end]; + CurrentPosition = end; + validpaths.add(CurrentPosition); + #while queue: + # x,y,d = queue.pop(); + if end == startpos: + return validpaths; + #x,y,d = end; + NextPositions = pathmap[end]; + for np in NextPositions: + validpaths.update(FindSpots(startpos,np,pathmap,pathdis,validpaths.copy())); + + return validpaths; + +print("FINSPOTS"); +FirstEnd = PathEnds.pop(); +testing = FindSpots(start,FirstEnd,PathMap,PathDis,set()); +print("testing"); +print(testing); +print(len(testing)); + + + +storeshit = set(); + +for t in testing: + tx,ty,td = t; + storeshit.add((tx,ty)); + + +for y in range(yMax+1): + for x in range(xMax+1): + c = grid[(x,y)]; + #if (x,y) in tv: + # c = "O"; + counter = 0; + for ind in range(4): + if (x,y,ind) in testing: counter += 1; + if counter != 0: c = str(counter); + ##c = "O"; + #break;#''' + print(c, end=""); + print(); + +print("part 1 =", part1); +print("part 2 =", len(storeshit)); diff --git a/2024/aoc2024-d16-wash_attempt.py b/2024/aoc2024-d16-wash_attempt.py new file mode 100644 index 0000000..4d70b48 --- /dev/null +++ b/2024/aoc2024-d16-wash_attempt.py @@ -0,0 +1,102 @@ +#advent of code 2024 +#day 16 +#version 2 - slightly cleaned up +#don't know anymore, can't explain - keeping the unrevised version because it's hilariously dogshit +#part 1: simple shortest path search +#part 2: keep the path searching function running until all paths with distance equal to the shortest path are registered +#keep track of distance for each node, kinda like djikstra, distance to each node is stored in a dictionary +#with only exception that it stores all of the possible +#in short: linked list, in format: node_1:set_of_previous_nodes, previous nodes have shortest possible path to that node +#keep a map of previous steps, that is Position_now:set of positions that could be used to reach +#I also commented out a check to prevent going backwards (take step north, then take step south) +#but I guess that was taken care of during other checks like how big is the distance so it didnt matter +#the entries in queues with distance greater than registered shortest path are discarded +#the check is repeated (probably unnecessarily) before queuepush +#my other issue: there could be more than 1 directions from which I could reach the E +#while I registered all of them, durign testing I used only one of them +#turns out there weren't multiple ends (all valid paths reach E from the same direction) +#sidenote: i think i solved that earlier, because I was getting similar values, but I didn't bother to check + +#assumptions: +#only 1 starting position +#i think the code will work for multiple ends (E) as well, as long as the puzzle wants the shortest path to the closest end + +import heapq + +grid = {}; +xMin, yMin, xMax, yMax = 0,0,0,0; #could get rid of it but w/e +dirs = [(1,0),(0,1),(-1,0),(0,-1)]; #east, south, west, north + +f = open("16.in","r"); +for y,l in enumerate(f): + yMax = max(y,yMax); + for x,c in enumerate(l.strip()): + if c == "S": + start = (x,y,0); + c = "." + grid[(x,y)]=c; + xMax = max(xMax,x); +f.close(); + +def getAdjacent(coordinates): + adj = []; + xp, yp, dp = coordinates; + for i,d in enumerate(dirs): + dx,dy = d; + if grid.get((xp+dx,yp+dy),"#") != "#": + adj.append((xp+dx,yp+dy,i)); + return adj; + +def pathfinding(startingpos): + ends = set(); #max 4, coordinates of E but coming from each direction + BigNumber = xMax*yMax*100000000000; #used to initialize Shortest Path to have something to compare with + ShortestPath = BigNumber; + pathmap,pathdis = {},{}; + queue = []; + heapq.heappush(queue,(0,startingpos)); + pathmap[startingpos] = set(); + while queue: + distance, coords = heapq.heappop(queue); + if distance > ShortestPath: continue; + px,py,pd = coords; + if grid.get((px,py),"#") == "E": + ShortestPath = min(ShortestPath,distance); #this should be updated only once + if distance == ShortestPath: + ends.add(coords); #always the same E, just from different direction + NextValid = getAdjacent((px,py,pd)); + for NV in NextValid: #for each valid adjacent node (valid here means it's not a wall) + next_dist = distance+1+1000*(NV[2]!=pd); + prev_dist = pathdis.get(NV,BigNumber); + if next_dist > prev_dist: + continue; + if next_dist < prev_dist: + pathmap[NV] = set(); #reset the set of positions with shortest path to it + pathdis[NV] = next_dist; #update the shortest path to node NV + pathmap[NV].add(coords); + heapq.heappush(queue,(next_dist,NV)); + return ShortestPath, pathmap, ends; + +def FindSpots(startpos,CurrentNode,pathmap): + validpaths = set(); + validpaths.add((CurrentNode[0],CurrentNode[1])); + if CurrentNode == startpos: + return validpaths; + NextPositions = pathmap[CurrentNode]; #read the set of nodes that connected to this node + for np in NextPositions: + validpaths.update(FindSpots(startpos,np,pathmap)); + return validpaths; + +ValidTiles = set(); #tiles that are on one of the best paths through the maze +part1, PathMap, PathEnds = pathfinding(start); +for EndPosition in PathEnds: + ValidTiles.update(FindSpots(start,EndPosition,PathMap)); +part2 = len(ValidTiles); +''' #map print +for y in range(yMax+1): + for x in range(xMax+1): + c = grid[(x,y)]; + if (x,y) in ValidTiles: c = str("O"); + print(c, end=""); + print(); #''' +print("part 1 =", part1); +print("part 2 =", part2); diff --git a/2024/aoc2024-d17.py b/2024/aoc2024-d17.py new file mode 100644 index 0000000..c5a41b1 --- /dev/null +++ b/2024/aoc2024-d17.py @@ -0,0 +1,65 @@ +#advent of code 2024 +#day 17 +#code needs input reading, hardcoded my input out of convenience +#the fucking commas where part of a solution lol, misread the problem there +#if I were to reverse the logic for 3rd argument in broot function +#it could work for longer inputs +import re +RegsRaw, ProgRaw = open("17.in","r").read().split("\n\n"); +#by Eric's request, the input is removed +MyCode = []; +MyA = ; + +Register = {}; +Register[0] = 0; #A +Register[1] = 0; #B +Register[2] = 0; #C + +def combo(op): + if op <= 3: return op; + elif op == 4: return Register[0]; + elif op == 5: return Register[1]; + elif op == 6: return Register[2]; + +def runprogram(code,A): + Results = []; + InstrPointer = 0; + Register[0] = A; #A + while InstrPointer < len(code): + operand = code[InstrPointer+1]; + Inst = code[InstrPointer]; + #print(InstrPointer, Inst , operand); + if Inst == 0: Register[0] = Register[0]>>combo(operand); + elif Inst == 1: Register[1] = Register[1]^operand; + elif Inst == 2: Register[1] = combo(operand)%8; + elif Inst == 3: + if Register[0] != 0: InstrPointer = operand -2; + elif Inst == 4: Register[1] = Register[1]^Register[2]; + elif Inst == 5: Results.append(combo(operand)%8); + elif Inst == 6: Register[1] = Register[0]>>combo(operand); + elif Inst == 7: Register[2] = Register[0]>>combo(operand); + InstrPointer += 2; + return Results; + +def broot(code,PotentialA,ind): + valid = []; + if ind == 0: + PotentialA = [0]; + for pa in PotentialA: + for option in range(8): + A_to_check = pow(8,(15-ind))*option + pa; + output = runprogram(code,A_to_check); + if output[-ind-1:] == code[-ind-1:]: valid.append(A_to_check); + if ind != 15: + valid = broot(code,valid.copy(),ind+1); + return valid; + +part1 = ",".join([str(n) for n in runprogram(MyCode,MyA)]); +print("part 1 =", part1); + +MinimalValues = broot(MyCode,[],0); +part2 = MinimalValues[0]; +for mv in MinimalValues: + if runprogram(MyCode,mv) == MyCode: part2 = min(part2,mv); + +print("part 2 =",part2); diff --git a/2024/aoc2024-d18.py b/2024/aoc2024-d18.py new file mode 100644 index 0000000..5f848fc --- /dev/null +++ b/2024/aoc2024-d18.py @@ -0,0 +1,64 @@ +#advent of code 2024 +#day 18 +#advent of gridbroot + +import heapq + +mygrid = {}; +FallingBytes = []; +lim = 70 + 1; +bytelim = 1024; +for p in [(X,Y) for Y in range(lim) for X in range(lim)]: mygrid[p] = "."; +#myfile = "18.ex"; +myfile = "18.in"; +if myfile != "18.in": #if example + lim = 7; + bytelim = 12; + +f = open(myfile,"r"); +for counter,l in enumerate(f): + bytex,bytey = [int(v) for v in l.strip().split(",")]; + FallingBytes.append((bytex,bytey)); + if counter < bytelim: mygrid[(bytex,bytey)] = "#"; +f.close(); + +start = (0,0); +end = (lim-1,lim-1); +dirs = [(1,0),(0,1),(-1,0),(0,-1)]; #east, south, west, north + +def getAdjacent(grid,coordinates): + adj = []; + xp, yp = coordinates; + for i,d in enumerate(dirs): + dx,dy = d; + if grid.get((xp+dx,yp+dy),"#") != "#": + adj.append((xp+dx,yp+dy)); + return adj; + +def shortestpath(grid,startpos): + score = 0; + visited = set(); + queue = [(0,startpos)]; + while queue: + dist, pos = heapq.heappop(queue); + if pos in visited: continue; + visited.add(pos); + if pos == end: + score = dist; + break; + NextPositions = getAdjacent(grid,pos); + for NP in NextPositions: + heapq.heappush(queue,(dist+1,NP)); + return score + +part1 = shortestpath(mygrid,start); +print("part 1 =",part1); +part2 = None; +for b_ind,b in enumerate(FallingBytes[bytelim:]): + mygrid[b] = "#"; + path = shortestpath(mygrid,start); + if path == 0: + part2 = f'{b[0]},{b[1]}'; + break; + +print("part 2 =",part2); diff --git a/2024/aoc2024-d19.py b/2024/aoc2024-d19.py new file mode 100644 index 0000000..eb3721a --- /dev/null +++ b/2024/aoc2024-d19.py @@ -0,0 +1,49 @@ +#advent of code 2024 +#day 19 +#unfortunately I didn't figure it out in time on my own +#I read some tips on the internet and returned to it on later date +#my attempt was kinda close but I didn't manage to correctly +#control the flow of the program which lead to duplicated paths +#I used the patterns dictionary to split the patterns based on their +#first letter so I don't need to check all patterns at the same time, +#only those potentially correct +#then, using CalcDesign function, we iterate over the whole string +#the dictionary PatternPaths stores the total amount of possible ways +#to reach a given substring of the function argument +#when we check each character c of the argument, we first look up +#how many paths there are to reach this substring (if it's the first +#letter then it is hardcoded as 1). Then we iterate over the list of +#patterns that begin with given character. +#if the substring plus pattern are the same as the substring of design +#then it is counted as possible path +#function returns a bool and an int: if there's at least one way to reach +#desired design (part 1), and amount of possible ways to reach it (part 2) + +def CalcDesign(design): + PatternPaths = {}; + for c_ind,c in enumerate(design): #character index, character + subpath = PatternPaths.get(design[:c_ind],0) + 1*(c_ind==0); + for pattern in patterns.get(c,[]): + subdesign = design[:c_ind] + pattern; + if subdesign == design[:c_ind + len(pattern)]: + if subdesign not in PatternPaths: + PatternPaths[subdesign] = 0; + PatternPaths[subdesign] += subpath + 0; + paths = PatternPaths.get(design,0); + return paths != 0, paths; + +part1 = 0; +part2 = 0; +patterns = {}; +data1, data2 = open("19.in","r").read().split("\n\n"); +for data in data1.strip().split(", "): + if data[0] not in patterns: patterns[data[0]] = []; + patterns[data[0]].append(data); + +for des in data2.strip().split("\n"): + ok,TotalPaths = CalcDesign(des); + part1 += ok*1; + part2 += TotalPaths; + +print("part 1 =", part1); +print("part 2 =", part2); diff --git a/2024/aoc2024-d20.py b/2024/aoc2024-d20.py new file mode 100644 index 0000000..16ed3c4 --- /dev/null +++ b/2024/aoc2024-d20.py @@ -0,0 +1,84 @@ +#advent of code 2024 +#day 20 +#shamelessly copypasted previous pathfinding and input parsing +#except it needed much adjustments because it's not really pathfinding +#basically: calculate map of distances between each point with djikstra +#since the path never branches, you can use these distances +#instead of recalculating the path after each cheat +#cheat + +grid = {}; +xMin, yMin, xMax, yMax = 0,0,0,0; #could get rid of it but w/e +dirs = [(1,0),(0,1),(-1,0),(0,-1)]; #east, south, west, north + +f = open("20.in","r"); +for y,l in enumerate(f): + yMax = max(y,yMax); + for x,c in enumerate(l.strip()): + if c == "S": + start = (x,y); + c = "." + elif c == "E": + end = (x,y); + c = "." + grid[(x,y)]=c; + xMax = max(xMax,x); +f.close(); + +def getAdjacent(coordinates): + adj = []; + xp, yp = coordinates; + for d in dirs: + dx,dy = d; + if grid.get((xp+dx,yp+dy),"#") != "#": + adj.append((xp+dx,yp+dy)); + return adj; + +def djikstra(startpos,endpos): + queue = []; + DistanceMap = {}; + queue = [(startpos,0)]; + while queue: + coords,dist = queue.pop(); + if coords in DistanceMap: continue; + DistanceMap[coords] = min(DistanceMap.get(coords,float('inf')),dist); + for NextPos in getAdjacent(coords): + queue.append((NextPos,dist+1)); + return DistanceMap; + +def cheatAdjacent(coordinates,secs): + adj = set(); + px,py = coordinates; + for X in range(secs+1): + for Y in range(secs+1-X): + adj.add((px+X*1,py+Y*1)); + adj.add((px+X*(-1),py+Y*(-1))); + adj.add((px+X*(1),py+Y*(-1))); + adj.add((px+X*(-1),py+Y*(1))); + return adj; + +PathDistances = djikstra(start,end); +part1 = 0; +part2 = 0; +for position in PathDistances: + d1 = PathDistances.get(position,-1); #negative value if there's no match + CheatedSteps = cheatAdjacent(position,20); + for ch in CheatedSteps: + d2 = PathDistances.get(ch,-1); #negative value if there's no match + if d2 == -1: continue; #if the step isn't in the PathDistances, then it's not valid + manhattan = abs(ch[0]-position[0]) + abs(ch[1]-position[1]) + ScoreDifference = d2-d1 - manhattan + if ScoreDifference >= 100: #from description, doesn't work for example + part2 += 1; + part1 += 1*(manhattan <= 2); + +print("part 1 =", part1); +print("part 2 =", part2); +#grid print for reference/debugging +#for y in range(yMax+1): +# for x in range(xMax+1): +# c = grid[(x,y)]; +# if (x,y) == start: c = "S"; +# elif (x,y) == end: c = "E"; +# print(c, end=""); +# print(); diff --git a/2024/aoc2024-d21_hardcoded.py b/2024/aoc2024-d21_hardcoded.py new file mode 100644 index 0000000..1d360b2 --- /dev/null +++ b/2024/aoc2024-d21_hardcoded.py @@ -0,0 +1,237 @@ +#advent of code 2024 +#day 21 +#finally fucking worked +#I had a good idea for part1 to not generate all steps but only count +#the number of steps since the strings for part 2 would eat up all the RAM +#however I got hit by another problem which I didn't forsee, +#that is permutations. Basically, for part 2, you need to take into account +#that maybe going in different order is going to yield better results +#I hardcoded the possible steps instead of DFSing them like a normal +#human being and doubled down on it later. When I'll have more time and will to +#improve the code, I'll include the part where I generate the movements +#solution for part 1 was developed on my own, but for part 2 I needed +#external help (at least I understand what's going on in here so it's not +#that I copy-pasted someone else's code). +from functools import cache +import itertools +#use this for later +''' +keyboard_num = {}; +keyboard_num["7"] = (0,0); +keyboard_num["8"] = (1,0); +keyboard_num["9"] = (2,0); +keyboard_num["4"] = (1,0); +keyboard_num["5"] = (1,1); +keyboard_num["6"] = (1,2); +keyboard_num["3"] = (2,0); +keyboard_num["2"] = (2,1); +keyboard_num["1"] = (2,2); +keyboard_num["0"] = (3,1); +keyboard_num["A"] = (3,2); +keyboard_dir = {}; +keyboard_dir"^"] = (1,0); +keyboard_dir"A"] = (2,0); +keyboard_dir"<"] = (0,1); +keyboard_dir"v"] = (1,1); +keyboard_dir">"] = (2,1); #''' + +dn = {}; +dn["^"] = {}; +dn["A"] = {}; +dn["<"] = {}; +dn["v"] = {}; +dn[">"] = {}; +dn["^"]["^"] =["A"]; +dn["^"]["A"] =[">A"]; +dn["^"]["<"] =["v<A"]; +dn["^"]["v"] =["vA"]; +dn["^"][">"] =["v>A",">vA"]; +dn["A"]["^"] =["<A"]; +dn["A"]["A"] =["A"]; +dn["A"]["<"] =["v<<A","<v<A"]; +dn["A"]["v"] =["v<A","<vA"]; +dn["A"][">"] =["vA"]; +dn["<"]["^"] =[">^A"]; +dn["<"]["A"] =[">^>A",">>^A"]; +dn["<"]["<"] =["A"]; +dn["<"]["v"] =[">A"]; +dn["<"][">"] =[">>A"]; +dn["v"]["^"] =["^A"]; +dn["v"]["A"] =["^>A",">^A"]; +dn["v"]["<"] =["<A"]; +dn["v"]["v"] =["A"]; +dn["v"][">"] =[">A"]; +dn[">"]["^"] =["^<A","<^A"]; +dn[">"]["A"] =["^A"]; +dn[">"]["<"] =["<<A"]; +dn[">"]["v"] =["<A"]; +dn[">"][">"] =["A"]; + +kn={}; +kn["7"] = {}; +kn["8"] = {}; +kn["9"] = {}; +kn["4"] = {}; +kn["5"] = {}; +kn["6"] = {}; +kn["1"] = {}; +kn["2"] = {}; +kn["3"] = {}; +kn["0"] = {}; +kn["A"] = {}; +kn["7"]["7"] =["A"]; +kn["7"]["8"] =[">A"]; +kn["7"]["9"] =[">>A"]; +kn["7"]["4"] =["vA"]; +kn["7"]["5"] =["v>A",">vA"]; +kn["7"]["6"] =["v>>A",">v>A",">>vA"]; +kn["7"]["1"] =["vvA"]; +kn["7"]["2"] =["vv>A","v>vA",">vvA"]; +kn["7"]["3"] =["vv>>A","v>v>A","v>>vA",">vv>A",">v>vA",">>vvA"]; +kn["7"]["0"] =["vv>vA","v>vvA",">vvvA"]; +kn["7"]["A"] =["vv>v>A","vv>>vA","v>vv>A","v>v>vA","v>>vvA",">vvv>A",">vv>vA",">v>vvA",">>vvvA"]; +kn["8"]["7"] =["<A"]; +kn["8"]["8"] =["A"]; +kn["8"]["9"] =[">A"]; +kn["8"]["4"] =["v<A","<vA"]; +kn["8"]["5"] =["vA"]; +kn["8"]["6"] =["v>A",">vA"]; +kn["8"]["1"] =["vv<A","v<vA","<vvA"]; +kn["8"]["2"] =["vvA"]; +kn["8"]["3"] =["vv>A","v>vA",">vvA"]; +kn["8"]["0"] =["vvvA"]; +kn["8"]["A"] =["vvv>A","vv>vA","v>vvA",">vvvA"]; +kn["9"]["7"] =["<<A"]; +kn["9"]["8"] =["<A"]; +kn["9"]["9"] =["A"]; +kn["9"]["4"] =["v<<A","<v<A","<<vA"]; +kn["9"]["5"] =["v<A","<vA"]; +kn["9"]["6"] =["vA"]; +kn["9"]["1"] =["vv<<A","v<v<A","v<<vA","<vv<A","<v<vA","<<vvA"]; +kn["9"]["2"] =["vv<A","v<vA","<vvA"]; +kn["9"]["3"] =["vvA"]; +kn["9"]["0"] =["vvv<A","vv<vA","v<vvA","<vvvA"]; +kn["9"]["A"] =["vvvA"]; +kn["4"]["7"] =["^A"]; +kn["4"]["8"] =["^>A",">^A"]; +kn["4"]["9"] =["^>>A",">^>A",">>^A"]; +kn["4"]["4"] =["A"]; +kn["4"]["5"] =[">A"]; +kn["4"]["6"] =[">>A"]; +kn["4"]["1"] =["vA"]; +kn["4"]["2"] =["v>A",">vA"]; +kn["4"]["3"] =["v>>A",">v>A",">>vA"]; +kn["4"]["0"] =["v>vA",">vvA"]; +kn["4"]["A"] =["v>v>A","v>>vA",">vv>A",">v>vA",">>vvA"]; +kn["5"]["7"] =["^<A","<^A"]; +kn["5"]["8"] =["^A"]; +kn["5"]["9"] =["^>A",">^A"]; +kn["5"]["4"] =["<A"]; +kn["5"]["5"] =["A"]; +kn["5"]["6"] =[">A"]; +kn["5"]["1"] =["v<A","<vA"]; +kn["5"]["2"] =["vA"]; +kn["5"]["3"] =["v>A",">vA"]; +kn["5"]["0"] =["vvA"]; +kn["5"]["A"] =["vv>A","v>vA",">vvA"]; +kn["6"]["7"] =["^<<A","<^<A","<<^A"]; +kn["6"]["8"] =["^<A","<^A"]; +kn["6"]["9"] =["^A"]; +kn["6"]["4"] =["<<A"]; +kn["6"]["5"] =["<A"]; +kn["6"]["6"] =["A"]; +kn["6"]["1"] =["v<<A","<v<A","<<vA"]; +kn["6"]["2"] =["v<A","<vA"]; +kn["6"]["3"] =["vA"]; +kn["6"]["0"] =["vv<A","v<vA","<vvA"]; +kn["6"]["A"] =["vvA"]; +kn["1"]["7"] =["^^A"]; +kn["1"]["8"] =["^^>A","^>^A",">^^A"]; +kn["1"]["9"] =["^^>>A","^>^>A","^>>^A",">^^>A",">^>^A",">>^^A"]; +kn["1"]["4"] =["^A"]; +kn["1"]["5"] =["^>A",">^A"]; +kn["1"]["6"] =["^>>A",">^>A",">>^A"]; +kn["1"]["1"] =["A"]; +kn["1"]["2"] =[">A"]; +kn["1"]["3"] =[">>A"]; +kn["1"]["0"] =[">vA"]; +kn["1"]["A"] =[">v>A",">>vA"]; +kn["2"]["7"] =["^^<A","^<^A","<^^A"]; +kn["2"]["8"] =["^^A"]; +kn["2"]["9"] =["^^>A","^>^A",">^^A"]; +kn["2"]["4"] =["^<A","<^A"]; +kn["2"]["5"] =["^A"]; +kn["2"]["6"] =["^>A",">^A"]; +kn["2"]["1"] =["<A"]; +kn["2"]["2"] =["A"]; +kn["2"]["3"] =[">A"]; +kn["2"]["0"] =["vA"]; +kn["2"]["A"] =["v>A",">vA"]; +kn["3"]["7"] =["^^<<A","^<^<A","^<<^A","<^^<A","<^<^A","<<^^A"]; +kn["3"]["8"] =["^^<A","^<^A","<^^A"]; +kn["3"]["9"] =["^^A"]; +kn["3"]["4"] =["^<<A","<^<A","<<^A"]; +kn["3"]["5"] =["^<A","<^A"]; +kn["3"]["6"] =["^A"]; +kn["3"]["1"] =["<<A"]; +kn["3"]["2"] =["<A"]; +kn["3"]["3"] =["A"]; +kn["3"]["0"] =["v<A","<vA"]; +kn["3"]["A"] =["vA"]; +kn["0"]["7"] =["^^^<A","^^<^A","^<^^A"]; +kn["0"]["8"] =["^^^A"]; +kn["0"]["9"] =["^^^>A","^^>^A","^>^^A",">^^^A"]; +kn["0"]["4"] =["^^<A","^<^A"]; +kn["0"]["5"] =["^^A"]; +kn["0"]["6"] =["^^>A","^>^A",">^^A"]; +kn["0"]["1"] =["^<A"]; +kn["0"]["2"] =["^A"]; +kn["0"]["3"] =["^>A",">^A"]; +kn["0"]["0"] =["A"]; +kn["0"]["A"] =[">A"]; +kn["A"]["7"] =["^^^<<A","^^<^<A","^^<<^A","^<^^<A","^<^<^A","^<<^^A","<^^^<A","<^^<^A","<^<^^A"]; +kn["A"]["8"] =["^^^<A","^^<^A","^<^^A","<^^^A"]; +kn["A"]["9"] =["^^^A"]; +kn["A"]["4"] =["^^<<A","^<^<A","^<<^A","<^^<A","<^<^A"]; +kn["A"]["5"] =["^^<A","^<^A","<^^A"]; +kn["A"]["6"] =["^^A"]; +kn["A"]["1"] =["^<<A","<^<A"]; +kn["A"]["2"] =["^<A","<^A"]; +kn["A"]["3"] =["^A"]; +kn["A"]["0"] =["<A"]; +kn["A"]["A"] =["A"]; + + +codes = [l for l in open("21.in","r").read().strip().split("\n")]; + +def GenDirMoves(mystring, seqs): + options = [seqs[x][y] for x, y in zip("A" + mystring, mystring)] + return ["".join(x) for x in itertools.product(*options)] + +@cache +def CalcSteps(DirMoves,PrevPos,depth): + if depth == 1: + return sum(len(dn[pos1][pos2][0]) for pos1,pos2 in zip("A"+DirMoves,DirMoves)); + score = 0; + for pos1, pos2 in zip("A"+DirMoves,DirMoves): + score += min(CalcSteps(substring,"A",depth-1) for substring in dn[pos1][pos2]) + return score; + +def get_score(inputs,NumberOfRobots): + total = 0; + for data in inputs: + options = GenDirMoves(data,kn); + LengthOfShortestSequence = float('inf'); + for op in options: + LengthOfShortestSequence = min(LengthOfShortestSequence,CalcSteps(op,"A",NumberOfRobots)) + NumericPartOfCode = int(data[:-1]); + Complexity = NumericPartOfCode*LengthOfShortestSequence; + total += Complexity; + return total; + +part1 = get_score(codes,2); +part2 = get_score(codes,25); + +print("part 1 =", part1); +print("part 1 =", part2); + diff --git a/2024/aoc2024-d22.py b/2024/aoc2024-d22.py new file mode 100644 index 0000000..5c4c809 --- /dev/null +++ b/2024/aoc2024-d22.py @@ -0,0 +1,79 @@ +#advent of code day 22 +#day 22 +#first puzzle I did after getting filtered by day 19 +#easy enough, just needed to calculate the prices per sequences +#before calculating the sums to speed things up +#for part 1 jsut calculate the new secret number after 2000 iterations +#for part 2: make 2 dictionaries with secret number indexes as keys +#each value in both dictionaries are lists +#1 dictionary is for how prices are changing, the other one is current prices +#make a set of all possible sequences from all secret keys based on price change dictionary +#make a 3rd dictionary which has secret number as key and another dictionary as value +#the nested dictionary contains prices based on a sequence +#after that just iterate over the set of possible sequences make a sum +#of the prices for that sequence, choose the highest +#one thing that lead to a wrong answer was that I was constantly updating +#the price in 3rd dictionary, but according to problem descriptions +#monkeys sell the first time the sequence occurs, which means I needed to +#only register the price once, then skip the sequence next time it occurs in +#given secret number + +SecretNumbers = [int(l) for l in open("22.in","r").read().strip().split("\n")]; + +def CalcSecret(previous_number): + next_number = (previous_number<<6)^previous_number; + next_number = next_number%16777216; + next_number = (next_number>>5)^next_number; + next_number = next_number%16777216; + next_number = (next_number<<11)^next_number; + next_number = next_number%16777216; + return next_number; + +print("please wait 1/3"); +part1 = 0; +step = 2000; +changes = {}; +prices = {}; +#calculate the 2000 iterations of each secret number +#sum up all values of 2000th iteration for part 1 +#store the prices of each number for each iteration +#store the change in price of each number for each iteration +for num_i,num in enumerate(SecretNumbers): + num_old = 0 + num; + changes[num_i] = []; + prices[num_i] = []; + prices[num_i].append(num%10); + for s in range(step): + num_new = CalcSecret(num_old); + changes[num_i].append(num_new%10-num_old%10); + prices[num_i].append(num_new%10); + num_old = 0 + num_new; + part1 += num_old; + +print("please wait 2/3"); +#create a set of all possible sequences +#store the price of a secret number when given sequence occurs +prices_per_seq = {}; +sequences = set(); +for num_i in changes: + prices_per_seq[num_i] = {}; + for j in range(3,len(changes[num_i])): + subseq = tuple(changes[num_i][j-3:j+1]); + sequences.add(subseq); + price_sub = prices[num_i][j+1]; + if subseq in prices_per_seq[num_i]: continue; + prices_per_seq[num_i][subseq] = price_sub + 0; + +print("please wait 3/3"); +#for each sequence calculate the sum of prices for each secret number +#when given sequence occurs. Store the highest sum for part 2 +part2 = 0; +for s_i,sequence in enumerate(sequences): + print(s_i+1,"/",len(sequences)); #to make sure the code still runs + score = 0; + for num_i in prices_per_seq: + score += prices_per_seq[num_i].get(sequence,0); + part2 = max(score,part2); + +print("part 1 =", part1); +print("part 2 =", part2); diff --git a/2024/aoc2024-d23.py b/2024/aoc2024-d23.py new file mode 100644 index 0000000..ca87fb3 --- /dev/null +++ b/2024/aoc2024-d23.py @@ -0,0 +1,73 @@ +#advent of code 2024 +#day 23 +#this is rewritten to adapt for part 2. All possible sets of computers +#are searched for recursively (with FindNetwork function) +#and stored in subnetworks set. Then it iterates over all elements of +#subnetworks set. If the element has 3 computers, then it iterates over +#all computers in the set. If at least one computer starts with "t", +#it is counted towards part 1. We keep track of the longest set of +#computers and update part2 variable when it changes. +#The way FindNetwork works is that it takes a name of PC and a set of previously +#visited computers that are all iterconnected. Then the given PC is added +#to the set, the set is sorted (to avoid duplicates) and added to +#subnetworks set. It iterates over all computers connected to PC from argument +#according to Connections dictionary. If the computer is already in +#the cluster, it is skipped. Then, we nest another loop to check if the +#connections of the computer match the computers in the cluster. +#if not, it's skipped. if yes, it call the FindNetwork function again +#with the computer and updated cluster (NextCluster) as arguments. +#infinite loop is prevented while checking whether or not the computer +#is already in the cluster. Runtime is sped up due to discarding already +#visited clusters accoroding to subnetworks set. +#the password for part2 is just a string of computer names separated with commas +#similar to previous day +#I think the correct term is "ring" or "topology" but that's completely irrelevant +#for the puzzle + +Connections = {}; +f = open("23.in","r"); +for l in f: + PC1, PC2 = l.strip().split("-"); + if PC1 not in Connections: Connections[PC1] = set(); + if PC2 not in Connections: Connections[PC2] = set(); + Connections[PC1].add(PC2); + Connections[PC2].add(PC1); +f.close(); + +subnetworks = set(); + +def FindNetwork(PC,Cluster): + NextCluster = Cluster.copy(); + NextCluster.add(PC); + NextCluster = sorted(NextCluster); + if tuple(NextCluster) in subnetworks: return; + subnetworks.add(tuple(NextCluster)); + for NextPC in Connections[PC]: + ok = True; + if NextPC in Cluster: continue; + for OtherPCs in NextCluster: + if OtherPCs not in Connections[NextPC]: ok = False; + if not ok: continue; + FindNetwork(NextPC, set(NextCluster)); + + +for i,computer in enumerate(Connections): + print(i, "/", len(Connections)); + FindNetwork(computer,set()); + +part1 = 0; +part2 = None; +LargestNetworkSize = 0; +for subnet in subnetworks: + SubnetSize = len(subnet) + if SubnetSize == 3: + for computer in subnet: + if computer[0] == "t": + part1 += 1; + break; + LargestNetworkSize = max(LargestNetworkSize,SubnetSize); + if LargestNetworkSize == SubnetSize: part2 = subnet; + +part2 = ",".join(part2); +print("part 1 =",part1); +print("part 2 =",part2); diff --git a/2024/aoc2024-d24.py b/2024/aoc2024-d24.py new file mode 100644 index 0000000..49d2c6f --- /dev/null +++ b/2024/aoc2024-d24.py @@ -0,0 +1,82 @@ +#advent of code 2024 +#day 24 +#part 2 requires reading the input, then either solve by hand (like I did) +#or make some kind of detection of abnormailities (for example, +#z-wires should always by outputted by XOR gate, +#output of x XOR y should always go as input to another XOR connected to z-wire etc +#basically the whole program is just a lot of adder gates, +#adding all bits from x and y wires and outputting them into z-wires, +#mixed together with 8 errors. +#part 1 is kind of shitty so I won't bother explaining. +#I should probably implement some kind of verification of calculations +#that is: calculate the z in binary, calculate the x and y in binary +#and calculate the z as a sum of x and y + +import re +data_initial, data_gates = open("24.in","r").read().split("\n\n"); + +Wires = {}; +AllGates = {}; + +def calc(IN01,GATE,IN02,OUT): + CurrentValue = Wires.get(OUT,False); + if GATE == "AND": Wires[OUT] = Wires[IN01] & Wires[IN02]; + elif GATE == "OR": Wires[OUT] = Wires[IN01] | Wires[IN02]; + elif GATE == "XOR": Wires[OUT] = Wires[IN01] ^ Wires[IN02]; + +for line in data_gates.strip().split("\n"): + in1, gt, in2, out = re.findall(r'\w+',line.strip()); + AllGates[(in1, gt, in2, out)] = False; + +for line in data_initial.split("\n"): + wire, wireval = line.strip().split(": "); + Wires[wire] = bool(int(wireval)); + +go = True; #keep hgoing until all gates were used +while go: + go = False; + for Gate in AllGates: + if AllGates[Gate]: continue; #skip gates which already ran + go = True; + a1,a2,a3,a4 = Gate; + if Wires.get(a1,"notyet") != "notyet" and Wires.get(a3,"notyet") != "notyet": + calc(*Gate); + AllGates[Gate] = True; + +X_set = []; +Y_set = []; +Z_set = []; +for w in Wires: + if w[0] == "x": X_set.append((w,int(Wires[w]))); + if w[0] == "y": Y_set.append((w,int(Wires[w]))); + if w[0] == "z": Z_set.append((w,int(Wires[w]))); + +Xvals = reversed(sorted(X_set, key = lambda m: m[0])); +Yvals = reversed(sorted(Y_set, key = lambda m: m[0])); +Z_set = reversed(sorted(Z_set, key = lambda m: m[0])); +Xbinary, Ybinary, Zbinary = "","",""; +for zzz in Z_set: Zbinary += str(zzz[1]); +for yyy in Yvals: Ybinary += str(yyy[1]); +for xxx in Xvals: Xbinary += str(xxx[1]); +Zcorrect = int(Xbinary,2) + int(Ybinary,2); +Zcorrbin = str(bin(Zcorrect)); +print("diagnostics"); +print("binary X = ", Xbinary); +print("binary Y = ", Ybinary); +print(f'(addition) {"-"*len(Zcorrbin)}'); +print("binary Z =", Zcorrbin); +print(); +print("decimal X =", int(Xbinary,2)); +print("decimal Y =", int(Ybinary,2)); +print("decimal Z =", Zcorrect, "<- this should be the output for part 2"); +print("false Z =", Zbinary); + +part1 = int(Zbinary,2) +print(); +print("part 1 = ", part1); +#hardcoded for my input, I did it with pen and paper +FoundIncorrectWires = ["wbw","wgb","jct","z39","gwh","z09","rcb","z21"]; +FoundIncorrectWires = sorted(FoundIncorrectWires); +part2 = ",".join(FoundIncorrectWires); +print("part 2 = ", part2); + diff --git a/2024/aoc2024-d25.py b/2024/aoc2024-d25.py new file mode 100644 index 0000000..4f14ee6 --- /dev/null +++ b/2024/aoc2024-d25.py @@ -0,0 +1,55 @@ +#advent of code 2024 +#day 25 +#I'm not sure if my solution is general enough to work on modified inputs +#like bigboys but I guess it's good enough to work on original AOC one. +#parse schematics, decide if they are a key or a lock based on first row +#generate the heights of each pin +#compare each key with each lock column by column + +data = open("25.in","r").read().strip().split("\n\n"); + +def getDimensions(gridraw): + Category = None; + Schematics = {}; + xMax = 0; + yMax = 0; + for y, line in enumerate(gridraw.strip().split("\n")): + yMax = max(yMax,y); + if y == 0: + if line == "."*len(line): Category = "key"; + else: Category = "loc"; + for x, c in enumerate(line): + xMax = max(xMax,x); + Schematics[(y,x)] = c; + heights = []; + if Category == "key": + for x in range(xMax+1): + h = sum( Schematics[(y,x)]=="#" for y in range(1,yMax) ); + heights.append(h); + else: + for x in range(xMax+1): + h = sum( Schematics[(y,x)]=="#" for y in range(yMax-1,0,-1) ); + heights.append(h); + return Category, heights; + +Keyed = []; +Locked = []; +XMAX = 0; +YMAX = 0; +XMAX = len(data[0].split("\n")[0]) +YMAX = len(data[0].split("\n")) -2; +for d in data: + cat, dims = getDimensions(d); + if cat == "key": Keyed.append(dims); + if cat == "loc": Locked.append(dims); + +part1 = 0; +for Key in Keyed: + for Lock in Locked: + fit = True; + for col in range(XMAX): + if Key[col] + Lock[col] > YMAX: fit = False; + part1 += 1*fit; + +print("part 1 =", part1); + |