Numere as razões positivas

14

Os números racionais positivos podem ser mostrados como numeráveis ​​com o seguinte processo:

  1. Zero tem o ordinal 0
  2. Organize os outros números em uma grade para que a linha a, coluna b contenha a / b
  3. Traçar um zig-zag diagonal de cima para a direita e para baixo à esquerda
  4. Mantenha um registro contínuo dos números exclusivos encontrados ao longo do zig-zag

Aqui está uma foto do zig-zag:

Comece em 1/1, movimento inicial para a direita

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.

HAEM
fonte
Gostaria de saber se existem esquemas de numeração alternativos que contribuem para um código mais curto.
QWR
1
Numeradores de frações: oeis.org/A157807 denominadores: oeis.org/A157813 Não foram encontradas correspondências para a sequência ordinal: oeis.org/…
qwr
Entendo. você tem que reduzir a fração e depois contar. não é o zig-zag única
don brilhante

Respostas:

4

Geléia ,  21  20 bytes

Provavelmente superável por um número de bytes usando alguma matemática inteligente ...

:g/
ǵSRRUĖ€UÐeẎÇ€Qi

Um link monádico que aceita uma lista [p,q]retornando o número natural atribuído p/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

:g/ - Link 1, simplify a pair: list of integers, [a, b]
  / - reduce using:
 g  - Greatest Common Divisor -> gcd(a, b)
:   - integer division (vectorises) -> [a/gcd(a,b), b/gcd(a,b)]

ǵSRRUĖ€UÐeẎÇ€Qi - Main Link: list of integers, [p, q]
Ç                - call last Link as a monad (simplify)
 µ               - start a new monadic chain (call that V)
  S              - sum -> the diagonal V will be in plus one
   R             - range -> [1,2,3,...,diag(V)+1]
    R            - range (vectorises) -> [[1],[1,2],[1,2,3],...,[1,2,3,...,diag(V)+1]]
     U           - reverse each       -> [[1],[2,1],[3,2,1],[diag(V)+1,...,3,2,1]]
      Ė€         - enumerate €ach     -> [[[1,1]],[[1,2],[2,1]],[[1,3],[2,2],[3,1]],[[1,diag(V)+1],...,[diag(V)-1,3],[diag(V),2],[diag(V)+1,1]]]
         Ðe      - apply only to the even indexed items:
        U        -   reverse each     -> [[[1,1]],[[2,1],[1,2]],[[1,3],[2,2],[3,1]],[[4,1],[3,2],[2,3],[1,4]],...]
           Ẏ     - tighten            -> [[1,1],[2,1],[1,2],[1,3],[2,2],[3,1],[4,1],[3,2],[2,3],[1,4],...]
            Ç€   - for €ach: call last Link as a monad (simplify each)
                 -                    -> [[1,1],[2,1],[1,2],[1,3],[1,1],[3,1],[4,1],[3,2],[2,3],[1,4],...]
              Q  - de-duplicate       -> [[1,1],[2,1],[1,2],[1,3],[3,1],[4,1],[3,2],[2,3],[1,4],...]
               i - index of V in that list
Jonathan Allan
fonte
3

Perl 6 ,  94  90 bytes

->\p,\q{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique.first(p/q,:k)+1}

Teste-o

{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique.first($^p/$^q):k+1}

Teste-o

Isso basicamente gera toda a sequência de valores e para quando encontra uma correspondência.

Expandido:

{  # bare block lambda with placeholder parameters $p,$q

  (
      ( # sequence of numerators

        {
          |( # slip into outer sequence (flatten)

            1      # start at one
            
            (
              $    # state variable
              += 2 # increment it by two each time this block is called
            )
            
            1      # finish at one
          )

        }
         * # never stop generating values
      )


    Z/   # zip using &infix:« /  » (generates Rats)


      ( # sequence of denominators

        1,  # start with an extra one

        {
          |( # slip into outer sequence (flatten)

            1
            
            (
              ( $ ||= 1 ) # state variable that starts with 1 (rather than 0)
              += 2        # increment it by two each time this is called
            )
            
            1
          )
        }
         * # never stop generating values
      )


  ).unique            # get only the unique values
  .first( $^p / $^q ) # find the first one that matches the input
  :k                  # get the index instead (0 based)
  + 1                 # add one               (1 based)
}

