Jeden Tag, jede Minute, ... jede Mikrosekunde werden viele Entscheidungen von Ihrem Computer getroffen. In Hochsprachen haben diese normalerweise die Form von Anweisungen wie if, whileund for, aber auf der grundlegendsten Ebene gibt es Anweisungen in Maschinensprache, die als Verzweigungs- / Sprunganweisungen bezeichnet werden . Moderne Prozessoren stellen Anweisungen in einer Pipeline in die Warteschlange , und dies bedeutet, dass der Prozessor entscheiden muss, ob die Pipeline mit Anweisungen unmittelbar nach einer Verzweigung (dh nicht genommen ) oder den Anweisungen am Verzweigungsziel gefüllt werden soll.

Wenn der Prozessor nicht richtig errät, müssen die Anweisungen, die falsch in die Pipeline eingegeben wurden, ignoriert und die richtigen Anweisungen abgerufen werden, was zu einer Verzögerung führt. Die Aufgabe des Zweigprädiktors besteht darin, zu erraten, ob der Zweig genommen wird, um die kostspieligen Maßnahmen zum Nachfüllen der Pipeline zu vermeiden.

Sie müssen einen Prädiktor schreiben, der bei einer Abfolge vergangener Entscheidungen die nächste Entscheidung richtig errät. Ihr Programm kann in jeder Sprache geschrieben werden, vorausgesetzt, Sie geben den Link zu seinem Interpreter an, wenn es sich um eine obskure / Golfsprache handelt. Es muss den tatsächlichen Verlauf der Vergangenheit als erstes Befehlszeilenargument verwenden, wird jedoch nicht für die erste Vermutung der Sequenz bereitgestellt. Sie müssen dann Ihre Vermutung zurückgeben, indem Sie sie auf stdout drucken. Eine Entscheidung hat die Form "y" oder "n". Jeder Testfall besteht aus einer Folge von 72 Entscheidungen. Sie können also davon ausgehen, dass das angegebene Verlaufsargument niemals länger als 71 Zeichen sein wird. Zum Beispiel der Test "Alternating 1":

ynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynyn

Sie werden disqualifiziert, wenn Ihr Programm:

• gibt nicht innerhalb einer Sekunde ein Ergebnis zurück
• gibt weder ein ynoch ein n(neue Zeilen spielen keine Rolle und werden ignoriert)
• versucht, Code oder Dateien zu ändern, die mit dieser Herausforderung verbunden sind, einschließlich des Codes anderer Konkurrenten
• enthält alles andere böswillige

Sie können eine Datei für die Persistenz verwenden, wenn Sie dies wünschen. Sie muss jedoch eindeutig benannt sein und den oben genannten Anforderungen entsprechen.

Dies ist eine Code-Herausforderung , kein Code-Golf . Der Sieg wird vom Zweigprädiktor-Prädiktor dem Konkurrenten gewährt, dessen Lösung die meisten Zweige in der gesamten Testsuite erfolgreich vorhersagt. Tests:

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

Die vollständigen Tests und das Runner-Programm befinden sich in diesem GitHub-Repository . Fügen Sie einfach Ihren Prädiktor src/predictors.txtin das Formular ein <name>,<command to run>und führen Sie ihn aus main.py. Ich habe bereits zwei sehr grundlegende Prädiktoren für einfache Tests bereitgestellt. Ich würde eine Spaltenbreite von mindestens 92 empfehlen, wenn der Runner für eine schöne Ausgabe ausgeführt wird. Wenn Sie irgendwelche Fehler damit entdecken, lassen Sie es mich bitte wissen. :) :)

Kompressor (Rubin), Punktzahl 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

Überprüft, ob die aktuelle Zeichenfolge komprimierbarer wäre, wenn am Ende 'y' oder 'n' hinzugefügt würde. Wenn Sie gleichermaßen komprimierbar sind, verwenden Sie diejenige, die am häufigsten angezeigt wird.

DéjàVu (Mathematica), Punktzahl 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"}];

Sucht nach einer linearen Wiederholung im Muster und berechnet den nächsten Term. Speichern Sie zum Testen unter DéjàVu,MathematicaScript -script <file>.

Historiker (Kotlin), Punktzahl 1548/1656 ≈ 93,478%

Prognostiziert die Zukunft aus der Vergangenheit.

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')
}

Kompilieren mit: kotlinc Historian.kt
Ausführen mit:kotlin HistorianKt

Pattern-Finder (Java), Punktzahl 1570/1656 (94,8%) 1532/1656 (92,5%)

Leichte Verbesserungen für komplexe Muster.

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;
    }

}

Factorio (Python3), Punktzahl 1563/1656 ≈ 94,38%

Faktorisiert die Sequenz von links nach rechts in eine Reihe sich wiederholender und abwechselnder Muster. Bevorzugt in erster Linie längere Übereinstimmungslängen, wählt jedoch die Wiederholung über abwechselnde Muster und kürzere über längere Zykluslängen im Falle eines Unentschieden.

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()

Repeater (Python), Punktzahl 1173/1656 ≈ 70,83%

Dieser Prädiktor errät einfach Ja, wenn es keine Historie gibt, andernfalls wiederholt er das vorherige tatsächliche Ergebnis.

import sys

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

! Repeater (Python), Punktzahl 483/1656 ≈ 29,17%

Wenn es keine Historie gibt, wird dieser Prädiktor nein erraten, andernfalls wird das Gegenteil des letzten tatsächlichen Ergebnisses wiederholt.

import sys

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

2-Toucher (Python), Punktzahl 1087/1656 ≈ 65,64%

Wenn es mindestens zwei vorherige Ergebnisse gab, die gleich waren, oder wenn es bisher ein Ergebnis gab, wird dieser Prädiktor dasselbe wählen. Wenn es keinen Verlauf gibt, wird "y" ausgewählt. Wenn es mindestens zwei Ergebnisse gab und die letzten beiden nicht gleich waren, wird das Gegenteil des jüngsten gewählt.

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"

Ich würde einen Kommentar hinterlassen, aber die Anforderung von 50 Wiederholungen hindert mich daran.

Konnte die Antwort von @ histocrat geringfügig verbessern

Kompressor (Rubin), Punktzahl 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

Ich habe es auf verschiedene Arten optimiert und eine Verbesserung von + 0,12% war das Beste, was ich gefunden habe.