1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
#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);
|
