inital commitHEADmaster

6 files changed, 398 insertions, 0 deletions

diff --git a/19/1.lua b/19/1.lua
new file mode 100644
index 0000000..209efc1
--- /dev/null
+++ b/19/1.lua
@@ -0,0 +1,129 @@
+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 function perm_yields(n)
+	local memgen = {} -- memoize generation
+	-- permutate all the ways to yield n geodes
+	local function permgen(left,tbl)
+		--print("Perm",left)
+		if left < 0 then return end
+		if left == 0 then
+			local ty = table.concat(tbl)
+			if memgen[ty] == nil then
+				coroutine.yield(tbl)
+				memgen[ty] = true
+			end
+		end
+		for i = time - 1,time-left - 1,-1 do
+			local minesfor = time - i
+			if tbl[i] == nil and (minesfor <= left) then
+				tbl[i] = "geode"
+				permgen(left - minesfor,tbl)
+				tbl[i] = nil
+			end
+		end
+	end
+	return coroutine.wrap(function() permgen(n,{}) end)
+end
+
+local dependencies = {"clay","obsidian"}
+local function rperm(a,n,perm)
+	local function rperm_helper(a,n,rst,restrict)
+		if n ==  0 then
+			coroutine.yield(rst)
+		else
+			for _,v in pairs(a) do
+				local lc = #rst
+				rst[lc + 1] = v
+				rperm_helper(a,n-1,rst)
+				rst[lc + 1] = nil
+			end
+		end
+	end
+	return coroutine.wrap(function() rperm_helper(a,n,{}) end)
+end
+
+local state = {
+	minute = 0,
+	resources = {ore = 0, clay = 0, obsidian = 0, geode = 0},
+	robots = {ore = 1, clay = 0, obsidian = 0, geode = 0}
+}
+
+local function copy_state(tbl)
+	local newtbl = {}
+	for k,v in pairs(tbl) do
+		newtbl[k] = v
+	end
+	for _,n in pairs({"resources","robots"}) do
+		newtbl[n] = {}
+		for k,v in pairs(tbl[n]) do
+			newtbl[n][k] = v
+		end
+	end
+	return newtbl
+end
+
+local function can_build(state,blueprint,name)
+	---print("state",state,"blueprint",blueprint,"name",name)
+	for res, amt in pairs(blueprint[name]) do
+		if state.resources[res] < amt then
+			return false
+		end
+	end
+	return true
+end
+
+local function simulate(blueprint, state, build_order, geode_times)
+	while state.minute <= time do
+		if geode_times[state.minute] then
+			if not can_build(state,blueprint,"geode") then
+				print("Failed to build geode at",state.minute)
+				return false
+			end
+		elseif #build_order > 0 and can_build(state,blueprint,build_order[1]) then
+			local rname = build_order[1]
+			for res,amt in pairs(blueprint[rname]) do
+				state.resources[res] = state.resources[res] - amt
+			end
+			state.robots[rname] = state.robots[rname] + 1
+			table.remove(build_order,1)
+		end
+		for res,count in pairs(state.robots) do
+			state.resources[res] = state.resources[res] + count
+		end
+		state.minute = state.minute + 1
+	end
+	return true
+end
+
+local function feasable(blueprint, geode_times)
+	for i = 1,12 do
+		print("Trying with",i,"other robots")
+		for perm in rperm({"ore","clay","obsidian"},i) do
+			local state = copy_state(state)
+			if simulate(blueprint, state, perm, geode_times) then
+				print("Successful simulation")
+				return true
+			end
+		end
+	end
+end
+
+for combo in perm_yields(56) do
+	print("combo:",combo)
+end
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)
diff --git a/19/ext.lua b/19/ext.lua
new file mode 100755
index 0000000..c1eb1cc
--- /dev/null
+++ b/19/ext.lua
@@ -0,0 +1,62 @@
+-- Override tostring to display more info about the table

+local old_tostring = tostring

+local numtabs = 0

+local printed_tables = {}

+

+local function tostring_helper(el)

+	assert(type(el) == "table", "Tried to call helper with something that was not a table, it was a " .. type(el))

+	local mt = getmetatable(el)

+	if mt and mt.__tostring then

+		return mt.__tostring(el)

+	elseif printed_tables[el] == true then

+		return old_tostring(el)

+	else

+		printed_tables[el] = true

+		numtabs = numtabs + 1

+		local strbuilder = setmetatable({"{"},{__index = table})

+		for k,v in pairs(el) do

+			local key,value

+			if type(k) == "table" then

+				key = tostring_helper(k)

+			else

+				key = old_tostring(k)

+			end

+			if type(v) == "table" then

+				value = tostring_helper(v)

+			else

+				value = old_tostring(v)

+			end

+			strbuilder:insert(string.format("%s%s : %s", string.rep("\t",numtabs), key, value))

+		end

+		strbuilder:insert(string.rep("\t",numtabs - 1) .. "}")

