代码高尔夫：Fractran

Question

挑战

编写一个充当 Fractran 解释器的程序。无论哪种语言，按字符数计算最短的口译员都是获胜者。您的程序必须接受两个输入：要执行的 fractran 程序和输入整数 n。该程序可以采用任何适合您的程序的形式 - 例如，二元组列表或平面列表。输出必须是单个整数，即执行结束时寄存器的值。

Fractran

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

1. 检查当前状态与程序计数器下当前分数的乘积是否为整数。如果是，则将当前状态乘以当前分数，并将程序计数器重置为列表的开头。
2. 使程序计数器前进。如果到达列表末尾，则停止，否则返回步骤 1。

有关 Fractran 如何以及为何工作的详细信息，请参阅 esolang 条目 和此条目 关于良好的数学/数学不好。

测试向量

程序： [(3, 2)]
输入： 72 (2³3²)
输出： 243 (3⁵)

程序： [(3, 2)]
输入：1296 (2⁴3⁴)
输出： 6561 (3⁸)

程序： [(455, 33), (11, 13), (1, 11), ( 3, 7), (11, 2), (1, 3)]
输入： 72 (2³3²)
输出： 15625 (5⁶)

额外测试向量：

您提交的内容无需正确执行最后一个程序即可成为可接受的答案。但如果确实如此，那就太好了！

程序： [(455, 33)、(11, 13)、(1, 11)、(3, 7)、(11, 2)、(1, 3)]
输入： 60466176 (2¹⁰3¹⁰)
输出： 7888609052210118054117285652827862296732064351090230047702789306640625 (5¹⁰⁰

)计分

程序严格按照字符长度进行排名 - 最短的是最好的。请随意提交布局良好、记录良好的代码版本和“缩小”版本的代码，以便人们可以看到发生了什么。

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

然而，作为额外奖励，任何能够在 fractran 中提供可用的 fractran 解释器的人都将获得 500 点声誉奖励。万一出现多个自托管解释器的情况，分数数量最少的解释器将获得赏金。

获奖者

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

令人难以置信的是，此后这个问题被另一种 fractran 解决方案击败了 - Amadeus 的解决方案仅用 84 个分数！在我的参考 Python 解决方案上运行时，它能够在几秒钟内执行前两个测试用例。它对分数使用了一种新颖的编码方法，这也值得仔细研究。

荣誉提及：

• Stephen Canon 的解决方案，采用 165 个字符的 x86 程序集（28 个字节机器代码）
• Jordan 的解决方案，使用 52 个字符的 ruby​​ - 处理长整数
• Useless的解决方案用87个Python字符组成，虽然不是最短的Python解决方案，但却是最短的Python解决方案之一很少有解决方案不是递归的，因此可以轻松处理更困难的程序。它也非常具有可读性。

Answer 1

Fractran - 1779 分数

（编辑：已修复）

（我希望人们仍然关注这个帖子，因为这花了一段时间！）

看起来所以不会让我发布这么长的东西，所以我在此处发布了 Fractran 源代码。

输入指定如下：

首先，我们通过以下方式对分数 m/n = p_0^a0... p_k^ak 进行编码：从

• 1 开始。然后，对于每个 ai ：
• 如果 ai > 则乘以 p_2i^ai 0
• 如果 a_i a_i 则乘以 p_2i+1^{-ai} 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 语句（为了方便！）。其代码可以在此处找到。

如果您想自己将该代码编译为 Fractran，可以找到我的（C++）程序 这里 [tar.gz]。在令人惊叹的测试（和炫耀）中，我使用了我的 C++ YAML 解析器 yaml-cpp< /a>，所以你必须下载并链接到它。对于 yaml-cpp 和“编译器”，您需要 CMake 来生成跨平台 makefile。

该程序的用法是：

./fracc interpreter.frp

它从标准输入读取函数的名称，并将相应的“伪分数”（我将在稍后解释）写入标准输出。因此，要编译解释器（Interpret 函数），您可以运行

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++，因为函数的所有参数都是通过引用传递的。如果你又觉得懒了，你可以下载我的翻译此处 [tar.gz]（没有 makefile；只有两个.cpp 文件，因此直接调用 gcc 就可以了），

因此您可以比较两个解释器，运行 C++ 版本（它也需要伪 Fractran 中的输入/输出），检查是否有效，然后说服自己元-语言也有效

---

。

