Ciclos en el toro

20

Desafío

Este desafío tendrá que escribir un programa que toma en dos enteros ny my da salida a los números de bucles que no se cruzan en el nde mtoro hechas comenzando en (0,0)y sólo dando pasos hacia arriba y hacia la derecha. Puedes pensar en el toro como la cuadrícula con envoltura tanto en la parte superior como en la inferior y en los lados.

Este es el por lo que gana menos bytes.

Ejemplo

Por ejemplo, si la entrada es n=m=5, una caminata válida es

(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,3) -> (2,4) -> 
(2,0) -> (3,0) -> (4,0) -> (4,1) -> (4,2) -> (4,3) -> 
(0,3) -> (1,3) -> (1,4) -> 
(1,0) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3) -> (3,4) -> (4,4) -> 
(0,4) -> (0,0)

como se muestra en el gráfico.

Un bucle en el toro.

Algunos ejemplos de entradas / salidas

f(1,1) = 2 (up or right)
f(1,2) = 2 (up or right-right)
f(2,2) = 4 (up-up, up-right-up-right, right-right, right-up-right-up)
f(2,3) = 7
f(3,3) = 22
f(2,4) = 13
f(3,4) = 66
f(4,4) = 258
Peter Kagey
fuente
1
metro=norte
Creo que un toro también tiene una envoltura izquierda-derecha. ¿Deberíamos suponer que solo tiene una envoltura de arriba hacia abajo? La imagen de ejemplo no parece implicar como tal.
Erik the Outgolfer
@EriktheOutgolfer La imagen muestra el camino naranja envolviéndose de derecha a izquierda, ¿no?
Arnauld
@Arnauld Sí, pero no parece coherente con la descripción del desafío ("Puedes pensar en el toro como la cuadrícula con envoltura tanto en la parte superior como en la inferior")
Erik the Outgolfer
@EriktheOutgolfer Eso es cierto. Y ahora que lo mencionas, el camino azul está mal. Primero debe envolverse de derecha a izquierda y luego de arriba a abajo.
Arnauld

Respuestas:

4

Jalea , 28 bytes

ạƝ§=1Ȧ
²‘p/’ŒPÇƇḢÐṂ%⁸QƑƇṪÐṂL

Un enlace monádico que acepta una lista [m,n], que produce el recuento.

TIO-jt1qe1v9 ... aunque tiene poco sentido, es demasiado ineficiente.
(¡Ni siquiera puedo ejecutar[2,3]localmente con 16 GB de RAM)!

¿Cómo?

Fuerza bruta: crea coordenadas de una versión en mosaico lo suficientemente grande, luego filtra el conjunto de potencia de estos puntos a esos caminos con vecinos que solo aumentan en uno en una sola dirección, luego filtra a aquellos que comienzan en una coordenada mínima (es decir, el origen) y, al mismo tiempo, elimina esta coordenada de inicio de cada uno. Luego usa la aritmética de módulo para regresar a un toro y filtra cualquier coordenada que contenga duplicados (es decir, aquellos que contienen intersecciones) y, finalmente, filtra a aquellos con coordenadas finales mínimas (es decir, que termina en el origen) y produce la longitud del resultado.

ạƝ§=1Ȧ - Link 1: all neighbours differ by 1 in exactly one direction
 Ɲ     - for neighbours:
ạ      -   absolute difference
  §    - sum each
   =1  - equal to one (vectorises)
     Ȧ - any and all? (falsey if empty or contains a falsey value when flattened)

