#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# Table comparison

edited July 2013 Posts: 1,976

Say I have two tables of variables, either 0 or 1. You can think of them as grids, like

``````{
0, 1, 1, 0,
1, 0, 0, 1,
1, 0, 0, 1,
0, 1, 1, 0,
}
``````

You can access the variable by calling table[y][x]. But say I have another table, maybe 8x8 rather than 4x4. How can I check if the 8x8 grid contains the same pattern as the 4x4 grid? Please respond quickly, I need the answer today. This is something very important...

Also, can you add a maximum amount changes before it says the pattern does not exist? So if, say, the 8x8 grid has an extra 1 that it doesn't care?

Tagged:

• Posts: 305

for you, what is "the same pattern" ?

```{
0, 1, 1, 0,
1, 0, 0, 1,
1, 0, 0, 1,
0, 1, 1, 0,
}

samePattern ?

{
0, 1, 1, 1, 1, 1, 1, 0,
1, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 1,
0, 1, 1, 1, 1, 1, 1, 0,
}
```
• Posts: 2,161

Off the top of my head, I can't think of a way that's quicker than a simple search.

Big table is `n x n`, little table is `m x m`.

``````errors = 0
for i = 0,n-m-1 do
for j = 0,n-m-1 do
for k = 1,m do
for l = 1,m do
if little[k][l] ~= big[k+i][l+i] then
errors = errors + 1
end
if errors > maxerrors then
break
end
end
if errors > maxerrors then
break
end
end
if errors > maxerrors then
break
end
end
if errors > maxerrors then
break
end
end -- not sure how many ends I've stacked up here!
``````

Might be out by one on the outer loop. We need multiple breaks because we need to get out of the whole slew of loops when we hit the maximum number of errors - I don't know if it's possible to break out of multiple loops in a single step.

• Posts: 1,976

@HyroVitalityProtago 8x8 is something like

``````{
0, 0, 0, 0, 1, 1, 0, 0,
0, 0, 0, 1, 0, 0, 1, 0,
0, 0, 0, 1, 0, 0, 1, 0,
0, 0, 0, 0, 1, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
}
``````

The circle is in the top right, how can I detect that?

@Andrew_Stacey Can you explain that search a bit better? I can't figure out how it iterates the tables. And I know you said at n is and what m is but I'm still not sure.

``````for i = 0,n-m-1 do
for j = 0,n-m-1 do
for k = 1,m do
for l = 1,m do
``````

Out of i, j, k, and l's n's or m's, which are width and which are height? Instead of n or m could you maybe say bigWidth, bigHeight, littleWidth, and littleHeight?

Also, where do you use j? I don't see it used anywhere, is that a mistake or is it supposed to be that way?

• Posts: 2,161

Always assume incompetence! Yes, the second `i` was meant to be a `j`.

According to the lua users mailing list (http://lua-users.org/lists/lua-l/2006-08/msg00373.html), breaking out of a multiple loop is easiest when the loop is in a function.

``````function searchInTable(littleTable,bigTable,maxErrors)

maxErrors = maxErrors or 1 -- supply a default

local bigRows = #bigTable[1] -- maybe your rows & cols are the other way around
local bigCols = #bigTable
local littleRows = #littleTable[1]
local littleCols = #littleTable

-- we'll search the big table by looking starting at a particular offset
-- the first offset will be so that (1,1) in the little table corresponds
-- to (1,1) in the big table, so offset is (0,0).
-- the last offset will be so that (littleRows,littleCols)
-- maps to (bigRows,bigCols) so the last offset is
-- (bigRows - littleRows,bigCols - littleCols)
local rowDifference = bigRows - littleRows
local colDifference = bigCols - littleCols

local errors = 0

-- iterate through the offsets
for rowOffset = 0, rowDifference do
for colOffset = 0, colDifference do
-- for a given offset, we iterate through the little table and compare
-- its value at a (row,col) with the corresponding value in the big table
for row = 1, littleRows do
for col = 1, littleCols do
if littleTable[row][col] ~= bigTable[row + rowOffset][col + colOffset] then
errors = errors + 1
end
if errors > maxErrors then
return false
end
end
end
end
end
return true

end
``````
• Mod
Posts: 5,396

It might be simpler to program if you flatten the tables into strings and search for the small string in the big string - which is just a single search.

That won't give you the approximate match, however.

• Posts: 2,161

@Ignatz Wouldn't work, if I've understood the search correctly. The flattened table wouldn't contain the subtables as contiguous substrings.

• Posts: 1,976

Thanks, @Andrew_Stacey the code works and now I understand it!

• Posts: 2,161

@SkyTheCoder There's a flaw in it. I'll fix it later.

• Posts: 2,161

Here you go:

``````function setup()
bigTable =
{
{0, 0, 0, 0, 1, 1, 0, 0},
{0, 0, 0, 1, 0, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 1, 0},
{0, 0, 0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0}
}
littleTable =
{
{0, 1, 1, 0},
{1, 0, 0, 1},
{1, 0, 0, 1},
{0, 1, 1, 0}
}
if tableIn(littleTable,bigTable,1) then
print("Success")
else
print("Failure")
end
end

function draw()
end

function tableIn(lt,bt,me)
me = me or 1 -- number of allowed errors

-- big table dimensions
local br = #bt
local bc = #bt[1]
-- little table dimensions
local lr = #lt
local lc = #lt[1]

-- offset range
local mr = br - lr
local mc = bc - lc

-- loop over the offsets looking for a match
for i=0,mr do
for j=0,mc do
-- if we get a match, return true
-- otherwise continue with the search
if tableIn_aux(lt,bt,i,j,lr,lc,me) then
return true
end
end
end
-- no match found, return false
return false
end

function tableIn_aux(lt,bt,i,j,lr,lc,me)
local err = 0
for k=1,lr do
for l=1,lc do
if lt[k][l] ~= bt[k+i][l+j] then
err = err + 1
end
if err >= me then
return false
end
end
end
return true
end
``````