Escreva uma função (usando o mínimo de bytes possível) que obtenha uma matriz bidimensional de qualquer número de colunas e linhas nas quais:
0
representa bloco vazio,1
representa bloco de cobra.
A função deve retornar o número de caminhos possíveis que a cobra percorreu.
Exemplo 1:
Entrada:
[
[1,1,1,1,1],
[0,0,0,0,1],
[0,0,0,0,1],
]
Saída: 2
No exemplo acima, a função retornará 2
porque a resposta é uma das seguintes:
Exemplo 2:
Entrada:
[
[1,1,1,1],
[0,0,1,1],
[0,0,1,1],
]
Saída: 6
Neste exemplo, a função retornará 6
porque a resposta é uma das seguintes:
Nota:
Ao avaliar a entrada, você pode assumir que:
- As matrizes que representam colunas sempre terão os mesmos tamanhos (portanto, as matrizes são retangulares);
- Existe pelo menos 1 caminho válido;
- A cobra não pode andar pelas bordas (como pode acontecer em algumas versões da cobra);
- A cobra sempre terá pelo menos 2 blocos;
- A cobra não pode se mover na diagonal;
- Os caminhos são direcionados. (portanto, dois caminhos que terminam em posições diferentes, mas que parecem exatamente iguais não são o mesmo caminho, isso somará o total)
code-golf
grid
binary-matrix
Adelin
fonte
fonte
[[0,0,1,1],[0,0,1,1],[0,0,1,1]]
. A maioria das respostas dar 16, mas dá 15.Respostas:
Wolfram Language (Mathematica) , 16 + 83 = 99 bytes
Declaração de importação da biblioteca (16 bytes):
Corpo real da função (83 bytes):
Experimente online!
Observe que a pergunta apenas pede o número de caminhos hamiltonianos no gráfico.
No entanto, (por algum motivo) a
HamiltonianPath
função não funciona realmente com gráfico direcionado ( exemplo ). Então, usei a solução alternativa descrita nesta pergunta do Mathematica.SE :True
) conectado a todos os outros vértices.O gráfico é construído usando
MakeGraph
(irritantemente não há embutido diretamente equivalente), usando a função booleana##||Norm[#-#2]==1&
, que retornaTrue
se e somente se um dos argumentos forTrue
ou a distância entre os dois vértices1
.Tr[1^x]
não pode ser usado em vez deLength@x
e<2
não pode ser usado em vez de==1
.HamiltonianPath
pode ser usado se o gráfico não for direcionado, com o corpo da função ocupando 84 bytes (exatamente 1 byte a mais que o envio atual):Experimente online!
fonte
JavaScript (ES6),
154134 bytesExperimente online!
Quão?
Método
A partir de cada célula possível, enchemos a matriz, limpando todas as células em nosso caminho. Sempre que a matriz não contém mais 1 , aumentamos o número n de caminhos possíveis.
Cada caminho válido é contado 4 vezes devido à direção escolhida na última célula, o que realmente não importa. Portanto, o resultado final é n / 4 .
Função recursiva
Em vez de chamar a função recursiva g () a partir do retorno de chamada do segundo mapa () como este ...
... definimos a função recursiva g () diretamente como o retorno de chamada de map () :
Apesar da fórmula bastante longa
y=1/y?y:Y
necessária para definir o valor inicial de y , isso economiza 2 bytes no geral.Código comentado
fonte
Geléia ,
1211 bytesExperimente online!
Explicação.
fonte
§ỊML
vez de§ỊP€S
salvar um byte - acho que deve funcionar?§ÐṂL
que é um pouco mais rápido.Python 2 ,
257246241234233227214210 bytesExperimente online!
Salvou
fonte
w
eh
Python 2, 158 bytes
Experimente online!
fonte
Haskell ,
187155 bytesExperimente online!
fonte