Konteks:
Seorang miliarder yang tertutup telah menciptakan acara permainan untuk menarik para programmer terbaik dan terpandai di dunia. Pada hari Senin di tengah malam, ia memilih satu orang dari kumpulan pelamar untuk menjadi kontestan minggu ini, dan memberi mereka permainan. Anda adalah kontestan yang beruntung minggu ini!
Game minggu ini:
Tuan rumah memberi Anda akses API ke tumpukan 10.000 amplop digital. Amplop ini diurutkan secara acak, dan di dalamnya berisi nilai dolar, antara $ 1 dan $ 10.000 (tidak ada dua amplop yang berisi nilai dolar yang sama).
Anda memiliki 3 perintah yang Anda inginkan:
Baca (): Baca angka dolar dalam amplop di bagian atas tumpukan.
Take (): Tambahkan angka dolar dalam amplop ke dompet permainan Anda, dan keluarkan amplop dari tumpukan.
Pass (): Lepaskan amplop di bagian atas tumpukan.
Aturan:
Jika Anda menggunakan Pass () pada amplop, uang di dalamnya hilang selamanya.
Jika Anda menggunakan Take () pada amplop yang berisi $ X, sejak saat itu, Anda tidak boleh menggunakan Take () pada amplop yang berisi <$ X. Ambil () pada salah satu amplop ini akan menambah $ 0 ke dompet Anda.
Tulis algoritma yang menyelesaikan permainan dengan jumlah uang maksimal.
Jika Anda menulis solusi dengan Python, jangan ragu untuk menggunakan pengontrol ini untuk menguji algoritma, milik @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca
Jika Anda menggunakan pengontrol, Anda tidak dapat mengakses global, Anda hanya dapat menggunakan 3 perintah API yang disediakan, dan variabel cakupan lokal. (@Beta Decay)
Catatan: "Maksimal" dalam hal ini berarti nilai median di dompet Anda setelah N> 50 berjalan. Saya berharap, meskipun saya ingin terbukti salah, bahwa nilai median untuk algoritma yang diberikan akan konvergen ketika N meningkat hingga tak terbatas. Jangan ragu untuk mencoba memaksimalkan mean, tetapi saya merasa bahwa mean lebih mungkin terlempar oleh N kecil daripada mediannya.
Sunting: mengubah jumlah amplop menjadi 10k untuk memudahkan pemrosesan, dan menjadikan Take () lebih eksplisit.
Sunting 2: Kondisi hadiah telah dihapus, mengingat pos ini menggunakan meta.
Skor tinggi saat ini:
PhiNotPi - $ 805.479
Reto Koradi - $ 803.960
Dennis - $ 770.272 (Revisi)
Alex L. - $ 714.962 (Revisi)
sumber
Jawaban:
CJam,
$ 87.143$ 700.424$ 720.327$ 727.580$ 770.272Program ini mensimulasikan seluruh permainan beberapa kali dan menghitung median.
Bagaimana cara menjalankannya
Saya telah mencetak kiriman saya dengan melakukan 100.00 tes berjalan:
Pendekatan
Untuk setiap amplop, kami melakukan hal berikut:
Perkirakan jumlah uang yang pasti akan hilang dengan mengambil amplop.
Jika R adalah konten dan M adalah maksimum yang telah diambil, jumlahnya dapat diperkirakan sebagai R (R-1) / 2 - M (M + 1) / 2 , yang memberikan uang semua amplop dengan konten X dalam interval (M, R) mengandung.
Jika belum ada amplop yang dilewati, estimasi akan sempurna.
Hitung jumlah uang yang pasti akan hilang dengan menyerahkan amplop.
Ini hanyalah uang yang berisi amplop.
Periksa apakah hasil bagi dari keduanya kurang dari 110 + 0,016E , di mana E adalah jumlah amplop yang tersisa (tidak termasuk amplop yang tidak dapat diambil lagi).
Jika demikian, ambil. Kalau tidak, lulus.
sumber
Python,
$ 680.646$ 714.962Mengambil jumlah yang lebih besar dan lebih besar dalam langkah ukuran antara $ 125 dan $ 190. Berlari dengan N = 10.000 dan dapatkan median $ 714962. Ukuran langkah ini berasal dari coba-coba dan tentu saja tidak optimal.
Kode lengkap, termasuk versi modifikasi dari pengontrol @ Maltysen yang mencetak bagan batang saat dijalankan:
Alamat BitCoin: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7
Wow OP terkirim! Terima kasih @LivingInformation!
sumber
max_taken
dalam kode Anda sendiri, karena itu bukan bagian dari API game resmi. Tapi itu sepele untuk dilakukan.read()
,take()
danpass()
metode dalam kode yang diposting, karena itu adalah "3 perintah yang Anda inginkan" berdasarkan definisi dalam pertanyaan.C ++, $ 803.960
Hasil yang dilaporkan adalah median dari 10.001 pertandingan.
sumber
C ++, ~ $ 815.000
Berdasarkan solusi Reto Koradi, tetapi beralih ke algoritma yang lebih canggih begitu ada 100 (valid) amplop yang tersisa, mengacak permutasi acak dan menghitung kenaikan berikutnya yang paling berat. Ini akan membandingkan hasil pengambilan dan tidak mengambil amplop, dan rakus akan memilih pilihan terbaik.
sumber
Java, $ 806.899
Ini dari uji coba 2501 putaran. Saya masih berusaha mengoptimalkannya. Saya menulis dua kelas, pembungkus dan pemain. Pembungkus instantiate pemain dengan jumlah amplop (selalu 10.000 untuk hal yang nyata), dan kemudian memanggil metode
takeQ
dengan nilai amplop atas. Pemain kemudian kembalitrue
jika mereka mengambilnya,false
jika mereka melewatinya.Pemain
Pembungkus
Penjelasan lebih rinci akan segera hadir, setelah saya menyelesaikan optimasi.
Gagasan intinya adalah untuk dapat memperkirakan hadiah dari bermain game dari set amplop tertentu. Jika set amplop saat ini adalah {2,4,5,7,8,9}, dan amplop atas adalah 5, maka ada dua kemungkinan:
Jika kita menghitung hadiah yang diharapkan dari {7,8,9} dan membandingkannya dengan hadiah yang diharapkan dari {2,4,7,8,9}, kita akan dapat mengetahui apakah mengambil 5 itu sepadan.
Sekarang pertanyaannya adalah, diberikan satu set amplop seperti {2,4,7,8,9} berapa nilai yang diharapkan? Saya menemukan nilai yang diharapkan tampaknya proporsional dengan jumlah total uang di set, tetapi berbanding terbalik dengan akar kuadrat dari jumlah amplop yang dibagi menjadi uang. Ini datang dari "sempurna" memainkan beberapa permainan kecil di mana semua amplop memiliki nilai yang hampir sama.
Masalah selanjutnya adalah bagaimana menentukan " jumlah efektif amplop." Dalam semua kasus, jumlah amplop diketahui persis dengan melacak apa yang telah Anda lihat dan lakukan. Sesuatu seperti {234.235.236} pasti tiga amplop, {231.232.233.234.235} pasti 5, tetapi {1,2.234.235.236} harus benar-benar dihitung sebagai 3 dan bukan 5 amplop karena 1 dan 2 hampir tidak berharga, dan Anda tidak akan pernah LULUS pada 234 jadi Anda kemudian dapat mengambil 1 atau 2. Saya punya ide untuk menggunakan entropi Shannon untuk menentukan jumlah efektif amplop.
Saya menargetkan perhitungan saya ke situasi di mana nilai-nilai amplop didistribusikan secara seragam selama beberapa interval, yang merupakan apa yang terjadi selama pertandingan. Jika saya mengambil {2,4,7,8,9} dan memperlakukannya sebagai distribusi probabilitas, entropinya adalah 1,50242. Kemudian saya lakukan
exp()
untuk mendapatkan 4.49254 sebagai jumlah efektif amplop.Taksiran hadiah dari {2,4,7,8,9} adalah
30 * 4.4925^-0.5 * 4/3 = 18.87
Jumlah pastinya
18.1167
.Ini bukan perkiraan yang tepat, tapi saya benar-benar bangga dengan seberapa baik ini cocok dengan data ketika amplop didistribusikan secara seragam dalam suatu interval. Saya tidak yakin dengan pengali yang benar (saya menggunakan 4/3 untuk saat ini) tetapi di sini adalah tabel data tidak termasuk pengali.
Regresi linier antara yang diharapkan dan aktual memberikan nilai R ^ 2 sebesar 0,999994 .
Langkah saya berikutnya untuk meningkatkan jawaban ini adalah meningkatkan estimasi ketika jumlah amplop mulai menjadi kecil, yaitu ketika amplop tidak kira-kira didistribusikan secara seragam dan ketika masalahnya mulai menjadi butiran.
Sunting: Jika ini dianggap layak bitcoin, saya baru saja mendapat alamat di(Ini di sini sejak penulis tantangan membagikan hadiah.)1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg
. Terima kasih!sumber