如果您受到启发，并且真的希望看到这个解释器的解释，您可以根据我们获得的 Fractran 输出类型编写一个“聪明的”Fractran 解释器。输出非常结构化 - 函数序列是使用信号实现的，因此如果您以某种方式缓存解释器所在的位置，如果没有任何重要变化，您可以立即跳转到那里。我认为，这将极大地加快程序速度（也许会减少一项或多项权力的运行时间）。

但是，我不太确定如何做到这一点，而且我对所做的事情很满意，所以我将其作为练习留给读者。

Answer 2

Fractran：84 个分数

FTEVAL = [197*103/(2^11*101), 101/103, 103*127/(2*101), 101/103, 109/101,
  2*23/(197*109), 109/23, 29/109,197*41*47/(31*59), 11^10*53/(127*197), 197/53,
  37/197, 7^10*43/(11^10*37), 37/43, 59/(37*47), 59/47, 41*61/59, 31*67/(41*61),
  61/67, 7*67/(127*61), 61/67,101/71, 73/(127^9*29), 79/(127^2*73),
  83/(127*73), 89/(2*29), 163/29, 127^11*89/79, 337/83, 2*59/89, 71/61,
  7*173/(127*163), 163/173, 337*167/163, 347/(31*337), 337/347, 151/337,
  1/71,19*179/(3*7*193), 193/179, 157/(7*193), 17*181/193, 7*211/(19*181),
  181/211, 193/181, 157/193, 223/(7*157), 157/223, 281*283/239,
  3*257*269/(7*241), 241/269, 263/241, 7*271/(257*263), 263/271, 281/263,
  241/(17*281), 1/281, 307/(7*283), 283/307, 293/283, 71*131/107, 193/(131*151),
  227/(19*157), 71*311/227, 233/(151*167*311), 151*311/229, 7*317/(19*229),
  229/317, 239*331/217, 71*313/157, 239*251/(151*167*313), 239*251/(151*313),
  149/(251*293), 107/(293*331), 137/199, 2^100*13^100*353/(5^100*137),
  2*13*353/(5*137), 137/353, 349/137, 107/349, 5^100*359/(13^100*149),
  5*359/(13*149), 149/359, 199/149]

这完全是手写的。我确实编写了一种伪语言，以便能够更清楚地表达事物，但我没有编写编译器，而是选择直接编写优化的 Fractran 代码。

FTEVAL 接受输入 3^initial_state * 5^encoded_program * 199，生成中间结果 3^interpreted_program_state * 199，并在可被 233 整除的数字处完全停止。代码>.

解释后的程序被嵌入为单个 11 基数内的 10 基数数字列表，使用数字“a”来标记除最后之外的边界。加法程序 [3/2] 被编码为

int("3a2", 11) = 475.

乘法程序 [455/33, 11/13, 1/11, 3/7, 11/2, 1/3] 被编码为

int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657

真正的大数。

第一个测试向量在不到一秒内完成，在 4545 次迭代后产生了所需的结果，并在 6172 次迭代后停止。这是完整输出。

不幸的是，当我尝试第二个测试向量时，Sage 段错误（但我认为它可以在 Nick 使用素数指数向量的实现下工作）。

这里的空间实在是太小了，无法解释一切。但这是我的伪代码。希望我会在几天内写出我的过程。

# Notations:
# %p
#     designates the exponent of prime factor p that divides the
#     current state.
# mov x y
#     directly translates to the fraction y/x; its meaning: test if x divides
#     the current state, if so divide the current state by x and multiply it by
#     y.  In effect, the prime exponents of x and y are exchanged.  A Fractran
#     program only comprises of these instructions; when one is executable, the
#     program continues from the beginning.
# dec x => mov x, 1
#     wipes out all factors of x
# inc x => mov 1, x
#     this form is here for the sake of clarity, it usually appears in a
#     loop's entry statement and is merged as such when compiled
# sub n ret m {...}
#     conceptually represents a Fractran sub-program, which will execute just
#     like a normal Fractran program, that is, the sub-program's statements
#     execute when triggered and loop back.  The sub-program only exits when none of
#     its statement is executable, in which occasion we multiply the program's
#     state by m.  We can also explicitly break out early on some conditions.
#     It is also possible to enter a sub-prorgram via multiple entry points and
#     we must take care to avoiding this kind of behavior (except in case where
#     it is desirable).

# entry point 101: return 29
# Divide %2 modulo 11:
#   - quotient is modified in-place
#   - remainder goes to %127
sub 101 ret 101 { mov 2^11, 197 }
sub 101 ret 109 { mov 2, 127 }
sub 109 ret 29 { mov 197, 2 }

