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 in Questions 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?

Comments

  • 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
    
  • IgnatzIgnatz 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
Sign In or Register to comment.