Para onde está indo a cobra?

35

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á 2porque a resposta é uma das seguintes:

insira a descrição da imagem aqui

Exemplo 2:

Entrada:

[
  [1,1,1,1],
  [0,0,1,1],
  [0,0,1,1],
]

Saída: 6

Neste exemplo, a função retornará 6porque a resposta é uma das seguintes:

insira a descrição da imagem aqui

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)
Adelin
fonte
13
Bem-vindo ao PPCG! Bom primeiro desafio.
Laikoni
5
Nota secundária: "Sempre haverá pelo menos uma linha e uma coluna" é redundante, pois a cobra sempre terá pelo menos 2 blocos.
Stewie Griffin
2
Casos de teste sugeridos: o fornecido por @StewieGriffin e [[0,0,1,1],[0,0,1,1],[0,0,1,1]]. A maioria das respostas dar 16, mas dá 15.
Kevin Cruijssen
2
Parece que todo mundo até agora (inclusive eu) assumiu que 2 caminhos terminam em posições diferentes, mas que parecem exatamente iguais não são o mesmo caminho. Eu acho que isso precisa ser explicitamente especificado.
Arnauld
2
@ Arnauld - isso mesmo. Dois caminhos que terminam em posições diferentes, mas de outra forma parecendo exatamente o mesmo não são o mesmo caminho , isso somará o total. No seu exemplo o total deve ser de 16, se não me engano - Não posso accuratelly calcular agora, mas você começa o ponto
Adelin

Respostas:

11

Wolfram Language (Mathematica) , 16 + 83 = 99 bytes

Declaração de importação da biblioteca (16 bytes):