# entry point 59: return 61
# Multiply %127 by 10^%31 then add result to %7,
# also multiply %31 by 10 in-place.
sub 59 ret 41*61 {
  mov 31, 197*41
  sub 197 ret 37 { mov 127, 11^10 }
  sub 37 { mov 11^10, 7^10 }
}
sub 61 ret 61 { mov 41, 31 }
sub 61 ret 61 { mov 127, 7 } # the case where %31==0

# entry point 71: return 151 if success, 151*167 if reached last value
# Pop the interpreted program stack (at %2) to %7.
sub 71 {
  # call sub 101
  inc 101

  # if remainder >= 9:
  mov 29*127^9, 73
  #     if remainder == 11, goto 79
  mov 73*127^2, 79
  #     else:
  #         if remainder == 10, goto 83
  mov 73*127, 83
  #         else:
  #             if quotient >= 1: goto 89
  mov 29*2, 89
  #             else: goto 163
  mov 29, 163

  # 79: restore remainder to original value, then goto 89
  mov 79, 127^11*89

  # 83: reached a border marker, ret
  mov 83, 337

  # 89: the default loop branch
  # restore quotient to original value, call 59 and loop when that rets
  mov 2*89, 59
  mov 61, 71

  # 163: reached stack bottom,
  # ret with the halt signal
  sub 163 ret 337*167 { mov 127, 7 }

  # 337: clean up %31 before ret
  sub 337 ret 151 { dec 31 }
}

# entry point 193, return 157
# Divide %3 modulo %7:
#   - quotient goes to %17
#   - remainder goes to %19
sub 193 ret 17*181 {
  mov 3*7, 19
}
mov 7*193, 157
sub 181 ret 193 { mov 19, 7 }
mov 193, 157
sub 157 ret 157 { dec 7 }

# entry point 239: return 293
# Multiply %17 by %7, result goes to %3
mov 239, 281*283
sub 241 { mov 7, 3*257 }
sub 263 ret 281 { mov 257, 7 }
mov 281*17, 241
sub 283 ret 293 { dec 7 }

# entry point 107: return 149 if success, 233 if stack empty
# Pop the stack to try execute each fraction
sub 107 {
  # pop the stack
  inc 71*131

  # 151: popped a value
  # call divmod %3 %7
  mov 131*151, 193

  # if remainder > 0:
  mov 19*157, 227
  #     pop and throw away the numerator
  mov 227, 71*311
  #     if stack is empty: halt!
  mov 151*167*311, 233
  #     else: call 239 to multiply back the program state and gave loop signal
  mov 151*311, 229
  sub 229 ret 239*331 { mov 19, 7 }
  # else: (remainder == 0)
  #     pop the numerator
  mov 157, 71*313
  #     clear the stack empty signal if present
  #     call 239 to update program state and gave ret signal
  mov 151*167*313, 239*251
  mov 151*313, 239*251

  # after program state is updated
  # 313: ret
  mov 293*251, 149
  # 331: loop
  mov 293*331, 107
}

# main
sub 199 {
  # copy the stack from %5 to %2 and %13
  sub 137 ret 137 { mov 5^100, 2^100*13^100 }
  sub 137 ret 349 { mov 5, 2*13 }

  # call sub 107
  mov 349, 107

  # if a statement executed, restore stack and loop
  sub 149 ret 149 { mov 13^100, 5^100 }
  sub 149 ret 199 { mov 13, 5 }
}

Answer 3

x86_64 程序集，165 个字符（28 字节机器代码）。

状态在 %rdi 中传递，程序（指向以空结尾的分数数组的指针）在 %rsi 中。根据通常的 C 风格调用约定，结果以 %rax 形式返回。使用非标准调用约定或 Intel 语法（这是 AT&T 语法）会丢失更多字符，但我很懒；其他人可以做到这一点。几乎可以肯定，通过重新安排控制流可以节省一两条指令，如果有人想这样做，请随意。

中间计算（状态*分子）最多可达 128 位宽，但仅支持 64 位状态。

_fractran:
0:  mov     %rsi,   %rcx    // set aside pointer to beginning of list
1:  mov    (%rcx),  %rax    // load numerator
    test    %rax,   %rax    // check for null-termination of array
    jz      9f              // if zero, exit
    mul     %rdi
    mov   8(%rcx),  %r8     // load denominator
    div     %r8
    test    %rdx,   %rdx    // check remainder of division
    cmovz   %rax,   %rdi    // if zero, keep result
    jz      0b              // and jump back to program start
    add     $16,    %rcx    // otherwise, advance to next instruction
    jmp     1b
