Mathemann

1 files changed, 18 insertions, 13 deletions

diff --git a/2023/08/solve.py b/2023/08/solve.py
index 61742f4..957cee1 100644
--- a/2023/08/solve.py
+++ b/2023/08/solve.py
@@ -6,29 +6,34 @@ nodes = dict(
 )
 
 
-def part1():
+def part1(start):
     steps = 0
-    curr = "AAA"
+    curr = start
     while True:
         d = path[steps % len(path)]
         curr = nodes[curr][0 if d == "L" else 1]
         steps += 1
-        if curr == "ZZZ":
+        if curr[2] == "Z":
             return steps
 
 
+def lcm(steps):
+    bi_gcd = lambda m, n: m if not n else bi_gcd(n, m % n)
+    res = steps[0]
+    for s in steps[1:]:
+        res = s * (res // bi_gcd(res, s))
+    return res
+
+
 def part2():
-    steps = 0
+    steps = []
     curr = [k for k in nodes.keys() if k[2] == "A"]
-    para = len(curr)
-    while True:
-        d = path[steps % len(path)]
-        for i in range(para):
-            curr[i] = nodes[curr[i]][0 if d == "L" else 1]
-        steps += 1
-        if len([k for k in curr if k[2] == "Z"]) == para:
-            return steps
+    for s in curr:
+        steps.append(part1(s))
+
+    # modulo ring yay
+    return lcm(steps)
 
 
-# print(part1())
+print(part1("AAA"))
 print(part2())