代码高尔夫：Fractran

Question

代码高尔夫：Fractran

49

挑战

编写一个程序，作为Fractran解释器。以字符计数最少的方式实现，无论是哪种语言，都是获胜者。您的程序必须接收两个输入：要执行的fractran程序和输入整数n。程序可以采用任何方便您的程序的形式 - 例如，2元组列表或平面列表。输出必须是单个整数，即执行结束时寄存器的值。

Fractran

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

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

有关Fractran的工作原理和原因的详细信息，请参见esolang entry和good math/bad math上的this entry。

测试向量

程序：[(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¹⁰⁰)

提交与评分

程序将按照字符长度严格排名，最短的为最佳。可以同时提交美观且有文档的代码和“minified”版本的代码，以便人们了解情况。

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

额外奖励，任何能够提供一个自托管的fractran解释器的人将获得500声望点奖励。如果存在多个自托管解释器，则具有最少分数的解释器将获得赏金。

获胜者

官方获胜者是Jesse Beder's solution，他提交了一个由1779个分数构成的自托管fractran解决方案。但实际上，该解决方案的执行速度太慢，甚至无法执行1+1。

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

荣誉提名：

Stephen Canon's solution，使用165个字符的x86汇编语言（28个字节的机器代码）
Jordan's solution，使用52个字符的ruby - 可处理长整数
Useless's solution，使用87个字符的Python，虽然不是最短的Python解决方案之一，但是它是少数不是递归的解决方案之一，因此可以轻松处理更难的程序。它也非常易读。

- Nick Johnson

20

对于不可避免的关门派: 在 Stack Overflow 上有超过100个标记为代码高尔夫的问题。这是一个合法的帖子，并且会得到有趣而富有启发性的回答。此外，它是一个社区 Wiki，因此没有人会通过它来攫取声誉。 - Nick Johnson

8

@R. Pate：在我之前可以先去和其他 104 个代码高尔夫的人争论一下，或者在 Meta 上提出来，社区共识通常是支持的。@mmyers：谢谢，我会更新问题。 - Nick Johnson

9

目前的共识看起来相当强大（超过20个人支持“可以，如果你不喜欢就忽略它”）：http://meta.stackexchange.com/questions/20912/so-weekly-code-golf。当然，你（和其他关心此事的人）应该投票，并且如果你的观点没有被覆盖，也应该说明你的观点。 - ire_and_curses

5

我并非预先发表评论，而是在别人投票关闭之后才进行了评论。 - Nick Johnson

6

我只是发表个人意见：这是一个很棒的问题，一方面因为我喜欢代码高尔夫，另一方面更重要的是因为它让我了解了一个非常有趣的东西（以前从没听说过这种“语言”，但它太棒了！）。 - Edan Maor

显示剩余8条评论

25个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Useless · Answer 1

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

- RCIX · Answer 2

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语句（不是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

- danielkza · Answer 3

一个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;那样定义多个变量，你可以添加任意数量的参数。无论你是否实际传递它们，它们都默认为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;
};

- Reverend Gonzo · Answer 4

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

- RCIX · Answer 5

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

很遗憾，它不能处理奖励向量 :(

因为从命令行中获取内容很麻烦，所以我手动输入了一些，但这是返回的结果。

(注意：保留HTML标签)

- hobbs · Answer 6

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

注意事项：

当前实现中，冒号表示法first @program: pointy-sub不起作用，应使用first BLOCK, @program。
Rakudo似乎存在一个有缺陷的Rat，会给出错误的结果。当前版本的Niecza可以正确快速地运行所有测试程序，包括“额外”的分数计算。

- Isaac · Answer 7

方案：326

我觉得需要一个Scheme的提交，以保持平衡。我也只是想借此机会来研究一下。（请原谅我的基础知识，我相信这可以被优化，并且我愿意听取建议！）

#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）

- comingstorm · Answer 8

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的作品。

- Nick Johnson · Answer 9

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)

- mob · Answer 10

Perl, 84 82 char

使用标准输入。

@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