代码高尔夫：Fractran
挑战
写一个充当Fractran解释器的程序。 按字数计算的最短的翻译是任何语言都是胜利者。 你的程序必须有两个input：要执行的fractran程序和input的整数n。 该程序可以是任何方便您的程序的forms – 例如，2元组列表，或平面列表。 输出必须是一个整数，即执行结束时的寄存器值。
Fractran
Fractran是由John Conway发明的一种琐碎的深奥语言。 fractran程序由正分数列表和初始状态n组成。 解释器维护一个程序计数器，最初指向列表中的第一个分数。 Fractran程序按以下方式执行：
- 检查当前状态的产品和当前在程序计数器下的分数是否为整数。 如果是，则将当前状态乘以当前分数，并将程序计数器复位到列表的开始位置。
- 推进计划柜台。 如果到达列表的末尾，请停止，否则返回到步骤1。
有关Fractran工作原理和方法的详细信息，请参阅esolang条目以及math/math不错的条目 。
testing向量
计划： [（3，2）]
input： 72（2 3 3 2 ）
产出： 243（3 5 ）
计划： [（3，2）]
input： 1296（2 4 3 4 ）
输出： 6561（3 8 ）
程序： [（455,33），（11,13），（1,11），（3,7），（11,2），（1,3）]
input： 72（2 3 3 2 ）
输出： 15625（5 6 ）
奖金testingvector：
您的提交不需要正确执行最后一个程序是一个可以接受的答案。 但是，如果是这样的话！
程序： [（455,33），（11,13），（1,11），（3,7），（11,2），（1,3）]
input： 60466176（2 10 3 10 ）
输出： 7888609052210118054117285652827862296732064351090230047702789306640625（5 100 ）
提交和评分
程序严格按字符长度sorting – 最短是最好的。 随意提交一个很好的布局和logging和一个“缩小”版本的代码，所以人们可以看到发生了什么事情。
'J'这个语言是不能接受的。 这是因为在其中一个链接的页面上，J中已经有一个众所周知的解决scheme。 如果你是J粉丝，对不起！
然而，作为额外的奖励，任何能够在 fractran中提供工作的fractran解释器的人都将获得500点声望点奖励。 在不太可能的情况下，有多个自我托pipe口译员，分数最less的口译员将获得赏金。
获奖者
提交包含1779个分数的自承载fractran解决scheme的官方获胜者是Jesse Beder的解决scheme 。 实际上，解决scheme太慢，甚至不能执行1 + 1。
令人难以置信的是，这已经被另一个fractran解决scheme殴打 – Amadaeus的解决scheme只有84个部分！ 在我的参考Python解决scheme上运行时，它能够在几秒钟内执行前两个testing用例。 它使用了一种新颖的编码方法，这也值得仔细观察。
尊敬的提到：
- Stephen Canon的解决scheme是在165个字符的x86汇编（28个字节的机器码）
- 约旦的解决scheme在52个字符的ruby – 处理长整数
- 无用的解决scheme在87个字符的Python，虽然不是最短的Python解决scheme，是less数不recursion的解决scheme之一，因此轻松地处理更难的程序。 这也是非常可读的。
Fractran – 1779分数
（编辑：固定）
（我希望人们仍然遵循这个线索，因为这花了一段时间！）
似乎所以SO不会让我发布任何东西，所以我在这里发布了Fractran源代码。
input规定如下：
首先，我们编码一个分数m/n = p_0^a0... p_k^ak通过：
- 从1开始。然后，对于每个
ai： - 如果
ai > 0乘以p_2i^ai - 如果
a_i < 0则乘以p_2i+1^{-ai}
这样，我们将任何分数编码为正整数。 现在，给定一个progoram（编码分数F0，F1，…的序列），我们用这个编码
p_0^F0 p1^F1 ...
最后，input口译员给出：
2^(program) 3^(input) 5
program和input如上编码。 例如，在第一个testing问题中， 3/2被编码为15 ，所以程序被编码为2^15 ; 108被编码为500 。 所以，我们通过
2^{2^15} 3^500 5
到程序。 输出的forms就是这样
2^(program) 3^(output)
所以在第一个例子中，它会是
2^{2^15} 3^3125
它是如何工作的？
我写了一个汇编到Fractran的元语言。 它允许函数（简单的Fractran和其他函数序列）， while循环和if语句（为了方便！）。 代码可以在这里find。
如果你想自己编译代码到Fractran，我的（C ++）程序可以在这里find[tar.gz]。 在一个惊人的展示dogfooding（和炫耀），我用我的C + + YAML分析器yaml-cpp ，所以你必须下载并链接。 对于yaml-cpp和“编译器”，你都需要CMake来生成跨平台的makefile。
这个程序的用法是：
./fracc interpreter.frp
它从标准input中读取一个函数的名称，并将相应的“伪分数”（我将在一秒钟内解释）写入标准输出。 所以要编译解释器（解释函数），你可以运行
echo "Interpret" | ./fracc interpreter.frp > interpret
输出（“pseudo-Fractran”）将是一系列行，每行都有一串空格分隔的数字。 一条线对应于一个分数：如果该线的第n个数字是an ，那么该分数是p_n^an的乘积。
把它转换成Fractran是很容易的，但是如果你懒，你可以使用-fractions.py 。 [ 注 ：之前我有一个C ++程序，而且我不小心忽略了整数溢出。 我把它翻译成Python来避免这种情况。]
关于input的注意事项 ：如果你想以这种方式testing一个不同的函数，那么约定总是相同的。 它在伪Fractran中有许多参数（通常是函数上面的注释解释了这个），所以给它想要的东西，在下一个时隙加上1 （所以在普通的Fractran中，一次乘以第一个素数将不会使用）。 这是函数开始前的“信号”位。
然而，
我不build议真正尝试运行Fractran解释器（唉）。 我testing了它的许多组件，例如函数IncrementPrimes ，它使用一对素数并返回下两个素数，使用我愚蠢的C ++解释器（无需发布:)需要大约8分钟的时间运行。 另外，它至less在函数调用次数方面是二次方的 – 函数调用的次数增加一倍，至less需要四倍的时间（如果有while循环或if语句， if ）。 所以我猜，运行解释器将需要至less几天，如果不是几年:(
那么我怎么知道它的工作原理？ 那么当然，我不是100％肯定的，但是我非常接近。 首先，我testing了许多组件，特别是我非常全面地testing了元语言的所有元素（函数序列和if和while语句）。
另外，元语言很容易翻译成你喜欢的语言，甚至更容易翻译成C ++，因为函数的所有参数都是通过引用传递的。 如果你再次感到懒惰，可以在这里下载我的翻译[tar.gz]（没有makefile;只有两个.cpp文件，所以直接调用gcc就可以）。
所以你可以比较两个解释器，运行C ++版本（它也需要在伪Fractran中input/输出），检查它是否有效，然后说服你自己也可以使用元语言。
要么！
如果你感觉到灵感，并且真的希望看到这个解释器被解释，那么可以根据我们得到的Fractran输出types来编写一个“聪明的”Fractran解释器。 输出是非常结构化的 – 函数序列是用信号实现的，所以如果你以某种方式caching解释器的位置，那么如果没有什么重要的改变，你可以立即跳到那里。 我认为，这会大大加快程序的速度（可能会减less一个或多个权力的运行时间）。
但是，我不确定如何做到这一点，而且我对所做的事情感到满意，所以我将把它作为一个读者的练习。
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]
这完全是用手写的。 我编写了一个伪语言，能够更清楚地expression事物，但是我没有写一个编译器，而是select直接编写优化的Fractran代码。
FTEVAL需要input3^initial_state * 5^encoded_program * 199 ，产生中间结果3^interpreted_program_state * 199 decoded_program_state 3^interpreted_program_state * 199 ，并且完全停止在可被233整除的数字处。
解释的程序被embedded一个基本的10位数字内的一个基数为10的数字，使用数字“a”来标记边界，除了在最后。 添加程序[3/2]被编码为
int("3a2", 11) = 475.
乘法程序[455 / 33,11 / 13,1 / 11,3 / 7,1 / 2,1 / 3]编码为
int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657
这是一个真正的大数目。
第一个testing向量在不到一秒内完成，在4545次迭代之后产生期望的结果，并在6172次迭代之后停止。 这里是完整的输出 。
不幸的是，当我尝试第二个testing向量的时候，鼠尾草已经被遗忘了（但是我认为它会在Nick的实现中使用主要的指数向量）。
这里的空间实在太小，无法解释一切。 但是这是我的伪代码。 希望能在几天后写出我的过程。
# Notations: # %p # designates the exponent of prime factor p that divides the # current state. # mov xy # 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 } }
x86_64汇编 ，165个字符（28个字节的机器码）。
状态在％rdi中传递，程序（指向零终止的分数数组）指向％rsi。 按照通常的C风格调用约定，结果以％rax的forms返回。 使用非标准调用约定或英特尔语法（这是AT＆T语法）会减less几个字符，但我很懒; 别人可以做到这一点。 如果有人想要这样做的话，一两条指令几乎可以肯定的通过重新安排控制stream程来节省。
中间计算（状态*分子）可以高达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 。
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
受到gnibbler解决scheme的启发，我能够使用Rational来获得解决scheme 53 52个字符。 比上面的（不太优雅的）解决scheme还要长一些。
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个字符。）
Golfscript – 32
{！^ {1 = $ 1 \％}？1 = {〜@ \ / * ^ F} {} if}个：F
; 108 [[3 2]] fp
＃243
; 1296 [[3 2]] fp
＃6561
; 108 [[455 33] [11 13] [1 11] [3 7] [11 2] [1 3]] fp
＃15625
; 60466176 [[455 33] [11 13] [1 11] [3 7] [11 2] [1 3]] fp
＃7888609052210118054117285652827862296732064351090230047702789306640625
哈斯克尔 ，102个字符
import List import Ratio l&n=maybe n((&)l.numerator.(n%1*).(!!)l)$findIndex((==)1.denominator.(n%1*))l
$ ghci 前奏>：米列表比例 Prelude List Ratio> let l＆n = maybe n（（＆）l.numerator。（n％1 *）。（!!）l）$ findIndex（（==）1.denominator。（n％1 *））l 前奏名单比率> [3％2]＆108 243 前奏名单比率> [3％2]＆1296 6561 前奏名单比例> [455％33,11％13,1％11,3％7,11％2,1％3]＆108 15625
88放宽对input/输出格式的限制。
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.分母 前奏名单比例> [455％33,11％13,1％11,3％7,11％2,1％3]＆108 15625％1
Python， 83 82 81 72 70个字符。
以分数formsinput是非常方便的。 和Ruby解决scheme一样的想法。
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
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 fc $回声108 3 2。 | ./a.out; 回声 243 $ echo 1296 3 2。 | ./a.out; 回声 6561 $回声108 455 33 11 13 1 11 3 7 11 2 1 3。 | ./a.out; 回声 15625
Python – 53
感谢保罗的改进
f=lambda n,c:next((f(n*x,c)for x in c if x*n%1==0),n)
testing用例
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
这个有点理论性。 前两种情况运行正常，但其他两种情况下recursion深度失败。 也许有人可以让它与一个生成器expression式一起工作
f=lambda n,c:([f(n*i/j,c)for i,j in c if n%j<1]+[n])[0]
这是一种可能性，但是即使不包括import也可能增长到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()
F＃：80个字符
let rec fp=function|x,(e,d)::t->fp (if e*x%d=0I then(e*x/d,p)else(x,t))|x,_->x
这是一个扩展版本，使用match pattern with |cases而不是function ：
//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
testing代码：
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＃交互testing）：
> runtests();; val it : bool list = [true; true; true; true]
编辑让我们有更多的乐趣，并计算一些素数（请参阅起始post中的链接页面）。 我写了一个新的函数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 gp (x,pp) = seq { match x,pp with |x,(e,d)::t -> yield x yield! gp (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]
毫无疑问，这是我写过的最奇怪，最缓慢的素数生成器。 我不确定这是好事还是坏事。
一个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))<p.length){};return n;};
input格式为[[a,b],[c,d]] 。 我利用Javascript的宽容：而不是做var x=0, y=0; ，你可以添加尽可能多的参数，只要你喜欢。 不pipe你是否真的通过它们，因为它们默认为null 。
漂亮的版本：
函数g（n，p）{
var q，c，i = 0;
while（i <p.length）{
q = p [i];
c = n * q [0];
如果（c％q [1]！= 0）{
++ I;
} else {
n = c％q [1];
我= 0;
}
}
返回n;
};
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()
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); } } }
减less在201个字符 （没有名称空间声明或任何，只是一个使用语句（而不是系统）和主要function）的权重：
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是通过命令行参数）：
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
Groovy ， 136 117 107个字符。
调用groovy fractal.groovy [input状态] [作为数字列表的程序向量]
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
Perl， 84 82 char
使用标准input。
@P=<>=~/\d+/g;$_=<>; ($a,$%)=@P[$i++,$i++],$_*$a%$%or$i=0,$_*=$a/$%while$i<@P; print
需要110个字符才能通过奖金testing：
use Math'BigInt blcm;@P=<>=~/\d+/g;$_=blcm<>; ($%,$=)=@P[$i++,$i++],$_*$%%$=or$i=0,($_*=$%)/=$=while$i<@P;print
哈斯克尔： 116 109个字符
fpx[]=x fpx((n,d):b)|x*n`mod`d==0=fp(x*n`div`d)p|True=fpxb main=do{p<-readLn;x<-readLn;print$fpxp}
这最终有点像达里奥的入门。
scheme：326
我认为需要一个计划提交，以平等。 我也只是想借口玩它。 （请原谅我的基本知识，我相信这可以优化，我愿意提供build议！）
#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)))))
testing：
(fractran_interpreter 108 0 '(3/2))
(fractran_interpreter 60466176 0 '(455/33 11/13 1/11 3/7 11/2 1/3))
我得到奖金vector！ （使用博士计划，分配256 MB）
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个字符 （在我的另一个答案，由痕迹build议减less，更多build议由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
（手动input一些内容，因为从命令行中取出东西是件痛苦的事，尽pipe这是返回的结果）
不处理奖金vector伤心:(
Python中的参考实现
这个实现在素数分解上运行。
首先，它通过将分子和分母编码为（idx，value）元组的列表（其中idx是素数（2是素数0,3是素数1，等等））来解码分数元组的列表。
当前状态是每个素数的指数列表，按索引。 执行指令需要先对分母进行迭代，检查索引状态元素是否至less是指定值，然后如果匹配，则减小分母中指定的状态元素，并递增分子中指定的状态元素。
这种方法大约是在Python中对大整数进行算术运算的速度的5倍，而且更容易debugging！
通过构build一个数组映射每个主要索引（variables）到第一次检查分数分母中的数组，然后使用它构造一个“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)
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; } } }
笔记：
-
The colon notation
first @program: pointy-subdoesn't work on current implementations; first BLOCK, @program has to be used instead. -
Rakudo appears to have a buggy
Ratgiving incorrect results. Current Niecza runs all of the test programs correctly and quickly, including the "bonus" fraction.
Haskell, 142 characters
Without any additional libraries and full I/O.
tnf=case f of{(a,b):f'->if mod nb == 0then(\r->r:(trf))$a*n`div`b else tn f';_->[]} main=readLn>>=(\f->readLn>>=(\n->print$last$tnf))
Java, 200 192 179 characters
I think everyone knows that Java would not have the shortest implementation, but I wanted to see how it would compare. It solves the trivial examples, but not the bonus one.
Here is the minimized version:
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
Here is the cleaned-up version:
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); } }
Scheme 73 characters
My first attempt, at doing this with completely standard R 5 RS Scheme, came in at 104 characters:
(define(fpn)(let l((qp)(nn))(if(null? q)n(let((a(* n(car q))))(if(integer? a)(lpa)(l(cdr q)n))))))
Running against a few items in the test vector:
> (f '(3/2) 1296) 6561 > (f '(455/33 11/13 1/11 3/7 11/2 1/3) 60466176) 7888609052210118054117285652827862296732064351090230047702789306640625
If you assume that λ is bound to lambda and let/cc is defined (as they are in PLT Scheme; see below for definitions for running this in Schemes that don't define those), then I can adapt Jordan's second Ruby solution to Scheme, which comes out to 73 characters (note that the argument order is the reverse of my first solution, but the same as Jordan's; in this version, that saves one character).:
(define(fnp)(let/cc r(map(λ(i)(if(integer?(* ni))(r(f(* ni)p))))p)n))
If I don't have λ and let/cc predefined, then this one comes in at 111 characters (88 if the fairly common call/cc abbreviation is defined):
(define(fnp)(call-with-current-continuation(lambda(r)(map(lambda(i)(if(integer?(* ni))(r(f(* ni)p))))p)n)))
Definitions of λ and let/cc :
(define-syntax λ
(syntax-rules ()
((_ . body) (lambda . body)))
(define-syntax let/cc
(syntax-rules ()
((_ var . body) (call-with-current-continuation (lambda (var) . body)))))
A bit late… dc 84 chars
Just for fun a dc solution (OpenBSD)
[ss1sp]s1[Rlp1+sp]s2?l1xz2/sz[z2/ds_:bl_:az0<L]dsLx 1[;als*lp;b~0=1e2lpdlz!<L]dsLxlsp
It handles all the cases:
$ dc fractran.dc 455 33 11 13 1 11 3 7 11 2 1 3 60466176 7888609052210118054117285652827862296732064351090230047702789306640625
I can't leave comments yet but here's a "slightly" shorter version of RCIX's C# version (i believe it's 7 chars shorter)
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);}}}
which uses
Func<string,decimal> d=Convert.ToDecimal
and calls d(); 代替
using b=Convert;
and repeatedly calling b.ToDecimal(); 。
I also removed an unnecessary pair of curly braces around the else statement to gain 1 char :).
I also replaced the a[i+1] with a[++i] and in the following else body i replaced i+=2 with i++ to gain another char 😛
