Es kann gezeigt werden, dass die positiven rationalen Zahlen mit dem folgenden Verfahren numerierbar sind:

1. Null hat die Ordnungszahl 0
2. Ordnen Sie die anderen Zahlen in einem Raster so an, dass Zeile a, Spalte b a / b enthält
3. Zeichnen Sie einen diagonalen Zickzack von rechts oben nach links unten
4. Führen Sie eine fortlaufende Liste der eindeutigen Zahlen entlang des Zick-Zacks

Hier ist ein Bild vom Zick-Zack:

Die angetroffenen Zahlen sind also in der richtigen Reihenfolge

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

Und die vereinfachten, eindeutigen Zahlen sind

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, ...

Herausforderung:

• Geben Sie die Ordnungszahl von p / q aus, wenn zwei ganze Zahlen größer als Null p und q gegeben sind
• p und q müssen nicht unbedingt co-prime sein
• Kürzester Code gewinnt
• Standardlücken sind verboten

Testfälle:

Hier sind die ersten 24 rationalen Zahlen und die gewünschte Ausgabe für jede:

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

Und für weitere Testfälle sind hier die 200 ersten positiven rationalen Zahlen in der Reihenfolge:

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 

Rufen Sie die umgekehrte Frage an , bei der der erste Zug fehlschlägt, sodass Sie die Antworten nicht verwenden können, um zusätzliche Testfälle zu generieren.

Jelly ,  21 bis  20 Bytes

^{Wahrscheinlich durch eine Anzahl von Bytes mit etwas kluger Mathematik zu schlagen ...}

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

Ein monadischer Link, der eine Liste akzeptiert, [p,q]die die natürliche Nummer zurückgibt, die zugewiesen wurde p/q.

Probieren Sie es online! Oder sehen Sie sich die Testsuite an .

Wie?

Beachten Sie zunächst, dass die N- ^te Diagonale alle rationalen Zahlen des Gitters enthält, für die die Summe aus Zähler und Nenner gleich N + 1 ist. Wenn also eine Funktion gegeben ist, die ein [p,q]Paar auf die einfachste Form reduziert ( [p/gcd(p,q),q/gcd(p,q)]), können wir die Diagonalen so weit wie möglich bilden müssen * sein, alle Einträge reduzieren, Deduplizieren und den Index der vereinfachten Eingabe finden.

* eigentlich noch ein weiteres hier um ein byte zu speichern

: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

Perl 6 ,  94  90 Bytes

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

Probier es aus

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

Probier es aus

Dies generiert im Grunde die gesamte Folge von Werten und stoppt, wenn eine Übereinstimmung gefunden wird.

Erweitert:

{  # 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}…*)erzeugt die unendliche Folge von Zählern ( |(…)wird oben zum Abflachen verwendet)

(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}…*) erzeugt die unendliche Folge von Nennern

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

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)

Probieren Sie es online!

4 Bytes gespart durch Mr. Xcoder ; 1 Byte von Jonathon Frech .

Wie Mr. Xcoder bemerkte, können wir in Python 3 etwas bessere Ergebnisse erzielen, da unter anderem die Ganzzahldivision standardmäßig Floating-Ergebnisse liefert und wir lists einfacher entpacken können :

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)

Probieren Sie es online!

Python 3 ,157, 146, 140133 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)

Probieren Sie es online!

gewann 11 Bytes dank Jonathan Frech

gewann 6 weitere Bytes und dann 7 dank Chas Brown

J, 41 , 35 , 30 Bytes

-11 Bytes dank FrownyFrog

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

Probieren Sie es online!

original 41 bytes post mit erklärung

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

ungolfed

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

Erläuterung

                  +
                  | 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││││ ││└─┴─┴────────┘││
  │ │             ││  │││  │        ││  │││┌─┬─┬──┐│<││  ││└─┴─┴───┘│││ ││              ││
  │ │             ││  │││  │        ││  ││││<│@│|.││ ││  ││         │││ ││              ││
  │ │             ││  │││  │        ││  │││└─┴─┴──┘│ ││  ││         │││ ││              ││
  │ │             ││  │││  │        ││  ││└────────┴─┘│  ││         │││ ││              ││
  │ │             ││  │││  │        ││  │└────────────┴──┘│         │││ ││              ││
  │ │             ││  │││  │        │└──┴─────────────────┴─────────┘││ ││              ││
  │ │             ││  ││└──┴────────┴────────────────────────────────┘│ ││              ││
  │ │             ││  │└──────────────────────────────────────────────┴─┘│              ││
  │ │             │└──┴──────────────────────────────────────────────────┴──────────────┘│
  └─┴─────────────┴──────────────────────────────────────────────────────────────────────┘

Probieren Sie es online!

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

Rust, 244 Bytes

Ich habe eine einfache Formel erstellt, um die "einfache" Ordnungszahl eines "einfachen" Zickzacks ohne die Einschränkungen des Puzzles zu finden. Dabei habe ich Dreieckszahlenformeln verwendet: https://www.mathsisfun.com/algebra/triangular-numbers.html . Dies wurde mit Modulo 2 modifiziert, um die Zick-Zack-Bewegungen in jeder diagonalen Reihe des Puzzles zu berücksichtigen. Das ist Funktion h ()

Dann zum Haupttrick dieses Puzzles: wie man bestimmte Wiederholungswerte, wie 3/3 gegen 1/1, 4/2 gegen 2/1, in der Zick-Zack-Spur nicht zählt. Ich habe die Beispiele 1-200 durchgesehen und festgestellt, dass der Unterschied zwischen einem einfachen Zick-Zack-Dreieck-Zähler und demjenigen, den das Puzzle haben möchte, ein Muster hat. Das Muster der "fehlenden" Zahlen ist 5, 12, 13, 14, 23 usw., was zu einem Treffer im OEIS führte. Es ist eines, das von Robert A Stump unter https://oeis.org/A076537 beschrieben wurde wurde. Um Zahlen wie 3/3, 4/2 und 1/1 zu "deduplizieren", können Sie überprüfen, ob GCD> 1 für die x, y aller "vorherigen" Ordnungszahlen im Zickzack. Dies ist die 'for'-Schleife und g () ist die gcd.

Ich denke, mit einem eingebauten gcd wäre es kürzer gewesen, aber ich konnte es irgendwie nicht leicht finden (ich bin ein bisschen neu bei Rust und Integer, verwirrt mich), und ich mag die Tatsache, dass dieses eine gerade Ganzzahl-Arithmetik verwendet, und keine eingebauten oder Bibliotheken jeglicher Art.

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
}

JavaScript (ES6), 86 Byte

Übernimmt Eingaben in der Currying-Syntax (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)

Probieren Sie es online!

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

(Ich bin neu im Code-Golfen, daher kann dies wahrscheinlich leicht verbessert werden.)

Erläuterung

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