9:  mov     %rdi,   %rax    // copy result for return
    ret

删除注释、无关的空格和最小化版本的详细标签 _fractran。

Answer 4

Ruby，58 57 56 53 52 个字符

这是我的第一个代码高尔夫条目，所以请温柔一点。

def f(n,c)d,e=c.find{|i,j|n%j<1};d ?f(n*d/e,c):n end

用法：

irb> f 108, [[455, 33], [11, 13], [1,11], [3,7], [11,2], [1,3]]
=> 15625

irb> f 60466176, [[455, 33], [11, 13], [1, 11], [3, 7], [11, 2], [1, 3]]
=> 7888609052210118054117285652827862296732064351090230047702789306640625

漂亮版本 (252)：

def fractran(instruction, program)
  numerator, denominator = program.find do |numerator, denominator|
    instruction % denominator < 1
  end

  if numerator
    fractran(instruction * numerator / denominator, program)
  else
    instruction
  end
end

Ruby，53 52 使用 Rational

Inspired by gnibbler 的解决方案 我能够使用 Rational 得到一个减少到 53 52 个字符的解决方案。 仍然比上面（不太优雅）的解决方案长一个。

def f(n,c)c.map{|i|return f(n*i,c)if i*n%1==0};n end

用法：（

irb> require 'rational'
irb> f 60466176, [Rational(455, 33), Rational(11, 13), Rational(1, 11), Rational(3, 7), Rational(11, 2), Rational(1, 3)]
=> Rational(7888609052210118054117285652827862296732064351090230047702789306640625, 1)

对更漂亮的输出的 to_i 调用将添加 5 个字符。）

Answer 5

