aoc

commit f082999a23e7a09caea480f2f88dd0710c02745b (patch)
parent 5e0ba25451e791762a9be69aceb8f9f5b3f2d690
Author: Alex Karle <alex@alexkarle.com>
Date:   Wed, 11 Dec 2024 14:44:29 +0100

2024: Add Day 11

Love me a good "but does it scale" problem :)

Diffstat:
A
2024/11/naive.py
 | 
35
+++++++++++++++++++++++++++++++++++
A
2024/11/optim.py
 | 
45
+++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 80 insertions(+), 0 deletions(-)
diff --git a/2024/11/naive.py b/2024/11/naive.py
@@ -0,0 +1,35 @@
+#!/usr/bin/env python3
+import sys
+import os
+
+def parse():
+    return [int(i) for i in next(sys.stdin).split()]
+
+def debug(msg):
+    if os.getenv("DEBUG"):
+        print(msg)
+
+def cycle(stones):
+    news = []
+    for s in stones:
+        if s == 0:
+            news.append(1)
+        else:
+            ss = str(s)
+            mid = len(ss) // 2
+            l, r = ss[0:mid], ss[mid:]
+            if len(l) == len(r):
+                news.append(int(l))
+                news.append(int(r))
+            else:
+                news.append(s * 2024)
+    return news
+
+if __name__ == '__main__':
+    stones = parse()
+    debug(stones)
+    for i in range(int(os.getenv("N", 25))):
+        print(i, len(stones))
+        stones = cycle(stones)
+        debug(stones)
+    print(len(stones))
diff --git a/2024/11/optim.py b/2024/11/optim.py
@@ -0,0 +1,45 @@
+#!/usr/bin/env python3
+import sys
+import os
+
+def parse():
+    return [int(i) for i in next(sys.stdin).split()]
+
+def debug(msg):
+    if os.getenv("DEBUG"):
+        print(msg)
+
+# f(x, n) = count of nodes after iterating n steps
+#
+# f(x, n) is either
+#   f(1, n-1)              if x == 0
+#   f(y, n-1)  + f(z, n-1) if x even dig
+#   f(2024*x, n-1)         otherwise
+#
+# We can memoize the output, since eventually it will cycle!
+cache = {}
+def count(stone, n):
+    if n == 0:
+        return 1
+    if (stone, n) in cache:
+        return cache[(stone, n)]
+    if stone == 0:
+        c = count(1, n - 1)
+    else:
+        ss = str(stone)
+        mid = len(ss) // 2
+        l, r = ss[0:mid], ss[mid:]
+        if len(l) == len(r):
+            c = count(int(l), n-1) + count(int(r), n-1)
+        else:
+            c = count(stone * 2024, n-1)
+    cache[(stone, n)] = c
+    return c
+
+if __name__ == '__main__':
+    stones = parse()
+    tot = 0
+    n = int(os.getenv("N", 25))
+    for s in stones:
+        tot += count(s, n)
+    print(tot)