The branch predictor challenge

Question

Every day, every minute, ... every microsecond, many decisions are made by your computer. In high-level languages, these typically take the form of statements like if, while and for, but at the most basic level there exist machine language instructions called branch/jump instructions. Modern processors queue instructions up in a pipeline, and this means that the processor needs to decide whether to fill the pipeline with instructions immediately following a branch (i.e. it is not taken) or the instructions at the branch destination.

If the processor does not guess correctly, the instructions which have been wrongly entered into the pipeline need to be ignored and the correct instructions must be fetched, causing a delay. The job of the branch predictor is to try and guess whether the branch will be taken to avoid the costly action of refilling the pipeline.

You must write a predictor that will, given a sequence of past decisions, guess the next decision correctly. Your program can be written in any language, provided you specify the link to its interpreter if it's an obscure/golfing language. It must take the past actual history as its first command-line argument, but it will not be provided for the first guess of the sequence. You must then return your guess by printing it to stdout. A decision is of the form "y" or "n". Each test case is a sequence of 72 decisions, so you can assume that the specified history argument will never be longer than 71 characters. For example, the "Alternating 1" test:

ynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynyn

You will be disqualified if your program:

• does not return a result within one second
• does not return either a y or n (new lines don't matter and are ignored)
• attempts to modify any code or file associated with this challenge, including other contender's code
• contains anything otherwise malicious

You may use a file for persistence if you wish, but it must be uniquely named and conform to the above.

This is a code-challenge, not code-golf. Victory will be granted by the branch predictor predictor to the contender whose solution successfully predicts the most branches in the whole test suite. 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

The full set of tests and runner program are situated at this GitHub repository. Simply add your predictor to src/predictors.txt in the form <name>,<command to run> and run main.py. I have provided two very basic predictors already for simple testing. I would recommend a column width of at least 92 when running the runner for nice output. If you happen to spot any bugs with it, please let me know. :)

Answer 1

Compressor (Ruby), score 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

Checks whether the current string would be more compressible if 'y' or 'n' were added to the end. If equally compressible, use the one that's shown up the most.

Answer 2

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

Looks for a linear recurrence in the pattern, and computes the next term. For testing, save as DéjàVu,MathematicaScript -script <file>.

Answer 3

Historian (Kotlin), score 1548/1656 ≈ 93.478%

Predicts the future from the past.

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

Compile with: kotlinc Historian.kt
Run with: kotlin HistorianKt

Answer 4

Factorio (Python3), score 1563/1656 ≈ 94.38%

Factors the sequence from left to right into a series of repeating and alternating patterns. Primarily favours longer match lengths, but chooses repeating over alternating patterns and shorter over longer cycle lengths in case of a tie.

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

Answer 5

Pattern-Finder (Java), score 1570/1656 (≈94.8%) 1532/1656 (≈92.5%)

Slight improvements for complex patterns.

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

}

Answer 6

Repeater (Python), score 1173/1656 ≈ 70.83%

This predictor simply guesses yes if there's no history, otherwise repeats the previous actual outcome.

import sys

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

!Repeater (Python), score 483/1656 ≈ 29.17%

If there's no history this predictor will guess no, otherwise will repeat the opposite of the last actual outcome.

import sys

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

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

If there were at least two previous outcomes that were the same, or there has been one outcome so far, this predictor will choose the same. If there is no history, it will choose "y". If there were at least two outcomes and the most recent two were not the same, it will choose the opposite of the most recent.

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"

Answer 7

I would leave a comment, but the 50 rep requirement prevents me.

Was able to get a small improvement on @histocrat's answer

Compressor (Ruby), score 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

I tweaked it in a number of different ways, and a +0.12% improvement was the best I found.