²‘p/’ŒPÇƇḢÐṂ%⁸QƑƇṪÐṂL - Main Link: list of integers, [m,n]
²                     - square (vectorises) -> [m*m, n*n]
 ‘                    - increment (vectorises) -> [m*m+1, n*n+1]
   /                  - reduce with:
  p                   -   Cartesian product
    ’                 - decrement (vectorises) -> all the coordinates of an m*m by n*n grid
                      -                           including [0, 0] and [m*m, n*n] 
     ŒP               - power-set -> all paths going either up OR right at each step, but not
                      -              necessarily by only 1, and
                      -              necessarily both up and right (e.g. [...[1,3],[5,7],[6,2],...])
        Ƈ             - filter keep those for which:
       Ç              -   call last Link (1) as a monad
                      -              ...now all remaining paths do only go in steps
                      -              of one up or one right
          ÐṂ          - filter keep those minimal under:
         Ḣ            -   head - removes the 1st coordinate from each and yields them for the filter
                      -          ...so only those which started at [0,0] but without it
            %⁸        - modulo by the left argument ([m,n]) (vectorises)
                Ƈ     - filter keep those for which:
               Ƒ      -   is invariant when:
              Q       -     de-duplicated
                      -          ...so no repetitions of torus coordinates (and we already removed
                      -          the first [0,0] which must be present exactly twice)
                  ÐṂ  - filter keep those minimal under:
                 Ṫ    -   tail
                      -          ...so only those which ended at [0,0] 
                    L - length
Jonathan Allan
fuente
12

Python 2 , 87 bytes

f=lambda m,n,z=0,l=[]:z==0if z in l else sum(f(m,n,(z+d)%m%(n*1j),l+[z])for d in(1,1j))

Pruébalo en línea!

Lo interesante aquí es usar un número complejo zpara almacenar la coordenada de la posición actual. Podemos subir agregando 1y mover a la derecha agregando 1j. Para mi sorpresa, el módulo funciona en números complejos de una manera que nos permite manejar el ajuste para cada dimensión por separado: haciendo %mactos en la parte real y %(n*1j)actos en la parte imaginaria.

xnor
fuente
Bien hecho. FWIW, mi mejor intento sin usar un número complejo es 91 bytes en Python 3.8.
Arnauld
@Arnauld Interesante idea con el k:=x+y*m. Me hace preguntarme si sería más corto usarlo kdirectamente (x,y), usarlo en x+y*mlugar de hacerlo x+y*1j. Lástima que Python 3 no permita módulos complejos.
xnor
Este enfoque ahorra 5 bytes en JS. :)
Arnauld
7

JavaScript (ES6), 67 bytes

metro×norte<32

Toma entrada como (m)(n).

m=>n=>(g=(k,l)=>l>>k&1?!k:g((k+m)%(m*n),l|=1<<k)+g(k-~k%m-k%m,l))``

Pruébalo en línea!

Para que funcione para cualquier entrada, podríamos usar BigInts para 73 bytes :

m=>n=>(g=(k,l=k)=>l&(b=1n<<k)?!k:g((k+m)%(m*n),l|=b)+g(k-~k%m-k%m,l))(0n)

Pruébalo en línea!


JavaScript (ES6),  76 73  72 bytes

Toma entrada como (m)(n).

m=>n=>(g=(x,y)=>g[x+=y*m]?!x:g(-~x%m,y,g[x]=1)+g(x%m,-~y%n)+--g[x])(0,0)

Pruébalo en línea!

Comentado

m => n => (         // m = width; n = height
  g = (             // g is a recursive function taking:
        x, y        //   the current coordinates (x, y) on the torus
      ) =>          //
    g[              // the surrounding object of g is also used for storage
      x += y * m    // turn x into a key for the current coordinates
    ] ?             // if this cell was already visited:
      !x            //   return 1 if we're back to (0, 0), or 0 otherwise
    :               // else:
      g(            //   first recursive call:
        -~x % m,    //     move to the right
        y,          //     leave y unchanged
        g[x] = 1    //     mark the current cell as visited by setting the flag g[x]
      ) +           //   add the result of
      g(            //   a second recursive call:
        x % m,      //     restore x in [0...m-1]
        -~y % n     //     move up
      ) +           //
      --g[x]        //   clear the flag on the current cell
)(0, 0)             // initial call to g with (x, y) = (0, 0)
Arnauld
fuente
3

