8
\$\begingroup\$

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 , not . 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. :)

\$\endgroup\$
14
  • 3
    \$\begingroup\$ I downvoted this challenge because in my opinion it does not capture the essence of a branch predictor. Right now your challenge is more about general predicion AI rather than a branch predictor. At the very least a branch predictor challenge must have very stringent memory requirements, incremental history, and every decision must be a function of a memory address. Also, your challenge is not self-contained. \$\endgroup\$
    – orlp
    Jan 20, 2016 at 21:25
  • 4
    \$\begingroup\$ I like this challenge. I think that a purely 50/50 random test case is a bad idea. However, an 80/20 random would be fine, as well as other test cases that include parts that are random (as some of your test cases currently do). I'd recommend including all of your test cases on your post. \$\endgroup\$ Jan 20, 2016 at 21:29
  • \$\begingroup\$ @NathanMerrill Thanks, I've removed all randomness from tests. \$\endgroup\$
    – Doddy
    Jan 20, 2016 at 21:35
  • 1
    \$\begingroup\$ @Doddy Sorry, I meant coin guessing game. One player keeps generating zeros and ones, and the other tries to guess then. \$\endgroup\$
    – orlp
    Jan 20, 2016 at 22:19
  • 2
    \$\begingroup\$ are we supposed to avoid optimizing for these test cases? someone is going to just submit a "perfect" algorithm that compares the history to the known test corpus and scores 95%+ \$\endgroup\$
    – Sparr
    Jan 21, 2016 at 2:10

7 Answers 7

14
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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

}
\$\endgroup\$
3
  • \$\begingroup\$ @TheNumberOne Are you sure? If so, I will put that as the score. Good job on your post though; you win me! \$\endgroup\$ Jan 23, 2016 at 18:07
  • \$\begingroup\$ Ah, you improved your performance for the 1-2-3 test case. \$\endgroup\$ Jan 24, 2016 at 23:48
  • \$\begingroup\$ @TheNumberOne Yes, after some serious testing, I realised that was killing my percentage. The question does not exactly say that what I did was not allowed... \$\endgroup\$ Jan 25, 2016 at 0:36
1
\$\begingroup\$

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()
\$\endgroup\$
0
\$\begingroup\$

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"
\$\endgroup\$
0
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.