← 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

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