summaryrefslogtreecommitdiff
path: root/19_2022.py
blob: 5f0fd9fc5a93ca6a19a2abe8eacfff48bb5007b7 (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
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)