Todos los días, cada minuto, ... cada microsegundo, su computadora toma muchas decisiones. En lenguajes de alto nivel, estos típicamente toman la forma de declaraciones como if, whiley for, pero en el nivel más básico existen instrucciones de lenguaje de máquina llamadas instrucciones de salto / rama . Los procesadores modernos ponen en cola las instrucciones en una tubería , y esto significa que el procesador necesita decidir si llenar la tubería con instrucciones inmediatamente después de una rama (es decir, no se toma ) o las instrucciones en el destino de la rama.

Si el procesador no adivina correctamente, las instrucciones que se ingresaron incorrectamente en la tubería deben ignorarse y las instrucciones correctas deben buscarse, lo que provoca un retraso. El trabajo del predictor de rama es tratar de adivinar si se tomará la rama para evitar la costosa acción de rellenar la tubería.

Debe escribir un predictor que, dada una secuencia de decisiones pasadas, adivine la siguiente decisión correctamente. Su programa se puede escribir en cualquier idioma, siempre que especifique el enlace a su intérprete si es un lenguaje oscuro / de golf. Debe tomar el historial real pasado como su primer argumento de línea de comandos, pero no se proporcionará para la primera aproximación de la secuencia. Luego debe devolver su suposición imprimiéndola en stdout. Una decisión tiene la forma "y" o "n". Cada caso de prueba es una secuencia de 72 decisiones, por lo que puede suponer que el argumento del historial especificado nunca tendrá más de 71 caracteres. Por ejemplo, la prueba "Alternar 1":

ynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynyn

Será descalificado si su programa:

• no devuelve un resultado dentro de un segundo
• no devuelve ni a yni n(las nuevas líneas no importan y se ignoran)
• intenta modificar cualquier código o archivo asociado con este desafío, incluido el código de otro contendiente
• contiene cualquier otra cosa maliciosa

Puede usar un archivo para persistencia si lo desea, pero debe tener un nombre único y cumplir con lo anterior.

Este es un desafío de código , no un código de golf . El predictor de rama otorgará la victoria al contendiente cuya solución predice con éxito la mayoría de las ramas en todo el conjunto de pruebas. Pruebas:

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

El conjunto completo de pruebas y el programa runner se encuentran en este repositorio de GitHub . Simplemente agregue su predictor src/predictors.txten el formulario <name>,<command to run>y ejecútelo main.py. Ya he proporcionado dos predictores muy básicos para pruebas simples. Recomendaría un ancho de columna de al menos 92 al ejecutar el corredor para obtener una buena salida. Si encuentra algún error con él, hágamelo saber. :)

Compresor (Ruby), puntaje 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

Comprueba si la cadena actual sería más comprimible si 'y' o 'n' se agregaran al final. Si es igualmente compresible, use el que se muestra más.

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

Busca una recurrencia lineal en el patrón y calcula el siguiente término. Para probar, guardar como DéjàVu,MathematicaScript -script <file>.

Historiador (Kotlin), puntaje 1548/1656 ≈ 93.478%

Predice el futuro del pasado.

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

Compilar con: kotlinc Historian.kt
Ejecutar con:kotlin HistorianKt

Buscador de patrones (Java), puntaje 1570/1656 (≈94.8%) 1532/1656 (≈92.5%)

Ligeras mejoras para patrones complejos.

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), puntaje 1563/1656 ≈ 94.38%

Factores de la secuencia de izquierda a derecha en una serie de patrones repetitivos y alternos. Principalmente favorece la duración de los partidos más largos, pero elige repetir sobre patrones alternos y más cortos sobre ciclos más largos en caso de empate.

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

Repetidor (Python), puntaje 1173/1656 ≈ 70.83%

Este predictor simplemente adivina sí si no hay historial, de lo contrario repite el resultado real anterior.

import sys

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

! Repetidor (Python), puntuación 483/1656 ≈ 29.17%

Si no hay historial, este predictor adivinará que no, de lo contrario repetirá lo contrario del último resultado real.

import sys

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

2-toucher (Python), puntaje 1087/1656 ≈ 65.64%

Si hubo al menos dos resultados anteriores que fueron iguales, o ha habido un resultado hasta ahora, este predictor elegirá lo mismo. Si no hay historial, elegirá "y". Si hubo al menos dos resultados y los dos más recientes no fueron iguales, se elegirá lo opuesto al más reciente.

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"

Dejaría un comentario, pero el requisito de 50 repeticiones me lo impide.

Pude obtener una pequeña mejora en la respuesta de @ histocrat

Compresor (Ruby), puntaje 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

Lo modifiqué de varias maneras diferentes, y una mejora de + 0.12% fue lo mejor que encontré.