summaryrefslogtreecommitdiff
path: root/2020
diff options
context:
space:
mode:
Diffstat (limited to '2020')
-rw-r--r--2020/aoc2020-d11.py62
-rw-r--r--2020/aoc2020-d12.py93
-rw-r--r--2020/aoc2020-d13.py46
-rw-r--r--2020/aoc2020-d14.py72
-rw-r--r--2020/aoc2020-d15.py35
-rw-r--r--2020/aoc2020-d16.py71
-rw-r--r--2020/aoc2020-d17.py72
-rw-r--r--2020/aoc2020-d18.py53
-rw-r--r--2020/aoc2020-d19.py58
-rw-r--r--2020/aoc2020-d20.py363
10 files changed, 925 insertions, 0 deletions
diff --git a/2020/aoc2020-d11.py b/2020/aoc2020-d11.py
new file mode 100644
index 0000000..06c7626
--- /dev/null
+++ b/2020/aoc2020-d11.py
@@ -0,0 +1,62 @@
+#advent of code 2020
+#day 11
+
+directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)];
+
+#for part 1
+def scan1(grid,pos):
+ around = "";
+ y,x = pos;
+ for dy,dx in directions:
+ if (y+dy,x+dx) not in grid: continue;
+ around += grid[(y+dy,x+dx)];
+ return around;
+#for part 2
+def scan2(grid,pos):
+ around = "";
+ for dy,dx in directions:
+ y,x = pos;
+ while True:
+ x += dx;
+ y += dy;
+ if (y,x) not in grid:
+ break;
+ elif grid[(y,x)] != ".":
+ around += grid[(y,x)];
+ break;
+ return around;
+
+#correct function is passed as an argument (scan)
+def simulate(grid,scan,lim):
+ score = 0;
+ while True:
+ gridDupe = dict();
+ for coordinates in grid:
+ state = grid[coordinates];
+ y,x = coordinates;
+ around = scan(grid,coordinates);
+ if around.count("#") == 0 and state == "L":
+ gridDupe[coordinates] = "#";
+ elif around.count("#") >= lim and state == "#":
+ gridDupe[coordinates] = "L";
+ for dupe in gridDupe:
+ grid[dupe] = gridDupe[dupe];
+ if len(gridDupe) == 0:
+ break;
+ for coordinates in grid:
+ if grid[coordinates] == "#": score += 1;
+ return score;
+
+grid1 = dict();
+PuzzleInput = open("11.in","r");
+for y,line in enumerate(PuzzleInput):
+ line = line[:-1];
+ for x, c in enumerate(line):
+ grid1[(y,x)] = c;
+PuzzleInput.close();
+grid2 = grid1.copy();
+
+p1 = simulate(grid1,scan1,4);
+p2 = simulate(grid2,scan2,5);
+print("part 1 =",p1);
+print("part 2 =",p2);
diff --git a/2020/aoc2020-d12.py b/2020/aoc2020-d12.py
new file mode 100644
index 0000000..4f70f79
--- /dev/null
+++ b/2020/aoc2020-d12.py
@@ -0,0 +1,93 @@
+#advent of code 2020
+#day 12
+#Im experimenting with different parsing,
+#the [:-1] is for skipping the empty line
+#big mistake: giving north a negative value,
+#which meant that my left and right turns where flipped
+#changed it after getting the correct value
+navigationInstructions = [line for line in open("12.in","r").read().split("\n")][:-1];
+
+directions = dict();
+directions[0] = (0,1); #east
+directions[1] = (-1,0); #south
+directions[2] = (0,-1); #west
+directions[3] = (1,0); #north
+
+#part 1
+def actions(act,val,face):
+ if act == "N":
+ return (val,0,face);
+ elif act =="S":
+ return (-val,0,face);
+ elif act == "E":
+ return (0,val,face);
+ elif act == "W":
+ return (0,-val,face);
+ elif act == "L":
+ turn = val//90;
+ tempF = (4+face-turn)%4;
+ return (0,0,tempF);
+ elif act == "R":
+ turn = val//90;
+ tempF = (4+face+turn)%4
+ return (0,0,tempF);
+ elif act == "F":
+ mody,modx = directions[face];
+ return (mody*val,modx*val,face);
+
+#part 2
+def NewActions(act,val,wayY,wayX):
+ if act == "N":
+ return (0,0,wayY+val,wayX);
+ elif act =="S":
+ return (0,0,wayY-val,wayX);
+ elif act == "E":
+ return (0,0,wayY,wayX+val);
+ elif act == "W":
+ return (0,0,wayY,wayX-val);
+ elif act == "L":
+ turn = val//90;
+ tempW = (wayY,wayX);
+ for t in range(turn):
+ tempW = (tempW[1],-tempW[0]);
+ return (0,0,tempW[0],tempW[1]);
+ elif act == "R":
+ turn = val//90;
+ tempW = (wayY,wayX);
+ for t in range(turn):
+ tempW = (-tempW[1],tempW[0]);
+ return (0,0,tempW[0],tempW[1]);
+ elif act == "F":
+ return (wayY*val,wayX*val,wayY,wayX);
+ else:
+ return False;
+
+#ship coordinates, part 1
+X1 = 0;
+Y1 = 0;
+D1 = 0; #direction
+#ship coordinates, part 2
+X2,Y2,D2 = 0,0,0;
+WX, WY = 10,1; #waypoint relative coordinates
+
+for instr in navigationInstructions:
+ action = instr[0];
+ value = int(instr[1:]);
+ dy1,dx1,dd1 = actions(action,value,D1); #part 1
+ Y1 += dy1;
+ X1 += dx1;
+ D1 = dd1;
+ dy2,dx2,dwy,dwx = NewActions(action,value,WY, WX); #part 2
+ Y2 += dy2;
+ X2 += dx2;
+ WY = dwy;
+ WX = dwx;
+
+if X1 < 0: X1 = -X1;
+if Y1 < 0: Y1 = -Y1;
+p1 = X1 + Y1;
+if X2 < 0: X2 = -X2;
+if Y2 < 0: Y2 = -Y2;
+p2 = X2 + Y2;
+print("part 1 =",p1);
+print("part 2 =",p2);
diff --git a/2020/aoc2020-d13.py b/2020/aoc2020-d13.py
new file mode 100644
index 0000000..dd0d0d1
--- /dev/null
+++ b/2020/aoc2020-d13.py
@@ -0,0 +1,46 @@
+#advent of code 2020
+#day 13
+#kinda cheated, the chinese remainder theorem (CRT) was copy-pasted from google search results
+#the source where I was reading how it works didn't really provide a good example
+#will definitely look it up later :)
+
+def gcd_extended(a, b):
+ if a == 0:
+ return b, 0, 1
+ gcd, x1, y1 = gcd_extended(b % a, a)
+ x = y1 - (b // a) * x1
+ y = x1
+ return gcd, x, y
+
+def find_min_x(num, rem):
+ prod = 1
+ for n in num:
+ prod *= n
+ result = 0
+ for i in range(len(num)):
+ prod_i = prod // num[i]
+ _, inv_i, _ = gcd_extended(prod_i, num[i])
+ result += rem[i] * prod_i * inv_i
+ return result % prod
+
+PuzzleInput = open("13.in","r").read().split("\n");
+timestamp = int(PuzzleInput[0]);
+buses = PuzzleInput[1].split(",");f b != "x"];
+
+times = dict();
+BusList = [];
+OffsetList = [];
+for index, bus in enumerate(buses):
+ if bus == "x": continue;
+ bus = int(bus);
+ BusList.append(bus);
+ OffsetList.append(bus-index);
+ d = timestamp%bus;
+ NextStop = timestamp-d+bus;
+ times[NextStop] = (bus,bus-d);
+
+busID, WaitTime = times[min(times)];
+p1 = busID * WaitTime;
+p2 = find_min_x(BusList,OffsetList); #CRT
+print("part 1 =",p1);
+print("part 2 =",p2);
diff --git a/2020/aoc2020-d14.py b/2020/aoc2020-d14.py
new file mode 100644
index 0000000..4f3c4b1
--- /dev/null
+++ b/2020/aoc2020-d14.py
@@ -0,0 +1,72 @@
+#advent of code 2020
+#day 14
+#first puzzle where I was stuck with wrong answer even tho the code look ok
+#trimming down the amount of code helped a lot, since there seemed to be a
+#wrong variable consider during comparison
+#probably should've used binary values instead of converting numbers
+#to binary manually
+
+import re
+import itertools
+
+def GetBit(decimal): #convert decimal to bit as a list
+ b = [];
+ for p in range(35,-1,-1):
+ power = pow(2,p);
+ x1 = decimal//power;
+ b.append(x1);
+ decimal -= x1*power;
+ return b;
+
+def GetDec(bit): #convert bit (list) to integer
+ dec = 0;
+ for index, bv in enumerate(bit):
+ dec += bv*pow(2,len(bit)-1-index);
+ return dec;
+
+def GetAddresses(MemoryAddress, CurrentMask):
+ addresses = [];
+ BitAddress = GetBit(MemoryAddress);
+ Xlocations = [];
+ for options in itertools.product([0,1],repeat=CurrentMask.count("X")):
+ NewAddress = [];
+ xcount = 0;
+ for bi, ba in enumerate(BitAddress):
+ if CurrentMask[bi] == "X":
+ NewAddress.append(options[xcount]);
+ xcount += 1;
+ elif CurrentMask[bi] == '1':
+ NewAddress.append(1);
+ else:
+ NewAddress.append(ba);
+ addresses.append(GetDec(NewAddress));
+ return addresses;
+
+mem1 = dict();
+mem2 = dict();
+mask = None;
+
+PuzzleInput = open("14.in","r");
+for line in PuzzleInput:
+ line = line[:-1];
+ if line[2] == "s": #a bit obfuscated "if it starts with 'mask = ' "
+ mask = list(line.replace("mask = ",""));
+ else:
+ digits = [int(v) for v in re.findall(r'\d+',line)];
+ addr, value = digits;
+ bval = GetBit(value);
+ for i,m in enumerate(mask):
+ if m == "X": continue;
+ bval[i] = int(m);
+ mem1[int(addr)] = GetDec(bval);
+ #part 2
+ for FloatAddress in GetAddresses(addr,mask):
+ mem2[FloatAddress] = value;
+PuzzleInput.close();
+
+p1 = 0;
+p2 = 0;
+for a1 in mem1: p1 += mem1[a1];
+for a2 in mem2: p2 += mem2[a2];
+print("part 1 =",p1);
+print("part 2 =",p2);
diff --git a/2020/aoc2020-d15.py b/2020/aoc2020-d15.py
new file mode 100644
index 0000000..10910fe
--- /dev/null
+++ b/2020/aoc2020-d15.py
@@ -0,0 +1,35 @@
+#advent of code 2020
+#day 15
+#it took less than 1min to bruteforce part 2 so I guess it's a free star
+
+limit1 = 2020;
+limit2 = 30000000;
+turn = 0;
+SpokenNumbers = dict();
+StartingNumbers =[int(N) for N in open("15.in","r").read().split(",")];
+for i,n in enumerate(StartingNumbers[:-1]):
+ turn += 1;
+ SpokenNumbers[n] = i+1;
+ #LastNumber = n;
+ print(turn,n);
+
+p1 = None;
+p2 = None;
+turn += 1;
+LastNumber = StartingNumbers[-1];
+
+while turn < limit2:
+ turn += 1;
+ if LastNumber in SpokenNumbers:
+ speak = turn -1 - SpokenNumbers[LastNumber];
+ else:
+ speak = 0;
+ SpokenNumbers[LastNumber] = turn -1;
+ LastNumber = speak;
+ print(turn, speak); #since it's a bruteforce I'm leaving it as a progress bar
+ if turn == limit1:
+ p1 = LastNumber;
+
+p2 = LastNumber;
+print("part 1 = ", p1);
+print("part 2 = ", p2);
diff --git a/2020/aoc2020-d16.py b/2020/aoc2020-d16.py
new file mode 100644
index 0000000..86cd8eb
--- /dev/null
+++ b/2020/aoc2020-d16.py
@@ -0,0 +1,71 @@
+#advent of code 2020
+#day 16
+#I spent a lot of time fixing its logic during solving
+#so the code was cleaned thorougly after finishing
+#which was a good idea because i was doing it directly after
+#and still have to think for a minute what some lines are actually doing
+#I think there's a way to skip looping over tickets for second time
+#but it would make it unnecessarily convoluted
+#I also tried making understandable variable names way too hard for a puzzle code
+p1 = 0;
+p2 = 1;
+requirements = dict();
+NearbyTickets = [];
+PuzzleInput = open("16.in","r").read().split("\n\n");
+#rules for ticket fields
+for line in PuzzleInput[0].split("\n"):
+ FieldName, FieldValues = line.split(":");
+ FieldValues = [ tuple([int(v) for v in fv.split("-")]) for fv in FieldValues.split(" or ")];
+ requirements[FieldName] = FieldValues;
+#your ticket
+MyTicket = [int(val) for val in PuzzleInput[1].split("\n")[1].split(",")];
+#nearby tickets
+for line in PuzzleInput[2].split("\n")[1:]:
+ if len(line) <= 1: continue;
+ NearbyTickets.append([int(val) for val in line.split(",")]);
+
+GoodTickets = [];
+for ticket in NearbyTickets:
+ ValidTicket = True;
+ for TicketValue in ticket:
+ for FieldValues1, FieldValues2 in requirements.values():
+ test1 = FieldValues1[0] <= TicketValue <= FieldValues1[1];
+ test2 = FieldValues2[0] <= TicketValue <= FieldValues2[1];
+ valid = test1 or test2;
+ if valid: break;
+ if not valid:
+ p1 += TicketValue;
+ ValidTicket = False;
+ if ValidTicket: GoodTickets.append(ticket);
+
+Fields = dict();
+InvalidFields = dict();
+#find for which fields the numbers in tickets are viable for
+#store them in InvalidFields dict
+for ticket in GoodTickets:
+ for ti, TicketValue in enumerate(ticket):
+ for FieldName in requirements:
+ if FieldName in Fields.values(): continue;
+ FieldValues1, FieldValues2 = requirements[FieldName];
+ test1 = FieldValues1[0] <= TicketValue <= FieldValues1[1];
+ test2 = FieldValues2[0] <= TicketValue <= FieldValues2[1];
+ valid = test1 or test2;
+ if not valid:
+ if FieldName not in InvalidFields: InvalidFields[FieldName] = set();
+ InvalidFields[FieldName].add(ti);
+
+#all fields have different number of possible places and its linear
+#that is: field 1 has 19/20 possible assignments, field 2 has 18/20 etc.
+#by sorting it from longest to shortest we make assign the fields in a single loop
+#check which indexes are missing and skip the indexes that have their field assigned
+for FieldName in sorted(InvalidFields, key = lambda f: len(InvalidFields[f]) , reverse=True):
+ FieldIndexes = [FieldIndex for FieldIndex in range(len(requirements)) if FieldIndex not in InvalidFields[FieldName]];
+ FieldIndexes = [FieldIndex for FieldIndex in FieldIndexes if FieldIndex not in Fields]; #trim already assigned fields
+ Fields[FieldIndexes[0]] = FieldName;
+
+for key in Fields:
+ if "departure" in Fields[key]: p2 *= MyTicket[key];
+
+print("part 1 =",p1);
+print("part 2 =",p2);
+
diff --git a/2020/aoc2020-d17.py b/2020/aoc2020-d17.py
new file mode 100644
index 0000000..d26439d
--- /dev/null
+++ b/2020/aoc2020-d17.py
@@ -0,0 +1,72 @@
+#advent of code 2020
+#day 17
+#bruteforce bros win again
+#im not sure how to calculate both parts at the same time
+#since the bounds will definitely be different between 3D and 4D
+
+import itertools
+
+PocketDimension1 = set();
+PocketDimension2 = set();
+limit = 6;
+PuzzleInput = open("17.in","r");
+for y,line in enumerate(PuzzleInput):
+ for x,c in enumerate(line[:-1]):
+ if c == "#":
+ PocketDimension1.add((x,y,0));
+ PocketDimension2.add((x,y,0,0));
+PuzzleInput.close();
+
+print("3D");
+for turn in range(limit):
+ CopiedDimension1 = set();
+ bounds = [];
+ for i in range(3):
+ lo = min([p[i] for p in PocketDimension1]);
+ hi = max([p[i] for p in PocketDimension1]);
+ bounds.append([lo,hi]);
+
+ for x in range(bounds[0][0]-1, bounds[0][1]+2):
+ for y in range(bounds[1][0] -1, bounds[1][1] +2):
+ for z in range(bounds[2][0] -1, bounds[2][1] +2):
+ neighbors = 0;
+ for dx,dy,dz in itertools.product([-1,0,1],repeat=3):
+ if dx==dy==dz==0 : continue;
+ if (x+dx,y+dy,z+dz) in PocketDimension1: neighbors+=1;
+ if (x,y,z) in PocketDimension1:
+ if 2 <= neighbors <= 3: CopiedDimension1.add((x,y,z));
+ else:
+ if neighbors == 3: CopiedDimension1.add((x,y,z));
+
+ PocketDimension1 = CopiedDimension1.copy();
+ print(f'turn {turn+1}/{limit}');
+
+print("4D");
+for turn in range(limit):
+ CopiedDimension2 = set();
+ bounds = [];
+ for i in range(4):
+ lo = min([p[i] for p in PocketDimension2]);
+ hi = max([p[i] for p in PocketDimension2]);
+ bounds.append([lo,hi]);
+
+ for x in range(bounds[0][0]-1, bounds[0][1]+2):
+ for y in range(bounds[1][0] -1, bounds[1][1] +2):
+ for z in range(bounds[2][0] -1, bounds[2][1] +2):
+ for w in range(bounds[3][0] -1, bounds[3][1] +2):
+ neighbors = 0;
+ for dx,dy,dz,dw in itertools.product([-1,0,1],repeat=4):
+ if dx==dy==dz==dw==0 : continue;
+ if (x+dx,y+dy,z+dz,w+dw) in PocketDimension2: neighbors+=1;
+ if (x,y,z,w) in PocketDimension2:
+ if 2 <= neighbors <= 3: CopiedDimension2.add(( x,y,z,w));
+ else:
+ if neighbors == 3: CopiedDimension2.add((x,y,z,w));
+
+ PocketDimension2 = CopiedDimension2.copy();
+ print(f'turn {turn+1}/{limit}'); #it takes a while so im leaving this as a countdown
+
+p1 = len(PocketDimension1);
+p2 = len(PocketDimension2);
+print("part 1 =",p1);
+print("part 2 =",p2);
diff --git a/2020/aoc2020-d18.py b/2020/aoc2020-d18.py
new file mode 100644
index 0000000..8bcdbe1
--- /dev/null
+++ b/2020/aoc2020-d18.py
@@ -0,0 +1,53 @@
+#advent of code 2020
+#day 18
+#in my first or second aoc I coded a function to find nested brackets
+#that was painful and Im not doing it again
+#therefore regex
+
+import re
+
+def calcAdvanced(equation): #part 2
+ while True:
+ try:
+ lb, ub = re.search(r'(\d)+\s{1}(\+){1}(\s){1}\d+', equation).span();
+ subequation = equation[lb:ub].split(" ");
+ equation = equation[0:lb] + str(calcOperators(subequation)) + equation[ub:];
+ except:
+ break;
+ return int(eval(equation));
+
+def calcOperators(values): #part 1
+ prev = values[0];
+ for v in range(2,len(values),2):
+ prev = str(eval(prev+values[v-1]+values[v]));
+ return prev;
+
+def calcBrackets(eq,part):
+ while True:
+ try:
+ lb, ub = re.search(r'\({1}([\d]|[\s]|[*]|[+])+\){1}', eq).span();
+ if part == 1:
+ subeq = eq[lb+1:ub-1].split(" ");
+ newval = str(calcOperators(subeq));
+ else:
+ subeq = eq[lb:ub];
+ newval = str(calcAdvanced(subeq));
+ eq = eq[0:lb] + newval + eq[ub:];
+ except:
+ break;
+ if part == 1:
+ subeq = eq.split(" ");
+ return int(calcOperators(subeq));
+ else:
+ return int(calcAdvanced(eq));
+
+p1 = 0;
+p2 = 0;
+PuzzleInput = open("18.in","r");
+for line in PuzzleInput:
+ line = line[:-1];
+ p1 += calcBrackets(line,1);
+ p2 += calcBrackets(line,2);
+PuzzleInput.close();
+print("part 1 =",p1);
+print("part 2 =",p2);
diff --git a/2020/aoc2020-d19.py b/2020/aoc2020-d19.py
new file mode 100644
index 0000000..fb4497d
--- /dev/null
+++ b/2020/aoc2020-d19.py
@@ -0,0 +1,58 @@
+#advent of code 2020
+#day 19
+import re
+
+def FindRule(r,d):
+ if d >20: return "";
+ elif type(rules[r]) == str:
+ return rules[r];
+ else:
+ suboptions = [];
+ for subset in rules[r]:
+ subopt = "(";
+ for sr in subset:
+ subopt += FindRule(sr,d+1);
+ subopt += ")";
+ suboptions.append(subopt);
+ return "(" + "|".join(suboptions) + ")";
+
+rules = dict();
+PuzzleInput = open("19.in","r").read().split("\n\n");
+rules_raw = PuzzleInput[0].split("\n");
+messages = PuzzleInput[1].split("\n");
+for rule in rules_raw:
+ rule_i, rule_vals = rule.split(": ");
+ rule_i = int(rule_i);
+ if rule_vals[0] == '"':
+ rules[rule_i] = rule_vals[1];
+ else:
+ rules[rule_i] = [[int(r) for r in subrule.split(" ")] for subrule in rule_vals.split(" | ")];
+
+TotalRule = "";
+TotalRule = FindRule(0,0);
+regsearch = re.compile(TotalRule);
+
+p1 = 0;
+for message in messages:
+ message = message.replace("\n","");
+ regfind = regsearch.fullmatch(message);
+ if regfind != None:
+ p1+=1;
+
+print("part 1 =",p1);
+#part 2: change of rules 8 and 11
+rules[8] = [[42], [42, 8]];
+rules[11] = [[42,31], [42,11,31]];
+TotalRule = "";
+TotalRule = FindRule(0,0);
+p2 = 0;
+for countdown,message in enumerate(messages):
+ #print(len(messages) - countdown, len(messages));
+ message = message.replace("\n","");
+ regfind = re.findall(TotalRule+"+",message);
+ if regfind:
+ for x in regfind:
+ if message in x:
+ p2+=1;
+ break;
+print("part 2 =",p2);
diff --git a/2020/aoc2020-d20.py b/2020/aoc2020-d20.py
new file mode 100644
index 0000000..0a2c870
--- /dev/null
+++ b/2020/aoc2020-d20.py
@@ -0,0 +1,363 @@
+#advent of code 2020
+#day 20
+#I struggled a lot but somehow managed to finish without any help
+#love the idea, seems extremely easy at first but gets progressively more complex
+#in summary:
+#for each tile, for each side of the tile, find the fitting tile
+#the corners will have 2 neighbours, the tiles at edges will have 3 neighbours
+#assign coordinates to corners and edges
+#with the outer tiles assigned, we can assign the inner tiles
+#after that, check how is each tile setup now and in which direction the sides should be facing
+#adjust accordingly
+#assumptions:
+# whole image is a square
+# the monster can appear in any orientation (which seems false, at least for my input)
+# there is exactly one match for each side of a tile
+#code could use some cleanup so I'll revisit this in the future
+#right now I'm happy I trimmed it down to 1/3 of what it was when solved
+import math
+
+def DirectionalRotating(tileID,rotdir):
+ if rotdir > 0: #counterclockwise i think
+ return [ [ tiles[tileID][r][c] for r in range(len(tiles[tileID][c])) ] for c in range(len(tiles[tileID])-1,-1,-1) ];
+ else: #clockwise i hope
+ return [ [ tiles[tileID][r][c] for r in range(len(tiles[tileID][c])-1,-1,-1) ] for c in range(len(tiles[tileID])) ];
+
+def rotating(tileID):
+ return [ [ tiles[tileID][r][c] for r in range(len(tiles[tileID][c])-1,-1,-1) ] for c in range(len(tiles[tileID])) ];
+
+def flipping(tileID,side):
+ if side == 0: #left to right (probably)
+ return [ [ tiles[tileID][c][r] for r in range(len(tiles[tileID][c])-1,-1,-1) ] for c in range(len(tiles[tileID])) ];
+ else: #up to down (i think)
+ return [ [ tiles[tileID][c][r] for r in range(len(tiles[tileID][c])) ] for c in range(len(tiles[tileID])-1,-1,-1) ];
+
+#this function was my first attempt at solving this and somehow it's vital
+#which probably means that my solution is borderline hardcoded
+def InitialMatching(MatchTile, MatchTileEdge, RevTile, RevTileEdge):
+ fuck = dict();
+ fuck[0] = 2;
+ fuck[1] = 3;
+ fuck[2] = 0;
+ fuck[3] = 1;
+ matchUP = [tiles[MatchTile][0][c] for c in range(0,size)];
+ matchDOWN = [tiles[MatchTile][size-1][c] for c in range(0,size)];
+ matchLEFT = [tiles[MatchTile][c][0] for c in range(0,size)];
+ matchRIGHT = [tiles[MatchTile][c][size-1] for c in range(0,size)];
+ matchEdges = [matchUP,matchRIGHT,matchDOWN,matchLEFT];
+ steps = 0;
+ while (RevTileEdge+steps)%4 != fuck[MatchTileEdge]:
+ tiles[RevTile] = rotating(RevTile);
+ steps += 1;
+ revUP = [tiles[RevTile][0][c] for c in range(0,size)];
+ revDOWN = [tiles[RevTile][size-1][c] for c in range(0,size)];
+ revLEFT = [tiles[RevTile][c][0] for c in range(0,size)];
+ revRIGHT = [tiles[RevTile][c][size-1] for c in range(0,size)];
+ revEdges = [revUP,revRIGHT,revDOWN,revLEFT];
+ if matchEdges[MatchTileEdge] != revEdges[(MatchTileEdge+2)%4]:
+ tiles[RevTile] = flipping(RevTile,MatchTileEdge%2);
+
+#find pattern PattList inside the image img
+def FindPattern(img,PattList):
+ MatchingPixels = set();
+ amount = sum([imline.count("#") for imline in PattList]);
+ for iy in range(len(img) - len(PattList) ):
+ for ix in range(len(img[iy]) - len(PattList[0]) ):
+ IsValid = True;
+ subset = set();
+ for ply,pll in enumerate(PattList):
+ for plx, plc in enumerate(pll):
+ if plc == " ": continue;
+ IsValid = plc == img[iy+ply][ix+plx] == "#";
+ if IsValid:
+ subset.add((iy+ply,ix+plx))
+ else:
+ break;
+ if not IsValid: break;
+ if amount == len(subset): MatchingPixels.update(subset);
+ return MatchingPixels;
+
+#create all flipped and rotated version of pattern, return them in a list
+def MonsterFlip(patt):
+ Monsters = [];
+ for rotation in range(4):
+ Monsters.append(patt);
+ #flip
+ patt = [ [patt[c][r] for r in range(len(patt[c])-1,-1,-1)] for c in range(len(patt)) ];
+ Monsters.append(patt);
+ #rotate
+ if rotation%2 == 0: #flips must alternate between horizontal and vertical
+ patt = [ [patt[r][c] for r in range(len(patt)-1,-1,-1)] for c in range(len(patt[0])) ];
+ else:
+ patt = [ [patt[r][c] for r in range(len(patt))] for c in range(len(patt[0])-1,-1,-1) ];
+ return Monsters;
+
+tiles = dict();
+size = 0;
+PuzzleInput = open("20.in","r").read();
+for pi in PuzzleInput.split("\n\n"):
+ lines = pi.split("\n");
+ value = int(lines[0][5:9]);
+ tiles[value] = [];
+ for y,line in enumerate(lines[1:]):
+ if len(line) == 0: continue;
+ tiles[value].append(list(line));
+ size = len(line);
+# ^ 0
+# > 1
+# v 2
+# < 3
+directions = [(0,size,1), (size-1,-1,-1)];
+options = dict();
+
+for tile1 in tiles:
+ options[tile1] = [];
+ UP1 = [tiles[tile1][0][c] for c in range(0,size)];
+ DOWN1 = [tiles[tile1][size-1][c] for c in range(0,size)];
+ LEFT1 = [tiles[tile1][c][0] for c in range(0,size)];
+ RIGHT1 = [tiles[tile1][c][size-1] for c in range(0,size)];
+ edges1 = [UP1,RIGHT1,DOWN1,LEFT1];
+ for tile2 in tiles:
+ if tile1==tile2: continue;
+ UP2 = [tiles[tile2][0][c] for c in range(0,size)];
+ DOWN2 = [tiles[tile2][size-1][c] for c in range(0,size)];
+ LEFT2 = [tiles[tile2][c][0] for c in range(0,size)];
+ RIGHT2 = [tiles[tile2][c][size-1] for c in range(0,size)];
+ edges2 = [UP2,RIGHT2,DOWN2,LEFT2];
+ for i2 in range(len(edges2)):
+ for i1 in range(len(edges1)):
+ if edges1[i1] == edges2[i2] or edges1[i1] == [edges2[i2][rev] for rev in range(size-1,-1,-1)]:
+ InitialMatching(tile1,i1,tile2,i2);
+ options[tile1].append(tile2);
+
+part1 = 1;
+corners = [];
+Imgedges = [];
+for ot in options:
+ if len(options[ot]) == 2: corners.append(ot);
+ if len(options[ot]) == 3: Imgedges.append(ot);
+for tid in corners:
+ part1 *= tid;
+print("part 1 =",part1);
+############################################################################################################################
+TotalTiles = len(tiles);
+WholeImageSize = int(math.sqrt(TotalTiles));
+coordinates = dict();
+queue = [corners[0]];
+coordinates[corners[0]] = (0,0)
+fitted = set();
+imgdirs = dict();
+imgdirs[0] = (1,0);
+imgdirs[1] = (0,1);
+imgdirs[2] = (-1,0);
+imgdirs[3] = (0,-1);
+#assigning the tiles to coordinates based on neighbours
+#first 3 corners and 2 edges
+SeparateQueue = [];
+coordinates[options[corners[0]][0]] = (0,1);
+coordinates[options[corners[0]][1]] = (1,0);
+queue = [];
+queue.extend(options[corners[0]]);
+while queue:
+ #print(len(queue));
+ t = queue.pop();
+ if t in fitted: continue;
+ ty,tx = coordinates[t];
+ for fit in options[t]:
+ if fit in coordinates: continue;
+ if fit in Imgedges :
+ queue.append(fit);
+ dx = 0 + 1*(ty==0);
+ dy = 0 + 1*(tx==0);
+ coordinates[fit] = (ty+dy,tx+dx);
+ elif fit in corners:
+ dx = 0 + 1*(ty==0);
+ dy = 0 + 1*(tx==0);
+ coordinates[fit] = (ty+dy,tx+dx);
+ else:
+ SeparateQueue.append(fit);
+
+#last corner and 2 edges
+queue = [];
+for cor in corners[1:]:
+ if cor in coordinates:
+ WasFitted = [wf for wf in options[cor] if wf in coordinates][0];
+ NotFitted = [wf for wf in options[cor] if wf not in coordinates][0];
+ cory,corx = coordinates[cor];
+ nfx = 0 + corx*(corx==WholeImageSize-1) + 1*(corx!=WholeImageSize-1) ;
+ nfy = 0 + cory*(cory==WholeImageSize-1) + 1*(cory!=WholeImageSize-1) ;
+ coordinates[NotFitted] = (nfy,nfx);
+ queue.append(NotFitted);
+
+while queue:
+ t = queue.pop();
+ if t in fitted: continue;
+ ty,tx = coordinates[t];
+ for fit in options[t]:
+ if fit in coordinates: continue;
+ dx = 0 + 1*(ty==WholeImageSize-1);
+ dy = 0 + 1*(tx==WholeImageSize-1);
+ if fit in Imgedges :
+ queue.append(fit);
+ coordinates[fit] = (ty+dy,tx+dx);
+ elif fit in corners:
+ coordinates[fit] = (ty+dy,tx+dx);
+ else:
+ SeparateQueue.append(fit);
+
+#filling in the rest
+while len(coordinates) != len(tiles):
+ NewQueue = [til for til in tiles if til not in coordinates];
+ for item in reversed(NewQueue):
+ NotMatched = [nm for nm in options[item] if nm not in coordinates];
+ Matched = [nm for nm in options[item] if nm in coordinates];
+ CordsOfMatched = [coordinates[com] for com in Matched];
+ if len(Matched) == 2:
+ p0 = CordsOfMatched[0];
+ p1 = CordsOfMatched[1];
+ dpy = p0[0]-p1[0];
+ dpx = p0[1]-p1[1];
+ if dpy > 1 or dpy < -1: continue;
+ if dpx > 1 or dpx < -1: continue;
+ if dpy*dpx < 0:
+ o1 = (min(p0[0],p1[0]) , min(p0[1],p1[1]));
+ o2 = (max(p0[0],p1[0]) , max(p0[1],p1[1]));
+ else:
+ o1 = (max(p0[0],p1[0]) , min(p0[1],p1[1]));
+ o2 = (min(p0[0],p1[0]) , max(p0[1],p1[1]));
+ #check if the possible points are within image boundaries, same check for elifs below
+ v1 = o1[0] in range(0,WholeImageSize) and o1[1] in range(0,WholeImageSize);
+ v2 = o2[0] in range(0,WholeImageSize) and o2[1] in range(0,WholeImageSize);
+ if not v1 and not v2:
+ continue;
+ elif o1 in coordinates.values() and v2 and o2 not in coordinates.values():
+ coordinates[item] = o2;
+ elif o2 in coordinates.values() and v1 and o1 not in coordinates.values():
+ coordinates[item] = o1;
+ elif len(Matched) == 3:
+ comYs = set( [com[0] for com in CordsOfMatched] );
+ comXs = set( [com[1] for com in CordsOfMatched] );
+ if len(comYs) > len(comXs):
+ oy = min(comYs)+1;
+ ox = [xxx[1] for xxx in CordsOfMatched if xxx[0] != oy ][0];
+ else:
+ ox = min(comXs)+1;
+ oy = [xxx[0] for xxx in CordsOfMatched if xxx[1] != ox ][0];
+ o1 = (oy,ox);
+ v1 = o1[0] in range(0,WholeImageSize) and o1[1] in range(0,WholeImageSize);
+ if o1 not in coordinates.values() and v1:
+ coordinates[item] = o1;
+ elif len(Matched) == 4:
+ comYs = set( [com[0] for com in CordsOfMatched] );
+ comXs = set( [com[1] for com in CordsOfMatched] );
+ oy = min(comYs)+1;
+ ox = min(comXs)+1;
+ o1 = (oy,ox);
+ v1 = o1[0] in range(0,WholeImageSize) and o1[1] in range(0,WholeImageSize);
+ if o1 not in coordinates.values() and v1:
+ coordinates[item] = o1;
+
+InversedCoords = dict();
+for cord in coordinates:
+ InversedCoords[coordinates[cord]] = cord;
+
+YrangeLow = min([ICpoint[0] for ICpoint in InversedCoords]);
+YrangeHigh = max([ICpoint[0] for ICpoint in InversedCoords]);
+
+for tile1 in tiles:
+ options[tile1] = [];
+ UP1 = [tiles[tile1][0][c] for c in range(0,size)];
+ DOWN1 = [tiles[tile1][size-1][c] for c in range(0,size)];
+ LEFT1 = [tiles[tile1][c][0] for c in range(0,size)];
+ RIGHT1 = [tiles[tile1][c][size-1] for c in range(0,size)];
+ edges1 = [UP1,RIGHT1,DOWN1,LEFT1];
+ for tile2 in tiles:
+ if tile1==tile2: continue;
+ UP2 = [tiles[tile2][0][c] for c in range(0,size)];
+ DOWN2 = [tiles[tile2][size-1][c] for c in range(0,size)];
+ LEFT2 = [tiles[tile2][c][0] for c in range(0,size)];
+ RIGHT2 = [tiles[tile2][c][size-1] for c in range(0,size)];
+ edges2 = [UP2,RIGHT2,DOWN2,LEFT2];
+ for i2 in range(len(edges2)):
+ for i1 in range(len(edges1)):
+ if edges1[i1] == edges2[i2] or edges1[i1] == [edges2[i2][rev] for rev in range(size-1,-1,-1)]:
+ InitialMatching(tile1,i1,tile2,i2);
+ options[tile1].append(tile2);
+
+RequiredSides = dict();
+for y in range(1+max([Ymax[0] for Ymax in InversedCoords])):
+ for x in range(1+max([Xmax[1] for Xmax in InversedCoords])):
+ tile1 = InversedCoords[(y,x)]
+ RequiredSides[tile1] = dict();
+ UP1 = [tiles[tile1][0][c] for c in range(0,size)];
+ DOWN1 = [tiles[tile1][size-1][c] for c in range(0,size)];
+ LEFT1 = [tiles[tile1][c][0] for c in range(0,size)];
+ RIGHT1 = [tiles[tile1][c][size-1] for c in range(0,size)];
+ edges1 = [UP1,RIGHT1,DOWN1,LEFT1];
+ for di,dd in enumerate([(-1,0),(0,1),(1,0),(0,-1)]):
+ dy,dx = dd;
+ if (y+dy,x+dx) not in InversedCoords: continue;
+ tile2 = InversedCoords[ (y+dy,x+dx) ];
+ UP2 = [tiles[tile2][0][c] for c in range(0,size)];
+ DOWN2 = [tiles[tile2][size-1][c] for c in range(0,size)];
+ LEFT2 = [tiles[tile2][c][0] for c in range(0,size)];
+ RIGHT2 = [tiles[tile2][c][size-1] for c in range(0,size)];
+ edges2 = [UP2,RIGHT2,DOWN2,LEFT2];
+ for i1 in range(len(edges1)):
+ if edges1[i1] in edges2 or [edges1[i1][rev] for rev in range(size-1,-1,-1)] in edges2:
+ RequiredSides[tile1][i1] = di;
+ break;
+ CorrectlyFacing = [face for face in RequiredSides[tile1] if RequiredSides[tile1][face] == face ];
+ IncorrectFacing = [face for face in RequiredSides[tile1] if face not in CorrectlyFacing ];
+ sidetest = [(4-(RequiredSides[tile1][xddd] - xddd))%4 for xddd in RequiredSides[tile1]];
+ if sidetest.count(sidetest[0]) == len(sidetest):
+ if sidetest[0] == 1:
+ for rotato in range(sidetest[0]):
+ tiles[tile1] = DirectionalRotating(tile1, IncorrectFacing[0] - RequiredSides[tile1][IncorrectFacing[0]] );
+ else:
+ for rotato in range(sidetest[0] ):
+ tiles[tile1] = DirectionalRotating(tile1, RequiredSides[tile1][min(IncorrectFacing)] - min(IncorrectFacing) );
+ elif sidetest.count(0) + sidetest.count(2) == len(sidetest):
+ WhichToFlip = set([xddd%2 for xddd in RequiredSides[tile1] if (4-(RequiredSides[tile1][xddd] - xddd))%4 == 2]);
+ for wtflip in WhichToFlip:
+ tiles[tile1] = flipping(tile1,(wtflip+1)%2);
+ elif sidetest.count(1) + sidetest.count(3) == len(sidetest):
+ tiles[tile1] = flipping(tile1,1);
+ tiles[tile1] = DirectionalRotating(tile1, min(IncorrectFacing) - RequiredSides[tile1][min(IncorrectFacing)] );
+
+image = [];
+for y in range(1+max([Ymax[0] for Ymax in InversedCoords])):
+ ImageLine = [ [] for s in range(1,size-1)];
+ for x in range(1+max([Xmax[1] for Xmax in InversedCoords])):
+ for tileY, _ in enumerate(tiles[InversedCoords[(y,x)]]):
+ if tileY >= size-2: continue;
+ ImageLine[tileY] += tiles[InversedCoords[(y,x)]][tileY+1][1:-1] ;
+ image += ImageLine;
+
+#from puzzle description
+monster = ''' #
+# ## ## ###
+ # # # # # # '''
+#turn monster into list
+pattern = [];
+for m in monster.split("\n"):
+ pattern.append(list(m));
+
+#######
+hashes = sum([imline.count("#") for imline in image]); # all hashes in the image
+PartOfMonster = set();
+#iterate over alle combinations of monster pattern, count the matching tiles
+for monflip in MonsterFlip(pattern):
+ PartOfMonster.update(FindPattern(image,monflip));
+
+part2 = hashes - len(PartOfMonster); #water roughness
+print("part 2 =",part2);
+
+#print all monsters
+#for imy,imline in enumerate(image):
+# for imx, imchar in enumerate(imline):
+# if (imy,imx) in PartOfMonster:
+# print("O",end="")
+# else:
+# print(imchar,end="")
+# print();
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-29 11:51:09 +0000