capitalex / path-bag.lua

local PathBag = require "path-bag" local the_eye = require "the-eye" local pprint = require "pprint" -- knowledge base local kb = PathBag.new() for _, pixel in ipairs(the_eye) do kb:insert { "image", "eye", pixel[4], pixel[5], pixel[1], pixel[2], pixel[3] } end math.randomseed(os.time()) local function uuid() local template ='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx' return string.gsub(template, '[xy]', function (c) local v = (c == 'x') and math.random(0, 0xf) or math.random(8, 0xb) return string.format('%x', v) end) end local function io_add(kb) local node, b = kb:get_and_bind { "@add", "eval", "$id", "$x", "$y" } if not node then return false end kb:remove_node(node) kb:insert { "@add", "success", b.id, b.x + b.y } return true end local function io_put_pixel(kb) local node, b = kb:get_and_bind { "@put", "pixel", "$r", "$g", "$b", "$x", "$y" } if not node then return false end kb:remove_node(node) love.graphics.setColor(b.r, b.g, b.b, 1.0) love.graphics.points(b.x, b.y) return true end local function put_pixel(kb) local put_pixel, b1 = kb:get_and_bind { "put", "pixel", "$r", "$g", "$b", "at", "$px_result", "$py_result" } if not put_pixel then return false end local px, b2 = kb:get_and_bind { "@add", "success", b1.px_result, "$px" } if not px then return false end local py, b3 = kb:get_and_bind { "@add", "success", b1.py_result, "$py" } if not py then return false end kb:remove_node(put_pixel) kb:remove_node(px) kb:remove_node(py) kb:insert { "@put", "pixel", b1.r, b1.g, b1.b, b2.px, b3.py } return true end local function next_cursor_down_1(kb) local next_cursor, b1 = kb:get_and_bind { "next", "cursor", "down", "$down_id" } if not next_cursor then return false end local add_success, b2 = kb:get_and_bind { "@add", "success", b1.down_id, "$cy" } if not add_success then return false end kb:remove_node(next_cursor) kb:remove_node(add_success) kb:insert { "cursor", 0, b2.cy } return true end local function next_cursor_right_1(kb) local next_cursor, b1 = kb:get_and_bind { "next", "cursor", "right", "$right_id", "$cy" } if not next_cursor then return false end local add_success, b2 = kb:get_and_bind { "@add", "success", b1.right_id, "$cx" } if not add_success then return false end kb:remove_node(next_cursor) kb:remove_node(add_success) kb:insert { "cursor", b2.cx, b1.cy } return true end local function draw_image_1(kb) local draw_image, b1 = kb:get_and_bind { "draw", "image", "$image", "$x", "$y" } if not draw_image then return end local cursor, b2 = kb:get_and_bind { "cursor", "$cx", "$cy" } if not cursor then return end local image, b3 = kb:get_and_bind { "image", "$image", b2.cx, b2.cy, "$r", "$g", "$b" } if not image then return end kb:remove_node(cursor) local px_id = uuid() local py_id = uuid() kb:insert { "put", "pixel", b3.r, b3.g, b3.b, "at", px_id, py_id } kb:insert { "advance", "cursor", b2.cx, b2.cy } kb:insert { "@add", "eval", px_id, b1.x, b2.cx } kb:insert { "@add", "eval", py_id, b1.y, b2.cy } return true end local function advance_cursor_1(kb) local node, b = kb:get_and_bind { "advance", "cursor", 249, 165 } if not node then return false end kb:remove_node(node) return true end local function advance_cursor_2(kb) local node, b = kb:get_and_bind { "advance", "cursor", 249, "$cy" } if not node then return false end kb:remove_node(node) local down_id = uuid() kb:insert { "next", "cursor", "down", down_id } kb:insert { "@add", "eval", down_id, 1, b.cy } return true end local function advance_cursor_3(kb) local node, b = kb:get_and_bind { "advance", "cursor", "$cx", "$cy" } if not node then return false end kb:remove_node(node) local right_id = uuid() kb:insert { "next", "cursor", "right", right_id, b.cy } kb:insert { "@add", "eval", right_id, 1, b.cx } return true end local function draw_image_2(kb) local node, b = kb:get_and_bind { "draw", "image", "$image", "$x", "$y" } if not node then return false end kb:remove_node(node) return true end local function tick(kb) local node, b = kb:get_and_bind { "tick", "$dt" } if not node then return false end kb:remove_node(node) kb:insert { "draw", "image", "eye", 0, 0 } kb:insert { "cursor", 0, 0 } return true end local rules = { io_add , io_put_pixel , put_pixel , next_cursor_down_1 , next_cursor_right_1 , draw_image_1 , advance_cursor_1, advance_cursor_2, advance_cursor_3 , draw_image_2 , tick } local screen = love.graphics.newCanvas() function love.draw() love.graphics.setColor(1, 1, 1) love.graphics.draw(screen, 0, 0) love.graphics.setColor(1, 0, 0) love.graphics.print(tostring(love.timer.getFPS()) .. " fps", 0, 0) end function love.update(dt) local dt_fact = tostring(dt) local now = os.time() love.graphics.setCanvas(screen) love.graphics.clear(0, 0, 0, 0) kb:insert { "tick", dt } local rewrite = true -- pprint("--- START ---") -- pprint(kb) while rewrite do rewrite = false for i, rule in ipairs(rules) do if rule(kb) then -- print("--- MATCH ---") -- pprint(kb) rewrite = true break end end end love.graphics.setCanvas() local later = os.time() print(later - now) end

love = love or {} local pprint = require "pprint" --[[ If you are familiar with jargon, then a "path bag" is a muliset that is implemented as a prefix tree. this is a path this is another path this is a final path this is a path | V this <-> is <-> a <-> path {2} | | | + <-> final path {1} | + <-> another <-> path {1} --]] local PathBag = {} PathBag.__mt = {} function PathBag.new() local obj = { root = {children = {}, child_count = 0, count = 0} } return setmetatable(obj, {__index = PathBag.__mt}) end function PathBag.__mt:insert(path) local root = self.root for _, step in ipairs(path) do if not root.children[step] then root.children[step] = { value = step, children = {}, child_count = 0, count = 0, parent = root } root.child_count = root.child_count + 1 end root = root.children[step] end root.count = root.count + 1 end function PathBag.__mt:get(path) local root = self.root for _, step in ipairs(path) do if step == "*" then _, root = next(root.children) if not root then return end elseif not root.children[step] then return nil else root = root.children[step] end end return root.count ~= 0 and root or nil end function PathBag.__mt:remove_node(node) local leaf = node while leaf.parent do leaf.count = leaf.count - 1 if leaf.count <= 0 and leaf.child_count <= 0 then local path = leaf.value leaf = leaf.parent leaf.children[path] = nil leaf.child_count = leaf.child_count - 1 else return end end end function PathBag.__mt:get_and_bind(path) local bindings, root = {}, self.root for _, step in ipairs(path) do if type(step) == "string" and step:find("^%$") then key, root = next(root.children) if not root then return end bindings[step:sub(2)] = key elseif not root.children[step] then return nil else root = root.children[step] end end if root.count ~= 0 then return root, bindings end end return PathBag