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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
import sys
from collections import deque
infile = sys.argv[1] if len(sys.argv) > 1 else "data/19_2022.txt"
data = open(infile).read().strip()
lines = [x for x in data.split("\n")]
def solve(Co, Cc, Co1, Co2, Cg1, Cg2, T):
best = 0
S = (0, 0, 0, 0, 1, 0, 0, 0, T)
Q = deque([S])
SEEN = set()
while Q:
state = Q.popleft()
o, c, ob, g, r1, r2, r3, r4, t = state
best = max(best, g)
if t == 0:
continue
Core = max([Co, Cc, Co1, Cg1])
if r1 >= Core:
r1 = Core
if r2 >= Co2:
r2 = Co2
if r3 >= Cg2:
r3 = Cg2
if o >= t * Core - r1 * (t - 1):
o = t * Core - r1 * (t - 1)
if c >= t * Co2 - r2 * (t - 1):
c = t * Co2 - r2 * (t - 1)
if ob >= t * Cg2 - r3 * (t - 1):
ob = t * Cg2 - r3 * (t - 1)
state = (o, c, ob, g, r1, r2, r3, r4, t)
if state in SEEN:
continue
SEEN.add(state)
assert o >= 0 and c >= 0 and ob >= 0 and g >= 0, state
Q.append((o + r1, c + r2, ob + r3, g + r4, r1, r2, r3, r4, t - 1))
if o >= Co:
Q.append((o - Co + r1, c + r2, ob + r3, g + r4, r1 + 1, r2, r3, r4, t - 1))
if o >= Cc:
Q.append((o - Cc + r1, c + r2, ob + r3, g + r4, r1, r2 + 1, r3, r4, t - 1))
if o >= Co1 and c >= Co2:
Q.append(
(o - Co1 + r1, c - Co2 + r2, ob + r3, g + r4, r1, r2, r3 + 1, r4, t - 1)
)
if o >= Cg1 and ob >= Cg2:
Q.append(
(o - Cg1 + r1, c + r2, ob - Cg2 + r3, g + r4, r1, r2, r3, r4 + 1, t - 1)
)
return best
p1 = 0
p2 = 1
for i, line in enumerate(lines):
words = line.split()
id_ = int(words[1][:-1])
ore_cost = int(words[6])
clay_cost = int(words[12])
obsidian_cost_ore, obsidian_cost_clay = int(words[18]), int(words[21])
geode_cost_ore, geode_cost_clay = int(words[27]), int(words[30])
s1 = solve(
ore_cost,
clay_cost,
obsidian_cost_ore,
obsidian_cost_clay,
geode_cost_ore,
geode_cost_clay,
24,
)
p1 += id_ * s1
if i < 3:
s2 = solve(
ore_cost,
clay_cost,
obsidian_cost_ore,
obsidian_cost_clay,
geode_cost_ore,
geode_cost_clay,
32,
)
p2 *= s2
print(p1)
print(p2)
|