diff options
Diffstat (limited to '13_2024.py')
-rw-r--r-- | 13_2024.py | 62 |
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) |