summer warmup sesh part 2

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();