pengantar
Dalam tantangan ini, Anda akan diberikan daftar nomor floating point non-negatif yang diambil secara independen dari beberapa distribusi probabilitas. Tugas Anda adalah menyimpulkan distribusi itu dari angka-angka. Untuk membuat tantangan menjadi layak, Anda hanya memiliki lima distribusi untuk dipilih.
U
, distribusi seragam pada interval [0,1].T
, distribusi segitiga pada interval [0,1] dengan mode c = 1/2.B
, distribusi beta pada interval [0,1] dengan parameter α = β = 1/2.E
, distribusi eksponensial pada interval [0, ∞) dengan tingkat λ = 2.G
, distribusi gamma pada interval [0, ∞) dengan parameter k = 3 dan θ = 1/6.
Perhatikan bahwa semua distribusi di atas memiliki tepat 1/2.
Tugas
Input Anda adalah array nomor floating point non-negatif, dengan panjang antara 75 dan 100 inklusif. Keluaran Anda akan menjadi salah satu dari huruf-huruf tersebut UTBEG
, berdasarkan distribusi mana yang Anda tebak angka-angkanya.
Aturan dan Penilaian
Anda dapat memberikan program lengkap atau fungsi. Celah standar tidak diijinkan.
Dalam repositori ini , ada lima file teks, satu untuk setiap distribusi, masing-masing panjangnya persis 100 baris. Setiap baris berisi daftar koma-dibatasi 75 hingga 100 mengapung diambil secara independen dari distribusi dan dipotong menjadi 7 digit setelah titik desimal. Anda dapat memodifikasi pembatas agar sesuai dengan format array asli bahasa Anda. Agar memenuhi syarat sebagai jawaban, program Anda harus mengklasifikasikan dengan benar setidaknya 50 daftar dari setiap file . Skor dari jawaban yang valid adalah jumlah byte + jumlah total daftar yang salah klasifikasi . Skor terendah menang.
Jawaban:
Julia,
6062 byte +252 kesalahan =8264Ini cukup sederhana. Varian untuk distribusi sebagian besar berbeda - 1/4 untuk eksponensial, 1/8 untuk beta, 1/12 untuk gamma dan seragam, dan 1/24 untuk segitiga. Dengan demikian, jika kita menggunakan varians (di sini dilakukan menggunakan
std
deviasi standar, akar kuadrat varians) untuk menentukan distribusi yang mungkin, kita hanya perlu melakukan lebih banyak untuk membedakan gamma dari seragam; untuk itu, kami mencari nilai yang lebih besar dari 1 (menggunakanany(k.>1)
) - yang mengatakan, kami melakukan pemeriksaan untuk eksponensial dan gamma, karena meningkatkan kinerja secara keseluruhan.Untuk menyimpan byte, pengindeksan string
"EGTBU"
dilakukan alih-alih langsung mengevaluasi ke string dalam kondisi.Untuk pengujian, simpan file txt ke dalam direktori (pertahankan nama apa adanya), dan jalankan Julia REPL di direktori tersebut. Kemudian, lampirkan fungsi ke nama sebagai
dan gunakan kode berikut untuk mengotomatiskan pengujian (ini akan membaca dari file, mengubahnya menjadi array array, menggunakan fungsi, dan output untuk setiap ketidakcocokan):
Output akan terdiri dari baris yang berisi case yang tidak cocok, distribusi yang benar -> distribusi yang ditentukan, dan varians yang dihitung (mis.
13 G->E 0.35008999281668357
Berarti bahwa baris ke-13 dalam G.txt, yang seharusnya merupakan distribusi gamma, ditentukan sebagai eksponensial) distribusi, dengan standar deviasi 0,35008999 ...)Setelah setiap file, itu juga menampilkan jumlah ketidakcocokan untuk file itu, dan kemudian pada akhirnya juga menampilkan ketidakcocokan total (dan harus membaca 2 jika dijalankan seperti di atas). Kebetulan, seharusnya 1 ketidakcocokan untuk G.txt dan 1 ketidakcocokan untuk U.txt
sumber
R,
202 192 184 182 162154 byte + 0 kesalahanIni didasarkan pada rumus Bayesian P (D = d | X = x) = P (X = x | D = d) * P (D = d) / P (X = x), di mana D adalah distribusi dan X adalah sampel acak. Kami memilih d sehingga P (D = d | X = x) adalah yang terbesar dari 5.
Saya mengasumsikan flat sebelumnya (yaitu P (D = di) = 1/5 untuk i dalam [1,5]), yang berarti bahwa P (D = d) dalam pembilang adalah sama dalam semua kasus (dan penyebutnya akan sama saja dalam semua kasus), jadi kita bisa bermain golf semuanya kecuali P (x = X | D = d), yang (kecuali untuk distribusi segitiga) menyederhanakan fungsi asli di R.
ungolfed:
Perhatikan bahwa versi yang tidak dikenali tidak persis sama dengan versi golf karena menyingkirkan penyebut menghindari kasus Inf / Inf yang terjadi jika Anda membiarkan distribusi beta melebihi interval tertutup [0,1] alih-alih (0, 1) - seperti halnya data sampel. Pernyataan if tambahan akan menangani itu tetapi karena itu hanya untuk tujuan ilustrasi, itu mungkin tidak layak menambahkan kompleksitas yang bukan inti dari algoritma.
Terima kasih @Alex A. untuk pengurangan kode tambahan. Khusus untuk yang. Max!
sumber
{
dan yang sebelum penutupan}
, dan aliasingprod
, misalnyaP=prod
, lalu melakukanP(dunif(x))
, dll. Fungsi tidak memerlukan nama untuk menjadi kiriman yang valid, sehingga Anda dapat menghapusp=
. Juga, pekerjaan luar biasa. :)which.max(c(u,r,b,e,g))
di tempatc(u,r,b,e,g)==max(c(u,r,b,e,g))
.function(x){c("U","T","B","E","G")[which.max(lapply(list(dunif(x),sapply(x,function(y)max(0,2-4*abs(.5-y))),dbeta(x,.5,.5),dexp(x,2),dgamma(x,3,6)),prod))]}
CJam, 76
Kode sumber panjangnya 43 byte dan salah mengklasifikasikan 33 daftar.
Verifikasi
Ide
Membedakan distribusi eksponensial dan gamma dari yang tersisa itu mudah, karena hanya distribusi yang mengambil nilai lebih besar dari 1 .
Untuk memutuskan antara gamma , eksponensial , dan lainnya, kami melihat nilai tertinggi kedua dari sampel.
Jika terletak pada [1,5, ∞) , kami menebak gamma .
Jika terletak di [1, 1.5) , kami menebak eksponensial .
Jika terletak pada [0, 1) , kami memiliki tiga kemungkinan yang tersisa.
Distribusi yang tersisa dapat dibedakan dengan persentase nilai sampel yang terletak dekat dengan rata-rata ( 0,5 ).
Kami membagi panjang sampel dengan jumlah nilai yang masuk (0,3, 0,7) dan melihat hasil bagi.
Jika terletak pada (1, 2) , kami menebak segitiga .
Jika terletak di (2, 3) , kami menebak seragam .
Jika terletak di (3, ∞) , kami menebak beta .
Kode
sumber
Matlab,
428328 byte + 33 kesalahan klasifikasiProgram ini pada dasarnya membandingkan CDF nyata dengan perkiraan yang diberikan data, dan kemudian menghitung jarak rata-rata antara keduanya: Saya pikir gambar menjelaskan lebih lanjut:
Data yang diperlihatkan dalam gambar ini di sini menunjukkan dengan cukup jelas bahwa itu milik distribusi pirus, karena cukup dekat dengan yang itu, sehingga pada dasarnya adalah apa yang program saya lakukan. Mungkin bisa bermain golf lebih banyak. Bagi saya itu pertama-tama tantangan konseptual, tidak terlalu golf.
Pendekatan ini juga tidak tergantung pada pdf yang dipilih, itu akan bekerja untuk setiap set distribusi.
Kode (ungolfed) berikut harus menunjukkan bagaimana hal itu dilakukan. Versi golf di bawah ini.
Versi sepenuhnya golf:
sumber
Perl, 119 byte + 8 kesalahan klasifikasi = 127
Saya telah membuat pohon keputusan kecil pada tiga fitur:
Diminta dengan
perl -F, -lane -e '...'
. Saya tidak yakin apakah saya harus menambahkan penalti untuk parameter non-standar. Jika koma adalah spasi, kurasa aku bisa pergi tanpa -F,Output yang sedikit diformat (tanpa flag -l) adalah:
sumber
Python, 318 byte + 35 kesalahan klasifikasi
Ide: distribusi ditebak berdasarkan nilai-p dari tes Kolmogorov-Smirnov.
Uji
sumber