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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
|
require "ext"
local blueprints = {}
for line in io.lines() do
local bpn = line:match("Blueprint (%d+):")
bpn = tonumber(bpn)
blueprints[bpn] = {}
for robot, cost in line:gmatch("Each (%w+) robot costs (%d+) ore.") do --ore and clay
blueprints[bpn][robot] = {ore = tonumber(cost)}
end
for robot, c1, r1, c2, r2 in line:gmatch("Each (%w+) robot costs (%d+) (%w+) and (%w+) (%w+).") do
--obsidian and geode
blueprints[bpn][robot] = {[r1] = tonumber(c1),[r2]=tonumber(c2)}
end
end
print("Blueprints:")
print(blueprints)
local time = 24
local speculative_geodes = 0
-- 8 was originally 4 (since building clay, obsidian, and geode would be on
-- turn 4, 8 was found experimentally based on input.
for i = 4,time do --assume we build clay, obsidian, and geode immediately,
--how many geodes can we mine?
speculative_geodes = speculative_geodes + i
end
local state = {
minute = 0,
resources = {ore = 0, clay = 0, obsidian = 0, geode = 0},
robots = {ore = 1, clay = 0, obsidian = 0, geode = 0},
buildorder = {},
max_geodes = speculative_geodes
}
local function copy_state(tbl)
local resources, robots = tbl.resources, tbl.robots
local newtbl = {
minute = tbl.minute,
resources = {
ore = resources.ore,
clay = resources.clay,
obsidian = resources.obsidian,
geode = resources.geode
},
robots = {
ore = robots.ore,
clay = robots.clay,
obsidian = robots.obsidian,
geode = robots.geode
},
max_geodes = tbl.max_geodes
}
local buildorder = {}
for k,v in ipairs(tbl.buildorder) do
buildorder[k] = v
end
newtbl.buildorder = buildorder
return newtbl
end
local function can_build(state,blueprint,name)
local resources = state.resources
for res, amt in pairs(blueprint[name]) do
if resources[res] < amt then
return false
end
end
return true
end
local function step(state)
local resources = state.resources
for name, amt in pairs(state.robots) do
resources[name] = resources[name] + amt
end
state.minute = state.minute + 1
end
local table_concat = table.concat
local function bo_to_s(state)
-- a short representaiton of our build order, to use less memory
local s = {}
for _,v in ipairs(state.buildorder) do
s[#s + 1] = v:sub(2,2)
end
return table_concat(s)
end
local prl = {"ore","clay","obsidian"}
local table_remove = table.remove
local function simulate(blueprint)
print("Examining blueprint",blueprint)
local scpy = copy_state(state)
local branch = {scpy}
local known_builds = {} -- memoize build order
setmetatable(known_builds,{__mode="kv"})
local nbranches = 0
local max_geodes = 0
local max_cost = {ore=0,clay=0,obsidian=0}
-- examin our blueprint. If we have enouch ore robots to build anything
-- next turn, we never need to buid another ore robot.
-- Likewise, if we have enough clay robots to build anything next turn,
-- we never need another clay robot.
for robot, resources in pairs(blueprint) do
for res, amt in pairs(resources) do
max_cost[res] = math.max(max_cost[res],amt)
end
end
while #branch > 0 do
local tbranch = table_remove(branch)
--print("Examining ",tbranch)
if nbranches % 1000000 == 0 then
print("examined",nbranches,"branches",#branch,"active")
print("Curently examinig build order:")
print(bo_to_s(tbranch), #tbranch.buildorder)
print("Max geodes on this branch were:",tbranch.max_geodes, "vs", max_geodes, "at",tbranch.minute)
end
nbranches = nbranches + 1
if tbranch.minute == time then
if tbranch.resources.geode > max_geodes then
max_geodes = tbranch.resources.geode
print("New maximum:",max_geodes)
end
else
--only consider robots we don't have enough of
local robots = {}
for _, resource in ipairs(prl) do
if tbranch.robots[resource] < max_cost[resource] then
robots[#robots + 1] = resource
end
end
robots[#robots + 1] = "geode"
for _, robot in ipairs(robots) do
if can_build(tbranch, blueprint, robot) then
--a branch where we built the robot,
local ns = copy_state(tbranch)
for res, amt in pairs(blueprint[robot]) do
ns.resources[res] = ns.resources[res] - amt
end
step(ns)
local time_remaining = time - ns.minute
if robot ~= "geode" then
ns.max_geodes = ns.max_geodes - time_remaining
end
ns.robots[robot] = ns.robots[robot] + 1
ns.buildorder[#ns.buildorder + 1] = robot
local boc = bo_to_s(ns)
if not known_builds[boc] and ns.max_geodes > max_geodes then
known_builds[boc] = true
branch[#branch + 1] = ns
end
end
end
--a branch where we don't
step(tbranch)
local time_remaining = time - tbranch.minute
tbranch.max_geodes = tbranch.max_geodes - time_remaining
if tbranch.max_geodes > max_geodes then
branch[#branch + 1] = tbranch
end
end
end
print("Max geodes for blueprint was",max_geodes)
return max_geodes
end
local sum = 0
for bpn, blueprint in pairs(blueprints) do
max_geodes = simulate(blueprint)
sum = sum + (bpn * max_geodes)
end
print(sum)
|
