summaryrefslogtreecommitdiff
path: root/13_2024.py
blob: 06acce1ed48c2a12078bc32f9da7c454c38b1054 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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)