Todo dia, todo minuto, ... todo microssegundo, muitas decisões são tomadas pelo seu computador. Em linguagens de alto nível, elas geralmente assumem a forma de declarações como if, whilee for, mas no nível mais básico, existem instruções em linguagem de máquina chamadas instruções de desvio / salto . Os processadores modernos enfileiram as instruções em um pipeline , e isso significa que o processador precisa decidir se deve preencher o pipeline com instruções imediatamente após uma ramificação (ou seja, não é utilizada ) ou com as instruções no destino da ramificação.

Se o processador não acertar corretamente, as instruções que foram inseridas incorretamente no pipeline precisam ser ignoradas e as instruções corretas devem ser buscadas, causando um atraso. O trabalho do preditor de ramificação é tentar adivinhar se a ramificação será executada para evitar a ação cara de recarregar o pipeline.

Você deve escrever um preditor que, dada uma sequência de decisões passadas, adivinhe a próxima decisão corretamente. Seu programa pode ser escrito em qualquer idioma, desde que você especifique o link para o intérprete, se for um idioma obscuro / de golfe. Ele deve levar o histórico real do passado como seu primeiro argumento de linha de comando, mas não será fornecido para a primeira estimativa da sequência. Você deve retornar seu palpite, imprimindo-o em stdout. Uma decisão é da forma "y" ou "n". Cada caso de teste é uma sequência de 72 decisões, portanto, você pode assumir que o argumento histórico especificado nunca terá mais de 71 caracteres. Por exemplo, o teste "Alternando 1":

ynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynyn

Você será desqualificado se o seu programa:

• não retorna um resultado dentro de um segundo
• não retorna a you n(novas linhas não importam e são ignoradas)
• tenta modificar qualquer código ou arquivo associado a esse desafio, incluindo o código de outros concorrentes
• contém qualquer coisa maliciosa

Você pode usar um arquivo para persistência, se desejar, mas ele deve ter um nome exclusivo e estar em conformidade com o acima.

Este é um desafio de código , não de golfe de código . A vitória será concedida pelo preditor de preditor de ramificação ao candidato cuja solução predizer com sucesso a maioria dos ramos em todo o conjunto de testes. Testes:

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

O conjunto completo de testes e o programa runner estão situados neste repositório do GitHub . Basta adicionar seu preditor src/predictors.txtno formulário <name>,<command to run>e executar main.py. Já forneci dois preditores muito básicos para testes simples. Eu recomendaria uma largura de coluna de pelo menos 92 ao executar o corredor para obter uma saída agradável. Se você encontrar algum erro, entre em contato. :)

Compressor (Ruby), pontuação 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

Verifica se a cadeia atual seria mais compressível se 'y' ou 'n' fossem adicionados ao final. Se igualmente compressível, use o que é mais mostrado.

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

Procura uma recorrência linear no padrão e calcula o próximo termo. Para testar, salve como DéjàVu,MathematicaScript -script <file>.

Historiador (Kotlin), pontuação 1548/1656 ≈ 93,478%

Prevê o futuro do passado.

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 com: kotlinc Historian.kt
Executar com:kotlin HistorianKt

Localizador de padrões (Java), pontuação 1570/1656 (≈94,8%) 1532/1656 (≈92,5%)

Pequenas melhorias para padrões complexos.

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

}

Fatorio (Python3), pontuação 1563/1656 ≈ 94.38%

Fatora a sequência da esquerda para a direita em uma série de padrões repetidos e alternados. Favorece principalmente comprimentos de correspondência mais longos, mas escolhe repetir sobre padrões alternados e mais curtos ao longo de ciclos mais longos em 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), pontuação 1173/1656 ≈ 70,83%

Esse preditor simplesmente adivinha que sim se não houver histórico; caso contrário, repete o resultado real anterior.

import sys

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

Repetidor! (Python), pontuação 483/1656 ≈ 29,17%

Se não houver histórico, esse indicador adivinhar que não, caso contrário, repetirá o oposto do ú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), pontuação 1087/1656 ≈ 65.64%

Se houver pelo menos dois resultados anteriores iguais ou se houver um até agora, esse preditor escolherá o mesmo. Se não houver histórico, ele escolherá "y". Se houver pelo menos dois resultados e os dois mais recentes não forem os mesmos, ele escolherá o oposto dos mais recentes.

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"

Gostaria de deixar um comentário, mas o requisito de 50 representantes me impede.

Conseguiu uma pequena melhoria na resposta do @ histocrat

Compressor (Ruby), pontuação 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

Eu o aprimorei de várias maneiras diferentes, e uma melhoria de + 0,12% foi a melhor que encontrei.