Cycles sur le tore

20

Défi

Ce défi vous obligera à écrire un programme qui prend deux entiers net mgénère le nombre de boucles sans intersection sur le nby mtorus faites en commençant par (0,0)et en ne faisant que des pas vers le haut et vers la droite. Vous pouvez considérer le tore comme la grille avec un enroulement à la fois en haut et en bas et sur les côtés.

C'est le donc le moins d'octets gagne.

Exemple

Par exemple, si l'entrée est n=m=5, une marche valide est

(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)

comme le montre le graphique.

Une boucle sur le tore.

Quelques exemples d'entrées / sorties

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
la source
1
J'étais prêt à parier que cette séquence était sur OEIS pendant au moins , mais apparemment ce n'est pas (encore). m=n
Arnauld
Je pense qu'un tore a également un enveloppement gauche-droite. Devrions-nous supposer qu'il a uniquement un enveloppement de haut en bas? L'image d'exemple ne semble pas impliquer en tant que telle.
Erik the Outgolfer
@EriktheOutgolfer L'image montre le chemin orange qui s'enroule de droite à gauche, n'est-ce pas?
Arnauld
@Arnauld Oui, mais cela ne semble pas cohérent avec la description du défi ("Vous pouvez penser à Torus comme la grille avec un bouclage en haut et en bas.")
Erik the Outgolfer
@EriktheOutgolfer C'est vrai. Et maintenant que vous le mentionnez, le chemin bleu est faux. Il doit d'abord s'enrouler de droite à gauche puis de haut en bas.
Arnauld

Réponses:

4

Gelée , 28 octets

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

Un lien monadique acceptant une liste [m,n], ce qui donne le compte.

TIO-jt1qe1v9 ... bien qu'il y ait peu d'intérêt, c'est beaucoup trop inefficace.
(Je ne peux même pas courir[2,3]localement avec 16 Go de RAM)!

Comment?

Force brute - crée les coordonnées d'une version en mosaïque assez grande, puis filtre l'ensemble de puissance de ces points sur les chemins dont les voisins n'augmentent que d'un dans une seule direction, puis filtre ceux qui commencent à une coordonnée minimale (c'est-à-dire l'origine) et, en même temps, supprime cette coordonnée de départ de chacun. Utilise ensuite l'arithmétique modulo pour revenir à un tore et filtre toutes les coordonnées en double contenant (c'est-à-dire celles contenant des intersections) et, enfin, filtre celles qui ont des coordonnées de fin minimales (c'est-à-dire se terminant à l'origine) et donne la longueur du résultat.

ạƝ§=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
la source
12

Python 2 , 87 octets

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

Essayez-le en ligne!

La chose intéressante ici est d'utiliser un nombre complexe zpour stocker les coordonnées de la position actuelle. Nous pouvons monter en ajoutant 1et aller à droite en ajoutant 1j. À ma grande surprise, modulo travaille sur des nombres complexes d'une manière qui nous permet de gérer le wrapping pour chaque dimension séparément: faire des %mactes sur la partie réelle et %(n*1j)agir sur la partie imaginaire.

xnor
la source
Bien fait. FWIW, ma meilleure tentative sans utiliser un nombre complexe est de 91 octets en Python 3.8.
Arnauld
@Arnauld Idée intéressante avec le k:=x+y*m. Cela me fait me demander s'il serait plus court d'utiliser kdirectement pour (x,y), en utilisant x+y*mplutôt qu'en x+y*1j. Dommage Python 3 ne permet pas de module complexe.
xnor
Cette approche permet d'économiser 5 octets dans JS. :)
Arnauld
7

JavaScript (ES6), 67 octets

m×n<32

Prend l'entrée comme (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))``

Essayez-le en ligne!

Pour le faire fonctionner pour n'importe quelle entrée, nous pourrions utiliser BigInts pour 73 octets :

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)

Essayez-le en ligne!


JavaScript (ES6),  76 73  72 octets

Prend l'entrée comme (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)

Essayez-le en ligne!

Commenté

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
la source
3

Haskell, 88 80 octets

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$[]

Essayez-le en ligne!

Force brute simple: essayez toutes les combinaisons haut / droite, supprimez celles qui se croisent (nous gardons toutes les positions que nous avons visitées dans la liste a) et comptez celles qui finissent par atteindre la position (0,0).

Le cas de base de la récursivité est lorsque nous visitons une position une deuxième fois ( elem(x,y)a). Le résultat est 0^0= 1lorsque la position est (0,0)et compte pour le nombre de boucles ou 0( 0^x, avec xnon nul) sinon et n'augmente pas le nombre de boucles.

Edit: -8 octets grâce à @xnor.

nimi
la source
1
Les cas de base peuvent être combinés |elem(x,y)a=0^(x+y)et (0!0)[]peuvent l'être 0!0$[].
xnor
2

Gelée , 44 octets

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

Essayez-le en ligne!

O(2mn)

mn

Nick Kennedy
la source
1

Java 8, 120 octets

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);}

nm<32

Essayez-le en ligne.

Kevin Cruijssen
la source
1

CJam (50 caractères)

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

Démo en ligne . Il s'agit d'un programme qui prend deux entrées de stdin.

Enfin, nous avons une réponse à la question

La guerre, hein, à quoi ça sert?


Dissection

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
la source
1

Gelée , 54 39 octets

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

Essayez-le en ligne!

J'ai posté cela comme une réponse distincte à mon autre Jelly car c'est une méthode complètement différente. Ceci est plus proche en principe de la réponse de @ Arnauld. Il utilise une fonction récursive qui fonctionne à travers tous les chemins possibles jusqu'à ce qu'il atteigne un point déjà atteint, puis retourne le résultat d'une vérification pour savoir s'il est de retour au début. Je soupçonne que quelques octets supplémentaires pourraient être rasés. Maintenant changé en utilisant l'opérateur de tranche. Cela fonctionne bien jusqu'à 5x5. La profondeur de récursivité doit être au plus mx n.

Nick Kennedy
la source