高尔夫脚本 - 32

    
    {:^{1=1$\%!}?.1={~@\/*^f}{}if}:f

    ; 108 [[3 2]] f p
    # 243
    ; 1296 [[3 2]] f p
    # 6561
    ; 108 [[455 33][11 13][1 11][3 7][11 2][1 3]] f p
    # 15625
    ; 60466176 [[455 33][11 13][1 11][3 7][11 2][1 3]] f p
    # 7888609052210118054117285652827862296732064351090230047702789306640625

Answer 6

Haskell，102 个字符

import List
import Ratio
l&n=maybe n((&)l.numerator.(n%1*).(!!)l)$findIndex((==)1.denominator.(n%1*))l

$ ghci
Prelude> :m List Ratio
Prelude List Ratio> let l&n=maybe n((&)l.numerator.(n%1*).(!!)l)$findIndex((==)1.denominator.(n%1*))l
Prelude List Ratio> [3%2]&108
243
Prelude List Ratio> [3%2]&1296
6561
Prelude List Ratio> [455%33,11%13,1%11,3%7,11%2,1%3]&108
15625

88，对输入/输出格式有宽松的限制。

import List
import Ratio
l&n=maybe n((&)l.(*)n.(!!)l)$findIndex((==)1.denominator.(*)n)l

Prelude List Ratio> let l&n=maybe n((&)l.(*)n.(!!)l)$findIndex((==)1.denominator
Prelude List Ratio> [455%33,11%13,1%11,3%7,11%2,1%3]&108
15625 % 1

Answer 7

Python，83 82 81 72 70 个字符。

将输入作为fractions.Fraction 对象很方便。与 Ruby 解决方案中的想法相同。

def f(n,c):d=[x for x in c if x*n%1==0];return d and f(n*d[0],c) or n

# Test code:
from fractions import Fraction as fr
assert f(108, [fr(3, 2)]) == 243
assert f(1296, [fr(3, 2)]) == 6561
assert f(108, [fr(455, 33), fr(11, 13), fr(1, 11), fr(3, 7), fr(11, 2), fr(1, 3)]) == 15625
assert f(60466176, [fr(455, 33), fr(11, 13), fr(1, 11), fr(3, 7), fr(11, 2), fr(1, 3)]) == 7888609052210118054117285652827862296732064351090230047702789306640625

Answer 8

C，159 153 151 131 111 110 个字符

v[99],c,d;main(){for(;scanf("%d",v+c++););while(d++,v[++d])
*v%v[d]?0:(*v=*v/v[d]*v[d-1],d=0);printf("%d",*v);}

$ cc f.c
$ echo 108 3 2 . | ./a.out; echo
243
$ echo 1296 3 2 . | ./a.out; echo
6561
$ echo 108 455 33 11 13 1 11 3 7 11 2 1 3 . | ./a.out; echo
15625

Answer 9

Python - 53

感谢 Paul

f=lambda n,c:next((f(n*x,c)for x in c if x*n%1==0),n)

测试用例

from fractions import Fraction as fr
assert f(108, [fr(3, 2)]) == 243
assert f(1296, [fr(3, 2)]) == 6561
assert f(108, [fr(455, 33), fr(11, 13), fr(1, 11), fr(3, 7), fr(11, 2), fr(1, 3)]) == 15625
assert f(60466176, [fr(455, 33), fr(11, 13), fr(1, 11), fr(3, 7), fr(11, 2), fr(1, 3)]) == 7888609052210118054117285652827862296732064351090230047702789306640625

的改进Python - 54 不使用分数

f=lambda n,c:next((f(n*i/j,c)for i,j in c if n%j<1),n)

Python - 55

这有点理论化。前两种情况运行正常，但其他两种情况因递归深度而失败。也许有人可以让它与生成器表达式一起工作

f=lambda n,c:([f(n*i/j,c)for i,j in c if n%j<1]+[n])[0]

这是一种可能性，但即使不包含导入也会增长到 65

from itertools import chain
f=lambda n,c:(chain((f(n*i/j,c)for i,j in c if n%j<1),[n])).next()

Answer 10

F#：80 个字符

let rec f p=function|x,(e,d)::t->f p (if e*x%d=0I then(e*x/d,p)else(x,t))|x,_->x

这是使用 匹配模式与 |cases 而不是 函数 的扩展版本：

//program' is the current remainder of the program
//program is the full program
let rec run program (input,remainingProgram) =
    match input, remainingProgram with
        | x, (e,d)::rest -> 
            if e*x%d = 0I then //suffix I --> bigint
                run program (e*x/d, program) //reset the program counter
            else    
                run program (x, rest) //advance the program
        | x, _ -> x //no more program left -> output the state   

测试代码：

let runtests() = 
    [ f p1 (108I,p1) = 243I
      f p1 (1296I,p1) = 6561I
      f p2 (108I,p2) = 15625I
      f p2 (60466176I,p2) = pown 5I 100] 

和结果（在 F# 交互中测试） ：

> runtests();;
val it : bool list = [true; true; true; true]

编辑让我们享受更多乐趣，并计算一些素数（请参阅起始帖子中的链接页面）。我编写了一个新函数 g 来生成状态的中间值。

//calculate the first n primes with fractran
let primes n = 
    let ispow2 n = 
        let rec aux p = function
            | n when n = 1I -> Some p
            | n when n%2I = 0I -> aux (p+1) (n/2I)
            | _ -> None
        aux 0 n

    let pp = [(17I,91I);(78I,85I);(19I,51I);(23I,38I);(29I,33I);(77I,29I);(95I,23I); 
              (77I,19I);(1I,17I);(11I,13I);(13I,11I);(15I,14I);(15I,2I);(55I,1I)]

    let rec g p (x,pp) =
        seq { match x,pp with 
                |x,(e,d)::t -> yield x
                               yield! g p (if e*x%d=0I then (e*x/d,p) else (x,t))
                |x,_ -> yield x }

    g pp (2I,pp)
    |> Seq.choose ispow2
    |> Seq.distinct
    |> Seq.skip 1 //1 is not prime
    |> Seq.take n
    |> Seq.to_list

需要 4.7 秒才能计算出前 10 个素数：

> primes 10;;
Real: 00:00:04.741, CPU: 00:00:04.005, GC gen0: 334, gen1: 0, gen2: 0
val it : int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29]

毫无疑问，这是我写过的最奇怪、最慢的素数生成器。我不确定这是好事还是坏事。

Answer 11

Javascript 一个：99 个字符。无奖励向量 :(

function g(n,p,q,i,c){i=0;while(q=p[i],c=n*q[0],(c%q[1 ]?++i:(n=c/q[1],i=0))

输入格式为 [[a ,b],[c,d]]，我利用了 Javascript 的宽松性：您可以添加任意数量的参数，而不是执行 var x=0, y=0;。不管你是否真的通过它们，因为它们默认为 null

。

function g(n,p) {
    var q, c, i=0;
    while(i < p.length) {
        q = p[i];
        c = n * q[0];
        if(c % q[1] != 0) {
            ++i;
        } else {
            n = c % q[1];
            i = 0;
        }
    }
    return n;
};

Answer 12

Python, 110 103 95 87 个字符

frc.py

def f(n,c):
 d=c
 while len(d):
  if n%d[1]:d=d[2:]
  else:n=d[0]*n/d[1];d=c
 return n

---

test.py

（显示如何驱动它）

from frc import f
def test():
 """
 >>> f(108, [3,2])
 243
 >>> f(1296, [3,2])
 6561
 >>> f(108, [455,33,11,13,1,11,3,7,11,2,1,3])
 15625
 >>> f(60466176, [455, 33,11, 13,1, 11,3, 7,11, 2,1, 3])
 7888609052210118054117285652827862296732064351090230047702789306640625L
 """
 pass
import doctest
doctest.testmod()

Answer 13

C#：

整洁版本：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            int ip = 1;
            decimal reg = Convert.ToInt32(args[0]);
            while (true)
            {
                if (ip+1 > args.Length)
                {
                    break;
                }
                decimal curfrac = Convert.ToDecimal(args[ip]) / Convert.ToDecimal(args[ip+1]);
                if ((curfrac * reg) % 1 == 0)
                {
                    ip = 1;
                    reg = curfrac * reg;
                }
                else
                {
                    ip += 2;
                }
            }
            Console.WriteLine(reg);
            Console.ReadKey(true);
        }
    }
}

缩减版本重量为 201 个字符（没有命名空间声明或任何其他内容，只有单个 using 语句（不是系统）和 Main 函数):

using System;namespace T{using b=Convert;static class P{static void Main(string[] a){int i=1;var c=b.ToDecimal(a[0]);while(i+1<=a.Length){var f=b.ToDecimal(a[i])/b.ToDecimal(a[i+1]);if((f*c)%1==0){i=1;c*=f;}else{i+=2;}}Console.Write(c);}}}

示例（通过命令行参数输入）：

input: 108 3 2
output: 243.00
input: 1296 3 2
output: 6561.0000
input: 108 455 33 11 13 1 11 3 7 11 2 1 3
output: 45045.000000000000000000000000

Answer 14

Groovy、136 117 107 个字符。

调用为 groovy fractal.groovy [输入状态] [作为数字列表的程序向量]

a=args.collect{it as int}
int c=a[0]
for(i=1;i<a.size;i+=2) if(c%a[i+1]==0){c=c/a[i+1]*a[i];i=-1}
println c

示例

bash$ groovy fractal.groovy 108 455 33 11 13 1 11 3 7 11 2 1 3
Output: 15625

Answer 15

Perl，84 82 字符

使用标准输入。

@P=<>=~/\d+/g;$_=<>;
($a,$%)=@P[$i++,$i++],$_*$a%$%or$i=0,$_*=$a/$%while$i<@P;
print

需要 110 个字符才能通过奖励测试：

use Math'BigInt blcm;@P=<>=~/\d+/g;$_=blcm<>;
($%,$=)=@P[$i++,$i++],$_*$%%$=or$i=0,($_*=$%)/=$=while$i<@P;print

Answer 16

Haskell：116 109 个字符

f p x[]=x
f p x((n,d):b)|x*n`mod`d==0=f p(x*n`div`d)p|True=f p x b
main=do{p<-readLn;x<-readLn;print$f p x p}

这最终有点像 Dario 条目的山寨版。

Answer 17

方案：326

我认为为了平等，需要提交方案。我也只是想找个借口玩它。 （请原谅我的基础知识，我确信这可以优化，并且我愿意接受建议！）

#lang scheme
(define fractran_interpreter
(lambda (state pc program)
    (cond
        ((eq? pc (length program)) 
            (print state))
        ((integer? (* state (list-ref program pc)))
            (fractran_interpreter (* state (list-ref program pc)) 0 program))
        (else
            (fractran_interpreter state (+ pc 1) program)))))

测试：

(fractran_interpreter 108 0 '(3/2))

(fractran_interpreter 60466176 0 '(455/33 11/13 1/11 3/7 11/2 1/3))

我得到了奖励向量！ （使用 Dr.Scheme，分配 256 mb）

Answer 18

Lua：

整洁的代码：

a=arg;
ip=2;
reg=a[1];
while a[ip] do
    curfrac = a[ip] / a[ip+1];
    if (curfrac * reg) % 1 == 0 then
        ip=2;
        reg = curfrac * reg
    else
        ip=ip+2
    end
end
print(reg)

紧凑的代码重量为98个字符（Scoregraphic在我的其他答案上建议减少，gwell建议更多）：

a=arg i=2 r=a[1]while a[i]do c=a[i]/a[i+1]v=c*r if v%1==0 then i=2 r=v else i=i+2 end end print(r)

从命令行运行，提供首先是基数，然后是一系列分数，以空格分隔的数字形式呈现，如下所示：（

C:\Users\--------\Desktop>fractran.lua 108 3 2
243
C:\Users\--------\Desktop>fractran.lua 1296 3 2
6561
C:\Users\--------\Desktop>fractran.lua 108 455 33 11 13 1 11 3 7 11 2 1 3
15625

手动输入其中一些内容，因为从命令行获取内容很痛苦，尽管这是返回的结果）

不处理可悲的是奖金向量:(

Answer 19

Python 中的参考实现

此实现对质因数分解进行操作。

首先，它通过将分子和分母编码为 (idx, value) 元组列表来解码分数元组列表，其中 idx 是素数的编号（2 是素数 0，3 是素数 1，依此类推）。

当前状态是每个素数的指数列表（按索引）。执行指令需要首先迭代分母，检查索引状态元素是否至少为指定值，然后，如果匹配，则递减分母中指定的状态元素，并递增分子中指定的状态元素。

这种方法大约是 Python 中对大整数进行算术运算的速度的 5 倍，并且更容易调试！

进一步的优化是通过构造一个数组将每个素数索引（变量）映射到第一次在分数分母中检查它的时间，然后使用它构造一个“jump_map”，其中包含要为每个素数索引（变量）执行的下一条指令程序中的指令。

def primes():
  """Generates an infinite sequence of primes using the Sieve of Erathsones."""
  D = {}
  q = 2
  idx = 0
  while True:
    if q not in D:
      yield idx, q
      idx += 1
      D[q * q] = [q]
    else:
      for p in D[q]:
        D.setdefault(p + q, []).append(p)
      del D[q]
    q += 1

def factorize(num, sign = 1):
  """Factorizes a number, returning a list of (prime index, exponent) tuples."""
  ret = []
  for idx, p in primes():
    count = 0
    while num % p == 0:
      num //= p
      count += 1
    if count > 0:
      ret.append((idx, count * sign))
    if num == 1:
      return tuple(ret)

def decode(program):
  """Decodes a program expressed as a list of fractions by factorizing it."""
  return [(factorize(n), factorize(d)) for n, d in program]

def check(state, denom):
  """Checks if the program has at least the specified exponents for each prime."""
  for p, val in denom:
    if state[p] < val:
      return False
  return True

def update_state(state, num, denom):
  """Checks the program's state and updates it according to an instruction."""
  if check(state, denom):
    for p, val in denom:
      state[p] -= val
    for p, val in num:
      state[p] += val
    return True
  else:
    return False

def format_state(state):
  return dict((i, v) for i, v in enumerate(state) if v != 0)

def make_usage_map(program, maxidx):
  firstref = [len(program)] * maxidx
  for i, (num, denom) in enumerate(program):
    for idx, value in denom:
      if firstref[idx] == len(program):
        firstref[idx] = i
  return firstref

def make_jump_map(program, firstref):
  jump_map = []
  for i, (num, denom) in enumerate(program):
    if num:
      jump_map.append(min(min(firstref[idx] for idx, val in num), i))
    else:
      jump_map.append(i)
  return jump_map

def fractran(program, input, debug_when=None):
  """Executes a Fractran program and returns the state at the end."""
  maxidx = max(z[0] for instr in program for part in instr for z in part) + 1
  state = [0]*maxidx

  if isinstance(input, (int, long)):
    input = factorize(input)

  for prime, val in input:
    state[prime] = val

  firstref = make_usage_map(program, maxidx)
  jump_map = make_jump_map(program, firstref)

  pc = 0
  length = len(program)
  while pc < length:
    num, denom = program[pc]
    if update_state(state, num, denom):
      if num:
        pc = jump_map[pc]
      if debug_when and debug_when(state):
        print format_state(state)
    else:
      pc += 1

  return format_state(state)

Answer 20

Perl 6：77 个字符（实验）

sub f(@p,$n is copy){
loop {my$s=first {!($n%(1/$_))},@p or return $n;$n*=$s}}

换行符是可选的。调用方式：

say f([3/2], 1296).Int;
say f([455/33, 11/13, 1/11, 3/7, 11/2, 1/3], 60466176).Int;

可读版本：

sub Fractran (@program, $state is copy) {
  loop {
    if my $instruction = first @program:
      -> $inst { $state % (1 / $inst) == 0 } {
      $state *= $instruction;
    } else {
      return $state.Int;
    }
  }
}

注意：

1. 冒号符号 first @program: pointy-sub 不适用于当前的实现； 第一个 BLOCK，必须使用 @program。

2. Rakudo 似乎有一个有缺陷的 Rat，给出了错误的结果。目前的 Niecza 可以正确、快速地运行所有测试程序，包括“奖励”部分。

Answer 21

Haskell，142 个字符

没有任何额外的库和完整的 I/O。

t n f=case f of{(a,b):f'->if mod n b == 0then(\r->r:(t r f))$a*n`div`b else t n f';_->[]}
main=readLn>>=(\f->readLn>>=(\n->print$last$t n f))

Answer 22

Java，200 192 179 个字符

我想每个人都知道 Java 不会有最短的实现，但我想看看它会如何比较。它解决了一些琐碎的例子，但没有解决额外的问题。

这是最小化版本：

class F{public static void main(String[]a){long p=new Long(a[0]);for(int i=1;i<a.length;){long n=p*new Long(a[i++]),d=new Long(a[i++]);if(n%d<1){p=n/d;i=1;}}System.out.print(p);}}

java -cp 。 F 108 455 33 11 13 1 11 3 7 11 2 1 3

15625

java -cp 。 F 1296 3 2

6561

这是清理后的版本：

public class Fractran {

    public static void main(String[] args) {
        long product = new Long(args[0]);

        for (int index = 1; index < args.length;) {
            long numerator = product * new Long(args[index++]);
            long denominator = new Long(args[index++]);

            if (numerator % denominator < 1) {
                product = numerator / denominator;
                index = 1;
            } // if
        } // for

        System.out.print(product);
    }
}

Answer 23

方案 73 个字符

我第一次尝试使用完全标准的 R⁵RS 方案执行此操作，结果为 104 个字符：

(define(f p n)(let l((q p)(n n))(if(null? q)n(let((a(* n(car q))))(if(integer?
a)(l p a)(l(cdr q)n))))))

针对测试向量中的一些项目运行：

> (f '(3/2) 1296)
6561
> (f '(455/33 11/13 1/11 3/7 11/2 1/3) 60466176)
7888609052210118054117285652827862296732064351090230047702789306640625

如果您假设 λ< /code> 绑定到 lambda 并定义了 let/cc （因为它们在 PLT 方案中；请参阅下面的定义，了解在未定义这些方案的方案中运行它的定义） ），然后我可以将 Jordan 的第二个 Ruby 解决方案 改编为Scheme，结果为 73字符（请注意，参数顺序与我的第一个解决方案相反，但与 Jordan 的相同；在此版本中，节省了一个字符）。：

(define(f n p)(let/cc r(map(λ(i)(if(integer?(* n i))(r(f(* n i)p))))p)n))

如果我没有 λ 和 let/cc 预定义的，那么这个字符有 111 个字符（如果定义了相当常见的 call/cc 缩写，则为 88）：

(define(f n p)(call-with-current-continuation(lambda(r)(map(lambda(i)(if(integer?(*
n i))(r(f(* n i)p))))p)n)))

λ 和 的定义代码>让/抄送：

(define-syntax λ 
  (syntax-rules () 
    ((_ . body) (lambda . body)))

(define-syntax let/cc 
  (syntax-rules () 
    ((_ var . body) (call-with-current-continuation (lambda (var) . body)))))

Answer 24

有点晚了... dc 84 chars

只是为了好玩 dc 解决方案（OpenBSD）

[ss1sp]s1[Rlp1+sp]s2?l1xz2/sz[z2/ds_:bl_:az0<L]dsLx
1[;als*lp;b~0=1e2lpdlz!<L]dsLxlsp

它处理所有情况：

$ dc fractran.dc  
455 33 11 13 1 11 3 7 11 2 1 3 60466176
7888609052210118054117285652827862296732064351090230047702789306640625

Answer 25

我还不能发表评论，但这是 RCIX 的 C# 版本的“稍微”较短的版本（我相信它短了 7 个字符），

using System;namespace T{static class P{static void Main(string[] a){int i=1;Func<string,decimal> d=Convert.ToDecimal;var c=d(a[0]);while(i+1<=a.Length){var f=d(a[i])/d(a[++i]);if((f*c)%1==0){i=1;c*=f;}else i++;}Console.Write(c);}}}

它使用

Func<string,decimal> d=Convert.ToDecimal

并调用 d(); 而不是

using b=Convert;

重复调用 b.ToDecimal();。

我还删除了 else 语句周围一对不必要的花括号以获得 1 个字符:)。

我还将 a[i+1] 替换为 a[++i] ，在下面的 else 正文中，我将 i+=2 替换为i++ 获得另一个字符：P