code-golf - Code Golf : Fractran

Question

锁定。这个问题及其答案是locked因为这个问题是题外话，但具有历史意义。它目前不接受新的答案或互动。








挑战

编写一个程序，作为 Fractran口译员。在任何语言中，按字符数计算最短的口译员是赢家。您的程序必须接受两个输入:要执行的 fractran 程序和输入整数 n。该程序可以采用任何对您的程序来说方便的形式——例如，一个 2 元组列表或一个平面列表。输出必须是单个整数，即执行结束时寄存器的值。

分形 enzyme

Fractran 是由 John Conway 发明的一种微不足道的深奥语言.一个 fractran 程序由一个正分数列表和一个初始状态 n 组成。解释器维护一个程序计数器，最初指向列表中的第一个分数。 Fractran 程序以下列方式执行:

检查当前状态与当前程序计数器下的分数的乘积是否为整数。如果是，则将当前状态乘以当前分数并将程序计数器重置到列表的开头。

推进程序计数器。如果到达列表末尾，则停止，否则返回步骤 1。

有关 Fractran 工作原理和原因的详细信息，请参阅 the esolang entry和 this entry关于好数学/坏数学。

测试向量

程序: [(3, 2)]
输入: 72 (2332)
输出: 243 (35)

程序: [(3, 2)]
输入: 1296 (2434)
输出: 6561 (38)

程序: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)]
输入: 72 (2332)
输出: 15625 (56)

奖励测试向量:

您的提交不需要正确执行最后一个程序才能成为可接受的答案。但是，如果是这样，那就太赞了!

程序: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)]
输入: 60466176 (210310)
输出: 7888609052210118054117285652827862296732064351090230047702789306640625 (5100)

提交和评分

程序严格按字符长度排序 - 最短的最好。随意提交一个布局合理、文档齐全的代码以及一个“缩小”版本的代码，这样人们就可以看到发生了什么。

不允许使用“J”语言。这是因为在其中一个链接页面上的 J 中已经有一个众所周知的解决方案。 如果你是J粉丝，对不起!

然而，作为额外的奖励，任何能够在 fractran 中提供工作 fractran 口译员的人都将获得 500 点声望奖励。万一有多个自托管口译员，分数最少的口译员将获得赏金。

优胜者

在提交包含 1779 个分数的自托管 fractran 解决方案后，正式获胜者是 Jesse Beder's solution .然而，实际上，该解决方案即使执行 1+1 也太慢了。

令人难以置信的是，这已经被另一种 fractran 解决方案击败了 - Amadaeus's solution只有 84 个分数!在我的引用 Python 解决方案上运行时，它能够在几秒钟内执行前两个测试用例。它对分数使用了一种新颖的编码方法，这也值得仔细研究。

荣誉提及:

Stephen Canon's solution , 在 x86 程序集的 165 个字符中(28 个字节的机器码)

Jordan's solution在 ruby​​ 的 52 个字符中 - 处理长整数

Useless's solution在 Python 的 87 个字符中，虽然不是最短的 Python 解决方案，但它是为数不多的非递归解决方案之一，因此可以轻松处理更难的程序。它也非常具有可读性。

Answer 1

Fractran - 1779 分数

(编辑:固定)

(我希望人们仍然关注这个线程，因为这花了一段时间!)

看起来SO不会让我发布这么长的东西，所以我发布了Fractran源here .

输入指定如下:

首先，我们编码一个分数 m/n = p_0^a0... p_k^ak经过:

从 1 开始。然后，对于每个 ai :

乘以 p_2i^ai如果 ai > 0

乘以 p_2i+1^{-ai}如果 a_i < 0

这样，我们将任何分数编码为正整数。现在，给定一个程序(编码分数 F0、F1、...的序列)，我们将其编码为

p_0^F0 p1^F1 ...

最后，解释器的输入由下式给出:

2^(program) 3^(input) 5

哪里 program和 input编码如上。例如，在第一个测试题中， 3/2被编码为 15 ，所以程序被编码为 2^15 ;和 108被编码为 500 .所以，我们通过

2^{2^15} 3^500 5

到程序。输出，然后是形式

2^(program) 3^(output)

所以在第一个例子中，它将是

2^{2^15} 3^3125

它是如何工作的？

我写了一种编译成 Fractran 的元语言。它允许函数(简单的 Fractran 和其他函数的序列)和 while循环和 if声明(为了方便!)。可以找到该代码 here .

如果您想自己将该代码编译为 Fractran，可以找到我的 (C++) 程序 here [tar.gz]。在令人惊叹的 dogfooding 展示(和炫耀)中，我使用了我的 C++ YAML 解析器 yaml-cpp ，所以你必须下载并链接它。对于 yaml-cpp 和“编译器”，您都需要 CMake用于跨平台生成文件。

这个程序的用法是:

./fracc interpreter.frp

它从标准输入读取函数的名称，并将相应的“伪分数”(我将在稍后解释)写入标准输出。所以要编译解释器(解释函数)，你可以运行

echo "Interpret" | ./fracc interpreter.frp > interpret

输出(“pseudo-Fractran”)将是一系列行，每行都有一串空格分隔的数字。一条线对应一个分数:如果 n该行中的第一个数字是 an ，那么分数是 p_n^an 的乘积.

将其转换为 Fractran 非常容易，但是如果您很懒，可以使用 to-fractions.py . [ 备注 : 之前我有一个 C++ 程序，我不小心忽略了整数溢出。我将它翻译成 Python 以避免这种情况。]

输入注意事项 :如果你想以这种方式测试不同的功能，约定总是相同的。它在伪 Fractran 中有许多参数(通常是函数上面的注释解释了这一点)，所以给它它想要的，加上 1在下一个槽上(所以在普通的 Fractran 中，乘以它不会使用的第一个素数)。这是函数开始运行的“信号”位。

然而，

我不建议实际尝试运行 Fractran 解释器(唉)。我测试了它的许多组件，例如函数 IncrementPrimes ，它接受一对质数并返回接下来的两个质数，大约需要 8 分钟 运行，使用我愚蠢的 C++ 解释器(无需发布:)。另外，它(至少)在函数调用次数上呈二次方增长——函数调用次数加倍使其至少需要四倍的时间(如果有 while 循环或 if 语句，则更多)。所以我猜运行解释器至少需要几天，如果不是几年的话:(

那我怎么知道它有效呢？嗯，当然我不是 100% 确定，但我非常接近。首先，我测试了它的许多组件，特别是，我非常彻底地测试了元语言的所有元素(函数序列和 if 和 while 语句)。

此外，元语言很容易翻译成你喜欢的语言，甚至更容易翻译成 C++，因为函数的所有参数都是通过引用传递的。如果你又偷懒了，可以下载我的翻译 here [tar.gz](没有makefile；只有两个.cpp 文件，所以直接调用gcc 就可以了)。

所以你可以比较这两个解释器，运行 C++ 版本(它也接受伪 Fractran 中的输入/输出)，检查它是否有效，然后说服自己元语言也有效。

或者!

如果您感到受到启发，并且真的想看到这个解释器被解释，您可以根据我们得到的 Fractran 输出类型编写一个“聪明”的 Fractran 解释器。输出是非常结构化的 - 函数序列是使用信号实现的，所以如果你以某种方式缓存解释器所在的位置，如果没有重要的变化，你可以立即跳转到那里。我认为，这将大大加快程序的运行速度(可能会通过一个或多个权限减少运行时间)。

但是，我不确定如何执行此操作，而且我对所做的工作感到满意，因此我将其留给读者作为练习。