Determine if a grid contains another grid

Question

Challenge

Create a function takes in two 2-dimensional arrays of characters (or strings if the programming language does not have characters as a datatype) as inputs: a and b. If your language does not support these inputs, you may use any other standard one-byte variable.

Your task is to determine if b contains a. If this is so, return true. Otherwise, return false.

Sample Test Cases

a:

123
456
789

b:

123
456
789

should return true.

a:

code
golf

b:

thisis
code!!
golf!!
ohyeah

should return true.

a:

abcd
efgh
ijkl

b:

abcdef
ghijkl
mnopqr

should return false.

a:

abc
def

b:

1abc2
3def4
5ghi6

should return true

a:

ab
cd

b:

#ab##
##cd#

should return false

This is code-golf so least bytes wins.

Answer 1

Brachylog (v2), 4 bytes

s\s\

Try it online!

Most easily run as a full program, as usual for a decision-problem, with a specified as a command-line argument, b on standard input. The question asks for a function, and the program also works as a function, with b on the left, a on the right, and output via producing an exception if and only if the decision is false.

Explanation

s\s\
s     a substring of rows of {the left input}
 \…\  assert rectangular; swap row and column operations
  s   a substring of <s>rows</s> columns of {the above matrix}
      {implicit} assert that the result can be {the right input}

The "assert rectangular" is, obviously, pointless, as the question guarantees that already. The rest of the program does the grid-finding for us by identifying a substring of the rows and of the columns, i.e. a submatrix.

Meta-discussion

We've had a very similar question before; I'd expect most answers to one question to be modifiable into answers to the other. I think this is the neater version of it, though.

Answer 2

Python 2, 67 bytes

f=lambda a,b,r=4:b*r and f(a,b[1:],r)|f(a,zip(*b)[::-1],r-1)or a==b

Try it online!

Takes input as lists of tuples of characters.

Tries all sub-grids of b and checks if a is among them. The sub-grids are generated by recursively branching on either removing the first row of b or rotating it 90 degrees. After exactly four rotations, checks if the trimmed down b is equal to a.

Answer 3

Charcoal, 26 bytes

⌈⭆η⭆ι⁼θＥ✂ηκ⁺Ｌθκ¹✂νμ⁺Ｌ§θ⁰μ¹

Try it online! Link is to verbose version of code. Heavily based on my answer to Count the contiguous submatrices, the only difference being that instead of taking the sum of the matches I take the maximum, and because of the implicit string conversion due to the use of ⭆ the result is already a string which saves a byte.

Answer 4

J, ^{21 15 8} 7 bytes

1#.,@E.

Try it online!

-7 bytes thanks to Bolce Bussiere

original answer

J, ²¹ 15 bytes

<@[e.&,$@[<;.3]

Try it online!

-6 bytes thanks to FrownyFrog

how

• <@[ boxed left arg
• $@[<;.3] all rectangles in the right arg with the same shape as the left arg
• now pass those as the left and right arg to...
• is the left arg an elm of the right arg, after flattening both e.&,

Answer 5

05AB1E, 10 bytes

øŒεøŒI.å}à

Takes b as first input, a as second. Both inputs as character-matrices.

Port of @Mr.Xcoder's 05AB1E answer for this related challenge, so make sure to upvote him!

Try it online or verify all test cases.

Explanation:

øŒ          # Get the sublists of every column of the (implicit) input `b`
  ε         # Map each list of sublists to:
   øŒ       #  Get the sublists of every column again
            #  (now we have all sub-matrices of `b`)
     I.å    #  Check if the second input `a` is in this list of sub-matrices
        }à  # After the map: check if any are truthy by taking the maximum
            # (which is output implicitly as result)

Answer 6

JavaScript (ES6), 131 112 105 bytes

105 bytes:

f=(m,n)=>m.some((x,i)=>i<=m.length-n.length&x.some((c,j)=>n.every((l,z)=>(m[i+z]+'').indexOf(l,j)==2*j)))

Try it online!

Changes:

• m[i] into x and n[z] into l: Totally forgot that these variables were already instanciated
• && into &: Both sides of the operator are already booleans so a bitwise operator will work

---

112 bytes:

