49

挑战

编写一个充当Fractran解释器的程序。在任何语言中,按字符数计算最短的口译员获胜。您的程序必须有两个输入:要执行的 fractran 程序和输入整数 n。该程序可以是任何对您的程序方便的形式——例如,2 元组列表或平面列表。输出必须是单个整数,即执行结束时寄存器的值。

分形

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

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

有关 Fractran 工作方式和原因的详细信息,请参阅esolang 条目和关于好数学/坏数学的这个条目。

测试向量

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

程序: [(3, 2)]
输入: 1296 (2 4 3 4 )
输出: 6561 (3 8 )

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

奖金测试向量:

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

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

提交和评分

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

语言“J”是不可接受的。这是因为在其中一个链接页面上 J 中已经有一个众所周知的解决方案。如果你是J迷,对不起!

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

优胜者

在提交了一个包含 1779 个分数的自托管 fractran 解决方案后,官方获胜者是Jesse Beder 的解决方案。但是,实际上,即使执行 1+1,该解决方案也太慢了。

令人难以置信的是,这已经被另一种分形解决方案打败了——阿玛迪乌斯的解决方案只有 84 个分数!在我的参考 Python 解决方案上运行时,它能够在几秒钟内执行前两个测试用例。它对分数使用了一种新颖的编码方法,这也值得仔细研究。

荣誉提及:

  • Stephen Canon 的解决方案,165 个字符的 x86 程序集(28 个字节的机器码)
  • Jordan 的52 个 ruby​​ 字符解决方案 - 处理长整数
  • Useless 的87 个 Python 字符的解决方案,虽然不是最短的 Python 解决方案,但它是为数不多的非递归解决方案之一,因此可以轻松处理更难的程序。它的可读性也很强。
4

25 回答 25

45

Fractran - 1779 个分数

(编辑:固定)

(我希望人们仍然关注这个帖子,因为这需要一段时间!)

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

输入指定如下:

首先,我们通过以下方式对分数进行编码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

其中programinput编码如上。例如,在第一个测试问题中,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]。在令人惊叹的 dogfooding(和炫耀)展示中,我使用了我的 C++ YAML 解析器yaml-cpp,所以你必须下载并链接它。对于 yaml-cpp 和“编译器”,您需要CMake来生成跨平台的 makefile。

这个程序的用法是:

./fracc interpreter.frp

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

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

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

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

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


然而,

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

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

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

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


或者!

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

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

于 2009-11-20T23:28:59.997 回答
41

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

解释的程序作为一个以 10 为基数的列表嵌入到单个以 11 为基数的数字中,使用数字“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 }
}
于 2009-11-26T09:27:22.410 回答
20

x86_64 汇编,165 个字符(28 个字节的机器码)。

状态在 %rdi 中传递,程序(指向以 null 结尾的分数数组的指针)在 %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

于 2009-11-17T17:49:31.590 回答
16

红宝石,58 57 56 5352 个字符

这是我第一次打代码高尔夫,所以请温柔一点。

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

红宝石,5352 使用理性

受到gnibbler 解决方案的启发,我能够使用 Rational 获得解决方案5352 个字符。仍然比上面的(不太优雅的)解决方案长一个。

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 个字符。)

于 2009-11-17T20:00:30.937 回答
12

高尔夫球手 - 32

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

    ; 108 [[3 2]] 帧
    #243
    ; 第1296章 [[3 2]]
    # 6561
    ; 108 [[455 33][11 13][1 11][3 7][11 2][1 3]]
    #15625
    ; 60466176 [[455 33][11 13][1 11][3 7][11 2][1 3]] fp
    # 7888609052210118054117285652827862296732064351090230047702789306640625
于 2009-11-18T04:37:54.753 回答
7

哈斯克尔,102 个字符

