path: root/2020/aoc2020-d20.py

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