summaryrefslogtreecommitdiff
path: root/2020/aoc2020-d20.py
diff options
context:
space:
mode:
Diffstat (limited to '2020/aoc2020-d20.py')
-rw-r--r--2020/aoc2020-d20.py363
1 files changed, 363 insertions, 0 deletions
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 09:58:44 +0000