Determinar si una cuadrícula contiene otra cuadrícula

10

Desafío
Crear una función toma dos matrices bidimensionales de caracteres (o cadenas si el lenguaje de programación no tiene caracteres como tipo de datos) como entradas: a y b. Si su idioma no admite estas entradas, puede usar cualquier otra variable estándar de un byte.

Su tarea es determinar si b contiene a. Si es así, devuelve verdadero. De lo contrario, devuelve falso.

Ejemplos de casos de prueba

a:

123
456
789

b:

123
456
789

debería volver cierto.

a:

code
golf

b:

thisis
code!!
golf!!
ohyeah

debería volver cierto.

a:

abcd
efgh
ijkl

b:

abcdef
ghijkl
mnopqr

debería devolver falso.

a:

abc
def

b:

1abc2
3def4
5ghi6

debería volver verdadero

a:

ab
cd

b:

#ab##
##cd#

debería devolver falso

Menos bytes gana.

Peligro
fuente
2
Hola y bienvenido a codegolf! Edité sus casos de prueba para (con suerte) aclararlos un poco. Tenga en cuenta que tenemos un entorno limitado para trabajar en los desafíos antes de publicarlos en main. ¡Buena suerte!
FryAmTheEggman
2
Además, ¿puedo tomar la primera matriz como una matriz de cadenas y la segunda como una cadena separada por nuevas líneas, a pesar de que mi lenguaje (C #) tiene un tipo de caracteres incorporado?
Encarnación de la ignorancia
@Neil Los casos de prueba 2 y 3 no son cuadrados.
Robin Ryder
55
¿Podría agregar un caso de prueba de verdad donde ano está en bel borde izquierdo y un caso de prueba falsey donde cada línea aaparece en líneas consecutivas bpero con sus bordes izquierdos escalonados?
Shaggy
@EmbodimentofIgnorance sí
Hazard

Respuestas:

9

Brachylog (v2), 4 bytes

s\s\

Pruébalo en línea!

Se ejecuta más fácilmente como un programa completo, como de costumbre para un , con un argumento especificado como línea de comando, b en la entrada estándar. La pregunta solicita una función, y el programa también funciona como una función, con b a la izquierda, a a la derecha y la salida produce una excepción si y solo si la decisión es falsa .

Explicación

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}

La "afirmación rectangular" obviamente no tiene sentido, ya que la pregunta ya lo garantiza. El resto del programa realiza la búsqueda de la cuadrícula al identificar una subcadena de las filas y las columnas, es decir, una submatriz.

Meta-discusión

Hemos tenido una pregunta muy similar antes; Esperaría que la mayoría de las respuestas a una pregunta sean modificables en respuestas a la otra. Sin embargo, creo que esta es la versión más ordenada.

ais523
fuente
La respuesta más corta aquí, así que la aceptaré.
Peligro
7

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

Pruébalo en línea!

Toma datos como listas de tuplas de personajes.

Intenta todas las cuadrículas secundarias by comprueba si aestá entre ellas. Las subcuadrículas se generan ramificando recursivamente al quitar la primera fila bo al girarla 90 grados. Después de exactamente cuatro rotaciones, verifica si el recorte bes igual a a.

xnor
fuente
1
@mazzy Creo que se supone que las cuadrículas de entrada son rectángulos.
xnor
5

J , 21 15 8 7 bytes

1#.,@E.

Pruébalo en línea!

-7 bytes gracias a Bolce Bussiere

respuesta original

J , 21 15 bytes

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

Pruébalo en línea!

-6 bytes gracias a FrownyFrog

cómo

  • <@[ en caja izquierda arg
  • $@[<;.3] todos los rectángulos en el argumento derecho con la misma forma que el argumento izquierdo
  • ahora pasa esos como el argumento izquierdo y derecho a ...
  • es el argumento izquierdo un olmo del argumento derecho, después de aplanar ambos e.&,
Jonás
fuente
Creo que esto puede ser<@[e.&,$@[<;.3]
FrownyFrog
Ah ofc, ty! Si desea un desafío, eche un vistazo a esta monstruosidad con la que profané el sitio
Jonás,
1
-7 Bytes: +/@:,@E.. E. está prácticamente hecho para este desafío.
Bolce Bussiere
tyvm @BolceBussiere. Actualizaré esto esta noche.
Jonás
4

Carbón , 26 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Basado en gran medida en mi respuesta para contar las submatrices contiguas , la única diferencia es que, en lugar de tomar la suma de las coincidencias, tomo el máximo, y debido a la conversión de cadena implícita debido al uso del resultado, ya es una cadena que guarda un byte.

Neil
fuente
4

05AB1E , 10 bytes

øŒεøŒI.å}à

Toma bcomo primera entrada, acomo segunda. Ambas entradas como matrices de caracteres.

El puerto de la respuesta 05AB1E de @ Mr.Xcoder para este desafío relacionado , ¡así que asegúrese de votarlo!

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

øŒ          # 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)
Kevin Cruijssen
fuente
3

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])))

Pruébalo en línea!

Chas Brown
fuente
@Neil: arreglado ahora.
Chas Brown
3

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)))

Pruébalo en línea!

Cambios:

  • m[i]into xand n[z]into l: Olvidé por completo que estas variables ya estaban instanciadas
  • &&into &: Ambos lados del operador ya son booleanos, por lo que funcionará un operador bit a bit

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)))

Pruébalo en línea!

Cambios:

  • map((c,j)=>{...}).some(s=>s)en some((c,j)=>{...}): redundancia
  • m[i+z].join()into m[i+z]+'': una forma más corta de convertir la matriz en una cadena
  • indexOf(n[z].join(),j)into indexOf(n[z],j): el indexOf método ya se convierte n[z] en una cadena

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))

Pruébalo en línea!

Legible:

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)
  })
}

En lugar de comparar valores individuales, verifiqué si las líneas de la cuadrícula N estaban incluidas en las líneas de la cuadrícula M y, de ser así, en qué índices. Si todas las líneas se incluyen a partir del mismo índice, entonces la cuadrícula N está contenida en la cuadrícula M.

M. Paviza
fuente
2

PowerShell , 71 102 85 98 bytes

gracias @Jo King; Se agregaron casos de prueba.

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

Pruébalo en línea!

Menos golfizado:

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
mazzy
fuente
1

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}

Pruébalo en línea

Johan du Toit
fuente