分支预测挑战

Question

每一天每一分钟..。每一秒，你的电脑就会做出很多决定。在高级语言中，这些语言通常以if、while和for等语句的形式出现，但在最基本的级别上，存在着称为分支/跳转指令分支/跳转指令的机器语言指令。现代处理器在管道中将指令排队，这意味着处理器需要决定是在分支(即不接收)之后，还是在分支目的地上用指令填充管道。

如果处理器猜错了，则需要忽略错误输入管道的指令，必须获取正确的指令，从而导致延迟。分支预测器的工作是试图猜测是否会采取分支，以避免昂贵的行动，重新填充管道。

您必须编写一个预测器，根据过去的决策序列，正确地猜测下一个决定。您的程序可以用任何语言编写，只要您指定它的解释器链接(如果它是一种模糊/高尔夫语言)。它必须以过去的实际历史作为它的第一个命令行参数，但是它不会提供给对序列的第一个猜测。然后，您必须通过打印到stdout来返回您的猜测。决定的形式是"y“或"n”。每个测试用例都是由72个决策组成的序列，因此您可以假设指定的历史参数不会超过71个字符。例如，“交替1”测试：

ynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynynyn

如果您的程序：

• 不会在一秒钟内返回结果。
• 不返回y或n (新行无关紧要，被忽略)
• 尝试修改与此挑战相关的任何代码或文件，包括其他竞争者的代码
• 包含任何其他恶意的内容

如果您愿意的话，您可以使用一个持久化文件，但是它必须有唯一的名称，并且符合上面的要求。

这是一个代码挑战，不是密码-高尔夫。胜利将由分支预测器授予竞争者，其解决方案成功地预测了整个测试套件中最多的分支。测试：

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

完整的测试和转轮程序位于这个GitHub存储库。只需将您的预测器添加到src/predictors.txt的表单<name>,<command to run>中，并运行main.py。我已经为简单测试提供了两个非常基本的预测器。我建议在运行转轮时，列宽度至少为92，以获得良好的输出。如果你碰巧发现有什么问题，请告诉我。:)

Answer 1

压缩机，得分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

检查如果将'y‘或'n’添加到末尾，当前字符串是否更可压缩。如果同样可压缩，请使用显示最多的。

Answer 2

历史学家(科特林)，1548/1656

≈93.478%

从过去预测未来。

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

用：kotlinc Historian.kt编译

运行：kotlin HistorianKt

Answer 3

Factorio (Python3)，得分1563/1656≈94.38%

将从左到右的序列分解成一系列重复和交替的模式。主要倾向于更长的匹配长度，但选择重复而不是交替的模式和更短的周期更长的长度，在领带的情况下。

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