Codea solution to Bri_G's beermats puzzle

Main.lua

-- Beermats

function setup()
    displayMode(OVERLAY)
    
    -- load the socket library to get accurate time readings
    local socket=require("socket")
    -- measue the time at the start
    local st=socket:gettime()


    -- these are the symbols on the edges of the pieces.  I couldn't find the robot emoji nor the pumpkin so am using the bear and the koala instead.
    -- this is actually half of the edges because the other half are the reverse of these
    symbols = {
        "🐻🦊",
        "🐼🐸",
        "🐸🐯",
        "🐯🐼",
        "🦊🦁",
        "🐻🦁",
        "🐼🐻",
        "🐨🐼",
        "🐼🦊",
        "🦊🐯",
        "🦁🐯",
        "🐯🐻",
        "🐸🦊",
        "🐻🐸",
        "🦁🐸",
        "🦊🐨",
    }
    -- this generates the rest of the symbols by reversing the ones above and adding them in to the list.  Each emoji is 4 bytes long.
    -- the slightly weird way this is written is because I realised after I'd typed the above list that I wanted the reversed symbols at the start of the list
    for k=1,16 do
        table.insert(symbols, symbols[k])
        symbols[k] = string.sub(symbols[k],5,8) .. string.sub(symbols[k],1,4) 
    end
    
    -- this defines the pieces, each is a list of the sides going anti-clockwise around (from an arbitrary starting point), side 'A' corresponds to symbol 1, side 'B' to symbol 2 etc
    local mats = {
        {"abcdaefg", "hFiejHkb"},
        {"mnAcKJli", "GDcIfmoB"},
        {"pnEldjMG", "oLkHNPFg"},
        {"LhICOPAD", "JMKOpNEC"}
    }
    
    -- this part converts the strings of letters that define the pieces into lists of numbers, with 'A' -> 1, 'B' -> 2, and 'a' -> 17, 'b' -> 18 etc
    -- we do this by converting the letter to its ascii number and then doing a bit of bitwise arithmetic on it to convert it into the required range

    faces = {}
    local taba, tabb, sym
    for k,v in ipairs(mats) do
        taba = {}
        for l,u in ipairs(v) do
            tabb = {}
            for i=1,8 do
                sym = string.byte( string.sub(u,i,i))-1
                sym = ((sym ~ 64 ) - (sym&32)//2 )+ 1
                table.insert(tabb,sym)
            end
            table.insert(taba,tabb)
        end
        table.insert(faces,taba)
    end
    -- time check: everything up to here has been setting up the pieces ready for analysis, so the algorithm starts for real here
    local mid = socket:gettime()
    print("Conversion: " .. mid-st)
    
    -- initialise the table of edges of our graph.  Each element in this list will be a list of edges coming out of a particular node.  Our nodes are la elled 1 to 32 so we add empty lists for each node
    edges = {}
    for k=1,32 do
        table.insert(edges,{})
    end
    -- we have a dummy node, called 0, which we use to get our algorithm started
    edges[0] = {}
    local j,src,tgt
    -- we iterate through the sides of each piece (taking into account the fact that each piece has an "up" and "down")
    -- for each side, we look at the side places round from it, because if a side is used in a join, so will the side two places round
    -- then we add an edge from our source side to the *opposite* of the side two places round.  This is because that is what the next
    -- piece will need to have on it to match up with this piece
    -- Example: if we have
    -- | a     e |
    --  \ b c d /
    --    -----
    -- then side 'a' will have an edge to side 'C' because the next piece round will have to have a side 'C' to match the 'c' on this piece
    for k,v in ipairs(faces) do
        for l,u in ipairs(v) do
            for i=1,8 do
                j = (i-3)%8+1
                src = u[i]
                tgt = ((u[j]-1)~16)+1
                table.insert(edges[src],{tgt,{k,l,i}})
                if k == 1 then
                    -- any side on the first piece also gets an edge from our dummy node, this means that our algorithm has a place to start
                    table.insert(edges[0],{src,{0,0,0}})
                end
            end
        end
    end
    
    -- coroutines are great for recursive algorithms where you want to monitor what is going on because when they yield control, they remember where they were at and so when you ask them to resume, they carry on from where they left off.  During the draw cycle, this makes it possible to follow what's happening.  If we were interested purely in speed, we'd unroll this, but it's fast enough as it is.
    co = coroutine.create(function() doNode(edges, {{0},{},{}}) end)
    
    local r,p,mid
    -- okay, we're set up so let's do a time check
    mid=socket:gettime()
    print("Initialising: " .. mid-st)
    -- our coroutine will keep generating steps so we keep querying it until it reports that we're done
    while coroutine.status(co) ~= "dead" do
        r,p = coroutine.resume(co)
        if p then
            if #p[1] == 6 and p[1][6] == p[1][2] then
                mid=socket:gettime()
                print("Solution: " .. mid-st)
            end
        end
    end
        
    -- time check that we're done
    local en=socket:gettime()
    print("Completed: " .. en-st)
    
    -- re-setup the coroutine ready for re-running it in the draw
    co = coroutine.create(function() doNode(edges, {{0},{},{}}) end)
    step = true
    count = 0
    counting = true
    solutions = {}
end


-- This is the recursive step in the algorithm.  Our input for this step is the graph (the table of the edges) and our current path.  A path is a list of edges that we've selected, and we guarantee that the edges in the chosen path are consistent.  The recursive step is to consider all edges that can be added to the path and try them one by one.
function doNode(graph,path)
    local length = #path[1]
    local node = path[1][length] -- this node is at the end of our current path
    for k,v in ipairs(graph[node]) do -- this loops over the edges that come out from this current node
        if not path[2][v[2][1]] then -- we can't add an edge if the piece it corresponds to has already been used
            path[1][length+1] = v[1] -- path[1] is a list of the edges we've added, so when adding an edge we add it to this list
            path[3][length] = v[2] -- path[3] contains the information about each edge that's been added which is useful when we draw them 
            path[2][v[2][1]] = true -- path[2] keeps track of which pieces have been used 
            coroutine.yield(path) -- yield the current path (with the new edge added) back to the main program
            doNode(graph,path) -- call the recursive step on the new path
            path[1][length+1] = nil -- undo the additions to restore the path back to its previous state ready for the next iteration
            path[3][length] = nil
            path[2][v[2][1]] = false
        end
    end
end

function draw()
    background(40,40,50)
    translate(WIDTH/2,HEIGHT/2)
    -- keep track of how many steps we've taken
    text(count,-WIDTH/2+50,HEIGHT/2-50)
    local r,p
    if not step then
        -- this allows us to pause the routine, using the path from the previous run
        p = lp
    else
        -- get the current path from the algorithm
        r,p = coroutine.resume(co)

        if not p then
            -- when the algorithm is done then the final yield will return nil into the variable p
            -- so if we get nil, we re-setup the coroutine so that we can go round again
            co = coroutine.create(function() doNode(edges, {{0},{},{}}) end)
            -- but pause first
            step = false
            -- and stop counting our steps
            counting = false
            -- if we've found a solution before then before we restart, we'll show the first solution we found before restarting
            if #solutions ~= 0 then
                p = solutions[1]
            else
                -- if we didn't find a solution first time round, just start again
                r,p = coroutine.resume(co)
            end
        else
            -- a possible solution is only an actual solution if it is actually a cycle, ie it starts and ends at the same node
            -- because of our dummy node, we actually test for the second node in our path.
            if #p[1] == 6 and p[1][6] == p[1][2] then
                -- as our algorithm modifies p in place, to save a particular configuration we need to copy the table when saving
                table.insert(solutions,deepcopy(p))
                step = false
            end
        end
        if counting then
            -- first time round, count the number of steps
            count = count + 1
        end
        -- store the current path in case we want to reuse it next time
        lp = p
    end

    strokeWidth(2)
    fontSize(60)
    fill(255)
    -- now we draw the current configuration
    for i=1,4 do
        pushMatrix()
        rotate(i*90)
        translate(200,200)
        
        local d = vec2(200,200*math.tan(math.pi/8))
        local e = d:rotate(math.pi/4)
        -- draw four octagons
        for k=1,8 do
            line(d.x,d.y,e.x,e.y)
            d = e
            e = e:rotate(math.pi/4)
        end
        if p[3][i+1] then
            -- if we have this many edges in our path, this octagon is in use
            pushMatrix()
            rotate(-i*90)
            -- display the piece number and which way up it is
            text(p[3][i+1][1] .. "/" .. p[3][i+1][2],0,0)
            popMatrix()
            -- rotate the correct amount so that it is in the right orientation
            rotate(-p[3][i+1][3]*45-90)
            for j=1,8 do
                -- display the symbols on the sides
                rotate(45)
                pushMatrix()
                translate(160,0)
                rotate(90)
                text(symbols[faces[p[3][i+1][1]][p[3][i+1][2]][j]],0,0)
                popMatrix()
            end

        end
    popMatrix()
    end
end

function touched(t)
    -- allows us to pause
    if t.state == BEGAN then
        step = not step
    end
end

function deepcopy(s)
    -- produce a deep copy of a table
    local t = {}
    for k,v in pairs(s) do
        if type(v) == "table" then
            t[k] = deepcopy(v)
        else
            t[k] = v
        end
    end
    return t
end