Snack Break Problem #5

Followup on SB4

Here is the solution to SB4 that was posted on github.

SB4 is a problem that is probably best solved using recursion. Recursion is a strategy where you break a problem down into smaller and smaller cases and use a single function (or a few) to deal with each one. You can tell a function is a recursive function if it calls itself.

function recursive()
    -- function contents here
    return recursive() 
end

The function above is recursive because it calls itself continuously. Usually, when a recursive function has reached an answer it will break out of this self-calling cycle.

SB4 is an example of a problem that recursion would be good for; you will iterate through each of the contents of a table and translate them into string form. If you reach a table, then you will repeat the process all over again.

So, if you have a function tableToString, just call it on any table contents you encounter!

I hope you all try attempting this problem or at least save a copy of a solution; printing string forms of tables is very useful for debugging and the likes, and having your own table-to-string function gives you more control over the output than JSON.

Explaining my solution to SB4

function tableToString(t)
    if type(t) == "table" then
        local function parse(object)
            local objectType = type(object)
            return
                objectType == "table" and tableToString(object) or
                (objectType == "function" or objectType == "userdata") and objectType or
                objectType == "string" and table.concat({[["]], object, [["]]}) or
                object
        end

        local isArrayKey = { }
        local tableOutput = { }
        local tableOutputCount = 0

        for key, value in ipairs(t) do
            isArrayKey[key] = true
            tableOutput[tableOutputCount + 1] = parse(value)
            tableOutput[tableOutputCount + 2] = ", "
            tableOutputCount = tableOutputCount + 2
        end

        for key, value in next, t do
            if not isArrayKey[key] then
                tableOutput[tableOutputCount + 1] = "["
                tableOutput[tableOutputCount + 2] = parse(key)
                tableOutput[tableOutputCount + 3] = "] = "
                tableOutput[tableOutputCount + 4] = parse(value)
                tableOutput[tableOutputCount + 5] = ", "
                tableOutputCount = tableOutputCount + 5
            end
        end

        tableOutput[tableOutputCount] = nil

        local metatable = getmetatable(t)
        if metatable then
            return table.concat({"{", table.concat(tableOutput), "} <- ", tableToString(metatable)})
        end
        return table.concat({"{", table.concat(tableOutput), "}"})
    end
end

As I said above, recursion is a great way to approach this problem, since it is one that can be broken up into separate parts. Every single time we visit a table, we can apply a function that turns that table into a string. This solves the problem of turning tables in tables into strings as well!

The bulk of the work here is being done in the parse function, which determines how a value in the table should be translated.

local function parse(object)
    local objectType = type(object)
    return
        objectType == "table" and tableToString(object) or
        (objectType == "function" or objectType == "userdata") and objectType or
        objectType == "string" and table.concat({[["]], object, [["]]}) or
        object
end

1. If it is a table, we will take advantage of recursion!
2. If it is a function or if it is a userdata, then we turn it into its datatype (according to the specifications in the problem). It just so happens that we already have that thanks to type!
3. If it is a string, then we surround it with quotes!
4. If it is anything else, then we will just have it cast into a string naturally.

Notice that I made good use of the type function in Lua, which returns a string the contains the data type of the argument. type is a very useful function, so be sure to always keep it handy.

Another thing to note is that I properly tackled the task of separating the array from the dictionary part of the table, as demanded in the problem. This was accomplished with the help of ipairs, which is an iterator that conveniently only iterates through the array portion of a table!

local isArrayKey = { }

for key, value in ipairs(t) do
    isArrayKey[key] = true
    -- store in array form 
    -- {1, 2, 3}
end

for key, value in next, t do
    if not isArrayKey[key] then
        -- store in dictionary form 
        -- {["a"] = 1, ["b"] = 2, ["c"] = 3}
    end
end

This allowed me to store all array keys while representing entries in array form value. After that, I iterated through the table normally and only turned non-array keys into dictionary form key = value.

The final part was dealing with metatables. This may initially seem intimidating, but it is not as bad as it seems. A metatable is just a table associated with a table. So, when we call getmetatable on a table, we get a table that we can then turn into a string with recursion. Once we have our string, we can follow the problem's specifications and signify that it is a metatable with <-.

This week's problem

This week we will be looking at a property of matrices. The matrix is one of the most powerful and useful ways we can represent data in computer science.

Matrix transpose is SB5. You will be completing the contents of a given Matrix class with a transpose method!

Visit the link above for more details.

I'll see you all next week!