Prediktor cabang menantang

8

Setiap hari, setiap menit, ... setiap mikrodetik, banyak keputusan dibuat oleh komputer Anda. Dalam bahasa tingkat tinggi, ini biasanya mengambil bentuk pernyataan seperti if, whiledan 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 yatau n(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 , bukan . 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.txtdalam 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. :)

Doddy
sumber
3
Saya menurunkan tantangan ini karena menurut saya itu tidak menangkap esensi dari prediktor cabang. Saat ini tantangan Anda lebih pada prediksi umum AI daripada prediksi cabang. Paling tidak tantangan prediktor cabang harus memiliki persyaratan memori yang sangat ketat, riwayat tambahan, dan setiap keputusan harus merupakan fungsi dari alamat memori . Juga, tantangan Anda tidak mandiri.
orlp
4
Saya suka tantangan ini. Saya pikir murni case test 50/50 acak adalah ide yang buruk. Namun, 80/20 acak akan baik-baik saja, serta kasus uji lainnya yang mencakup bagian yang acak (seperti beberapa kasus uji Anda saat ini lakukan). Saya akan merekomendasikan untuk memasukkan semua test case Anda pada posting Anda.
Nathan Merrill
@NathanMerrill Terima kasih, saya telah menghapus semua keacakan dari tes.
Doddy
1
@Doddy Maaf, maksudku adalah permainan menebak koin . Satu pemain terus menghasilkan nol dan satu, dan yang lain mencoba menebaknya.
orlp
2
apakah kita seharusnya menghindari pengoptimalan untuk kasus uji ini? seseorang akan mengirimkan algoritme "sempurna" yang membandingkan sejarah dengan test corpus yang dikenal dan skor 95% +
Sparr

Jawaban:

14

Kompresor (Ruby), skor 1502/1656 ≈ 90,7%

require 'zlib'
input = $*[0].to_s.chomp
recent_input = input[-35..-1] || input
puts recent_input.chars.uniq.min_by { |char| [Zlib::Deflate.deflate(input+char,9).size,-input.count(char),-input[-10..-1].to_s.count(char)] } || ?y

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.

histokrat
sumber
7

DéjàVu (Mathematica), skor 503/552 ≈ 91,123%

If[Length[$ScriptCommandLine] < 2, Print["y"]; Exit[]];
input = Characters[$ScriptCommandLine[[2]]] /. {"y" -> 1, "n" -> 0};
For[test = Length[input], ! 
   ListQ[ker = FindLinearRecurrence[input[[-test ;;]]]], test--];
Print[LinearRecurrence[ker, input[[-test ;; Length[ker] - test - 1]], 
     test + 1][[-1]] /. {1 -> "y", _ -> "n"}];

Mencari pengulangan linier dalam pola, dan menghitung istilah berikutnya. Untuk pengujian, simpan sebagai DéjàVu,MathematicaScript -script <file>.

LegionMammal978
sumber
2

Sejarawan (Kotlin), skor 1548/1656 ≈ 93,478%

Memprediksi masa depan dari masa lalu.

fun main(args : Array<String>) {
    if (args.size == 0) {
        println('y')
        return
    }
    val history = args[0].reversed()
    var bestLength = 0
    var ys = 0
    var ns = 0
    for (i in 1..history.length-1) {
        var length = 0
        var j = i
        while (j < history.length) {
            if (history[j] == history[j - i]) {
                length++
            } else {
                break
            }
            j++
        }
        if (length > bestLength) {
            bestLength = length
            ys = 0
            ns = 0
        }
        if (length == bestLength) {
            if (history[i - 1] == 'y') {
                ys++
            } else {
                ns++
            }
        }
    }
    println(if (bestLength == 0) history[0] else if (ys >= ns) 'y' else 'n')
}

Kompilasi dengan: kotlinc Historian.kt
Jalankan dengan:kotlin HistorianKt

TheNumberOne
sumber
1

Penemu Pola (Jawa), skor 1570/1656 (≈94,8%) 1532/1656 (≈92,5%)

Perbaikan sedikit untuk pola yang kompleks.

public class Main {

    public static void main(String[] args) {
        if (args.length == 0) {
            System.out.print("y");
            return;
        }
        System.out.print(new Pattern(args[0]).getNext());
    }

}

class Pattern {

    private String pattern;
    private int index;
    private int length;

    public Pattern(String string) {
        setPattern(string);
    }

