inital commitHEADmaster

1 files changed, 172 insertions, 0 deletions

diff --git a/19/1_2.lua b/19/1_2.lua
new file mode 100644
index 0000000..6752862
--- /dev/null
+++ b/19/1_2.lua
@@ -0,0 +1,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)