+		numtabs = numtabs - 1

+		return strbuilder:concat("\n")

+	end

+

+end

+function tostring(el)

+	printed_tables = {}

+	if type(el) == "table" then

+		return tostring_helper(el)

+	end

+	return old_tostring(el)

+end

+

+-- Functions to save my hands

+function printf(fmt, ...)

+	print(string.format(fmt,...))

+end

+function errorf(fmt, ...)

+	--Our error isn't actually in this function, it's 1 above us (1) = 2

+	error(string.format(fmt,...),2)

+end

+function assertf(bool, fmt, ...)

+	assert(type(fmt) == "string", "Assertf arg #2 was \"" .. type(fmt) .. "\", expected string")

+	if not bool then

+		args = {fmt}

+		for k,v in ipairs({...}) do

+			table.insert(args,tostring(v))

+		end

+		error(string.format(unpack(args)),2)

+	end

+end

diff --git a/19/input.txt b/19/input.txt
new file mode 100644
index 0000000..5d340c6
--- /dev/null
+++ b/19/input.txt
@@ -0,0 +1,3 @@
+Blueprint 1: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 16 clay. Each geode robot costs 3 ore and 9 obsidian.
+Blueprint 2: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 19 clay. Each geode robot costs 3 ore and 19 obsidian.
+Blueprint 3: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 14 clay. Each geode robot costs 4 ore and 19 obsidian.
diff --git a/19/input2.txt b/19/input2.txt
new file mode 100644
index 0000000..5c80431
--- /dev/null
+++ b/19/input2.txt
@@ -0,0 +1,30 @@
+Blueprint 1: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 16 clay. Each geode robot costs 3 ore and 9 obsidian.
+Blueprint 2: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 19 clay. Each geode robot costs 3 ore and 19 obsidian.
+Blueprint 3: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 14 clay. Each geode robot costs 4 ore and 19 obsidian.
+Blueprint 4: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 3 ore and 8 obsidian.
+Blueprint 5: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 4 ore and 9 obsidian.
+Blueprint 6: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 7 clay. Each geode robot costs 3 ore and 20 obsidian.
+Blueprint 7: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 19 clay. Each geode robot costs 2 ore and 18 obsidian.
+Blueprint 8: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 17 clay. Each geode robot costs 3 ore and 19 obsidian.
+Blueprint 9: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 19 clay. Each geode robot costs 3 ore and 8 obsidian.
+Blueprint 10: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 14 clay. Each geode robot costs 4 ore and 11 obsidian.
+Blueprint 11: Each ore robot costs 2 ore. Each clay robot costs 2 ore. Each obsidian robot costs 2 ore and 15 clay. Each geode robot costs 2 ore and 7 obsidian.
+Blueprint 12: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 19 clay. Each geode robot costs 4 ore and 8 obsidian.
+Blueprint 13: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 16 clay. Each geode robot costs 2 ore and 9 obsidian.
+Blueprint 14: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 15 clay. Each geode robot costs 3 ore and 16 obsidian.
+Blueprint 15: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 20 clay. Each geode robot costs 2 ore and 9 obsidian.
+Blueprint 16: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 3 ore and 19 obsidian.
+Blueprint 17: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 9 clay. Each geode robot costs 3 ore and 15 obsidian.
+Blueprint 18: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 6 clay. Each geode robot costs 2 ore and 20 obsidian.
+Blueprint 19: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 15 clay. Each geode robot costs 4 ore and 20 obsidian.
+Blueprint 20: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 11 clay. Each geode robot costs 3 ore and 14 obsidian.
+Blueprint 21: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 19 clay. Each geode robot costs 4 ore and 11 obsidian.
+Blueprint 22: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 20 clay. Each geode robot costs 4 ore and 7 obsidian.
+Blueprint 23: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 9 clay. Each geode robot costs 2 ore and 20 obsidian.
+Blueprint 24: Each ore robot costs 2 ore. Each clay robot costs 2 ore. Each obsidian robot costs 2 ore and 17 clay. Each geode robot costs 2 ore and 10 obsidian.
+Blueprint 25: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 16 clay. Each geode robot costs 3 ore and 13 obsidian.
+Blueprint 26: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 14 clay. Each geode robot costs 4 ore and 10 obsidian.
+Blueprint 27: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 20 clay. Each geode robot costs 2 ore and 12 obsidian.
+Blueprint 28: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 18 clay. Each geode robot costs 2 ore and 11 obsidian.
+Blueprint 29: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 5 clay. Each geode robot costs 4 ore and 11 obsidian.
+Blueprint 30: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 20 clay. Each geode robot costs 2 ore and 17 obsidian.
diff --git a/19/sample.txt b/19/sample.txt
new file mode 100644
index 0000000..f39c094
--- /dev/null
+++ b/19/sample.txt
@@ -0,0 +1,2 @@
+Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian.
+Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay. Each geode robot costs 3 ore and 12 obsidian.