Ciclos no toro

20

Desafio

Este desafio terá que escrever um programa que leva dois inteiros ne me devolve o número lacetes não se cruzam no npor mtoro feitas por começando em (0,0)e só tomando medidas para cima e para a direita. Você pode pensar no toro como a grade envolvente, tanto na parte superior quanto na parte inferior e nas laterais.

Este é o pois o menor número de bytes vence.

Exemplo

Por exemplo, se a entrada for n=m=5, uma caminhada válida é

(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 mostrado no gráfico.

Um laço no toro.

Alguns exemplos de entradas / saídas

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
fonte
1
Eu estava disposto a apostar que essa sequência estava no OEIS por pelo menos , mas aparentemente não está (ainda). m=n
Arnauld
Eu acho que um toro também tem uma envolvente esquerda-direita. Devemos supor que ele tenha apenas uma envolvente de cima para baixo? A imagem de exemplo não parece implicar como tal.
Erik the Outgolfer
@EriktheOutgolfer A imagem mostra o caminho laranja passando da direita para a esquerda, não é?
Arnauld
@Arnauld Sim, mas não parece consistente com a descrição do desafio ("Você pode pensar no toro como a grade envolvente, tanto na parte superior quanto na inferior.")
Erik, o Outgolfer, em
@EriktheOutgolfer Isso é verdade. E agora que você mencionou, o caminho azul está errado. Primeiro, envolva da direita para a esquerda e depois de cima para baixo.
Arnauld

Respostas:

4

Gelatina , 28 bytes

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

Um link monádico que aceita uma lista [m,n], que gera a contagem.

TIO-jt1qe1v9 ... embora haja pouco sentido, é muito ineficiente.
(Eu não consigo nem rodar[2,3]localmente com 16GB de RAM)!

Quão?

Força bruta - cria coordenadas de uma versão lado a lado grande o suficiente e filtra o conjunto de potência desses pontos para os caminhos com vizinhos aumentando apenas um em uma única direção, depois filtra para aqueles que começam com uma coordenada mínima (por exemplo, a origem) e, ao mesmo tempo, remove essa coordenada inicial de cada uma. Em seguida, usa o módulo aritmético para retroceder a um toro e filtra quaisquer coordenadas duplicadas contendo (ou seja, aquelas que contêm interseções) e, finalmente, filtra àquelas com coordenadas finais mínimas (ou seja, termina na origem) e produz o comprimento do 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
fonte
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))

Experimente online!

O interessante aqui é usar um número complexo zpara armazenar as coordenadas da posição atual. Podemos subir adicionando 1e movendo para a direita adicionando 1j. Para minha surpresa, o módulo trabalha com números complexos de uma maneira que nos permite lidar com o empacotamento de cada dimensão separadamente: realizando %matos na parte real e %(n*1j)atuando na parte imaginária.

xnor
fonte
Bem feito. FWIW, minha melhor tentativa sem usar um número complexo é de 91 bytes no Python 3.8.
Arnauld
@ Arnauld Ideia interessante com o k:=x+y*m. Isso me faz pensar se seria mais curto usar kdiretamente para (x,y), usando em x+y*mvez de x+y*1j. Pena que o Python 3 não permita módulo complexo.
xnor 9/03
Essa abordagem economiza 5 bytes em JS. :)
Arnauld
7

JavaScript (ES6), 67 bytes

m×n<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))``

Experimente online!

Para que funcione para qualquer entrada, poderíamos usar o 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)

Experimente online!


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)

Experimente online!

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

Experimente online!

Força bruta simples: tente todas as combinações para cima / para a direita, descartando aquelas que se cruzam (mantemos todas as posições que visitamos na lista a) e contando aquelas que eventualmente atingem a posição (0,0)novamente.

O caso base da recursão é quando visitamos uma posição pela segunda vez ( elem(x,y)a). O resultado é 0^0= 1quando a posição é (0,0)e conta para o número de loops ou 0( 0^x, com xdiferente de zero) caso contrário e não aumenta o número de loops.

Editar: -8 bytes graças a @xnor.

nimi
fonte
1
Os casos base podem ser combinados |elem(x,y)a=0^(x+y)e (0!0)[]podem ser 0!0$[].
xnor 9/03
2

Geléia , 44 bytes

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

Experimente online!

O(2mn)

mn

Nick Kennedy
fonte
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);}

nm<32.

Experimente online.

Kevin Cruijssen
fonte
1

CJam (50 caracteres)

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

Demonstração online . Este é um programa que recebe duas entradas do stdin.

Finalmente, temos uma resposta para a pergunta

Guerra, hein, para que serve?


Dissecação

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
fonte
1

Geléia , 54 39 bytes

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

Experimente online!

Eu postei isso como uma resposta separada para o meu outro Jelly, porque é um método completamente diferente. Em princípio, isso está mais próximo da resposta de @ Arnauld. Ele usa uma função recursiva que trabalha em todos os caminhos possíveis até atingir um ponto que já foi alcançado e, em seguida, retorna o resultado de uma verificação se está de volta ao início. Suspeito que mais alguns bytes possam ser removidos. Agora alterado para usar o operador de fatia. Funciona bem para até 5x5. A profundidade da recursão deve ser no máximo mx n.

Nick Kennedy
fonte