Os números racionais positivos podem ser mostrados como numeráveis com o seguinte processo:
- Zero tem o ordinal 0
- Organize os outros números em uma grade para que a linha a, coluna b contenha a / b
- Traçar um zig-zag diagonal de cima para a direita e para baixo à esquerda
- Mantenha um registro contínuo dos números exclusivos encontrados ao longo do zig-zag
Aqui está uma foto do zig-zag:
Portanto, os números encontrados são, em ordem
1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 2/4, 3/3, 4/2, 5/1, 6/1, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 2/6, 3/5, 4/4, 5/3 ...
E os números únicos e simplificados encontrados são
1, 2, 1/2, 1/3, 3, 4, 3/2, 2/3, 1/4, 1/5, 5, 6, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 3/5, 5/3, ...
Desafio:
- Dadas duas superior a-zero inteiros p e q , saída do número ordinal de p / q
- peq não são necessariamente co-primos
- O código mais curto vence
- As brechas padrão são proibidas
Casos de teste:
Aqui estão os primeiros 24 números racionais encontrados e a saída desejada para cada um:
1/1: 1
2/1: 2
1/2: 3
1/3: 4
2/2: 1
3/1: 5
4/1: 6
3/2: 7
2/3: 8
1/4: 9
1/5: 10
2/4: 3
3/3: 1
4/2: 2
5/1: 11
6/1: 12
5/2: 13
4/3: 14
3/4: 15
2/5: 16
1/6: 17
1/7: 18
2/6: 4
3/5: 19
E, para outros casos de teste, aqui estão os 200 primeiros números racionais positivos em ordem:
1, 2, 1/2, 1/3, 3, 4, 3/2, 2/3, 1/4, 1/5,
5, 6, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 3/5, 5/3,
7, 8, 7/2, 5/4, 4/5, 2/7, 1/8, 1/9, 3/7, 7/3,
9, 10, 9/2, 8/3, 7/4, 6/5, 5/6, 4/7, 3/8, 2/9,
1/10, 1/11, 5/7, 7/5, 11, 12, 11/2, 10/3, 9/4, 8/5,
7/6, 6/7, 5/8, 4/9, 3/10, 2/11, 1/12, 1/13, 3/11, 5/9,
9/5, 11/3, 13, 14, 13/2, 11/4, 8/7, 7/8, 4/11, 2/13,
1/14, 1/15, 3/13, 5/11, 7/9, 9/7, 11/5, 13/3, 15, 16,
15/2, 14/3, 13/4, 12/5, 11/6, 10/7, 9/8, 8/9, 7/10, 6/11,
5/12, 4/13, 3/14, 2/15, 1/16, 1/17, 5/13, 7/11, 11/7, 13/5,
17, 18, 17/2, 16/3, 15/4, 14/5, 13/6, 12/7, 11/8, 10/9,
9/10, 8/11, 7/12, 6/13, 5/14, 4/15, 3/16, 2/17, 1/18, 1/19,
3/17, 7/13, 9/11, 11/9, 13/7, 17/3, 19, 20, 19/2, 17/4,
16/5, 13/8, 11/10, 10/11, 8/13, 5/16, 4/17, 2/19, 1/20, 1/21,
3/19, 5/17, 7/15, 9/13, 13/9, 15/7, 17/5, 19/3, 21, 22,
21/2, 20/3, 19/4, 18/5, 17/6, 16/7, 15/8, 14/9, 13/10, 12/11,
11/12, 10/13, 9/14, 8/15, 7/16, 6/17, 5/18, 4/19, 3/20, 2/21,
1/22, 1/23, 5/19, 7/17, 11/13, 13/11, 17/7, 19/5, 23, 24,
23/2, 22/3, 21/4, 19/6, 18/7, 17/8, 16/9, 14/11, 13/12, 12/13,
11/14, 9/16, 8/17, 7/18, 6/19, 4/21, 3/22, 2/23, 1/24, 1/25
Grite para a pergunta inversa , onde a primeira jogada é para baixo, para que você não possa usar as respostas para gerar casos de teste adicionais.
Respostas:
Geléia ,
2120 bytesProvavelmente superável por um número de bytes usando alguma matemática inteligente ...
Um link monádico que aceita uma lista
[p,q]
retornando o número natural atribuídop/q
.Experimente online! Ou veja a suíte de testes .
Quão?
Primeira nota que o N º diagonal encontrou contém todos os números racionais da grade para o qual a soma do numerador e denominador é igual a N + 1 , então dada uma função que reduz um
[p,q]
par de forma mais simples ([p/gcd(p,q),q/gcd(p,q)]
) podemos construir as diagonais, tanto quanto precisa ser *, reduza todas as entradas, desduplique e encontre o índice da entrada simplificada.* na verdade, mais um aqui para salvar um byte
fonte
Perl 6 ,
9490 bytesTeste-o
Teste-o
Isso basicamente gera toda a sequência de valores e para quando encontra uma correspondência.
Expandido:
({1…($+=2)…1}…*)
gera a sequência infinita de numeradores (|(…)
é usado acima para achatar)(1,{1…(($||=1)+=2)…1}…*)
gera a sequência infinita de denominadoresfonte
Python 2 ,
157144137134126125 bytesExperimente online!
4 bytes salvos devido ao Sr. Xcoder ; 1 byte de Jonathon Frech .
Como observado pelo Sr. Xcoder, podemos fazer um pouco melhor no Python 3, pois, entre outras coisas, a divisão de números inteiros padroniza os resultados flutuantes e podemos descompactar
list
s mais facilmente :Python 3 , 117 bytes
Experimente online!
fonte
**(j%-2|1)
ep-~q
.+1
final, já que1,1
'preciso' dar1
, não0
.Python 3 ,
157,146,140, 133 bytesExperimente online!
ganhou 11 bytes graças a Jonathan Frech
ganhou mais 6 bytes e depois 7 graças a Chas Brown
fonte
range(max(p,q)+1)
porrange(p+q)
.{*a}
vez deset(a)
.J,
41,35, 30 bytes-11 bytes graças ao FrownyFrog
Experimente online!
postagem original de 41 bytes com explicação
destroçado
explicação
Experimente online!
fonte
1+~.@;@([:<@|.`</.%~/~)@(1+i.@*)i.%
%i.~0~.@,@,[:]`|./.[:%/~1+i.@*
Python 3, 121 bytes
fonte
Ferrugem, 244 bytes
Criei uma fórmula simples para encontrar o ordinal "simples" de um ziguezague "simples", sem as restrições do quebra-cabeça, usando fórmulas triangulares de números: https://www.mathsisfun.com/algebra/triangular-numbers.html . Isso foi modificado no módulo 2 para explicar os zig-zags que viravam sua direção em cada linha diagonal do quebra-cabeça. Esta é a função h ()
Então, o principal truque desse quebra-cabeça: como 'não contar' certos valores repetidos, como 3/3 vs 1/1, 4/2 vs 2/1, na trilha do zig-zag. Executei os exemplos de 1 a 200 e notei que a diferença entre um contador triangular simples em zig-zag e o que o quebra-cabeça deseja possui um padrão. O padrão de números "ausentes" é 5, 12, 13, 14, 23 etc., o que resultou em um acerto no OEIS. É o descrito por Robert A Stump, em https://oeis.org/A076537 , para "deduplicar" números como 3/3, 4/2 e 1/1, você pode verificar se GCD> 1 para o x, y de todos os ordinais "anteriores" no zigue-zague. Este é o 'for' loops eg () que é o gcd.
Eu acho que com algum gcd embutido, teria sido mais curto, mas eu meio que não consegui encontrá-lo com muita facilidade (sou meio novo na Rust and Integer me confundiu), e eu gosto do fato de que este usa aritmética inteira direta, e nenhum builtins ou bibliotecas de qualquer tipo.
fonte
JavaScript (ES6), 86 bytes
Recebe entrada na sintaxe de currying
(p)(q)
.Experimente online!
fonte
Javascript, 79 bytes
(Eu sou novo no código de golfe, então isso provavelmente pode ser melhorado facilmente)
Explicação
fonte
(3,5)
deve resultar em19
(não24
)(1,1)==(2,2)==(3,3)
, pois(2,4)==(1,2)
,(4,2)==(2,1)
e(2,6)==(1,3)
. (ou seja,(2,2)
deve resultar em1
não5
, etc ...)