Determinar se uma grade contém outra grade

10

Desafio
Criar uma função recebe duas matrizes bidimensionais de caracteres (ou seqüências de caracteres se a linguagem de programação não possuir caracteres como um tipo de dados) como entradas: a e b. Se o seu idioma não suportar essas entradas, você poderá usar qualquer outra variável de um byte padrão.

Sua tarefa é determinar se b contém a. Se assim for, retorne true. Caso contrário, retorne false.

Casos de teste de amostra

a:

123
456
789

b:

123
456
789

deve retornar verdadeiro.

a:

code
golf

b:

thisis
code!!
golf!!
ohyeah

deve retornar verdadeiro.

a:

abcd
efgh
ijkl

b:

abcdef
ghijkl
mnopqr

deve retornar false.

a:

abc
def

b:

1abc2
3def4
5ghi6

deve retornar verdadeiro

a:

ab
cd

b:

#ab##
##cd#

deve retornar falso

Menos bytes ganham.

Perigo
fonte
2
Olá e bem-vindo ao codegolf! Editei seus casos de teste para (espero) torná-los um pouco mais claros. Observe que temos um sandbox para trabalhar nos desafios antes de publicá-los no main. Boa sorte!
FryAmTheEggman
2
Além disso, posso usar a primeira matriz como uma matriz de seqüências de caracteres e a segunda como uma sequência separada por novas linhas, mesmo que meu idioma (C #) tenha um tipo de caractere incorporado?
Modalidade de ignorância
Os casos de teste @ Neil 2 e 3 não são quadrados.
Robin Ryder
5
Você poderia adicionar um caso de teste de averdade onde não está na bborda esquerda de um caso de teste de Falsey em que cada linha aaparece em linhas consecutivas, bmas com as bordas esquerdas escalonadas?
Shaggy
@EmbodimentofIgnorance yes
Perigo

Respostas:

9

Braquilog (v2), 4 bytes

s\s\

Experimente online!

Mais facilmente executado como um programa completo, como de costume para um , com um especificado como argumento da linha de comandos, b na entrada padrão. A pergunta pede uma função, e o programa também funciona como uma função, com b à esquerda, a à direita e saída através da produção de uma exceção se e somente se a decisão for falsa .

Explicação

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}

O "afirmar retangular" é, obviamente, inútil, como a questão já garante isso. O restante do programa faz a busca por grade, identificando uma subcadeia de linhas e colunas, ou seja, uma submatriz.

Meta-discussão

Já tivemos uma pergunta muito parecida antes; Eu esperaria que a maioria das respostas para uma pergunta fosse modificável em respostas para a outra. Eu acho que essa é a versão mais limpa, no entanto.

ais523
fonte
Resposta mais curta aqui, então eu aceito.
Hazard
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

Experimente online!

Recebe entradas como listas de tuplas de caracteres.

Tenta todas as sub-grades be verifica se aestá entre elas. As sub-grades são geradas ramificando-se recursivamente, removendo a primeira linha bou girando-a 90 graus. Após exatamente quatro rotações, verifica se o recortado bé igual a a.

xnor
fonte
11
@mazzy Acho que as grades de entrada devem ser retângulos.
Xnor
5

J , 21 15 8 7 bytes

1#.,@E.

Experimente online!

-7 bytes graças a Bolce Bussiere

resposta original

J , 21 15 bytes

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

Experimente online!

-6 bytes graças ao FrownyFrog

como

  • <@[ caixa esquerda arg
  • $@[<;.3] todos os retângulos no argumento direito com a mesma forma que o argumento esquerdo
  • agora passe aqueles como o argumento esquerdo e direito para ...
  • é o argumento esquerdo e um olmo do argumento direito, depois de aplanar ambos e.&,
Jonah
fonte
Eu acho que isso pode ser<@[e.&,$@[<;.3]
FrownyFrog
Ah, claro, ty! Se você quer um desafio, dê uma olhada nessa monstruosidade com a qual eu maculei o site.
Jonah
11
-7 Bytes: +/@:,@E.. E. é praticamente feito para esse desafio.
Bolce Bussiere
tyvm @BolceBussiere. Vou atualizar isso hoje à noite.
Jonah
4

Carvão , 26 bytes

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

Experimente online! Link é a versão detalhada do código. Altamente baseado em minha resposta para Contar as submatrizes contíguas , a única diferença é que, em vez de pegar a soma das correspondências, eu levo o máximo e, devido à conversão implícita de strings devido ao uso do resultado, já é uma string que salva um byte.

Neil
fonte
4

05AB1E , 10 bytes

øŒεøŒI.å}à

Toma bcomo primeira entrada,a como segundo. Ambas as entradas como matrizes de caracteres.

Porto da resposta 05AB1E de @ Mr.Xcoder para este desafio relacionado , portanto, certifique-se de o vota!

Experimente online ou verifique todos os casos de teste .

Explicação:

øŒ          # 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
fonte
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])))

Experimente online!

Chas Brown
fonte
@ Neil: Corrigido agora.
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)))

Experimente online!

Alterar:

  • m[i]in xand n[z]into l: esqueci totalmente que essas variáveis ​​já foram instanciadas
  • &&into &: Ambos os lados do operador já são booleanos, portanto um operador bit a bit funcionará

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

Experimente online!

Alterar:

  • map((c,j)=>{...}).some(s=>s)em some((c,j)=>{...}): Redundância
  • m[i+z].join()into m[i+z]+'': uma maneira mais curta de converter a matriz em uma string
  • indexOf(n[z].join(),j)into indexOf(n[z],j): O indexOf método já se converte n[z] em uma 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))

Experimente online!

Legível:

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

Em vez de comparar valores individuais, verifiquei se as linhas da grade N foram incluídas nas linhas da grade M e, em caso afirmativo, em quais índices. Se todas as linhas forem incluídas iniciando no mesmo índice, a grade N estará contida na grade M.

M. Paviza
fonte
2

PowerShell , 71 102 85 98 bytes

obrigado @Jo King; casos de teste adicionados.

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

Experimente online!

Menos golfe:

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
confuso
fonte
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}

Experimente online

Johan du Toit
fonte