Beri nilai rasional positif

14

Angka-angka rasional positif dapat ditunjukkan sebagai angka dengan proses berikut:

  1. Nol memiliki ordinal 0
  2. Atur angka-angka lain dalam kisi sehingga baris a, kolom b berisi a / b
  3. Plot zig-zag diagonal kanan atas ke kiri bawah
  4. Pertahankan penghitungan angka unik yang ditemukan di sepanjang zig-zag

Ini gambar zig-zag:

Mulai dari 1/1, langkah awal ke kanan

Jadi, angka yang ditemui adalah, secara berurutan

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

Dan nomor unik yang disederhanakan yang ditemukan adalah

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

Tantangan:

  • Diberikan dua bilangan bulat p dan q yang lebih besar dari nol , menghasilkan bilangan p / q
  • p dan q tidak harus co-prime
  • Kode terpendek menang
  • Celah standar dilarang

Kasus uji:

Berikut adalah 24 angka rasional pertama yang ditemui, dan output yang diinginkan untuk masing-masing:

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

Dan, untuk kasus uji lebih lanjut, berikut adalah 200 bilangan rasional positif pertama secara berurutan:

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 

Serukan ke pertanyaan terbalik , di mana langkah pertama turun sehingga Anda tidak dapat menggunakan jawaban untuk menghasilkan kasus uji tambahan.

HAEM
sumber
Saya ingin tahu apakah ada skema penomoran alternatif yang membuat kode lebih pendek.
qwr
1
Numerator fraksi: oeis.org/A157807 penyebut: oeis.org/A157813 Tidak ada kecocokan untuk urutan ordinal: oeis.org/…
qwr
saya melihat. Anda harus mengurangi pecahan dan kemudian menghitung. ini bukan zig-zag saja
don bright

Jawaban:

4

Jelly ,  21  20 byte

Mungkin bisa dikalahkan oleh sejumlah byte menggunakan beberapa matematika pintar ...

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

Tautan monadik yang menerima daftar [p,q] yang mengembalikan nomor alami yang ditetapkan p/q.

Cobalah online!Atau lihat test-suite .

Bagaimana?

Perhatikan pertama bahwa diagonal ke- N yang dijumpai berisi semua bilangan rasional grid yang jumlah pembilang dan penyebutnya sama dengan N + 1 , jadi diberi fungsi yang mengurangi[p,q] pasangan ke bentuk paling sederhana ( [p/gcd(p,q),q/gcd(p,q)]) kita dapat membangun diagonal sejauh harus *, kurangi semua entri, hapus duplikat dan temukan indeks input yang disederhanakan.

* sebenarnya satu lagi di sini untuk menghemat satu 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
sumber
3

Perl 6 ,  94  90 byte

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

Menguji

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

Menguji

Ini pada dasarnya menghasilkan seluruh urutan nilai, dan berhenti ketika menemukan kecocokan.

Diperluas:

{  # 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}…*)menghasilkan urutan pembilang yang tak terbatas ( |(…)digunakan di atas untuk meratakan)

(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}…*) menghasilkan urutan penyebut tanpa batas

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
sumber
3

Python 2 , 157 144 137 134 126 125 byte

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)

Cobalah online!

4 byte disimpan karena Tn. Xcoder ; 1 byte dari Jonathon Frech .

Seperti dicatat oleh Mr. Xcoder, kita bisa melakukan sedikit lebih baik di Python 3 karena, antara lain, standar pembagian integer untuk mengapung hasil, dan kita dapat lebih mudah membongkar lists:

Python 3 , 117 byte

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)

Cobalah online!

Chas Brown
sumber
128 byte (-6) dengan menukar pecahan dan menggunakan **(j%-2|1)dan p-~q.
Tn. Xcoder
@Pak. Xcoder: Anda semua tentang modulo negatif hari ini! :) Saya pikir saya masih membutuhkan +1pada akhirnya, karena 1,1'harus' memberi 1, bukan 0.
Chas Brown
125 byte .
Jonathan Frech
124 byte :) Ya modulo negatif ternyata sangat membantu!
Tn. Xcoder
Sebenarnya 117 byte dalam Python 3
Mr. Xcoder
3

