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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
/* Part two runs orders of magnitude slower. */
#include <algorithm>
#include <cstdio>
#include <optional>
#include <vector>
using namespace std;
enum Material {
Ore, Clay, Obs, Geode, MatAmt
};
const Material Mats[] = {Ore, Clay, Obs, Geode};
// Material Matrix.
// heh
typedef int MatMat[MatAmt][MatAmt];
struct State
{
int amts[MatAmt] = {0};
int robots[MatAmt] = {1, 0, 0, 0};
int rem = 0;
State idle(int t) const {
State s = *this;
for (auto m : Mats) {
s.amts[m] += s.robots[m] * t;
}
s.rem -= t;
return s;
}
int timeUntil(const int reqs[MatAmt]) const {
int worst = 0;
for (auto m : Mats) {
if (amts[m] < reqs[m]) {
if (robots[m] == 0) return -1;
worst = max(worst, (reqs[m] - amts[m] + robots[m] - 1) / robots[m]);
}
if (rem < worst) return -1;
}
return worst + 1; // +1 to account for robot build
}
optional<State> buyRobot(MatMat const& costs, Material robot) const {
int t = timeUntil(costs[robot]);
if (t < 0 || rem <= t) return {};
State s = idle(t);
for (auto m : Mats) {
s.amts[m] -= costs[robot][m];
}
s.robots[robot]++;
return s;
}
int best(MatMat const& costs) const {
if (rem <= 0) return 0;
int r = 0;
bool wanted[MatAmt] = {0};
wanted[Geode] = true;
for (auto m : {Geode, Obs, Clay, Ore}) {
if (!wanted[m]) continue;
for (auto m2 : Mats) {
if (robots[m2] < costs[m][m2]) {
wanted[m2] = true;
}
}
auto s = buyRobot(costs, m);
if (s) {
r = max(r, s->best(costs));
}
}
State s = idle(rem);
r = max(r, s.amts[Geode]);
return r;
}
};
int
main()
{
const char *fmt = "Blueprint %d: "
"Each ore robot costs %d ore. "
"Each clay robot costs %d ore. "
"Each obsidian robot costs %d ore and %d clay. "
"Each geode robot costs %d ore and %d obsidian. ";
int id;
MatMat costs = {0};
int partOne = 0;
int partTwo = 1;
while (scanf(fmt, &id, &costs[Ore][Ore], &costs[Clay][Ore], &costs[Obs][Ore], &costs[Obs][Clay], &costs[Geode][Ore], &costs[Geode][Obs]) == 7) {
partOne += id * State{.rem=24}.best(costs);
if (id <= 3) {
partTwo *= State{.rem=32}.best(costs);
printf("two %d\n", partTwo);
}
}
printf("%d\n", partOne);
printf("%d\n", partTwo);
}
|