({1…($+=2)…1}…*)gera a sequência infinita de numeradores ( |(…)é usado acima para achatar)

(1 2 1)
(1 2 3 4 3 2 1)
(1 2 3 4 5 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1)

(1,{1…(($||=1)+=2)…1}…*) gera a sequência infinita de denominadores

1
(1 2 3 2 1)
(1 2 3 4 5 4 3 2 1)
(1 2 3 4 5 6 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 11 10 9 8 7 6 5 4 3 2 1)
Brad Gilbert b2gills
fonte
3

Python 2 , 157 144 137 134 126 125 bytes

def f(p,q):a=[((j-i)/(i+1.))**(j%-2|1)for j in range(p-~q)for i in range(j)];return-~sorted(set(a),key=a.index).index(p*1./q)

Experimente 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 lists mais facilmente :

Python 3 , 117 bytes

def f(p,q):a=[((j-i)/-~i)**(j%-2|1)for j in range(p-~q)for i in range(j)];return-~sorted({*a},key=a.index).index(p/q)

Experimente online!

Chas Brown
fonte
128 bytes (-6) trocando a fração e usando **(j%-2|1)e p-~q.
Mr. Xcoder
@Senhor. Xcoder: Você é o módulo negativo hoje! :) Acho que ainda preciso do +1final, já que 1,1'preciso' dar 1, não 0.
quer
125 bytes .
Jonathan Frech
124 bytes :) Sim, o módulo negativo acaba sendo realmente útil!
Mr. Xcoder
Na verdade 117 bytes em Python 3
Mr. Xcoder 17/18
3

Python 3 ,157, 146, 140, 133 bytes

def f(p,q):a=[(i+i-abs(j-i-i))/(abs(j-i-i+.5)+.5)for i in range(p+q)for j in range(4*i)];return sorted(set(a),key=a.index).index(p/q)

Experimente online!

ganhou 11 bytes graças a Jonathan Frech

ganhou mais 6 bytes e depois 7 graças a Chas Brown

bobrobbob
fonte
1
146 bytes .
Jonathan Frech
140 bytes .
Chas Brown
@bobrobbob: Bem-vindo ao PPCG! Não tenho muita certeza de como seu algoritmo funciona (embora claramente funcione); mas experimentalmente, parece que você pode salvar mais alguns bytes substituindo range(max(p,q)+1)por range(p+q).
Chas Brown
1
Você pode salvar mais alguns bytes usando em {*a}vez de set(a).
Mr. Xcoder
2

J, 41 , 35 , 30 bytes

-11 bytes graças ao FrownyFrog

%i.~0~.@,@,[:]`|./.[:%/~1+i.@*

Experimente online!

postagem original de 41 bytes com explicação

%>:@i.~[:([:~.@;[:<@|.`</.%"1 0)~(1+i.@*)

destroçado