<<Combinatorica`

Corpo real da função (83 bytes):

Length@HamiltonianCycle[MakeGraph[#~Position~1~Join~{1>0},##||Norm[#-#2]==1&],All]&

Experimente online!


Observe que a pergunta apenas pede o número de caminhos hamiltonianos no gráfico.

No entanto, (por algum motivo) a HamiltonianPathfunção não funciona realmente com gráfico direcionado ( exemplo ). Então, usei a solução alternativa descrita nesta pergunta do Mathematica.SE :

  • Adicione um vértice (chamado True) conectado a todos os outros vértices.
  • Conte o número de ciclos hamiltonianos no gráfico resultante.

O gráfico é construído usando MakeGraph(irritantemente não há embutido diretamente equivalente), usando a função booleana ##||Norm[#-#2]==1&, que retorna Truese e somente se um dos argumentos for Trueou a distância entre os dois vértices 1.


Tr[1^x]não pode ser usado em vez de Length@xe <2não pode ser usado em vez de ==1.


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

Length@HamiltonianPath[MakeGraph[#~Position~1,Norm[#-#2]==1&,Type->Undirected],All]&

Experimente online!

user202729
fonte
10

JavaScript (ES6), 154 134 bytes

m=>m.map((r,Y)=>r.map(g=(_,x,y,r=m[y=1/y?y:Y])=>r&&r[x]&&[-1,0,1,2].map(d=>r[r[x]=0,/1/.test(m)?g(_,x+d%2,y+~-d%2):++n,x]=1)),n=0)|n/4

Experimente 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 ...

m=>m.map((r,y)=>r.map((_,x)=>(g=(x,y,r=m[y])=>...g(x+dx,y+dy)...)(x,y)))

... definimos a função recursiva g () diretamente como o retorno de chamada de map () :

m=>m.map((r,Y)=>r.map(g=(_,x,y,r=m[y=1/y?y:Y])=>...g(_,x+dx,y+dy)...))

Apesar da fórmula bastante longa y=1/y?y:Ynecessária para definir o valor inicial de y , isso economiza 2 bytes no geral.

Código comentado

m =>                           // given the input matrix m[][]
  m.map((r, Y) =>              // for each row r[] at position Y in m[][]:
    r.map(g = (                //   for each entry in r[], use g() taking:
      _,                       //     - the value of the cell (ignored)
      x,                       //     - the x coord. of this cell
      y,                       //     - either the y coord. or an array (1st iteration),
                               //       in which case we'll set y to Y instead
      r = m[y = 1 / y ? y : Y] //     - r = the row we're currently located in
    ) =>                       //       (and update y if necessary)
      r && r[x] &&             //     do nothing if this cell doesn't exist or is 0
      [-1, 0, 1, 2].map(d =>   //     otherwise, for each direction d,
        r[                     //     with -1 = West, 0 = North, 1 = East, 2 = South:
          r[x] = 0,            //       clear the current cell
          /1/.test(m) ?        //       if the matrix still contains at least one '1':
            g(                 //         do a recursive call to g() with:
              _,               //           a dummy first parameter (ignored)
              x + d % 2,       //           the new value of x
              y + ~-d % 2      //           the new value of y
            )                  //         end of recursive call
          :                    //       else (we've found a valid path):
            ++n,               //         increment n
          x                    //       \_ either way,
        ] = 1                  //       /  do r[x] = 1 to restore the current cell to 1
      )                        //     end of map() over directions
    ),                         //   end of map() over the cells of the current row
    n = 0                      //   start with n = 0
  ) | n / 4                    // end of map() over the rows; return n / 4
Arnauld
fonte
10

Geléia , 12 11 bytes

ŒṪŒ!ạƝ€§ÐṂL

Experimente online!


Explicação.

ŒṪ               Positions of snake blocks.
  Œ!             All permutations.
                 For each permutation:
    ạƝ€             Calculate the absolute difference for each neighbor pair
       §            Vectorized sum.
                 Now we have a list of Manhattan distance between snake
                    blocks. Each one is at least 1.
        ÐṂL      Count the number of minimum values.
                    Because it's guaranteed that there exists a valid snake,
                    the minimum value is [1,1,1,...,1].
user202729
fonte
Novos recursos provam ser extremamente úteis.
User202729 18/0418
Que tal em §ỊMLvez de §ỊP€Ssalvar um byte - acho que deve funcionar?
Jonathan Allan
... ou §ÐṂLque é um pouco mais rápido.
Jonathan Allan
@JonathanAllan Só funciona se o resultado for diferente de zero.
User202729 #
@ JonathanAllan Então, ele realmente funciona.
User202729 19/0518
8

Python 2 , 257 246 241 234 233 227 214 210 bytes

lambda b:sum(g(b,i,j)for j,l in e(b)for i,_ in e(l))
e=enumerate
def g(b,x,y):d=len(b[0])>x>-1<y<len(b);c=eval(`b`);c[d*y][d*x]=0;return d and b[y][x]and('1'not in`c`or sum(g(c,x+a,y)+g(c,x,y+a)for a in(1,-1)))

Experimente online!


Salvou

  • -8 bytes, graças a Kevin Cruijssen
  • -14 bytes, graças a user202729
TFeld
fonte
11
249 bytes removendo weh
Kevin Cruijssen 18/18
11
O idioma certo para o trabalho?
Neil
5

Python 2, 158 bytes

E=enumerate
g=lambda P,x,y:sum(g(P-{o},*o)for o in P if x<0 or abs(x-o[0])+abs(y-o[1])<2)+0**len(P)
lambda L:g({(x,y)for y,r in E(L)for x,e in E(r)if e},-1,0)

Experimente online!

KSab
fonte
3

Haskell , 187 155 bytes

r=filter
l=length
(a,b)?(x,y)=abs(a-x)+abs(b-y)==1
l#x=sum[p!r(/=p)l|p<-x]
p![]=1
p!l=l#r(p?)l
f x|l<-[(i,j)|i<-[0..l x-1],j<-[0..l(x!!0)-1],x!!i!!j>0]=l#l

Experimente online!

user28667
fonte