#advent of code 2024
#day 12
#we needed area of the plot and its perimiter
#we floodfill given plot and store the coordinates of the plants
#then, on the borders, we register the coordinates of the plants
#that are adjacent to our plot and the direction from which it was
#registered during floodfill. the length of this set (perim) is the perimiter
#then, for part 2, we group the points in perim set by their direction
#(3rd parameter), then we sort each group based on the coordinate
#that is changing, that is: if the fence was registered from the north,
#then it is part of the north-facing fence, so we sort it by the x-axis
#identical for southern and similar for east/west (y-axis)
#iterate over every fence point, if the gap is greater 1 then increment
#the amount of sides. I probably should make a drawing because 
#I'll forget what it does in the future despite writing this comment
grid = {};
f = open("12.in","r");
for y,l in enumerate(f):
	for x,c in enumerate(l.strip()):
		grid[(x,y)]=c;
f.close();

dirs = [(1,0),(0,1),(-1,0),(0,-1)];
visited = set();

def getAdjacent(pos,l):
	adj = [];
	vis = set();
	xp, yp = pos;
	for di,d in enumerate(dirs):
		dx,dy = d;
		if grid.get((xp+dx,yp+dy),".") == l:
			adj.append((xp+dx,yp+dy));
		else:
			vis.add((xp+dx,yp+dy,di));
	return adj, vis;

def sides(perimiter):
	SidesTotal = 0;
	NumberOfSides = {};
	PerimsGrouped = {};
	for di in range(4):
		NumberOfSides[di] = 0;
		PerimsGrouped[di] = [m for m in perimiter if m[2]==di];
		PerimsGrouped[di] = sorted(PerimsGrouped[di], key=lambda m: (m[di%2],m[(di+1)%2]));
		if len(PerimsGrouped[di]) == 0: 
			continue;
		else:
			NumberOfSides[di] += 1;
		prevx,prevy,prevd = PerimsGrouped[di][0];
		for PerPos in PerimsGrouped[di][1:]:
			x,y,d = PerPos;
			if not(abs(x-prevx)==di%2 and abs(y-prevy) ==(di+1)%2): 
				NumberOfSides[di] += 1;
			prevx,prevy,prevd = x,y,d;
		SidesTotal += NumberOfSides[di];
	return SidesTotal;

def fill(startpos, letter):
	queue = [startpos];
	perim = set(); #add points that aren't part of the area but are adjacent
	v = set(); #visited points, that is: the area
	while queue:
		px,py = queue.pop();
		if (px,py) in v: continue;
		visited.add((px,py));
		v.add((px,py));
		NextValid, NextBorders = getAdjacent((px,py),letter);
		queue.extend(NextValid);
		perim = perim.union(NextBorders);
	return len(v), len(perim), sides(perim);

part1 = 0;
part2 = 0;
for g in grid:
	if g in visited:continue;
	L = grid[g];
	LandArea, LandPerim, LandSides = fill(g,L);
	part1 += LandArea*LandPerim;
	part2 += LandArea*LandSides;

print("part 1 =", part1);
print("part 2 =", part2);