Code Challenge: 2D Array Search

Question

Ok this one is like my previous array searching challenge but with a twist.

You must build a function to search one 2d array (or suitable equivalent in your language) of 32-bit integers for another, and return the X and Y index that the second array exists within the first. If the second array does not completely and contiguously exist in the first (i know the 1 dimensional term for it is substring, don't know the 2-dimensional term for it), then you must return -1, -1.

Example 1:

20, 30, 40 ,50
60, 70, 80, 90
100, 110, 120, 130

70, 80
110, 120

Expected Output 1: 1, 1

Example 2:

89, 20, 92, 48
58, 29, 63, 21
96, 12, 39, 42
947, 124, 948, 912

92, 48
64, 22

Expected Output: -1, -1

Misc:

• Your function must take any array size of up to an array of the maximum value of a 16 bit signed integer. (in X and/or Y)
• Any references for your function must be included, though other test harness data is not (any sort of main function, etc.)
• No use of internal or external predefined functions that serve this purpose.
• Your function must merely return the argument; how you display it to the user is up to you.
• If there are multiple copies of the second in the first, it must return the starting index who's X + Y value is lowest (Pretty much any criteria here is going to be arbitrary so this is the one i picked). If you have 2 matches with the same value, you may select which to return.

Answer 1

Python 2 & 3, 154 Characters

Works with arbitrarily large integers and arrays of arbitrary size. Arrays are represented as nested lists:

def s(h,n):a,b,c,d=map(len,(h,h[0],n,n[0]));return([(i,j)for i in range(a-c+1)for j in range(b-d+1)if[h[k][j:j+d]for k in range(i,i+c)]==n]+[(-1,-1)])[0]

Code used to test the above function:

assert (1, 1) == s(
  [[ 20,  30,  40,  50], 
   [ 60,  70,  80,  90], 
   [100, 110, 120, 130]],
  [[ 70,  80], 
   [110, 120]])
assert (-1, -1) == s(
  [[ 89,  20,  92,  48], 
   [ 58,  29,  63,  21], 
   [ 96,  12,  39,  42], 
   [947, 124, 948, 912]],
  [[92, 48], 
   [64, 22]])

Answer 2

Haskell, 128 Characters

Works with arbitrarily large integers and arrays of arbitrary size. Arrays are represented as nested lists:

l=length;s h n=last$(-1,-1):[(i,j)|i<-[0..l h-l n],j<-[0..l(h!!0)-l(n!!0)],map(\k->map(h!!k!!)[j..j+l(n!!0)-1])[i..i+l n-1]==n]

Code used to test the above function:

main :: IO ()
main = print $ s h1 n1 == (1, 1) && s h2 n2 == (-1, -1)

h1 = [[ 20,  30,  40,  50],
      [ 60,  70,  80,  90],
      [100, 110, 120, 130]]

n1 = [[ 70,  80],
      [110, 120]]

h2 = [[ 89,  20,  92,  48],
      [ 58,  29,  63,  21],
      [ 96,  12,  39,  42],
      [947, 124, 948, 912]]

n2 = [[92, 48],
      [64, 22]]

Answer 3

Python, 118 Characters

Returns a list of all the matches found, otherwise (-1,-1)

def f(a,b):i,j=a.shape;k,l=b.shape;return[(x,y)for y in
range(i)for x in range(j)if(a[y:y+k,x:x+l]==b).all()]or(-1,-1)

Testing code:

from numpy import array
a=array([[20, 30, 40 ,50],
         [60, 70, 80, 90],
         [100, 110, 120, 130]])
b=array([[70,80],
         [110,120]])
print(f(a,b))  # returns [(1,1)]

a=array([[89, 20, 92, 48],
         [58, 29, 63, 21],
         [96, 12, 39, 42],
         [947, 124, 948, 912]])
b=array([[92, 48],
         [64, 22]])

print(f(a,b))  # returns (-1,-1)

Answer 4

Ruby, 109 Characters

def f(a,b)a.size.times{|x|a[0].size.times{|y|return[x,y]if
a[x,b.size].map{|i|i[y,b[0].size]}==b}};[-1,-1]end

Testing code:

a=[[20, 30, 40 ,50],
   [60, 70, 80, 90],
   [100, 110, 120, 130]]
b=[[70,80],
   [110,120]]
p f(a,b) # [1, 1]

a=[[89, 20, 92, 48],
   [58, 29, 63, 21],
   [96, 12, 39, 42],
   [947, 124, 948, 912]]
b=[[92, 48],
   [64, 22]]
p f(a,b) # [-1, -1]

Answer 5

F# 263 255 253 characters (inc. spaces)

open Array
let L=length
let f a b=
 let y,x,r,c=L a,L a.[0],L b,L b.[0]
 match 
  [|for i=0 to y-r do 
    for j in 0..x-c->
    [|for p=i to i+r-1 do for q in j..j+c-1->a.[p].[q]=b.[p-i].[q-j]|]
    |>forall id,(i,j)|]|>tryFind fst with Some(_,t)->t|None-> -1,-1

This code represents the input as arrays of arrays.

Oops: hmm. After reading the problem description again this code doesn't perform as specified: it returns the lexicographically smallest sub-index it finds, instead of the smallest sum. E.g.: if there are two matches (1,5) and (2,2), it returns (1,5) (sums to 6), instead of (2,2) (sums to 4). I'll leave the code as is anyway, since I still think it's a nice case of F# abuse.

Warning: using 'open Array' to shorten all Array.find, Array.forall etc. won't work with future versions of F# (beyond 1.9.7.8).

Here's some test code:

let A = [|[|20;30;40;50|]          
          [|50;70;80;90|]
          [|100;110;120;130|]|]

let B = [|[|70;80|];[|110;120|]|]

let A2=[|[|89;20;92;48|]
         [|58;29;63;21|]
         [|96;12;39;42|]
         [|947;124;948;912|]|]

let B2=[|[|12;39;42|];[|947;948;912|]|]

let test1() = f A B = (1,1)

let test2() = f A2 B2 = (-1,-1)

Edit: using let L=length shortens code to 255 chars

Edit2: shaving off 2 more chars by using for i=0 to N instead of for i in 0..N.

Answer 6

Lua, 170

function f()for i=0,#a-#b do for j=0,#a[i]-#b[0]do h=1
for k=0,#b do for l=0,#b[k]do h=h and a[i+k][j+l]==b[k][l]end end
if h then return i,j end end end return -1,-1 end

-- Test cases

a={[0]={[0]= 20,  30,  40,  50},
       {[0]= 60,  70,  80,  90},
       {[0]=100, 110, 120, 130}}
b={[0]={[0]= 70,  80},
       {[0]=110, 120}}

print(f()) --> 1  1

b={[0]={[0]= 80,  90},
       {[0]=120, 130}}

print(f()) --> 1  2

a={[0]={[0]=10, 10, 10, 10, 10},
       {[0]=10, 10, 10, 20, 20},
       {[0]=20, 20, 20, 20, 20}}
b={[0]={[0]=10, 10},
       {[0]=20, 20}}

-- Yes, I know this is wrong according to the arbitrary requirement.
print(f()) --> 0  3

a={[0]={[0]= 89,  20,  92,  48},
       {[0]= 58,  29,  63,  21},
       {[0]= 96,  12,  39,  42},
       {[0]=947, 124, 948, 912}}

b={[0]={[0]= 92,  48},
       {[0]= 64,  22}}

print(f()) --> -1  -1

Answer 7

Golfscript 76 chars

{:b;:a,,{:y a\>b,<:c 0=,,{:x;c{x>b
0=,<}%b=[x y][]if}%{+}*}%{+}*.[-1.]if}:f;

[[20 30 40 50]
[60 70 80 90]
[100 110 120 130]]
[[70 80]
[110 120]]
f p

[[89 20 92 48]
[58 29 63 21]
[96 12 39 42]
[947 124 948 912]]
[[92 48]
[64 22]]
f p

Answer 8

Ruby, 119

Sometimes I just really like a solution, and then I don't want to change it ... such a pity transpose has so many letters ...

def f x,y
x.size.times{|i|x[0].size.times{|j|return[i,j]if x[i,y.size].transpose[j,y[0].size].transpose==y}}
[-1,-1]end