Ini adalah yang kedua dari serangkaian teka-teki yang akan saya posting setiap hari Senin di Midnight PST. Teka-teki pertama terletak di sini .
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 4 perintah yang Anda inginkan:
Baca (): Baca angka dolar dalam amplop di bagian atas tumpukan.
Take (): Tambahkan angka dolar di dalam amplop ke dompet permainan Anda, dan keluarkan amplop dari tumpukan.
Pass (): Lepaskan amplop di bagian atas tumpukan.
Oracle (M): Mengembalikan nilai rata-rata amplop M berikutnya dalam tumpukan, tidak termasuk yang saat ini dapat Anda Baca ().
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.
Jika Anda menggunakan Oracle (M) pada giliran T, amplop T + 1 hingga rata-rata T + M akan dikembalikan. Oracle () dinonaktifkan hingga giliran T + M.
Tulis algoritma yang menyelesaikan permainan dengan jumlah uang maksimal.
Jika Anda menulis algoritme Anda dengan Python, jangan ragu untuk menggunakan pengontrol ini yang disediakan oleh @Maltysen: https://gist.github.com/livinginformation/70ae3f2a57ecba4387b5
Catatan 1: "Maksimal" dalam hal ini berarti nilai median di dompet Anda setelah N> = 1000 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.
Catatan 2: karena semua solusi untuk bagian sebelumnya dari teka-teki ini valid di sini, pengeposan ulang memiliki nilai yang kecil. Hanya peningkatan algoritmik dari teka-teki sebelumnya yang akan dipertimbangkan untuk bagian II.
Sunting: Kondisi hadiah telah dihapus, mengingat postingan ini tentang meta.
sumber
M
, di mana Anda bisa memilihM
.Jawaban:
Groovy
$ 713337$ 817829$ 818227Kode bootstrap:
Algoritma
Saya membandingkan nilai yang tersisa dengan nilai yang mungkin. Skrip ini tidak cepat (membutuhkan 1 menit per 1000x simulasi) ... tetapi akan melakukan simulasi secara bersamaan.
Saya tidak tahu mengapa algoritme saya berfungsi, tetapi itu hanya coba-coba: menggabungkan operasi matematika dan memanipulasi konstanta. Saya menjalankannya 5000x untuk skor saat ini, dalam upaya untuk mengurangi fluktuasi skor (+/- $ 4000 tergantung pada jumlah iterasi).
Bahkan tanpa nubuat pada akhirnya, itu harus tetap (nyaris) mengalahkan solusi @ orlp untuk puzzle sebelumnya.
sumber
C # - $ 803,603 sekarang -> $ 804,760 (dengan oracle)
Kode Bootstrap
Kode Game:
Kredit adalah milik Reto Koradi ( /codegolf//a/54181/30910 )
Sunting: Penggunaan Dasar dari Oracle diimplementasikan. Jika oracle berikutnya di atas ambang batas untuk menggunakan memperluas amplop saat ini ke indeks Indeks Oracle. Ini tidak sering memukul tetapi ITU Peningkatan ;-)
sumber
Python - $ 74112
Hanya ambil, jika nilai saat ini lebih rendah dari nilai berikutnya (yaitu Anda dapat mengambil keduanya).
Python - (masih menghitung rata-rata)
Jawaban ini membutuhkan SANGAT PANJANG untuk menghitung. Ini mencapai sekitar $ 670.000 . Saya ingat setiap amplop yang saya lihat. Setiap kali saya harus membuat keputusan, saya menghasilkan dua daftar amplop yang tersisa yang berpotensi saya tambahkan ke dompet saya jika saya mengambil amplop saat ini atau meninggalkannya masing-masing.
Saya tidak mengoptimalkan kode.
Dan init_game dimulai seperti ini:
sumber
C # - $ 780.176
Periksa apakah nilai berikutnya berada di bawah 5% dari semua nilai yang tersisa. Dapatkan lebih santai saat kita sampai akhir.
Dan kelas game saya, sangat jelek, kelas game bahkan tidak memvalidasi jika oracle diizinkan, tetapi karena saya hanya menggunakan Oracle (1) yang seharusnya tidak menjadi masalah.
sumber
Java, $ 804.991
Skor dari 1001 putaran. Mungkin terlalu dekat untuk menelepon antara jawaban ini dan jawaban Stephan Schinkel .
Ini didasarkan pada jawaban saya dalam tantangan sebelumnya, karena ia menggunakan perhitungan berbasis entropi yang sama untuk memperkirakan imbalan. Perbedaan utama adalah bahwa itu sekarang hanya mengambil amplop berpasangan (1 & 2, lalu 3 & 4, dan seterusnya) dan melihat kemungkinan kombinasi take-take, take-pass, pass-take, dll. Ini juga menghitung skor perkiraan tepat ketika jumlah amplop yang valid benar-benar kecil.
"Pembungkus" yang saya tulis sebenarnya bukan pembungkus sejati, itu hanya memberikan amplop berpasangan alih-alih memanggil
Oracle(1)
fungsi setiap putaran lainnya.Secara keseluruhan, saya akan mengatakan bahwa, meskipun kompleksitasnya semakin meningkat, bot ini benar-benar tidak lebih baik dari bot saya sebelumnya.
Pemain
Pengendali
Alamat Bitcoin: 1BVBs9ZEP8YY4EpV868nxi2R23YfL7hdMq
sumber
Python 3 - $ 615570
Sebenarnya tidak menggunakan oracle ... Eh :)
Buat daftar semua amplop sebelumnya dan periksa apakah amplop saat ini kurang dari jumlah amplop sebelumnya dalam 10 peningkatan amplop.
sumber
Python, 87,424
Berikut ini adalah algoritma yang sederhana dan mudah, tujuh yang beruntung.
Pada dasarnya apa yang dilakukannya adalah mengkonversi read () ke string dan memeriksa apakah ada tujuh di dalamnya. Jika ada, dibutuhkan amplop. Jika tidak, ia melewatinya.
Rata-rata sekitar 81.000, saya belum melacak.
sumber