Table comparison

Questions
1

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?

2

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,
}
3

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.

4

@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?

5

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
6

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.

7

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

8

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

9

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

10

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