Tugas:
Program Anda diberi fraksi sederhana positif dan tepat dalam format .<numerator>/<denominator>
Untuk input ini, ia harus menemukan dua fraksi.
- Sebagian kecil yang kurang dari input.
- Sebagian kecil yang lebih besar dari input.
Kedua fraksi harus memiliki penyebut yang lebih rendah daripada input. Dari semua fraksi yang mungkin, mereka harus memiliki perbedaan terendah ke input.
Keluaran:
Output program Anda harus:
- Sebagian kecil dari input, dalam format
<numerator>/<denominator>
. - Diikuti oleh karakter spasi (ASCII-code 32).
- Diikuti oleh fraksi yang lebih besar dari input, dalam format
<numerator>/<denominator>
.
Sebagai berikut:
«fraction that is < input» «fraction that is > input»
Aturan:
- Semua fraksi yang dikeluarkan harus dalam nilai terendah .
- Semua fraksi yang dihasilkan harus fraksi yang tepat.
- Jika tidak ada fraksi yang tepat yang dimungkinkan oleh aturan, Anda harus mengeluarkan,
0
bukannya input <pecahan, dan1
bukannya input pecahan>. - Anda dapat memilih apakah Anda ingin menerima fraksi sebagai argumen baris perintah (misalnya
yourprogram.exe 2/5
) atau meminta input pengguna. - Anda dapat menganggap program Anda tidak akan menerima input yang tidak valid.
- Kode terpendek (dalam byte, dalam bahasa apa pun) menang.
Argumen baris perintah non-standar (argumen yang biasanya tidak diperlukan untuk menjalankan skrip) dihitung terhadap jumlah total karakter.
Apa yang tidak boleh dilakukan oleh program Anda :
- Bergantung pada sumber daya eksternal apa pun.
- Bergantung pada memiliki nama file tertentu.
- Output apa pun selain output yang dibutuhkan.
- Butuh waktu yang sangat lama untuk dijalankan. Jika program Anda berjalan lebih dari satu menit untuk pecahan dengan pembilang dan penyebut 6 digit (mis.
179565/987657
) Pada komputer pengguna rumahan rata-rata, itu tidak valid. - Fraksi keluaran dengan
0
sebagai penyebut. Anda tidak dapat membaginya dengan nol. - Fraksi keluaran dengan
0
sebagai pembilang. Program Anda harus menampilkan0
bukan sebagian kecil. - Kurangi fraksi yang dimasukkan. Jika fraksi yang diberikan sebagai input dapat direduksi, Anda harus menggunakan fraksi seperti yang diinput.
- Program Anda tidak boleh ditulis dalam bahasa pemrograman yang tidak ada kompiler / juru bahasa yang tersedia untuk umum sebelum tantangan ini diposting.
Contoh:
Input: 2/5
Keluaran: 1/3 1/2
Input: 1/2
Keluaran: 0 1
Input: 5/9
Keluaran: 1/2 4/7
Input: 1/3
Keluaran: 0 1/2
Input: 2/4
Keluaran: 1/3 2/3
Input: 179565/987657
Keluaran: 170496/937775 128779/708320
1/3 1/2
.Jawaban:
Sage -
119117Sage hanya diperlukan di baris terakhir, yang menangani output. Segala sesuatu yang lain juga berfungsi dengan Python.
Ganti
raw_input()
dengansys.argv[1]
agar input dibaca dari argumen baris perintah alih-alih prompt. Ini tidak mengubah jumlah karakter. (Tidak berfungsi dengan Python tanpa mengimporsys
terlebih dahulu.)Ini pada dasarnya secara rekonstruk membangun urutan Farey masing-masing dengan menggunakan mediasi dari elemen yang ada, tetapi membatasi diri pada elemen yang paling dekat dengan input. Dari sudut pandang lain, ia menjalankan pencarian bersarang-interval pada urutan Farey masing-masing.
Itu benar memproses semua contoh dalam waktu kurang dari satu detik di mesin saya.
Berikut ini adalah versi yang tidak dikoleksi:
sumber
exec
!Python 2.7 - 138
Saya mulai dengan solusi brute-force yang jelas, tetapi saya menyadari bahwa karena OP ingin dapat menyelesaikan contoh dengan enam digit pembilang dan penyebut dalam waktu kurang dari satu menit, saya memerlukan solusi yang lebih baik daripada mencoba satu triliun kemungkinan. Saya menemukan formula praktis di halaman Wikipedia untuk urutan Farey: Jika a / b, c / d adalah tetangga dalam salah satu urutan Farey, dengan
a/b<c/d
, makab*c-a*b=1
. Loop sementara di dalam f dalam program saya memperluas fakta ini ke angka-angka yang tidak berkurang, menggunakan gcd, yang dihitung loop lain.Saya sudah bermain golf ini cukup sulit, tapi saya ingin sekali mendengar saran.
Suntingan:
166-> 162: Dihapus
a
danb
dari program luar. Mereka tidak perlu.162-> 155:
str()
-> ``155-> 154: Ditambahkan
k
.154-> 152: Dihapus
x
dari dalam fungsi, bukan sebagai argumen.152-> 150: Memberikan
a
nilai default alih-alih memberikannya sebagai argumen.150-> 146: Mengubah inisialisasi
x
dany
.146-> 145: Dihapus
k
.145-> 144: Berubah ... dan ... atau ... menjadi (..., ...) [...], dengan demikian menghemat ruang.
144-> 138: Berubah (..., ...) [...] menjadi ... + ... * (...). Terima kasih kepada @ mbomb007.
Kasus uji:
Tes kedua hingga terakhir berlangsung di bawah satu detik di komputer saya, sedangkan yang terakhir membutuhkan waktu sekitar 5-10 detik.
sumber
k=1
adalah kejahatan murni.print`(a*n+p)/d`+('/'+`a`)*(a>1),
Mathematica, 163 byte
Ini sangat dibatasi oleh persyaratan input / output sebagai input dan string pengguna. Berurusan dengan string benar-benar rumit di Mathematica (setidaknya ketika Anda ingin bermain golf). Melakukan ini dengan cara alami di Mathematica, (hanya menggunakan bilangan bulat dan rasional) saya mungkin akan mendapatkan ini hingga 50% dari ukuran.
Ia dapat melakukan angka 6 digit dalam beberapa detik di komputer saya.
Sedikit lebih mudah dibaca (meskipun tidak benar-benar tidak ungolf):
Untuk bersenang-senang, melakukan ini "cara alami", yaitu sebagai fungsi mengambil pembilang dan penyebut dan mengembalikan dua rasional, ini hanya 84 karakter (jadi perkiraan 50% saya sebenarnya cukup dekat):
sumber
Julia -
127125 byteSaya telah mendekati ini dari perspektif matematika untuk menghindari perlunya loop, jadi kode ini berjalan cukup cepat untuk input besar (catatan: jika a / b adalah input, maka a * b harus sesuai dengan Int64 (Int32 pada sistem 32 bit) , jika tidak, jawaban yang tidak masuk akal dihasilkan - jika a dan b keduanya dapat diekspresikan dalam Int32 (Int16 pada sistem 32 bit), tidak ada masalah yang terjadi).
PEMBARUAN: Tidak perlu lagi membebani backslash untuk div, dengan menggunakan ÷, penghematan bersih 2 byte.
Tidak Disatukan:
Ide dasarnya: temukan d terbesar dan f kurang dari b yang memenuhi ad-bc = gcd (a, b) (terkecil berikutnya) dan be-af = gcd (a, b) (terbesar berikutnya), lalu hitung c dan e dari sana. Output yang dihasilkan adalah c / de / f, kecuali jika d atau f adalah 1, dalam hal ini / d atau / f dihilangkan.
Menariknya, ini berarti bahwa kode tersebut juga berfungsi untuk pecahan positif yang tidak benar, asalkan inputnya bukan bilangan bulat (yaitu, gcd (a, b) = a).
Di sistem saya, menginput
194857602/34512958303
tidak membutuhkan waktu untuk menghasilkan171085289/30302433084 23772313/4210525219
sumber
55552/999999
memberi saya-396/920632 486/936509
.int32(55552*999999)
memberi-282630400
. Bagi saya, dengan tes itu, saya dapat51143/920632 52025/936509
- perhatikan bahwa penyebutnya sama, dan bahwa 52025-51143 = 486 - (- 396). Saya akan menambahkan catatan untuk menyebutkan masalah ini.1234567891234567/2145768375829475878
hasil dalam869253326028691/1510825213275018197 365314565205876/634943162554457681
. Perubahan ini menambahkan hanya 3 karakter tambahan.JavaScript, 131
Dengan notasi panah gemuk dan
eval
panggilan:The
179565/987657
stress test dilaksanakan di sekitar 35 detik pada Firefox, lebih banyak pada Chrome (~ 6 menit)Metode lebih cepat dan tanpa
eval
dan notasi panah gemukThe
179565/987657
stress test dilaksanakan di sekitar 5 detik.Tidak golf:
sumber
eval
. EEK2/6
memberikan1/3 2/5
, namun1/3
tidak kurang dari tetapi sama untuk2/6
.perl, 142 byte (155 tanpa CPAN)
Atau jika modul CPAN tidak diizinkan / 3-4 kali kode lebih cepat diperlukan:
Versi sebelumnya membutuhkan 9,55 detik pada mesin saya, versi terakhir 2,44 detik.
Kurang terbaca:
sumber