Angka-angka rasional positif dapat ditunjukkan sebagai angka dengan proses berikut:
- Nol memiliki ordinal 0
- Atur angka-angka lain dalam kisi sehingga baris a, kolom b berisi a / b
- Plot zig-zag diagonal kanan atas ke kiri bawah
- Pertahankan penghitungan angka unik yang ditemukan di sepanjang zig-zag
Ini gambar zig-zag:
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.
Jawaban:
Jelly ,
2120 byteMungkin bisa dikalahkan oleh sejumlah byte menggunakan beberapa matematika pintar ...
Tautan monadik yang menerima daftar
[p,q]
yang mengembalikan nomor alami yang ditetapkanp/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
sumber
Perl 6 ,
9490 byteMenguji
Menguji
Ini pada dasarnya menghasilkan seluruh urutan nilai, dan berhenti ketika menemukan kecocokan.
Diperluas:
({1…($+=2)…1}…*)
menghasilkan urutan pembilang yang tak terbatas (|(…)
digunakan di atas untuk meratakan)(1,{1…(($||=1)+=2)…1}…*)
menghasilkan urutan penyebut tanpa batassumber
Python 2 ,
157144137134126125 byteCobalah 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
list
s:Python 3 , 117 byte
Cobalah online!
sumber
**(j%-2|1)
danp-~q
.+1
pada akhirnya, karena1,1
'harus' memberi1
, bukan0
.Python 3 ,
157,146,140, 133 byteCobalah online!
memenangkan 11 byte berkat Jonathan Frech
memenangkan 6 byte lebih banyak dan kemudian 7 berkat Chas Brown
sumber
range(max(p,q)+1)
denganrange(p+q)
.{*a}
alih-alihset(a)
.J,
41,35, 30 byte-11 byte berkat FrownyFrog
Cobalah online!
asli 41 byte posting dengan penjelasan
ungolfed
penjelasan
Cobalah online!
sumber
1+~.@;@([:<@|.`</.%~/~)@(1+i.@*)i.%
%i.~0~.@,@,[:]`|./.[:%/~1+i.@*
Python 3, 121 byte
sumber
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.
sumber
JavaScript (ES6), 86 byte
Mengambil input dalam sintaks currying
(p)(q)
.Cobalah online!
sumber
Javascript, 79 byte
(Saya baru mengenal kode golf, jadi ini mungkin dapat ditingkatkan dengan mudah)
Penjelasan
sumber
(3,5)
harus menghasilkan19
(tidak24
) sejak(1,1)==(2,2)==(3,3)
,(2,4)==(1,2)
,(4,2)==(2,1)
dan(2,6)==(1,3)
. (Yaitu(2,2)
seharusnya menghasilkan1
tidak5
, dll ...)