Day 8 2025

3 files changed, 66 insertions, 2 deletions

diff --git a/2025/08/a.py b/2025/08/a.py
index 5fdb11b..1980414 100644
--- 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
new file mode 100644
index 0000000..4a6d610
--- /dev/null
+++ 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
index 4ca1d2e..19fbb29 100644
--- 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).