% >:@i.~ [: ([: ~.@; [: <@|.`</. %"1 0)~ 1 + i.@*

explicação

                  +
                  | Everything to the right of this
                  | calculates the list
p (left arg)      |                                      create the
divided by q      |                                      diagonals.  yes,
      (right)     |                                     +this is a         +create this list
   |              |        ++ finally rmv ^alternately  |primitive ADVERB  |1..(p*q), and pass
   |   + the index          | the boxes,  |box, or      |in J              |it as both the left
   |   | of that  |         | and remove  |reverse and  |                  |and right arg to the
   |   | in the   |         | any dups    |box, each    |                  |middle verb, where each
   |   | list on  |         |             |diagonal     |                  |element will divide the
   |   | the right|         |             |             |       +----------+entire list, producing
   |   | plus 1   |         |             |             |       |          |the undiagonalized grid
   |   |          |         |             |             |       |          |
   |   |          |         |             |             |       |          |
   |   |          +         |             |             |       |          |
  ┌+┬──|──────────┬─────────|─────────────|─────────────|───────|──────────|─────────────┐
  │%│┌─+───────┬─┐│┌──┬─────|─────────────|─────────────|───────|────────┬─|────────────┐│
  │ ││┌──┬─┬──┐│~│││[:│┌────|─────────────|─────────────|───────|─────┬─┐│┌+┬─┬────────┐││
  │ │││>:│@│i.││ │││  ││┌──┬|───────┬─────|─────────────|───────|────┐│~│││1│+│┌──┬─┬─┐│││
  │ ││└──┴─┴──┘│ │││  │││[:│+──┬─┬─┐│┌──┬─|─────────────|─┬─────|───┐││ │││ │ ││i.│@│*││││
  │ │└─────────┴─┘││  │││  ││~.│@│;│││[:│┌|───────────┬─+┐│┌─┬─┬+──┐│││ │││ │ │└──┴─┴─┘│││
  │ │             ││  │││  │└──┴─┴─┘││  ││+────────┬─┐│/.│││%│"│1 0││││ ││└─┴─┴────────┘││
  │ │             ││  │││  │        ││  │││┌─┬─┬──┐│<││  ││└─┴─┴───┘│││ ││              ││
  │ │             ││  │││  │        ││  ││││<│@│|.││ ││  ││         │││ ││              ││
  │ │             ││  │││  │        ││  │││└─┴─┴──┘│ ││  ││         │││ ││              ││
  │ │             ││  │││  │        ││  ││└────────┴─┘│  ││         │││ ││              ││
  │ │             ││  │││  │        ││  │└────────────┴──┘│         │││ ││              ││
  │ │             ││  │││  │        │└──┴─────────────────┴─────────┘││ ││              ││
  │ │             ││  ││└──┴────────┴────────────────────────────────┘│ ││              ││
  │ │             ││  │└──────────────────────────────────────────────┴─┘│              ││
  │ │             │└──┴──────────────────────────────────────────────────┴──────────────┘│
  └─┴─────────────┴──────────────────────────────────────────────────────────────────────┘

Experimente online!

Jonah
fonte
35:1+~.@;@([:<@|.`</.%~/~)@(1+i.@*)i.%
FrownyFrog
obrigada, muito legal! i irá atualizá-lo totalmente mais tarde, uma vez que será necessário refazer a explicação ...
Jonah
E 30:%i.~0~.@,@,[:]`|./.[:%/~1+i.@*
FrownyFrog
isso é inteligente, use 0 e ~. para evitar o boxe e o incremento, eu adoro
Jonah
2

Python 3, 121 bytes

import math
def o(x,y):
 p=q=n=1
 while x*q!=p*y:a=p+q&1;p+=1+a*~-~-(p<2);q+=1-~-a*~-~-(q<2);n+=math.gcd(p,q)<2
 return n
orlp
fonte
2

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.

fn f(x:i64,y:i64)->i64 {
        fn h(x:i64,y:i64)->i64 {let s=x+y;(s*s-3*s+4)/2-1+(s+1)%2*x+s%2*y}
        fn g(x:i64,y:i64)->i64 {if x==0 {y} else {g(y%x,x)}}
        let mut a=h(x,y);
        for i in 1..x+y {for j in 1..y+x {if h(i,j)<h(x,y) && g(i,j)>1 {a-=1;}}}
        a
}
não brilhante
fonte
1

JavaScript (ES6), 86 bytes

Recebe entrada na sintaxe de currying (p)(q).

p=>q=>(g=x=>x*y?x*q-y*p?g(x+d,g[x/=y]=g[x]||++n,y-=d):n:g(x+!~d,y+=!~(d=-d)))(d=n=y=1)

Experimente online!

Arnauld
fonte
0

Javascript, 79 bytes

a=(p,q)=>p*q==1?1:1+((p+q)%2?q==1?a(p-1,q):a(p+1,q-1):p==1?a(p,q-1):a(p-1,q+1))

(Eu sou novo no código de golfe, então isso provavelmente pode ser melhorado facilmente)

Explicação

let a = (p, q) => p * q == 1 // If they are both 1
    ? 1
    // Do a recursive call and increment the result by 1
    : 1 + (
        (p + q) % 2 // If on an even-numbered diagonal
        ? q == 1 // If at the beginning of the diagonal
            ? a(p - 1, q) // Go to previous diagonal
            : a(p + 1, q - 1) // Go one back
        : p == 1 // rougly the same
            ? a(p, q - 1)
            : a(p - 1, q + 1)
    )
Bary12
fonte
4
(3,5)deve resultar em 19(não 24) (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 em 1não 5, etc ...)
Jonathan Allan