9
\$\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

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 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 at 21:07
  • \$\begingroup\$ @Neil Test cases 2 and 3 are not square. \$\endgroup\$ – Robin Ryder May 4 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 at 21:34
  • \$\begingroup\$ @EmbodimentofIgnorance yes \$\endgroup\$ – Hazard May 5 at 21:40

10 Answers 10

8
\$\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 at 21:43
6
\$\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.

\$\endgroup\$
  • 1
    \$\begingroup\$ @mazzy I think the input grids are supposed to be rectangles. \$\endgroup\$ – xnor May 7 at 6:17
4
\$\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.&,
\$\endgroup\$
  • \$\begingroup\$ I think this can be <@[e.&,$@[<;.3] \$\endgroup\$ – FrownyFrog May 6 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 at 14:17
  • 1
    \$\begingroup\$ -7 Bytes: +/@:,@E.. E. is pretty much made for this challenge. \$\endgroup\$ – Bolce Bussiere May 6 at 17:49
  • \$\begingroup\$ tyvm @BolceBussiere. i will update this tonight. \$\endgroup\$ – Jonah May 6 at 17:59
3
\$\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.

\$\endgroup\$
3
\$\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)
\$\endgroup\$
2
\$\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!

\$\endgroup\$
  • \$\begingroup\$ @Neil: Fixed now. \$\endgroup\$ – Chas Brown May 4 at 22:03
2
\$\begingroup\$

Wolfram Language (Mathematica), 46 bytes

nOr@@Or@@@BlockMap[#==n&,#,Dimensions@n,1]&

Try it online!

Curried function: call with f[a][b].

Are there shorter alternatives to Or@@Or@@@ or Dimensions?

\$\endgroup\$
2
\$\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.

\$\endgroup\$
1
\$\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
\$\endgroup\$
0
\$\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

\$\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.