From 12f551dbfef138880b29ba6abe4576714ae942cb Mon Sep 17 00:00:00 2001 From: blenovo Date: Sat, 2 Aug 2025 03:13:50 +0200 Subject: summer warmup sesh part 2 --- 2020/aoc2020-d11.py | 62 +++++++++ 2020/aoc2020-d12.py | 93 ++++++++++++++ 2020/aoc2020-d13.py | 46 +++++++ 2020/aoc2020-d14.py | 72 +++++++++++ 2020/aoc2020-d15.py | 35 +++++ 2020/aoc2020-d16.py | 71 ++++++++++ 2020/aoc2020-d17.py | 72 +++++++++++ 2020/aoc2020-d18.py | 53 ++++++++ 2020/aoc2020-d19.py | 58 +++++++++ 2020/aoc2020-d20.py | 363 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 10 files changed, 925 insertions(+) create mode 100644 2020/aoc2020-d11.py create mode 100644 2020/aoc2020-d12.py create mode 100644 2020/aoc2020-d13.py create mode 100644 2020/aoc2020-d14.py create mode 100644 2020/aoc2020-d15.py create mode 100644 2020/aoc2020-d16.py create mode 100644 2020/aoc2020-d17.py create mode 100644 2020/aoc2020-d18.py create mode 100644 2020/aoc2020-d19.py create mode 100644 2020/aoc2020-d20.py (limited to '2020') 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(); -- cgit v1.2.3