commit 5d69f923116a2b251a445c0cb9e6f23551ad686a
parent 01c2cd358b3f693181fa86e82414b3e32f9a890e
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 8 Dec 2025 07:29:26 +0100
Day 8 2025
Diffstat:
4 files changed, 67 insertions(+), 3 deletions(-)
diff --git a/2025/08/a.py b/2025/08/a.py
@@ -1,6 +1,32 @@
import fileinput
+N = 1000 # Change to 10 for test case
+
with fileinput.input() as lines:
- for line in lines:
- ...
+ pts = [tuple(int(x) for x in line[:-1].split(',')) for line in lines]
+
+r = range(len(pts))
+
+def dist(p, q):
+ return (p[0]-q[0])**2 + (p[1]-q[1])**2 + (p[2]-q[2])**2
+
+d = sorted([(dist(pts[i], pts[j]), i, j) for i in r for j in r if j > i])
+
+rep = [i for i in r]
+
+def findrep(i):
+ return i if rep[i] == i else findrep(rep[i])
+
+def joinrep(i, j):
+ rep[findrep(i)] = findrep(j)
+
+for i in range(N):
+ j, k = d[i][1], d[i][2]
+ if findrep(j) != findrep(k):
+ joinrep(j, k)
+sizes = [[0, i] for i in r]
+for i in r:
+ sizes[findrep(i)][0] += 1
+sizes.sort()
+print(sizes[-1][0] * sizes[-2][0] * sizes[-3][0])
diff --git a/2025/08/b.py b/2025/08/b.py
@@ -0,0 +1,26 @@
+import fileinput
+
+with fileinput.input() as lines:
+ pts = [tuple(int(x) for x in line[:-1].split(',')) for line in lines]
+
+r = range(len(pts))
+
+def dist(p, q):
+ return (p[0]-q[0])**2 + (p[1]-q[1])**2 + (p[2]-q[2])**2
+
+d = sorted([(dist(pts[i], pts[j]), i, j) for i in r for j in r if j > i])
+
+rep = [i for i in r]
+
+def findrep(i):
+ return i if rep[i] == i else findrep(rep[i])
+
+def joinrep(i, j):
+ rep[findrep(i)] = findrep(j)
+
+for _, j, k in d:
+ if findrep(j) != findrep(k):
+ joinrep(j, k)
+ sol = pts[j][0] * pts[k][0]
+
+print(sol)
diff --git a/2025/README.md b/2025/README.md
@@ -11,6 +11,7 @@ Example
```
Day -Part 1- -Part 2-
+ 8 00:29:14 00:33:02
7 00:05:27 00:20:40
6 00:13:38 01:49:24
5 00:04:39 00:22:19
@@ -100,3 +101,14 @@ end there from the previous row (that can be one or two tachyons).
I added a second solution for part 2 that does not use a map, but only
lists. This could be seen as a dynamic programming problem where the
iterative implementation is more intuitive than the recursive one.
+
+### Day 8: Playground
+
+This one required some optimization effort for part 2... unless one is
+already familiar with [the algorithm
+described](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm)
+in the problem statement, and I was from back in the days of competitive
+programming. In the end it was mostly a matter of figuring out the correct
+[data structure to represent the groups of joint
+boxes](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) (or
+a matter of remembering how it is implemented, if one already knows it).
diff --git a/README.md b/README.md
@@ -14,4 +14,4 @@ See `year/README.md` for instructions on how to run my code.
|2022| 50 | Rust | Done in 2025 to learn Rust |
|2023| 50 | C | All solved by December 25, 2023 |
|2024| 50 | C++ | Each solved within 24h |
-|2025| 14 | Python | Work in progress... |
+|2025| 16 | Python | Work in progress... |
