aoc

commit 3d1d1df937b997715071049f4597afcaf5067a1e (patch)
parent 7bf24fbbdb625de98ac2ff4dc5fd068b8f732d71
Author: Alex Karle <alex@alexkarle.com>
Date:   Sat, 14 Dec 2024 03:20:53 +0100

2024: Add day 13

Fun revisiting linear equations :)

Diffstat:
A
2024/13/1.py
 | 
51
+++++++++++++++++++++++++++++++++++++++++++++++++++
A
2024/13/2.py
 | 
61
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 112 insertions(+), 0 deletions(-)
diff --git a/2024/13/1.py b/2024/13/1.py
@@ -0,0 +1,51 @@
+#!/usr/bin/env python3
+import sys
+import re
+
+buta_re = re.compile("Button A: X\+(\d+), Y\+(\d+)")
+butb_re = re.compile("Button B: X\+(\d+), Y\+(\d+)")
+priz_re = re.compile("Prize: X=(\d+), Y=(\d+)")
+
+def parse():
+    games = []
+    game = {}
+    for l in sys.stdin:
+        am = buta_re.match(l)
+        bm = butb_re.match(l)
+        pm = priz_re.match(l)
+        if am:
+            game["A"] = [int(x) for x in am.groups(1)]
+        elif bm:
+            game["B"] = [int(x) for x in bm.groups(1)]
+        elif pm:
+            game["P"] = [int(x) for x in pm.groups(1)]
+        else:
+            games.append(game)
+            game = {}
+    if game:
+        games.append(game)
+    return games
+
+# Its a linear equation, so they should interesect exactly
+# once, not at all, or continuously (same line).
+# Searching the entire b space first (inner loop) gives
+# us the cheapest if they're the same line
+#
+# For pt 1, we just brute force it rather than solve it
+def solve(game):
+    for a in range(101):
+        for b in range(101):
+            if a * game['A'][0] + b * game['B'][0] == game['P'][0]:
+                if a * game['A'][1] + b * game['B'][1] == game['P'][1]:
+                    return (a, b)
+    return None
+
+
+if __name__ == '__main__':
+    tot = 0
+    games = parse()
+    for g in games:
+        sol = solve(g)
+        if sol is not None:
+            tot += sol[0] * 3 + sol[1]
+    print(tot)
diff --git a/2024/13/2.py b/2024/13/2.py
@@ -0,0 +1,61 @@
+#!/usr/bin/env python3
+import sys
+import re
+
+buta_re = re.compile("Button A: X\+(\d+), Y\+(\d+)")
+butb_re = re.compile("Button B: X\+(\d+), Y\+(\d+)")
+priz_re = re.compile("Prize: X=(\d+), Y=(\d+)")
+
+def parse():
+    games = []
+    game = {}
+    for l in sys.stdin:
+        am = buta_re.match(l)
+        bm = butb_re.match(l)
+        pm = priz_re.match(l)
+        if am:
+            game["A"] = [int(x) for x in am.groups(1)]
+        elif bm:
+            game["B"] = [int(x) for x in bm.groups(1)]
+        elif pm:
+            game["P"] = [int(x) + 10000000000000 for x in pm.groups(1)]
+        else:
+            games.append(game)
+            game = {}
+    if game:
+        games.append(game)
+    return games
+
+# Its a linear equation, so they should interesect exactly
+# once, not at all, or continuously (same line).
+#
+# For pt 2, we can't brute force--have to solve it!
+#
+# 94a + 22b = 8400
+# 34a + 67b = 5400
+#
+# P1 = A1a + B1b -> a = (P1 - B1b)/A1 = P1A2 - B1A2b
+# P2 = A2a + B2b -> a = (P2 - B2b)/A2 = P2A1 - B2A1b
+#
+# P1A2 - B1A2b = P2A1 - B2A1b
+# P1A2 - P2A1 = B1A2b - B2A1b
+# b = (P1A2 - P2A1) / (B1A2 - B2A1)
+def solve(game):
+    P1, P2 = game['P']
+    A1, A2 = game['A']
+    B1, B2 = game['B']
+    b = (P1 * A2 - P2 * A1) / (B1 * A2 - B2 * A1)
+    a = (P1 - B1 * b) / A1
+    if b != int(b) or b < 0 or a != int(a) or a < 0:
+        return None
+    return (a, b)
+
+
+if __name__ == '__main__':
+    tot = 0
+    games = parse()
+    for g in games:
+        sol = solve(g)
+        if sol is not None:
+            tot += sol[0] * 3 + sol[1]
+    print(tot)