← Blog Home

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!

Commentary

Leave a Comment

Perci1 says: June 7, 2015
Not gonna do this one because I have absolutely no idea what the problem is or even what a matrix is.
DigitalVeer says: June 7, 2015
The SB4 solution posted is nasty. Mine is very clean in comparison.
DigitalVeer says: June 7, 2015
I also feel like these problems are definitely aimed at the more experienced scripters on the site rather than just for everyone. I thought the snack problems were supposed to be things that could be done by everyone. Not everyone - and I doubt most - can solve these all in under 15 minutes.
dragonkeeper467 says: June 8, 2015
I actually learned something from this even though I didn't really get anywhere with this snack break problem, guys, these are supposed to be challenging, I agree in proposing one hard and one easy question each week, and I think it should be renamed to weekly challenge as it lasts for a week, and doesn't take a snack break to solve, usually takes longer for some people :P
lucas4114 says: June 9, 2015
@DigitalVeer, yeah I'm one of those beginners, I only know a few things at scripting... While looking at all theses "Snack Break Problems" I have completely no idea what anything means...
dragonkeeper467 says: June 11, 2015
@Perci1 I'd give it a try bro, you never know, this one isn't actually that bad, I think I nearly got the whole idea of it, I just hope im thinking in the right direction as to how to do it :P
0xDEADC0DE says: June 16, 2015
no
DigitalVeer says: June 16, 2015
No solution has been posted yet. If nothing by tonight, I'll link to my solution.
DigitalVeer says: June 17, 2015
Here is my solution: http://pastebin.com/1p4LfSr3