Nic*_*son 49 code-golf esoteric-languages
编写一个充当Fractran解释器的程序.任何语言的字符数最短的翻译都是赢家.你的程序必须有两个输入:要执行的fractran程序和输入整数n.该程序可以是任何方便您的程序的形式 - 例如,2元组列表或平面列表.输出必须是单个整数,是执行结束时寄存器的值.
Fractran是John Conway发明的一种微不足道的深奥语言.fractran程序由一系列正分数和一个初始状态n组成.解释器维护一个程序计数器,最初指向列表中的第一个部分.Fractran程序以下列方式执行:
有关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中提供工作分形翻译的人都将获得500点声望点奖励.在不太可能发生多个自托管解释器的情况下,分数最短的解释器将获得赏金.
在提交包含1779个分数的自托管fractran解决方案之后,官方获胜者是Jesse Beder的解决方案.实际上,解决方案太慢,甚至不能执行1 + 1.
令人难以置信的是,这已被另一个fractran解决方案击败 - Amadaeus的解决方案只有84个分数!在我的参考Python解决方案上运行时,它能够在几秒钟内执行前两个测试用例.它使用了一种新颖的分数编码方法,值得仔细研究.
荣誉提及:
Jes*_*der 45
(编辑:修复)
(我希望人们仍然关注这个话题,因为这需要一段时间!)
它似乎不会让我发布一些东西,所以我在这里发布了Fractran来源.
输入指定如下:
首先,我们m/n = p_0^a0... p_k^ak通过以下方式编码分数:
ai:p_2i^aiif 乘以ai > 0p_2i+1^{-ai}if 乘以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语句(为方便起见!).可以在此处找到该代码.
如果你想自己编译代码到Fractran,我的(C++)程序可以在这里找到[tar.gz].在令人惊叹的dogfooding(和炫耀)展示中,我使用了我的C++ YAML解析器yaml-cpp,所以你必须下载并链接它.对于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语句则更多).所以我猜测运行翻译至少需要几天,如果不是几年:(
那么我怎么知道它有效呢？嗯,当然我不是百分百肯定,但我非常接近.首先,我测试了很多很多组件,特别是,我非常彻底地测试了元语言的所有元素(函数if和while语句的序列).
此外,元语言很容易翻译成您喜欢的语言,甚至更容易翻译成C++,因为函数的所有参数都是通过引用传递的.如果你再次感到懒惰,你可以在这里下载我的翻译[tar.gz](没有makefile;它只是两个.cpp文件,所以直接调用gcc就可以了).
所以你可以比较两个解释器,运行C++版本(它还需要伪Fractran中的输入/输出),检查它是否有效,然后说服自己元语言也可以工作.
如果您感到受到启发,并且真的希望看到这个解释器被解释,您可以根据我们得到的Fractran输出类型编写一个"聪明的"Fractran解释器.输出是非常结构化的 - 函数序列是使用信号实现的,所以如果你以某种方式缓存解释器所在的位置,如果没有重要的改变,你可以立即跳转到那里.我认为,这将大大加快计划的速度(可能会减少一个或多个权力的运行时间).
但是,我不确定如何做到这一点,我对所做的事感到满意,所以我将把它作为读者的练习.
Hai*_*inh 41
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 segfaulted(但我认为它将使用Prime指数向量在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 }
}
Ste*_*non 20
x86_64程序集,165个字符(28个字节的机器代码).
状态在%rdi中传递,Program(指向以null结尾的分数数组的指针)在%rsi中.根据通常的C风格调用约定,结果以%rax返回.使用非标准的调用约定或Intel语法(这是AT&T语法)会丢弃更多的字符,但我很懒惰; 别人可以做到这一点.通过重新安排控制流程几乎可以肯定地保存一两条指令,如果有人想这样做,请随意.
中间计算(state*numerator)最大可达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最小化版本的详细标签.
Jor*_*ing 16
这是我有史以来的第一个高尔夫球场,所以请保持温和.
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
受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个字符.)
Joh*_*ooy 12
{:^{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
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
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
将输入作为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
感谢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()
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]
毫无疑问,这是我写过的最离奇,最慢的素数发生器.我不确定这是好事还是坏事.