import List
import Ratio
l&n=maybe n((&)l.numerator.(n%1*).(!!)l)$findIndex((==)1.denominator.(n%1*))l
$ ghci
Prelude>:m 列表比例
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 放宽了对输入/输出格式的限制。

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
前奏列表比例> [455%33,11%13,1%11,3%7,11%2,1%3]&108
15625 % 1
于 2009-11-17T16:56:36.657 回答
6

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
$ 回声 1296 3 2 。| ./a.out; 回声
6561
$ 回声 108 455 33 11 13 1 11 3 7 11 2 1 3 。| ./a.out; 回声
15625
于 2009-11-17T17:30:39.723 回答
6

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
于 2009-11-18T01:32:25.190 回答
5

蟒蛇 - 53

感谢保罗的改进

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)

蟒蛇 - 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()
于 2009-11-18T07:51:08.623 回答
5

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

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   

测试代码:

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]

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

于 2009-11-18T15:06:16.627 回答
4

Python,110 103 95 87 个字符

文件

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

测试.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()
于 2009-11-17T17:54:26.593 回答
4

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
于 2009-11-18T06:18:10.587 回答
4

一个 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;};

输入格式为[[a,b],[c,d]]. 我利用了 Javascript 的宽大优势:var x=0, y=0;您可以添加任意数量的参数,而不是 do 。你是否真的通过它们并不重要,因为它们默认为null.

漂亮的版本:

函数 g(n,p) {
    变量 q, c, i=0;
    而(i < p.length){
        q = p[i];
        c = n * q[0];
        如果(c % q[1] != 0){
            ++i;
        } 别的 {
            n = c % q[1];
            我 = 0;
        }
    }
    返回 n;
};
于 2009-11-18T07:41:45.587 回答
2

Groovy136 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
于 2009-11-17T16:57:42.443 回答
2

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
于 2009-11-17T17:29:05.550 回答
2

卢阿:

整洁的代码:

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

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

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

于 2009-11-18T05:42:07.150 回答
2

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 正确快速地运行所有测试程序,包括“奖励”部分。

于 2009-11-18T09:00:53.460 回答
2

方案: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)

于 2009-11-18T09:22:47.740 回答
2

哈斯克尔:116109 个字符

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}

这最终成为了对达里奥进入的模仿。

于 2009-11-18T12:34:27.890 回答
2

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)
于 2009-11-22T22:33:27.147 回答
1

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))
于 2009-11-17T17:37:04.600 回答
1

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

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

15625

爪哇-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);
    }
}
于 2009-11-17T20:56:34.993 回答
1

方案 73 个字符

我的第一次尝试是使用完全标准的 R 5 RS 方案,输入 104 个字符:

(define(fpn)(let l((qp)(nn))(if(null?q)n(let((a(* n(car q))))(if(整数?
a)(lpa)(l(cdr q)n))))))

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

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

如果您假设它λ绑定到lambdalet/cc已定义(就像它们在 PLT 方案中一样;请参阅下文以了解在未定义这些方案的方案中运行它的定义),那么我可以将Jordan 的第二个 Ruby 解决方案改编为方案,结果是73 个字符(请注意,参数顺序与我的第一个解决方案相反,但与 Jordan 的相同;在此版本中,节省了一个字符)。:

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

如果我没有预定义λlet/cc那么这个字符有 111 个字符(如果call/cc定义了相当常见的缩写,则为 88 个字符):

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

λ和的定义let/cc

(定义语法 λ
  (语法规则()
    ((_ .body) (lambda .body)))

(定义语法 let/cc
  (语法规则()
    ((_ var .body) (call-with-current-continuation (lambda (var) .body)))))
于 2009-11-22T04:41:15.757 回答
1

有点晚了... dc 84 字符

只是为了好玩一个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
于 2010-03-23T23:03:08.203 回答
0

我还不能发表评论,但这是 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]witha[++i]和在下面的 else 正文中我替换i+=2i++获得另一个字符:P

于 2009-11-26T11:24:03.297 回答