Setiap hari, setiap menit, ... setiap mikrodetik, banyak keputusan dibuat oleh komputer Anda. Dalam bahasa tingkat tinggi, ini biasanya mengambil bentuk pernyataan seperti if
, while
dan for
, tetapi pada tingkat paling dasar ada instruksi bahasa mesin yang disebut instruksi cabang / lompat . Prosesor modern mengantre instruksi dalam sebuah pipa , dan ini berarti bahwa prosesor perlu memutuskan apakah akan mengisi pipa dengan instruksi segera setelah cabang (yaitu tidak diambil ) atau instruksi di tujuan cabang.
Jika prosesor tidak menebak dengan benar, instruksi yang telah salah dimasukkan ke dalam pipa harus diabaikan dan instruksi yang benar harus diambil, menyebabkan penundaan. Tugas prediktor cabang adalah mencoba dan menebak apakah cabang akan diambil untuk menghindari tindakan mahal untuk mengisi ulang pipa.
Anda harus menulis alat prediksi yang akan, mengingat urutan keputusan sebelumnya, menebak keputusan selanjutnya dengan benar. Program Anda dapat ditulis dalam bahasa apa pun, asalkan Anda menentukan tautan ke penerjemahnya jika itu bahasa yang tidak jelas / golf. Itu harus mengambil sejarah aktual masa lalu sebagai argumen baris perintah pertama, tetapi itu tidak akan disediakan untuk tebakan pertama dari urutan. Anda kemudian harus mengembalikan tebakan Anda dengan mencetaknya ke stdout. Keputusan berbentuk "y" atau "n". Setiap test case adalah urutan dari 72 keputusan, sehingga Anda dapat mengasumsikan bahwa argumen histori yang ditentukan tidak akan pernah lebih dari 71 karakter. Misalnya, tes "Bergantian 1":
ynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynyn
Anda akan didiskualifikasi jika program Anda:
- tidak mengembalikan hasil dalam satu detik
- tidak mengembalikan a
y
ataun
(baris baru tidak masalah dan diabaikan) - mencoba mengubah kode atau file apa pun yang terkait dengan tantangan ini, termasuk kode pesaing lainnya
- mengandung apa pun yang berbahaya
Anda dapat menggunakan file untuk kegigihan jika Anda menginginkannya, tetapi itu harus dinamai secara unik dan sesuai dengan yang di atas.
Ini adalah tantangan kode , bukan golf kode . Kemenangan akan diberikan oleh prediktor prediktor cabang kepada pesaing yang solusinya berhasil memprediksi sebagian besar cabang di seluruh rangkaian uji. Tes:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy,All yes
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn,All no
ynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynyn,Alternating 1
nnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyynnyy,Alternating 2
yyynnnyyynnnyyynnnyyynnnyyynnnyyynnnyyynnnyyynnnyyynnnyyynnnyyynnnyyynnn,Alternating 3
nnnnyyyynnnnyyyynnnnyyyynnnnyyyynnnnyyyynnnnyyyynnnnyyyynnnnyyyynnnnyyyy,Alternating 4
yyyyyynnnnnnyyyyyynnnnnnyyyyyynnnnnnyyyyyynnnnnnyyyyyynnnnnnyyyyyynnnnnn,Alternating 5
nnnnnnnnnnnnyyyyyyyyyyyynnnnnnnnnnnnyyyyyyyyyyyynnnnnnnnnnnnyyyyyyyyyyyy,Alternating 6
yyyyyyyyyyyyyyyyyynnnnnnnnnnnnnnnnnnyyyyyyyyyyyyyyyyyynnnnnnnnnnnnnnnnnn,Alternating 7
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyynnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn,Alternating 8
yynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyynyyn,2-1
ynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnnynnn,1-3
nyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyy,5-1
nnnnnnnnnnnynnnnnnnnnnnynnnnnnnnnnnynnnnnnnnnnnynnnnnnnnnnnynnnnnnnnnnny,1-11
nyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyynyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy,35-1
yynnnnyynnnnyynnnnyynnnnyynnnnyynnnnyynnnnyynnnnyynnnnyynnnnyynnnnyynnnn,2-4
ynnyyynyynnnynnyyynyynnnynnyyynyynnnynnyyynyynnnynnyyynyynnnynnyyynyynnn,1-2-3
ynynynynynynynynynynynynynynynynynynyyyyyyyyyyyyyyyyyynnnnnnnnnnnnnnnnnn,A1/A7
yyyyyynnnnnnyyyyyynnnnnnyyyyyynnnnnnnnyynnyynnyynnyynnyynnyynnyynnyynnyy,A5/A2
nnnnnnnnnnnnyyyyyyyyyyyynnnnnnnnnnnnyyyynnnnyyyynnnnyyyynnnnyyyynnnnyyyy,A6/A4
nyyyyynyyyyynyyyyynyyyyynyyyyynyyyyynyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy,5-1/35-1
yyynnnyyynnnyyynnnnyyyyyyyyyyyyyyyyyyyyyyynyyyyynyyyyyyynnnnyynnnnyynnnn,A3/Y/5-1/2-4
yynnnnyynnnnyynnnnnyynnnynnyyynyynnnnnnynnnynnnynnnynnyynyynyynyynyynyyn,2-4/1-2-3/1-3/2-1
Set lengkap tes dan program pelari terletak di repositori GitHub ini . Cukup tambahkan prediktor Anda ke src/predictors.txt
dalam formulir <name>,<command to run>
dan jalankan main.py
. Saya telah menyediakan dua alat prediksi yang sangat mendasar untuk pengujian sederhana. Saya akan merekomendasikan lebar kolom setidaknya 92 ketika menjalankan pelari untuk hasil yang bagus. Jika Anda menemukan bug apa pun di dalamnya, beri tahu saya. :)
sumber
Jawaban:
Kompresor (Ruby), skor 1502/1656 ≈ 90,7%
Cek apakah string saat ini akan lebih kompresibel jika 'y' atau 'n' ditambahkan ke bagian akhir. Jika sama-sama kompresibel, gunakan yang paling banyak ditampilkan.
sumber
DéjàVu (Mathematica), skor 503/552 ≈ 91,123%
Mencari pengulangan linier dalam pola, dan menghitung istilah berikutnya. Untuk pengujian, simpan sebagai
DéjàVu,MathematicaScript -script <file>
.sumber
Sejarawan (Kotlin), skor 1548/1656 ≈ 93,478%
Memprediksi masa depan dari masa lalu.
Kompilasi dengan:
kotlinc Historian.kt
Jalankan dengan:
kotlin HistorianKt
sumber
Penemu Pola (Jawa), skor 1570/1656 (≈94,8%)
1532/1656 (≈92,5%)Perbaikan sedikit untuk pola yang kompleks.
sumber
Factorio (Python3), skor 1563/1656 ≈ 94,38%
Faktor urutan dari kiri ke kanan menjadi serangkaian pola berulang dan bergantian. Terutama mendukung panjang pertandingan yang lebih panjang, tetapi memilih mengulangi lebih dari pola bolak-balik dan lebih pendek dari panjang siklus yang lebih lama dalam kasus dasi.
sumber
Pengulang (Python), skor 1173/1656 ≈ 70,83%
Prediktor ini hanya menebak ya jika tidak ada riwayat, jika tidak mengulangi hasil aktual sebelumnya.
! Pengulang (Python), skor 483/1656 ≈ 29,17%
Jika tidak ada riwayat, prediktor ini akan menebak tidak, jika tidak akan mengulangi kebalikan dari hasil aktual terakhir.
2-toucher (Python), skor 1087/1656 ≈ 65,64%
Jika setidaknya ada dua hasil sebelumnya yang sama, atau sejauh ini ada satu hasil, prediktor ini akan memilih yang sama. Jika tidak ada riwayat, itu akan memilih "y". Jika setidaknya ada dua hasil dan yang terbaru tidak sama, itu akan memilih kebalikan dari yang terbaru.
sumber
Saya akan meninggalkan komentar, tetapi persyaratan 50 rep mencegah saya.
Mampu mendapatkan sedikit perbaikan pada jawaban @ histocrat
Kompresor (Ruby), skor 1504/1656 ≈ 90,82%
Saya men-tweak dengan berbagai cara, dan peningkatan + 0,12% adalah yang terbaik yang saya temukan.
sumber