    private void setPattern(String string) {
        if (string.length() == 0) {
            this.pattern = "y";
            this.index = 0;
            this.length = 1;
            return;
        }
        if (string.length() == 1) {
            this.pattern = string;
            this.index = 0;
            this.length = 1;
            return;
        }
        if (string.startsWith("ynnyyy")) {
            this.pattern = "ynnyyynyynnn";
            this.index = string.length() % 12;
            this.length = 12;
            return;
        }
        this.length = 0;
        char first = string.charAt(0);
        char current = first;
        boolean hasReverse = false;
        while (length < string.length() - 1 && !(hasReverse
                && current == first)) {
            hasReverse |= current != first;
            length++;
            current = string.charAt(length);
        }
        if (!(hasReverse && current == first)) {
            this.pattern = Character.toString(current);
            this.index = 0;
            this.length = 1;
            return;
        }
        this.pattern = string.substring(0, length);
        int i = length;
        while (i <= string.length() - length) {
            if (!string.substring(i, i + length).equals(pattern)) {
                setPattern(string.substring(i));
                return;
            }
            i += length;
        }
        this.index = string.length() % i;
        if (!string.substring(i).equals(pattern.substring(0, index))) {
            setPattern(string.substring(i));
        }
    }

    public char getNext() {
        char result = pattern.charAt(index);
        index = (index + 1) % length;
        return result;
    }

}
Cangkir Kopi
sumber
@TheNumberOne Anda yakin? Jika demikian, saya akan menempatkan itu sebagai skor. Pekerjaan bagus pada posting Anda; kamu memenangkan saya!
TheCoffeeCup
Ah, Anda meningkatkan kinerja Anda untuk test case 1-2-3.
TheNumberOne
@TheNumberOne Ya, setelah beberapa pengujian serius, saya menyadari bahwa itu membunuh persentase saya. Pertanyaannya tidak persis mengatakan bahwa apa yang saya lakukan tidak diizinkan ...
TheCoffeeCup
1

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.

def main():
    if len(sys.argv) < 2:
        print('y')
        sys.stdout.flush()
        return
    history = sys.argv[1]
    while history:
        score = 0
        period = 0
        l = 0
        for p in range(1, len(history)):
            if history[0] == history[p]:
                m = lambda a, b: a == b
                s0 = 1
            else:
                m = lambda a, b: a != b
                s0 = 0
            s = 0
            for i in range(len(history)):
                j = i + p
                if j < len(history):
                    if not m(history[i], history[j]):
                        break
                    s += 1
            if s > score or s == score and s0 > score0:
                score = s
                score0 = s0
                period = p
                match = m
                l = j
        if period == 0:
            print(history[0])
            sys.stdout.flush()
            return
        if l >= len(history):
            break
        l = (l // period) * period
        history = history[l:]
    print('y' if match(history[-period], 'y') else 'n')
    sys.stdout.flush()

if __name__ == '__main__':
    main()
pengguna1502040
sumber
0

Pengulang (Python), skor 1173/1656 ≈ 70,83%

Prediktor ini hanya menebak ya jika tidak ada riwayat, jika tidak mengulangi hasil aktual sebelumnya.

import sys

if len(sys.argv) == 1:
   print "y"
else:
   print sys.argv[1][-1:]

! 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.

import sys

if len(sys.argv) == 1:
   print "n"
else:
   if sys.argv[1][-1:] == "y":
      print "n"
   else:
      print "y"

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.

import sys

if len(sys.argv) == 1:
   print "y"
elif len(sys.argv[1]) == 1:
   print sys.argv[1][-1:]
else:
   l = len(sys.argv[1])

   if sys.argv[1][l - 2:l - 1] == sys.argv[1][-1:]:
      print sys.argv[1][-1:]
   else:
      if sys.argv[1][-1:] == "y":
         print "n"
      else:
         print "y"
Doddy
sumber
0

Saya akan meninggalkan komentar, tetapi persyaratan 50 rep mencegah saya.

Mampu mendapatkan sedikit perbaikan pada jawaban @ histocrat

Kompresor (Ruby), skor 1504/1656 ≈ 90,82%

require 'zlib'
input = $*[0].to_s.chomp
recent_input = input[-35..-1] || input
puts recent_input.chars.uniq.min_by { |char| [Zlib::Deflate.deflate(input+char,9).size,-input[-3..-1].to_s.count(char),-input.count(char)] } || ?y

Saya men-tweak dengan berbagai cara, dan peningkatan + 0,12% adalah yang terbaik yang saya temukan.

Connor Clark
sumber