Anda mengayuh sampan menyusuri sungai arung yang cukup cepat. Tiba-tiba, dayung Anda meledak, dan Anda mendapati diri Anda dalam situasi berbahaya yang melaju cepat di sungai tanpa dayung. Untungnya, Anda masih memiliki keterampilan pemrograman, sehingga Anda memutuskan untuk mengukir program di samping sampan untuk membantu Anda selamat dari jeram. Namun, tidak banyak area permukaan di samping sampan untuk menulis program Anda, jadi Anda harus membuat program sesingkat mungkin.
Sungai dapat direpresentasikan sebagai grid 8 x 16. Kami akan label kolom dengan angka 0
untuk 7
dan baris dengan nomor 0
untuk 15
.
y
--------15
--------14
--------13
--------12
--------11
--------10
--------9
--------8
--------7
--------6
--------5
--------4
--------3
--------2
--------1
--------0
01234567
x
Atas: Sungai yang tenang dan biasa-biasa saja tanpa penghalang. Secara alami, ini bukan sungai tempat Anda berada.
Anda mulai pada koordinat (4, 0) dan dari sana bergerak tak terkendali ke atas sungai (yaitu vektor (0,1)
) sampai Anda menabrak batu (diwakili oleh o
dalam contoh-contoh ini). Ketika Anda menabrak batu, Anda akan memiliki peluang 55% untuk bergerak melewati batu ke kiri (yaitu vektor (-1,1)
) dan 45% peluang untuk bergerak melewati batu ke kanan (yaitu vektor (1,1)
). Jika sampan ada di kolom paling kiri atau kanan, sampan akan selalu bergerak ke tengah. Jika tidak ada batu, itu akan bergerak lurus ke atas.
y
----x---15
----xo--14
-o--x---13
----x---12
---ox---11
---x----10
---xo---9
---ox---8
----xo--7
-----x--6
----ox--5
-o--x---4
----x---3
----xo--2
----x---1
----x---0
01234567
Atas: Rute yang mungkin diambil kano, direpresentasikan menggunakan karakter x
Mengingat peta sungai, tulislah sebuah program yang akan menampilkan kemungkinan sampan di kolom yang diberikan.
Terima input dengan metode apa pun yang sesuai untuk program Anda (mis. STDIN, argumen baris perintah raw_input()
, membaca dari file, dll). Bagian pertama dari input adalah bilangan bulat tunggal dari 0 hingga 7, mewakili kolom yang akan dicari probabilitas programnya. Berikut ini adalah daftar tupel dalam bentuk yang x,y
mewakili posisi batu.
Sebuah contoh:
Memasukkan:
4 4,1 5,5 3,5
Ini akan menunjukkan sungai dengan batu di posisi (4,1), (5,5), dan (3,5), dan menanyakan kemungkinan sampan berakhir di kolom ke-4.
Keluaran:
0.495
Perhatikan bahwa dalam contoh ini, posisi batuan simetris, yang memungkinkan masalah diselesaikan dengan distribusi binomial. Ini tidak selalu terjadi!
Selain itu, sungai akan selalu bisa dilintasi. Artinya, tidak akan pernah ada dua batu yang diposisikan berdekatan satu sama lain secara horizontal. Lihat komentar Glenn untuk contoh kasus yang tidak mungkin.
Ini adalah kode golf, sehingga jumlah karakter yang paling rendah menang. Jangan ragu untuk bertanya di komentar jika spesifikasinya tidak jelas.
Jawaban:
GolfScript, 105 karakter
Versi GolfScript yang menjadi lebih panjang dari yang dimaksudkan - tetapi setiap upaya dengan pendekatan yang berbeda bahkan lebih lama. Masukan harus diberikan pada STDIN.
Contoh:
Kode beranotasi:
sumber
Ruby,
204191172 karakterItu secara rekursif mensimulasikan semua hasil yang mungkin sambil melacak probabilitas hasil masing-masing individu, kemudian menambahkan kemungkinan itu ke counter kumulatif kapan
y == 15
.Trik mewah:
c,*r=gets.split
- operator "splat" (*
) mengambil semua elemen yang tersisagets.split
dan menempelkannya dalamr
arraynext {something} if {condition}
: pada dasarnya setara dengan"Ditemukan" oleh berkembang dariif condition; something; return; end
kereturn something if condition
kebreak something if condition
, dan kemudian saya pikir saya akan mencoba lebih pendek "loop operator" untuk melihat apakah itu akan bekerja (yang itu, tentu saja).Terima kasih kepada @ MartinBüttner yang menyarankan untuk menggunakan operator ternary yang dirantai (yang akhirnya menjadi baris ketiga yang sangat besar dalam kode golf di atas) dan menghilangkan poin di atas (yang menyelamatkan 19 karakter (!)).
Saya memang menggunakan trik yang agak mewah dengan itu, meskipun: Saya menyadari bahwa
s[foo],s[bar]
tidak berfungsi di Ruby untuk dua pemanggilan metode dalam satu pernyataan. Jadi pada saya pertama kali berubah ke(_=s[foo],s[bar])
(variabel dummy), tapi kemudian aku sadar bahwa aku hanya bisa menambah dan membuang kembali nilai-nilai:s[foo]+s[bar]
. Ini hanya berfungsi karena panggilan kes
hanya akan "mengembalikan" panggilan lain kes
atau nomor (o[x]+=p
), jadi saya tidak perlu khawatir untuk memeriksanil
.Berbagai optimasi lainnya:
p
alih-alihputs
untuk mencetak nomor,<1
bukan==0
(karena kano tidak pernah meninggalkan sungai) dan perbandingan serupa di tempat lain,[0]*8
untuk probabilitas awal karena angka-angka Ruby selalu "lewat nilai"Tidak Terkumpul:
sumber
next X if Y
menjadi operator ternary bersarang? Nice find though, Anda mungkin ingin menambahkannya ke tips Ruby!C #
418364bytesSelesaikan program C # yang mengharapkan input dari STDIN. Bekerja dengan membaca batu ke dalam array semua lokasi di sungai, secara efektif membuat peta, dan kemudian hanya melakukan 16 iterasi probabilitas bergerak di sekitar array desimal 8-lebar sebelum menghasilkan hasilnya.
Kode yang diformat:
sumber
for(;j-->0;)
). Anda dapat menyingkirkan beberapa karakter dengan mengganti yang terakhirC.WriteLine
denganC.Write
. Juga, jika Anda menggunakanfloat
alih-alih,decimal
Anda dapat menyimpan beberapa byte lagi.decimal
karenafloat
tidak akan tepat, tetapi desimal harus dilakukan untuk masalah ini, tetapi mungkin bisa lolos begitu saja seperti yang Anda katakan. Saya akan dimasukkan ke dalamC.Write
jika saya berhasil golf ini lebih jauh karena mungkin lebih dekat dengan spesifikasi daripadaC.WriteLine
karena saya tidak berpikir 4 byte memerlukan suntingan untuk program ukuran ini;)Haskell, 256 byte
Ini adalah versi yang sangat tidak digunduli bersama dengan beberapa trik yang digunakan:
Trik terakhir yang saya gunakan adalah mencatat bahwa Anda dapat bertindak seolah-olah batu dalam satu baris sebenarnya dipisahkan oleh jumlah yang sangat kecil. Dengan kata lain, Anda dapat menerapkan transformator distribusi probabilitas untuk setiap batu pada baris yang sama secara berurutan dan dalam urutan apa pun yang Anda inginkan, daripada menerapkan semuanya secara bersamaan. Ini hanya berhasil karena masalah ini melarang dua batu yang berdekatan secara horizontal.
Jadi program mengubah lokasi masing-masing batu menjadi trafo distribusi probabilitas, dipesan oleh koordinat y batu Transformer kemudian dirantai secara berurutan dan diterapkan pada distribusi probabilitas awal. Dan itu dia!
sumber
Perl 169 Bytes
Baca dari STDIN.
Cukup lurus ke depan, secara implisit menggunakan kolom -1 dan 8 untuk menghaluskan kasus perbatasan. Probabilitas dapat dengan aman disebarkan ke setiap level berikutnya karena tidak ada batu yang berdekatan, sehingga satu run sudah mencukupi.
sumber
PHP, 358
Menggunakan kekuatan otak untuk menentukan jalur yang mungkin dan kemungkinannya sulit, dan mungkin akan membutuhkan lebih banyak kode daripada hanya mensimulasikan 1.000.000 kecelakaan kano. Oh, kemanusiaan!
Contoh:
Golf:
Versi ini tidak melakukan pencetakan cantik dan menampilkan probabilitas mengambang dari pendaratan kano di posisi yang ditentukan.
sumber
PHP, 274
Saya tidak bisa membaca / menulis GolfScript untuk menyelamatkan hidup saya, tetapi melirik pengajuan @ Howard menunjuk saya ke arah yang lebih baik daripada hanya mensimulasikan 1 juta kecelakaan kano.
Dimulai dengan serangkaian probabilitas untuk posisi awal, kita dapat dengan mudah membagi angka-angka itu setiap kali batu ditemukan.
Contoh Output:
Golf:
Contoh dijalankan:
sumber
Haskell, 237
Saya hanya berharap sampan dilengkapi dengan ghc yang diinstal ...
Trik dengan daftar tak terbatas dicuri dari Matt Noonan, pujian kepadanya!
Saya harap logika saya benar, tetapi contoh Matt
"5 4,4 1,5 5,3 3,6 2,9 4,12 3,13"
menghasilkan0.5613750000000001
dan contoh OP"4 4,1 5,5 3,5"
menghasilkan0.49500000000000005
, yang tampaknya benar terlepas dari beberapa kesalahan floating point.Ini dia sedang beraksi:
sumber