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
84
85
86
87
88
89
90
91
92
|
#advent of code 2025
#day 09
#bit slow
#tried adding comments but will probably forget how it works anyway
tiles=[];
Ymax=0;
Xmax=0;
Ymin=10000000;
Xmin=10000000;
PuzzleInput=open("09.in","r");
for l in PuzzleInput:
t=tuple([int(v) for v in l.split(",")]);
tiles.append(t);
Xmax=max(Xmax,t[0]);
Ymax=max(Ymax,t[1]);
Xmin=min(Xmin,t[0]);
Ymin=min(Ymin,t[1]);
PuzzleInput.close();
part1=0;
green=set();
for ci1,corner1 in enumerate(tiles):
x1,y1=corner1;
for ci2,corner2 in enumerate(tiles):
if ci1==ci2: continue;
x2,y2=corner2;
area=(abs(x1-x2)+1)*(abs(y1-y2)+1);
part1=max(part1,area);
part2=0;
#create the perimiter of the figure ("green" set)
#check how big is a distance between each tile
#tiles are ordered
delta=[(1,0),(0,1)]
distancedTiles=[];
test=0;
maxdist=0;
for t in range(len(tiles)):
tile1=tiles[t];
tile2=tiles[(t+1)%len(tiles)];
for i in range(2):
if tile1[i]==tile2[i]: continue;
dx,dy=delta[i];
steps=tile2[i]-tile1[i];
dd=1*(steps>0) -1*(steps<0);
for step in range(abs(steps)):
green.add((tile1[0]+dx*dd*step,tile1[1]+dy*dd*step));
distancedTiles.append((abs(steps),tile1,tile2,i));
maxdist=max(maxdist,abs(steps));
#sort the distances from longest to shortest
distancedTiles=sorted(distancedTiles,key=lambda m: m[0],reverse=True);
#check if the candidate "dt" isn't an order of 10 lower compared to biggest distance
#the biggest area has to be along the longest edge
candidates=[dt for dt in distancedTiles if maxdist//dt[0]<10];
for can_i in range(len(candidates)):
candidate=candidates[can_i];
d,can1,can2,can_orient=candidate;
orient_1=candidates[(can_i)%len(candidates)][1][(can_orient+1)%2];
orient_2=candidates[(can_i+1)%len(candidates)][1][(can_orient+1)%2];
if orient_1 > orient_2:
lim_1=orient_1;
lim_2=Ymax+1;
else:
lim_1=0;
lim_2=orient_1+1;
can=sorted([can1,can2],key=lambda m:m[0])[1]
otherCandidates=[ocand for ocand in tiles if ocand[(can_orient+1)%2] in range(lim_1,lim_2)];
for ocand in otherCandidates:
#check if the X edge isn't in the way of perimiter (the longest edge doesn't count)
checkX=True;
for s in range(1+min(ocand[0],can[0]),max(ocand[0],can[0]) -1):
if can[0]==s: continue;
if (s,ocand[1]) in green:
checkX=False;
break;
if not checkX: continue;
#check if the Y edge isn't in the way of perimiter
checkY=True;
for s in range(1+min(ocand[1],can[1]),max(ocand[1],can[1]) -1):
if (can[0],s) in green:
checkY=False;
break;
if not checkY: continue;
area2=(abs(can[0]-ocand[0])+1)*(abs(can[1]-ocand[1])+1);
part2=max(part2,area2);
print("part 1 =",part1);
print("part 2 =",part2);
|
