16
\$\begingroup\$

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 so least bytes wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ Hi and welcome to codegolf! I edited your test cases to (hopefully) make them a bit more clear. Note that we have a sandbox for working on challenges before posting them to main. Good luck! \$\endgroup\$ – FryAmTheEggman May 4 '19 at 19:35
  • 2
    \$\begingroup\$ Also, may I take the first array as an array of strings and the second as a string separated by newlines, even though my language(C#) has a character type built in? \$\endgroup\$ – Embodiment of Ignorance May 4 '19 at 21:07
  • \$\begingroup\$ @Neil Test cases 2 and 3 are not square. \$\endgroup\$ – Robin Ryder May 4 '19 at 21:16
  • 5
    \$\begingroup\$ Could you add a truthy test case where a isn't on b's left edge and a falsey test case where each line of a appears in consecutive lines of b but with their left edges staggered? \$\endgroup\$ – Shaggy May 4 '19 at 21:34
  • \$\begingroup\$ @EmbodimentofIgnorance yes \$\endgroup\$ – Hazard May 5 '19 at 21:40

13 Answers 13

9
\$\begingroup\$

Brachylog (v2), 4 bytes

s\s\

Try it online!

Most easily run as a full program, as usual for a , 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.

\$\endgroup\$
  • \$\begingroup\$ Shortest answer here, so I'll accept it. \$\endgroup\$ – Hazard May 5 '19 at 21:43
7
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ @mazzy I think the input grids are supposed to be rectangles. \$\endgroup\$ – xnor May 7 '19 at 6:17
5
\$\begingroup\$

Charcoal, 26 bytes

⌈⭆η⭆ι⁼θE✂ηκ⁺Lθκ¹✂νμ⁺L§θ⁰μ¹

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.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

J, 21 15 8 7 bytes

1#.,@E.

Try it online!

-7 bytes thanks to Bolce Bussiere

original answer

J, 21 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.&,
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I think this can be <@[e.&,$@[<;.3] \$\endgroup\$ – FrownyFrog May 6 '19 at 8:51
  • \$\begingroup\$ Ah ofc, ty! If you want a challenge, have a look at this monstrosity I defiled the site with \$\endgroup\$ – Jonah May 6 '19 at 14:17
  • 1
    \$\begingroup\$ -7 Bytes: +/@:,@E.. E. is pretty much made for this challenge. \$\endgroup\$ – Bolce Bussiere May 6 '19 at 17:49
  • \$\begingroup\$ tyvm @BolceBussiere. i will update this tonight. \$\endgroup\$ – Jonah May 6 '19 at 17:59
4
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
4
+200
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @Neil: Fixed now. \$\endgroup\$ – Chas Brown May 4 '19 at 22:03
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.