Desafio
Este desafio terá que escrever um programa que leva dois inteiros n
e m
e devolve o número lacetes não se cruzam no n
por m
toro 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 código-golfe, 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.
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
code-golf
combinatorics
grid
topology
Peter Kagey
fonte
fonte
Respostas:
Gelatina , 28 bytes
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.
fonte
Python 2 , 87 bytes
Experimente online!
O interessante aqui é usar um número complexo
z
para armazenar as coordenadas da posição atual. Podemos subir adicionando1
e movendo para a direita adicionando1j
. 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%m
atos na parte real e%(n*1j)
atuando na parte imaginária.fonte
k:=x+y*m
. Isso me faz pensar se seria mais curto usark
diretamente para(x,y)
, usando emx+y*m
vez dex+y*1j
. Pena que o Python 3 não permita módulo complexo.JavaScript (ES6), 67 bytes
Toma entrada como
(m)(n)
.Experimente online!
Para que funcione para qualquer entrada, poderíamos usar o BigInts para 73 bytes :
Experimente online!
JavaScript (ES6),
76 7372 bytesToma entrada como
(m)(n)
.Experimente online!
Comentado
fonte
Haskell,
8880 bytesExperimente 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
=1
quando a posição é(0,0)
e conta para o número de loops ou0
(0^x
, comx
diferente de zero) caso contrário e não aumenta o número de loops.Editar: -8 bytes graças a @xnor.
fonte
|elem(x,y)a=0^(x+y)
e(0!0)[]
podem ser0!0$[]
.Geléia , 44 bytes
Experimente online!
fonte
Java 8, 120 bytes
Experimente online.
fonte
CJam (50 caracteres)
Demonstração online . Este é um programa que recebe duas entradas do stdin.
Finalmente, temos uma resposta para a pergunta
Dissecação
fonte
Geléia ,
5439 bytesExperimente 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.
fonte