Python 3 ,157, 146, 140, 133 byte

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)

Cobalah online!

memenangkan 11 byte berkat Jonathan Frech

memenangkan 6 byte lebih banyak dan kemudian 7 berkat Chas Brown

bobrobbob
sumber
1
146 byte .
Jonathan Frech
140 bytes .
Chas Brown
@bobrobbob: Selamat datang di PPCG! Saya tidak yakin bagaimana algoritme Anda bekerja (meskipun jelas tidak); tapi eksperimental, tampaknya Anda dapat menyimpan beberapa byte lagi dengan mengganti range(max(p,q)+1)dengan range(p+q).
Chas Brown
1
Anda dapat menyimpan lebih banyak byte dengan menggunakan {*a}alih-alih set(a).
Tn. Xcoder
2

J, 41 , 35 , 30 byte

-11 byte berkat FrownyFrog

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

Cobalah online!

asli 41 byte posting dengan penjelasan

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

ungolfed

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

penjelasan

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

Cobalah online!

Jonah
sumber
35:1+~.@;@([:<@|.`</.%~/~)@(1+i.@*)i.%
FrownyFrog
Terima kasih banyak! saya akan memperbarui sepenuhnya nanti karena akan memerlukan mengulang penjelasan ...
Jonah
Dan 30:%i.~0~.@,@,[:]`|./.[:%/~1+i.@*
FrownyFrog
itu pintar, gunakan 0 dan ~. untuk menghindari tinju dan kenaikan, saya menyukainya
Jonah
2

Python 3, 121 byte

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
sumber
2

Rust, 244 byte

Saya membuat formula sederhana untuk menemukan ordinal "polos" dari zigzag "polos", tanpa batasan teka-teki, menggunakan rumus angka segitiga: https://www.mathsisfun.com/algebra/triangular-numbers.html . Ini telah dimodifikasi dengan modulo 2 untuk memperhitungkan zig-zag membalik arah mereka setiap baris diagonal dalam teka-teki. Ini adalah fungsi h ()

Kemudian untuk trik utama dari teka-teki ini: cara 'tidak menghitung' nilai berulang tertentu, seperti 3/3 vs 1/1, 4/2 vs 2/1, dalam jejak zig-zag. Saya menjalankan 1-200 contoh, dan melihat perbedaan antara penghitung segitiga zig-zag polos, dan yang diinginkan puzzle, memiliki polanya. Pola angka "hilang" adalah 5, 12, 13, 14, 23, dll, yang menghasilkan hit di OEIS. Ini dijelaskan oleh Robert A Stump, di https://oeis.org/A076537 , untuk "menduplikasi" angka seperti 3/3, 4/2, dan 1/1, Anda dapat memeriksa apakah GCD> 1 untuk x, y dari semua tata cara "sebelumnya" di zigzag. Ini adalah 'untuk' loop dan g () yang merupakan gcd.

Saya kira dengan beberapa builtin gcd itu akan lebih pendek, tapi saya agak tidak bisa menemukannya dengan mudah (saya agak baru di Rust dan Integer membingungkan saya), dan saya suka fakta bahwa yang satu ini menggunakan aritmatika integer lurus, dan tidak ada builtin atau perpustakaan dalam bentuk apa pun.

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
}
jangan cerah
sumber
1

JavaScript (ES6), 86 byte

Mengambil input dalam sintaks 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)

Cobalah online!

Arnauld
sumber
0

Javascript, 79 byte

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

(Saya baru mengenal kode golf, jadi ini mungkin dapat ditingkatkan dengan mudah)

Penjelasan

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
sumber
4
(3,5)harus menghasilkan 19(tidak 24) sejak (1,1)==(2,2)==(3,3), (2,4)==(1,2), (4,2)==(2,1)dan (2,6)==(1,3). (Yaitu (2,2)seharusnya menghasilkan 1tidak 5, dll ...)
Jonathan Allan