f=(m,n)=>m.some((x,i)=>i<=m.length-n.length&&m[i].some((c,j)=>n.every((l,z)=>(m[i+z]+'').indexOf(n[z],j)==2*j)))

Try it online!

Changes:

• map((c,j)=>{...}).some(s=>s) into some((c,j)=>{...}): Redundancy
• m[i+z].join() into m[i+z]+'': A shorter way to convert the array into a string
• indexOf(n[z].join(),j) into indexOf(n[z],j): The indexOf method already converts n[z] into a string

---

131 bytes:

f=(m,n)=>m.some((x,i)=>i<=m.length-n.length&&m[i].map((c,j)=>n.every((l,z)=>m[i+z].join().indexOf(n[z].join(),j)==2*j)).some(s=>s))

Try it online!

Readable:

function f (m, n) {
  return m.some((x, i) => {
    return i <= m.length - n.length
      && m[i].map((c, j) => {
        return n.every((l, z) => {
          return m[i + z].join().indexOf(n[z].join(), j) == 2 * j
        })
      })
        .some(s => s)
  })
}

Instead of compairing individual values, I checked if the lines from grid N were included in the lines of grid M, and if so, at which indexes. If all of the lines are included starting from the same index then the grid N is contained in the grid M.

Answer 7

APL (Dyalog Unicode), 3 bytes

1∊⍷

Try it online!

It's like this question was made for APL!

Explanation

  ⍷   ⍝ 'find', returns a matrix with '1' in all positions where the first matrix is contained in the second
1∊    ⍝ checks if '1' is a member of this matrix

Answer 8

Wolfram Language (Mathematica), 46 37 bytes

Partition[#2,Dimensions@#,1]~FreeQ~#&

Try it online!

Returns True if b does not contain a, and False if it does.

Answer 9

Python 2, 106 118 113 bytes

lambda a,b,L=len:any(sum(A==B[j:j+L(A)]for A,B in zip(a,b[i:]))==L(a)for i in range(L(b))for j in range(L(b[0])))

Try it online!

Answer 10

PowerShell, 71 102 85 98 bytes

thanks @Jo King; test cases added.

param($a,$b)!!($a|%{$p=[regex]::Escape($_)
$b|sls $p -a -ca|% m*}|group index|?{"$a"-ceq$_.Group})

Try it online!

Less golfed:

param($a,$b)

$matches = $a|%{
    $pattern = [regex]::Escape($_)
    $b|Select-String $pattern -AllMatches -CaseSensitive|% Matches
}

$relevantGroupsByMatchPosition = $matches|group index|?{
    "$a"-ceq$_.Group  # the '$_.Group' contains matches in source order
                      # -ceq is case sensitivity equation operator
                      # -ceq performs an implicit conversion to the left operand type
}

!!($relevantGroupsByMatchPosition)  # true if the variable is not $null

Answer 11

Javascript, 150 bytes

f=(a,b)=>{_='length';for(r=i=0;i<=b[_]-a[_];i++)for(j=0;j<=b[0][_]-a[0][_];j++){u=0;a.map((l,y)=>l.map((c,x)=>u=u||b[i+y][j+x]!=c));r=r||!u;}return r}

Try it online

Answer 12

JavaScript (V8), 81 bytes

(m,n)=>m[s='some']((a,i)=>a[s]((b,j)=>!n[s]((c,k)=>c[s]((d,l)=>m[i+k][j+l]!=d))))

Try it online!

Answer 13

Octave/Matlab, 47 45 44 40/38 bytes

• -2 Default output to ans
• -1 Trace of inner product is the sum of the squares of the elements. Therefore use trace(a*a') instead of sum(a(:).^2)
• -4 Use find instead of any(any(...)) since any non-zero output of find is considered as a logical truth, and Matlab/Octave is 1-indexed.
• -2 but only in Matlab, since the second argument to xcorr2 does not need to be made numeric and is implicitly converted to whatever is the first argument's type.

Octave

@(a,b)find(xcorr2(a*1,b*1)==trace(a*a'))

Try it online!

Matlab

@(a,b)find(xcorr2(a*1,b)==trace(a*a'))

This works by computing the 2D cross-correlation function of matrices a and b (in a numeric from), and then checking whether an entry corresponding to a perfect overlap exists.