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)
|