3-SAT solver using Applied Energistics

cnf.lua

local path = ...
if not path then error("cnf [path]", 0) end

local ae = true -- Whether to spawn in AE or not
local redstone_side = "left" -- Side to position the button

local whole_path = shell.resolve(path)
local handle, err = fs.open(whole_path, "r")

if not handle then error("Cannot open path (" .. (err or "?") ..  ")", 0) end

local variables, clauses = 0, 0
local clause_list = {}

for line in handle.readLine do
	if line:sub(1, 1) == "c" or line == "" then
		-- Skip, a comment
	elseif line:sub(1, 1) == "p" then
		local vars, clause = line:match("^p cnf (%d+) +(%d+) *$")
		if not vars then
			printError("Malformed line " .. line)
			break
		end

		variables = tonumber(vars)
		clauses = tonumber(clause)
	elseif line == "%" then
		break
	else
		local a, b, c = line:match("^ *([%-0-9]+) +([%-0-9]+) +([%-0-9]+) +0$")
		if not a then
			printError(("Malformed line %q"):format(line))
			break
		end

		clause_list[#clause_list + 1] = {
			tonumber(a), tonumber(b), tonumber(c),
		}
	end
end

handle.close()

if #clause_list ~= clauses then
	error(("Different number of clauses (expected %d, got %d)"):format(clauses, #clause_list), 0)
elseif clauses == 0 then
	error("No clauses in the file: will definitely be satisfiable", 0)
end

commands.exec("clear @p")
commands.exec("kill @e[type=minecraft:item]")

local summon_recipe

if ae then
	summon_recipe = function(from, to)
		commands.summon("minecraft:item", "~", "~", "~", {
			Item = {
				id = "appliedenergistics2:encoded_pattern",
				Count = 1,
				tag = {
					crafting = false,
					["in"] = from,
					["out"] = { to },
				}
			}
		})
	end
else
	summon_recipe = function(from, to)
		local tag = { Outputs = { to } }
		for i = 1, #from do tag["Slot_" .. i] = from[i] end
		commands.summon("minecraft:item", "~", "~", "~", {
			Item = {
				id = "refinedstorage:pattern",
				Count = 1,
				tag = tag
			}
		})
	end
end

local function with_count(tbl, count)
	local out = {}
	for k, v in pairs(tbl) do out[k] = v end
	out.Count = count
	return out
end

local initial_items, variable_items, clause_items = {}, {}, {}

-- Generate variable items
do
	local colour = 0xFFFFFF / variables / 2
	for i = 1, variables do
		initial_items[i] = {
			id = "leather_helmet",
			Count = 1,
			tag = { display = {
				color = math.floor(colour * (i * 2 - 1)) ,
				Name = "Valuation " .. i,
			} }
		}

		variable_items[i] = {
			id = "leather_helmet",
			Count = 1,
			tag = { display = {
				color = math.floor(colour * i * 2) ,
				Name = "Variable " .. i,
			} }
		}

		variable_items[-i] = {
			id = "leather_boots",
			Count = 1,
			tag = { display = {
				color = math.floor(colour * i * 2),
				Name = "Variable ¬" .. i,
			} }
		}
	end
end

-- Generate clause items
do
	local colour = 0xFFFFFF / clauses
	for i = 1, clauses do
		clause_items[i] = {
			id = "leather_leggings",
			Count = 1,
			tag = { display = {
				color = math.floor(colour * i) ,
				Name = "Clause " .. i,
			} }
		}
	end
end

while redstone.getInput(redstone_side) do os.pullEvent("redstone") end
while not redstone.getInput(redstone_side) do os.pullEvent("redstone") end

print("Spawning variable items")
for i = 1, variables do
	commands.summon("minecraft:item", "~", "~", "~", { Item = initial_items[i] })
end

while redstone.getInput(redstone_side) do os.pullEvent("redstone") end
while not redstone.getInput(redstone_side) do os.pullEvent("redstone") end

print("Spawning variable patterns")
for i = 1, variables do
	summon_recipe({ initial_items[i] }, with_count(variable_items[i], clauses))
	summon_recipe({ initial_items[i] }, with_count(variable_items[-i], clauses))
end

while redstone.getInput(redstone_side) do os.pullEvent("redstone") end
while not redstone.getInput(redstone_side) do os.pullEvent("redstone") end

print("Spawning clause patterns")
for i = 1, #clause_list do
	local clause = clause_list[i]
	local result = clause_items[i]

	for j = 1, #clause do
		summon_recipe({ variable_items[clause[j]] }, clause_items[i])
	end
end

while redstone.getInput(redstone_side) do os.pullEvent("redstone") end
while not redstone.getInput(redstone_side) do os.pullEvent("redstone") end

print("Spawning accumulates")
do
	-- Build up a queue of items we need to generate
	local queue = {}
	for i = 1, #clause_items do queue[i] = clause_items[i] end

	local counter = 1
	local colour = 0xFFFFFF / 100

	while #queue > 1 do
		local items = {}
		for i = 1, math.min(#queue, 9) do
			items[i] = table.remove(queue, 1)
		end

		local result = {
			id = "leather_chestplate",
			Count = 1,
			tag = { display = {
				color = math.floor(colour * counter),
				Name = "Accumulate " .. counter,
			} }
		}

		summon_recipe(items, result)
		queue[#queue + 1 ] = result
		counter = counter + 1
	end
end