Desafio
Dada uma matriz binária e uma cadeia binária, determine se essa cadeia binária pode ser encontrada iniciando em qualquer ponto da matriz e movendo-se em qualquer direção em qualquer ponto subsequente para formar a cadeia binária. Ou seja, a corda pode ser encontrada dobrada, porém dentro da matriz?
A corda só pode ser dobrada a 90 graus ou 180 graus (conexões de borda; Distância 1 de Manhattan) e não pode se sobrepor a qualquer momento.
Exemplo
Vamos dar o seguinte exemplo:
Matrix:
010101
111011
011010
011011
Snake: 0111111100101
Este é um caso de teste de verdade. Podemos ver a cobra dobrada na seguinte posição:
0-1 0 1 0 1
|
1 1 1-0 1 1
| | | |
0 1 1 0-1-0
| |
0 1-1 0 1 1
Regras
- As brechas padrão se aplicam
- Você pode usar o comprimento da string e a largura e altura da matriz como entrada, se desejar
- Você pode pegar a matriz binária e a cadeia binária como uma cadeia multilinha / matriz de cadeias / cadeia associada a nova linha / qualquer outra coisa associada a cadeia e uma cadeia
- Você pode tomar as dimensões como uma matriz plana em vez de vários argumentos
- Seu programa deve ser finalizado para qualquer matriz 5 x 5 com qualquer sequência de comprimento 10 em menos de um minuto
Limitações
- A matriz não é necessariamente quadrada
- A sequência não ficará vazia
- A cadeia pode ter o comprimento 1
- A sequência não conterá mais quadrados do que o disponível (ou seja,
len(string) <= width(matrix) * height(matrix)
Casos de teste
Truthy
01010
10101
01010
10101
01010
0101010101010101010101010
01110
01100
10010
10110
01101
011111000110100
0
0
10
01
1010
100
010
001
100010001
Falsy
00000
00000
00000
00000
00000
1
10101
01010
10101
01010
10101
11
100
010
001
111
10001
01010
00100
01010
10001
1000100010001000101010100
code-golf
decision-problem
binary-matrix
HyperNeutrino
fonte
fonte
Respostas:
Python 2 ,
275271264249 bytes-1
comH
e removendo uma operação de corte ([:]
).[:]
), usando a atribuição de vários destinos para atribuir um valor a uma entrada visitadav not in "01"
(S=S[1:];M[y][x]=H;
->S=M[y][x]=S[1:];
) e alternando de um if / else ternário para um lógico simples (any(...)if S else 1
->not S or any(...)
).ZeroDivisionError
) quando a cobra é encontrada e retorna uma lista vazia ([]
) quando não há cobra a ser encontrada, que são dois comportamentos distintos.not S or
paraS<[1]or
~S==[]or
.Experimente online!
Explicação
Função Lambda que assume a matriz como uma lista bidimensional de seqüências de caracteres (
"0"
ou"1"
), a cobra como uma lista unidimensional e as dimensões da matriz como dois números inteiros.A função lambda procura na matriz por entradas que correspondam ao primeiro elemento da cobra. Para cada partida encontrada, ele chama
H
com uma cópia profunda da matriz, nenhuma cópia da cobra, as dimensões da matriz e a posição da partida.Quando
H
é chamado, ele removeS
a primeira entrada 'e define a entrada da matriz da posição especificada para algo diferente de"0", "1"
. SeS
'length for zero, ele retornaráTrue
; como se chama recursivamente, a cobra foi encontrada em algum lugar da matriz.Se
S
'length for diferente de zero, ele percorre as quatro direções cardinais, testa se essa posição está na matriz, compara o elemento matrix' nessa posição com o primeiro elemento deS
e - se corresponder - se chama recursivamente.H
Os valores de retorno são canalizados para os quadros da pilha, sempre verificando se pelo menos uma função encontrou uma possível cobra.Saída formatada
Eu aprimorei meu programa para também exibir o caminho que a cobra desliza (se houver). Ele usa o mesmo design de saída ASCII da pergunta. Link TIO .
fonte
m[:]for
~>m*1for
? Pode funcionar.JavaScript (ES6),
138134Não é tão diferente do @ Neil's, mas o que mais poderia ser?
Entrada: matriz como uma sequência de linhas múltiplas, sequência binária, largura (sem contar a nova linha)
Nota: a lógica na função recursiva
r
é um pouco invertida para economizar alguns bytesMenos golfe
Teste
fonte
JavaScript (ES6), 149 bytes
Toma a matriz como uma string delimitada por nova linha, a cobra como uma string e a largura (como um número inteiro). Basicamente baseado na resposta de @ JonathanFrech.
fonte
Mathematica,
180156141153138138104 104 bytesExemplo de entrada
Explicação
GridGraph@{##4}
é umGraph
objeto para uma grade de vértices com vértices adjacentes conectados por arestas, com dimensões{##4}
- ou seja,{#4,#5}
ou{width,height}
.x
(numerados1
em1##4 = width*height
), todos os vértices finaisy
e todos os caminhosp
de comprimento, no máximo,#3
dex
atéy
.""<>Part[Join@@#,p]
extrai os caracteres correspondentes da matriz e os coloca em uma sequência.s
, pesquisando em todos os níveis, porque esta é uma lista muito multidimensional que criamos.Nota: Substituir
#3
por{#3-1}
inFindPath
, de modo a encontrar apenas caminhos com o comprimento exato, é uma grande melhoria em termos de velocidade - mas custa mais 4 bytes.-24 bytes: tomando as dimensões das coisas como entrada
-15 bytes: usando
StringPart
eStringJoin
corretamente+12 bytes: corrigindo o caso tamanho 1
-15 bytes: ...
-2 bytes: tomando o tamanho da matriz como entrada como uma matriz
-32 bytes: usar
Table
para percorrer o caminho evita o usoFunction
, e usarMemberQ[...,s,All]
permite colar a matriz na mesa ao lidar com cobras de comprimento 1.fonte
C # (.NET Core) ,
346341336302297 bytesExperimente online!
5 bytes salvos jogando o
p
incremento5 bytes salvos considerando o comprimento da cobra e começando pela cauda, e removendo um espaço desnecessário
34 bytes salvos lendo o desafio corretamente e vendo que posso entender a altura e a largura da matriz
5 bytes salvos, o caso de teste de elemento único falhou e a correção foi benéfica
Ungolfed
fonte
if(...)return true;
->return ...;
.b[y,x]
precisa ser redefinido em algum momento. (Também pena de erro ortográfico o seu nome na minha resposta.)if(N(x,y,0)>0)return 0<1;
; a primeira aparição dereturn
.Kotlin , 413 bytes
Embelezado
Teste
fonte