summaryrefslogtreecommitdiff
path: root/13_2024.py
diff options
context:
space:
mode:
Diffstat (limited to '13_2024.py')
-rw-r--r--13_2024.py62
1 files changed, 62 insertions, 0 deletions
diff --git a/13_2024.py b/13_2024.py
new file mode 100644
index 0000000..06acce1
--- /dev/null
+++ b/13_2024.py
@@ -0,0 +1,62 @@
+infile = "data/13_2024.txt"
+data = open(infile).read().strip()
+lines = data.split("\n\n")
+dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
+p1 = 0
+p2 = 0
+
+
+def solve(ax, ay, bx, by, px, py, parj):
+ p2, best = 10000000000000 if parj else 0, None
+ for i in range(600):
+ for j in range(600):
+ cost = 3 * i + j
+ dx = ax * i + bx * j
+ dy = ay * i + by * j
+ if dx == dy and dx > 0:
+ score = dx / cost
+ if best is None or score < best[0]:
+ best = (score, i, j, cost, dx)
+ if best is None:
+ return 0
+ curr, i, j, cost, dx = best
+ amt = (p2 - 40000) // dx
+ dp = {}
+
+ def f(x, y):
+ if (x, y) in dp:
+ return dp[(x, y)]
+ if x == 0 and y == 0:
+ return 0
+ if x < 0:
+ return 10**20
+ if y < 0:
+ return 10**20
+ res = min(3 + f(x - ax, y - ay), 1 + f(x - bx, y - by))
+ dp[(x, y)] = res
+ return res
+
+ res = f(px + p2 - amt * dx, py + p2 - amt * dx)
+ if res < 10**15:
+ return res + amt * cost
+ else:
+ return 0
+
+
+for i, j in enumerate(lines):
+ a, b, prize = j.split("\n")
+ aw = a.split()
+ ax = int(aw[2].split("+")[1].split(",")[0])
+ ay = int(aw[3].split("+")[1].split(",")[0])
+ bw = b.split()
+ bx = int(bw[2].split("+")[1].split(",")[0])
+ by = int(bw[3].split("+")[1].split(",")[0])
+ pw = prize.split()
+ px = int(pw[1].split("=")[1].split(",")[0])
+ py = int(pw[2].split("=")[1])
+ p1 += solve(ax, ay, bx, by, px, py, False)
+ p2 += solve(ax, ay, bx, by, px, py, True)
+
+
+print(p1)
+print(p2)