Tantangan ini didasarkan pada gagasan Inverter Plouffle .
Tulis program dalam bahasa apa pun yang melakukan hal berikut:
Dimasukkan sebagai input bilangan rasional non-negatif yang
X
ditulis dalam desimal, misalnya 34.147425.Mengembalikan ekspresi matematika menggunakan hanya bilangan bulat non-negatif, spasi putih, tanda kurung, dan operator biner berikut:
- Tambahan
+
- Pengurangan
-
- Perkalian
*
- Divisi
/
- Eksponensial
^
Ekspresi harus dievaluasi
X
, atau setidaknya setuju dengan semua digitX
. Untuk melanjutkan contoh, output yang benar bisa13 + 20^(5/4) / 2
, karena 13 + 20 ^ (5/4) / 2 = 34.1474252688 ...- Tambahan
Output opsional dapat ditulis dalam notasi Polandia (awalan) atau membalikkan notasi Polandia (postfix), yaitu
+ 13 / ^ 20 / 5 4 2
baik-baik saja.
Program ini tunduk pada pembatasan berikut:
Celah standar dilarang! Secara khusus, program tidak dapat membaca tabel pencarian eksternal.
Kode sumber program harus lebih pendek dari 1024 karakter.
Program dengan rasio kompresi rata-rata terendah akan menang.
Untuk menentukan rasio kompresi rata-rata, Anda dapat menggunakan skrip Python berikut, atau menulis program setara Anda sendiri. Berikut adalah daftar 1000 angka acak.
import random
def f(x):
# edit this function so that it will return
# the output of your program given x as input
return "1 + 1"
random.seed(666)
S = 1000 # number of samples
t = 0.0
for n in xrange(0, S):
# pick a random decimal number
x = random.uniform(0, 1000)
# compute the compression ratio
# length of output / length of input
r = len(f(x).translate(None, " +-*/^()")) / float(len(str(x).translate(None, ".")))
t += r
print "Your average compression ratio is:", t / S
Semoga berhasil!
CATATAN:
Spasi putih dalam output tidak wajib. String seperti
1+1
,,1 +2
atau1 + 2
, semuanya baik-baik saja. Memang, skrip untuk menghitung skor tidak menghitung spasi putih dan tanda kurung dalam panjang output. Namun, perhatikan bahwa penggunaan spasi putih diperlukan jika Anda memilih Polandia atau membalikkan notasi Polandia.Mengenai notasi infiks yang biasa, aturan diutamakan adalah sebagai berikut: pertama semua eksponensial (
^
), lalu semua divisi (/
), lalu semua multiplikasi (*
), lalu semua penambahan (+
) dan semua pengurangan (-
). Tapi saya tidak tahu seberapa penting ini, karena Anda dapat menggunakan tanda kurung.Cara untuk mengedit fungsi
f
dalam skrip di atas bisa sebagai berikut, namun saya pikir itu tergantung pada sistem operasi Anda; pada GNU / Linux berfungsi. Beri nama program Anda "inverter" (atau "inverter.exe") dan letakkan di direktori yang sama dengan skrip Python. Program Anda harus mendapatkanX
argumen pertama dari baris perintah dan mengembalikan ekspresi dalam STDOUT. Kemudian editf
sebagai berikut:import os def f(x): return os.popen("./inverter " + str(x)).read()
EDIT: Sebagai konsekuensi dari komentar Thomas Kwa, sekarang operator tidak berkontribusi pada panjangnya ekspresi. Tantangannya harus lebih "menantang".
X = 5.23
nilai5.2301
ok, tapi5.2299
tidak?Jawaban:
Haskell, 1.08404005439
Ini menggunakan
approxRational
fungsi yang mengubah angka floating point menjadi fraksi dengan akurasi epsilon yang diberikan. Itu hanya mengembalikan fraksi ini. Karena Haskell mencetak rasional dengan%
di-antara, kita harus menggantinya dengan tanda pembagian/
.Parameter akurasi dihitung dari nomor input. Kita harus memperhitungkan bahwa semua angka harus cocok, jadi
4.39
tidak masalah untuk4.3
tetapi4.29
tidak. Saya menambahkan a5
ke nomor dan akurasinya adalah4999
pada tempat desimal yang sama dengan yang ditambahkan5
, misalnyaMisalnya
34.147425
->43777/1282
.Sunting: aturan untuk keakuratan telah berubah. Kasing uji mencakup angka hingga 11 desimal dan semua harus cocok.
Sunting II: sepertinya skrip Python menyediakan tidak menghapus baris baru, jadi saya telah mengubah dari
putStrLn
menjadiputStr
.Sunting III: lagi, aturan penilaian baru
sumber
1e-6
juga berfungsi, tetapi ini bukan codegolf ...Mathematica,
1.10121.10976107226107Sejauh ini, ini memiliki skor terendah! Memberikan yang rasional dengan penyebut terkecil yang diberi angka. (Maaf atas ketidakbacaannya, lupa bahwa ini bukan kontes golf sebentar.) Beberapa pengujian:
sumber
Python, 1.25927791772
Saya terkejut tidak ada orang lain yang mencoba pendekatan yang jelas, yang menimbulkan sekitar 26% overhead:
Ini baru saja dikonversi
XX.XXXX
menjadiXXXXXX/10^4
dan sebagainya. Untuk sebagian besar angka uji, ini berarti mengkonversi 12 digit (dan titik desimal yang tidak terhitung) menjadi 12 digit yang sama ditambah tiga lagi (ditambah dua simbol yang tidak terhitung).sumber
JavaScript 1.7056771894771656
Sangat sederhana, skor sangat buruk
sumber
Python, 1.9901028749
Fraksi yang berlanjut ternyata tidak menjadi pesaing yang serius, sayangnya.
contoh:
sumber
Python, 1.10900874126
Sebenarnya mengevaluasi fraksi lanjutan dalam jawaban saya sebelumnya menghasilkan setara dengan jawaban Matematika @ LegionMammal978, yang saya pikir adalah optimum naif. Melakukan lebih baik dari ini akan memerlukan menjadi kreatif dengan mewakili bilangan bulat, mungkin termasuk mencari fraksi sub-optimal untuk mendapatkan bilangan bulat yang lebih mudah diwakili.
contoh:
sumber