(编辑:固定)

看来我不会发布这么长的东西,所以我发布了Fractran源代码 here

输入指定如下:

首先,我们编码一个分数 m/n = p_0^a0... p_k^ak 作者:

• 从1开始。然后,每个 ai :
• 乘 p_2i^ai 如果 ai > 0
• 乘 p_2i+1^{-ai} 如果 a_i < 0

这样,我们将任何分数编码为正整数。现在,给定一个progoram(编码分数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 .

here [tar.gz]。在一个惊人的DOOFUTIN显示(和炫耀),我用我的C++ YAML解析器 yaml-cpp ,所以你必须下载并链接到它。对于yaml cpp和“编译器”,您需要 CMake 用于跨平台生成makefile。

此程序的用途是:

./fracc interpreter.frp

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

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

n 行中的第位数字为 an ,那么分数就是 p_n^an

将其转换为Fractran非常容易,但如果您很懒,可以使用 to-fractions.py . [ 注

关于输入的注释 :如果要以这种方式测试不同的函数,约定始终相同。它在pseudo Fractran中有许多参数(通常函数上方的注释解释了这一点),所以给它想要的,再加上一个 1

然而,

IncrementPrimes ,它接受一对素数并返回下两个素数,大约需要 8分钟 循环或 如果 声明)。所以我猜运行解释器至少需要几天,如果不是几年的话:(

如果 虽然 (陈述)非常彻底。

here

因此,你可以比较两个解释器,运行C++版本(它也采用伪FractRAN中的输入/输出),检查它是否有效,然后说服自己,元语言也能工作。

或

如果你感到受到鼓舞 真正地

但是,我真的不知道如何做到这一点,我对所做的很满意,所以我将把它留给读者作为练习。

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

这确实是一个很大的数字。

第一个测试向量在中完成 不到一秒钟 the complete output .

不幸的是,当我尝试第二个测试向量时,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 }
}

x86_64程序集 ,165个字符(28字节的机器代码)。

中间计算(状态*分子)最宽可达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 用于最小化版本。

58 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

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

红宝石, 52使用Rational

灵感来自 gnibbler's solution 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

Golfscript-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

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

python 82 81 72 70个字符。

以分数形式输入很方便。分数对象。与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

C , 159 131

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

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

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

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#interactive中测试):

> 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

说出前10个素数需要惊人的4.7秒:

> 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版本: . 无奖励向量:(

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

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

压缩版本称重在 (没有名称空间声明或任何名称空间声明,只有single using语句(不是system)和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

棒极了 , 136 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

84

使用标准输入。

@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

哈斯克尔:

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}

计划: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方案,分配256 mb)

卢阿:

整洁代码:

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

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

不处理奖金向量:(

Python中的参考实现

首先,它通过将分子和分母编码为(idx,value)元组列表来解码分数元组列表,其中idx是素数(2是素数0,3是素数1,等等)。

这种方法的速度大约是Python中对大整数执行算术运算速度的5倍,并且更易于调试!

通过构造一个数组,将每个素数索引(变量)映射到第一次检查分数分母中的素数索引(变量),然后使用该数组构造一个“跳转映射”,由下一条指令组成,以便为程序中的每条指令执行。

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

笔记:

1. 冒号符号 first @program: pointy-sub

2. Rakudo似乎有一辆四轮马车 Rat 给出错误的结果。当前的Niecza正确快速地运行所有测试程序,包括“奖金”部分。

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

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

15625

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

方案73个字符

我的第一次尝试,用完全标准的R ^5. 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

如果你假设 λ 必然 lambda 和 let/cc 已定义(正如它们在PLT方案中一样;有关在未定义它们的方案中运行此功能的定义,请参见下文),然后我可以进行调整 Jordan's second Ruby solution 到Scheme,总共73个字符(请注意,参数顺序与我的第一个解决方案相反,但与Jordan的相同;在这个版本中,保存了一个字符)。:

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

和 预定义的,那么这个是在111个字符(88,如果是相当常见的 call/cc 缩写定义如下:

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

定义 和 let/cc :

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

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

有点晚了。。。dc 84字符

只是为了好玩 dc

[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

我还不能留下评论,但这里有一个“稍微”短一点的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] i+=2 具有 i++