¿A dónde va esa serpiente?

35

Escriba una función (utilizando la menor cantidad de bytes posible) que tome una matriz bidimensional de cualquier número de columnas y filas en las que:

  • 0 representa bloque vacío,
  • 1 representa el bloque de serpiente.

La función debe devolver el número de caminos posibles que recorrió la serpiente.

Ejemplo 1:

Entrada:

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

Salida: 2

En el ejemplo anterior, la función regresará 2porque la respuesta es una de:

ingrese la descripción de la imagen aquí

Ejemplo 2

Entrada:

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

Salida: 6

En este ejemplo, la función regresará 6porque la respuesta es una de:

ingrese la descripción de la imagen aquí

Nota:

Al evaluar la entrada, puede suponer que:

  • Las matrices que representan columnas siempre tendrán los mismos tamaños (por lo que las matrices son rectangulares);
  • Existe al menos 1 ruta válida;
  • La serpiente no puede caminar a través de los bordes (como puede suceder en algunas versiones de serpiente);
  • La serpiente siempre tendrá al menos 2 bloques;
  • La serpiente no puede moverse en diagonal;
  • Los caminos están dirigidos. (por lo tanto, dos rutas que terminan en diferentes posiciones pero que se ven exactamente iguales no son la misma ruta, se sumarán al total)
Adelin
fuente
13
Bienvenido a PPCG! Bonito primer desafío.
Laikoni
55
Nota menor: "Siempre habrá al menos una fila y una columna" es redundante, dado que la serpiente siempre tendrá al menos 2 bloques.
Stewie Griffin
2
Casos de prueba sugeridos: el dado por @StewieGriffin y [[0,0,1,1],[0,0,1,1],[0,0,1,1]]. La mayoría de las respuestas dan 16, pero una da 15.
Kevin Cruijssen
2
Parece que todo el mundo hasta ahora (incluido yo) ha asumido que 2 caminos que terminan en diferentes posiciones pero que, por lo demás, se ven exactamente igual no son el mismo camino. Creo que esto debe especificarse explícitamente.
Arnauld
2
@Arnauld, eso es correcto. Dos caminos que terminan en diferentes posiciones pero que, de lo contrario, se ven exactamente iguales no son el mismo camino , sumarán el total. En su ejemplo, el total debería ser 16 si no me equivoco. No puedo calcular con precisión en este momento, pero usted entiende el punto
Adelin

Respuestas:

11

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

Declaración de importación de biblioteca (16 bytes):

<<Combinatorica`

Cuerpo de función real (83 bytes):

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

Pruébalo en línea!


Tenga en cuenta que la pregunta solo pide el número de ruta hamiltoniana en el gráfico.

Sin embargo, (por alguna razón) la HamiltonianPathfunción realmente no funciona con el gráfico dirigido ( ejemplo ). Entonces, utilicé la solución descrita en esta pregunta de Mathematica.SE :

  • Agregue un vértice (llamado True) que esté conectado a todos los demás vértices.
  • Cuente el número de ciclos hamiltonianos en el gráfico resultante.

El gráfico se construye usando MakeGraph(molestamente, no hay una función incorporada directamente equivalente), usando la función booleana ##||Norm[#-#2]==1&, que devuelve Truesi y solo si uno de los argumentos es Trueo la distancia entre los dos vértices es 1.


Tr[1^x]no se puede usar en lugar de Length@x, y <2no se puede usar en lugar de ==1.


HamiltonianPathse puede usar si el gráfico no está dirigido, con el cuerpo de la función toma 84 bytes (exactamente 1 byte más que el envío actual):

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

Pruébalo en línea!

usuario202729
fuente
10

JavaScript (ES6), 154134 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

Pruébalo en línea!

¿Cómo?

Método

Comenzando desde cada celda posible, inundamos la matriz, limpiando todas las celdas en nuestro camino. Siempre que la matriz no contenga más 1 's, incrementamos el número n de posibles caminos.

Cada ruta válida se cuenta 4 veces debido a la dirección elegida en la última celda, que en realidad no importa. Por lo tanto, el resultado final es n / 4 .

Función recursiva

En lugar de llamar a la función recursiva g () desde la devolución de llamada del segundo mapa () de esta manera ...

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

... definimos la función recursiva g () directamente como la devolución de llamada de map () :

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

A pesar de la fórmula bastante larga y=1/y?y:Yque se necesita para establecer el valor inicial de y , esto ahorra 2 bytes en general.

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
fuente
10

Jalea , 12 11 bytes

ŒṪŒ!ạƝ€§ÐṂL

Pruébalo en línea!


Explicación.

ŒṪ               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].
usuario202729
fuente
Las nuevas características demuestran ser extremadamente útiles.
user202729
¿Qué tal en §ỊMLlugar de §ỊP€Sguardar un byte? Creo que debería funcionar.
Jonathan Allan
... o §ÐṂLque es un poco más rápido.
Jonathan Allan
@JonathanAllan Solo funciona si el resultado es distinto de cero.
user202729
@JonathanAllan Entonces termina realmente funciona.
user202729
8

Pitón 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)))

Pruébalo en línea!


Salvado

  • -8 bytes, gracias a Kevin Cruijssen
  • -14 bytes, gracias al usuario202729
TFeld
fuente
1
249 bytes eliminando wyh
Kevin Cruijssen
1
¿El idioma correcto para el trabajo?
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)

Pruébalo en línea!

KSab
fuente
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

Pruébalo en línea!

usuario28667
fuente