Terinspirasi oleh The Great API Easter Egg Hunt!
Ringkasan
Tugas Anda adalah mencari integer yang telah ditentukan di "ruang Collatz" (akan dijelaskan nanti) menggunakan langkah sesedikit mungkin.
pengantar
Tantangan ini didasarkan pada dugaan Collatz yang terkenal, semoga semua orang di sini setidaknya mendengar. Ini adalah rekap yang diambil dari Mencetak nomor Super Collatz .
The Collatz Urutan (juga disebut 3x + 1 masalah) adalah di mana Anda mulai dengan bilangan bulat positif, untuk contoh ini kita akan menggunakan 10, dan menerapkan set ini langkah-langkah untuk itu:
if n is even: Divide it by 2 if n is odd: Multiply it by 3 and add 1 repeat until n = 1
Jarak Collatz C(m,n)
antara dua angka m
dan n
, untuk tujuan tantangan ini, adalah jarak antara dua angka dalam grafik Collatz (Kredit ke @tsh untuk memberi tahu saya tentang konsep ini), yang didefinisikan sebagai berikut: (menggunakan 21
dan 13
sebagai contoh ):
Tuliskan urutan Collatz untuk m
(dalam hal ini, 21
):
21, 64, 32, 16, 8, 4, 2, 1
Tuliskan urutan Collatz untuk n
(dalam hal ini, 13
):
13, 40, 20, 10, 5, 16, 8, 4, 2, 1
Sekarang hitung berapa banyak angka yang muncul hanya di salah satu urutan. Ini didefinisikan sebagai jarak Collatz antara m
dan n
. Dalam hal ini 8
, yaitu,
21, 64, 32, 13, 40, 20, 10, 5
Jadi kami memiliki jarak Collatz antara 21
dan 13
sebagai C(21,13)=8
.
C(m,n)
memiliki sifat-sifat baik berikut:
C(m,n)=C(n,m)
C(m,n)=0 iff. m=n
Semoga definisi C(m,n)
sekarang jelas. Ayo mulai berburu telur di ruang Collatz!
Pada awal permainan, pengontrol memutuskan posisi telur paskah, yang diekspresikan oleh koordinat satu dimensi: Bilangan bulat dalam interval [p,q]
(dengan kata lain, bilangan bulat antara p
dan q
, kedua ujungnya inklusif).
Posisi telur tetap konstan sepanjang permainan. Kami akan menyatakan koordinat ini sebagai r
.
Anda sekarang dapat membuat tebakan awal 0 , dan itu akan direkam oleh pengontrol. Ini adalah ronde 0 Anda. Jika Anda sangat beruntung bahwa Anda melakukannya dengan benar di tempat pertama (yaitu 0 = r), permainan berakhir, dan skor Anda adalah 0
(Semakin rendah skor, semakin baik). Kalau tidak, Anda memasuki ronde 1 dan Anda membuat tebakan baru 1 , ini berlangsung sampai Anda benar, yaitu n = r, dan skor Anda akan menjadi n
.
Untuk setiap putaran setelah 0, controller memberi Anda salah satu dari umpan balik berikut sehingga Anda dapat membuat tebakan yang lebih baik berdasarkan informasi yang diberikan. Mari kita asumsikan Anda saat ini di n
putaran ke - th dan karenanya tebakan Anda adalah n
- "Kamu menemukannya!" jika a n = r, dalam hal ini pertandingan berakhir dan Anda mencetak skor
n
. - "Kamu lebih dekat :)" jika C (a n , r) <C (a n-1 , r)
- "Anda berputar-putar di sekitar telur" jika C (a n , r) = C (a n-1 , r)
- "Anda lebih jauh :(" jika C (a n , r)> C (a n-1 , r)
Untuk menyimpan beberapa byte, saya akan memanggil respons sebagai "Benar", "Lebih Dekat", "Sama", "Lebih Jauh", dalam urutan yang disajikan di atas.
Berikut adalah contoh game dengan p=1,q=15
.
- a 0 = 10
- a 1 = 11, respons: "Closer"
- a 2 = 13, respons: "Lebih jauh"
- a 3 = 4, respons: "Lebih jauh"
- a 4 = 3, respons: "Closer"
- a 5 = 5, respons: "Sama"
- a 6 = 7, respons: "Benar"
Skor: 6
.
Tantangan
Rancang strategi deterministik untuk bermain game p=51, q=562
dengan skor terbaik.
Jawaban harus menjelaskan algoritme secara rinci. Anda dapat melampirkan kode apa pun yang membantu menjelaskan algoritma. Ini bukan codegolf sehingga Anda dianjurkan untuk menulis kode yang dapat dibaca.
Jawaban harus mencakup skor terburuk yang mungkin mereka raih untuk semua kasus yang mungkin terjadi r
, dan yang dengan skor terburuk terendah menang. Dalam kasus seri, algoritma yang memiliki skor rata-rata yang lebih baik untuk semua kemungkinan r
(yang juga harus dimasukkan dalam jawaban) menang. Tidak ada pemutus dasi lebih lanjut dan kami mungkin memiliki beberapa pemenang pada akhirnya.
Spesifikasi
- Untuk mengulangi,
r
terletak pada interval[51,562]
. - Celah default berlaku.
Bounty (Ditambahkan setelah jawaban pertama diposting)
Saya pribadi dapat menawarkan hadiah untuk jawaban di mana semua tebakan dibuat dalam kisaran [51,562]
sementara masih memiliki skor terburuk yang cukup rendah.
sumber
Jawaban:
Ruby, 196
Ini jauh lebih sulit daripada yang saya pikirkan. Saya harus menangani banyak kasus yang tidak jelas dan berakhir dengan banyak kode jelek. Tapi itu sangat menyenangkan! :)
Strategi
Setiap Urutan Collatz berakhir dengan urutan kekuatan 2 (mis: [16, 8, 4, 2, 1]). Segera setelah kekuatan 2 ditemukan, kita membaginya dengan 2 sampai kita mencapai 1. Mari kita sebut kekuatan pertama 2 dalam urutan pow2 terdekat (karena ini juga merupakan kekuatan terdekat 2 untuk nomor kita menggunakan Jarak Collatz). Untuk rentang yang diberikan (51-562), semua angka pow2 terdekat yang mungkin adalah: [16, 64, 128, 256, 512, 1024]
Versi pendek
Algoritma melakukan:
Versi terperinci
Diberikan permainan dengan nomor target
r
, strateginya adalah sebagai berikut:r
beberapa langkah mungkin.Hasil
Menjalankan algoritma untuk semua angka dalam kisaran 51-562 membutuhkan waktu sekitar satu detik pada PC normal dan skor totalnya adalah 38665.
Kode
Cobalah online!
sumber
skor terburuk: 11, jumlah skor: 3986
Semua tebakan berada dalam jangkauan
[51,562]
.Algoritme saya:
vals
, awalnya set berisi semua angka dalam jangkauan[51,562]
.Di setiap langkah, lakukan hal berikut:
guess
di kisaran[51,562]
sehingga, ketika nilai-nilai dalamvals
(tidak termasukguess
sendiri) dibagi menjadi 3 set yang sesuai dengan hasil yang mungkinCloser
,Same
danFarther
, ukuran maksimum yang 3 set minimum.Jika ada beberapa kemungkinan nilai
guess
memuaskan di atas, pilih yang terkecil.guess
.vals
sehingga mereka tidak bisa memberikan hasil itu.Implementasi referensi saya yang ditulis dalam C ++ dan Bash berjalan dalam waktu sekitar 7,6 detik pada mesin saya dan memberikan skor / jumlah skor terburuk seperti yang dijelaskan dalam judul.
Mencoba semua nilai tebakan pertama yang mungkin akan memakan waktu sekitar 1,5 jam di mesin saya. Saya mungkin mempertimbangkan untuk melakukan itu.
sumber