Haskell, 88 80 bytes

n#m|let(x!y)a|elem(x,y)a=0^(x+y)|b<-(x,y):a=(mod(x+1)n!y)b+(x!mod(y+1)m)b=0!0$[]

Pruébalo en línea!

Fuerza bruta simple: intente todas las combinaciones arriba / derecha, descartando las que se cruzan (mantenemos todas las posiciones que hemos visitado en la lista a) y contando las que finalmente llegan a la posición positiva (0,0)nuevamente.

El caso base de la recursión es cuando visitamos una posición por segunda vez ( elem(x,y)a). El resultado es 0^0= 1cuando la posición es (0,0)y cuenta hacia el número de bucles o 0( 0^x, con xno-cero) de otra manera y no aumenta el número de bucles.

Editar: -8 bytes gracias a @xnor.

nimi
fuente
1
Los casos base se pueden combinar |elem(x,y)a=0^(x+y)y (0!0)[]pueden ser 0!0$[].
xnor
2

Jalea , 44 bytes

×ƝṪ2*Ḥ_2Rḃ€2ċⱮؽ%³¬ẠƲƇịØ.Ṛ,Ø.¤ZÄZ%€ʋ€³ŒQẠ$€S

Pruébalo en línea!

O(2metronorte)

metronorte

Nick Kennedy
fuente
1

Java 8, 120 bytes

n->m->g(n,m,0,0);int g(int n,int m,int k,int l){return(l>>k)%2>0?k<1?1:0:g(n,m,(k+m)%(m*n),l|=1<<k)+g(n,m,k-~k%m-k%m,l);}

nortemetro<32

Pruébalo en línea.

Kevin Cruijssen
fuente
1

CJam (50 caracteres)

q~]:M:!a{9Yb2/\f{_W=@.+M.%a+_)a#g"WAR"=~}}:R~e_We=

Demo en línea . Este es un programa que toma dos entradas de stdin.

Finalmente tenemos una respuesta a la pregunta.

Guerra, ¿para qué sirve?


Disección

q~]:M        e# Parse input, collect in array, store in M (for moduli)
:!a          e# Zero and wrap in array for starting position (0, 0)
{            e# Define recursive block R
  9Yb2/      e#   Push [[1 0][0 1]], an array of movements
  \f{        e#   For each of those movements, with the current path,
    _W=@.+   e#     Add the movement to the last position in the path
    M.%      e#     Apply the wrapping
    a+       e#     Add to one copy of the path
    _)a#     e#     And find its index in another copy
    g"WAR"=~ e#     Switch on the sign of the index:
             e#       If the sign is -1, position not found, make a recursive call
             e#       If the sign is 0, found at start, push -1 to the stack
             e#       If the sign is 1, we have a self-intersection. We push 10 to
             e#       the stack for no other reason than to make the bad joke above
  }
}:R
~            e# Execute R
e_We=        e# Count the -1s which we pushed as sentinels
Peter Taylor
fuente
1

Gelatina , 54 39 bytes

ḣ2æ.2ị³¤+4
‘Ç;¥¦%³Ç=4ƊÑÇị$?
çⱮؽS
’Ñ0xÇ

Pruébalo en línea!

He publicado esto como una respuesta separada a mi otra Jelly porque es un método completamente diferente. Esto está más cerca en principio de la respuesta de @ Arnauld. Utiliza una función recursiva que funciona a través de todas las rutas posibles hasta que llega a un punto al que ya llegó, y luego devuelve el resultado de una comprobación de si ha vuelto al inicio. Sospecho que podrían eliminarse unos pocos bytes más. Ahora cambió a usar el operador de corte. Funciona bien para hasta 5x5. La profundidad de recursión debe ser como máximo mx n.

Nick Kennedy
fuente