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
orn
(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. :)