interpreter - 图灵机代码高尔夫

Question

好的，今天的目标是构建一个图灵机模拟器。对于那些不知道它是什么的人，请参阅Wikipedia 文章。我们今天使用的状态表位于作为该页面一部分的正式定义的末尾。

该代码将采用“0”和“1”字符串字符的序列，一个表示机器开始的字符的整数，以及一个表示程序状态的整数（无特定顺序），并输出最终结果对字符串的操作，以及最终位置。例子：

示例 1：

1010 state A(0)
   ^ (3)
1011 state B(1)
  ^ (2)
1011 state B(1)
 ^ (1)
1111 state A(0)
  ^ (2)
1111 state C(0)
   ^ (3)
1111 HALT
  ^ (2)

示例 2：

110100 state B(1)
   ^ (3)
110100 state B(1)
  ^ (2)
111100 state A(0)
   ^ (3)
111100 state C(2)
    ^ (4)
111110 state B(1)
     ^ (5)
1111110 state A(0)
      ^ (6, tape has been extended to right)
1111111 state B(1)
     ^ (5)
1111111 state B(1)
    ^ (4)
1111111 state B(1)
   ^ (3)
1111111 state B(1)
  ^ (2)
1111111 state B(1)
 ^ (1)
1111111 state B(1)
^ (0)
01111111 state B(1)
^ (0, tape has been extended to left)
11111111 state A(0)
 ^ (1)
11111111 state C(2)
  ^ (2)
11111111 HALT
 ^ (1)

杂项：

您的代码必须通过根据需要扩展字符串来正确处理写入磁带上“空格”的尝试。
由于指定的状态机未指定任何类型的“空白磁带”操作，因此将所有空白值视为 0。
您必须仅计算处理具有初始状态的字符串的评估的方法，如何输出该数据取决于您。
在磁带上向右移动是递增的（字符串位置 0 一直在左侧），状态 0 是 A，状态 1 是 B，状态 2 是 C。

（希望）最终编辑： 我对这个问题造成的混乱和麻烦表示最诚挚的歉意：我误读了我列出的提供的状态表，并将其倒退。我希望你能原谅我浪费你的时间；这完全是无意的！

score 10 · Accepted Answer

Python - 133 个字符

至少要打败 perl 一段时间:)

def f(t,i,s):
 t=map(int,t) 
 while s<3:t=[0]*-i+t+[0][:i>=len(t)];i*=i>0;c,t[i]=s*4+t[i]*2,1;i+=1-(2&2178>>c);s=3&3401>>c
 return t,i

Python - 172 个字符

def f(t,i,s):
 t=map(int,t)
 while s<3:
  t=[0]*-i+t+[0]*(i-len(t)+1);i=max(0,i);c,t[i]=t[i],1;i,s=[[(i-1,1),(i+1,2)],[(i+1,0),(i-1,s)],[(i+1,1),(i-1,3)]][s][c]
 return t,i

测试用例

assert f("1010",3,0) == ([1, 1, 1, 1], 2)
assert f("110100",3,1) == ([1, 1, 1, 1, 1, 1, 1, 1], 1)

score 9 · Accepted Answer

C - ~~282~~ 44 98 个字符 （包括所有内循环 var 和表声明）

#include<stdio.h>
#include<string.h>

char*S="  A2C1C2  C3A2A0";
f(char*p,char c){char*e;while(c){e=S+*p*8+c*2;*p=1;p+=*e++-66;c=*e-48;}}

char T[1000];
main()
{
  char *p;
        char c;
        char *e;

    int initial;
    scanf("%s %d %c",&T[500],&initial,&c);
    c = c - '0' + 1;

    for(p=&T[500]; *p; p++)
        *p -= '0';

    p = &T[500+initial];

    f(p, c);

    char *left = T;
    while((left < T+500)&&(!*left))
        left++;

    char *right = T+sizeof(T)-1;
    while((right > T+500)&&(!*right))
        right--;

    initial = p - left;

    for(p=left; p<=right; p++)
        *p+='0';

    printf("%.*s %d\n\n",right-left+1,left,initial);
}

score 6 · Accepted Answer

Perl 函数 101 字符

sub f{($_,$S,$p)=@_;for(%h=map{$i++,$_}split//;7^$S;$p-=$S<=>3){$S=7&236053>>3*($S%4*2+!!$h{$p}++)}};

f(@ARGV);
@allpos = sort keys %h;
for (@allpos){
    print $h{$_}?1:0;
}
print " H ".($p-$allpos[0])."\n";

这个很有趣。两招。它对磁带使用哈希，知道什么吗？哈希是可自动扩展的，因此无需再关心磁带边界。另一个技巧是结合读取和写入访问的单元格。只需更改内部约定 0，空格表示 0，任何其他值表示 1。这两个技巧意味着对输出进行一些简单的解码，但我相信没关系。我也没有在我的函数中计算最后一个分号，因为 gnibbler 没有在他的 Golfscript 中计算他的。

如果有人感兴趣，我也可以发布我的其他尝试。它们有点长，但使用有趣的技巧。例如，一个是基于正则表达式的，并且直接与磁带作为字符串一起工作，另一个是一种位符。

Perl 函数 112 字符

sub f{($_,$S,$p)=@_;for(split//;7^$S;@_=($p=0,@_)if($p-=$S<=>3)<0){$S=7&236053>>3*($S%4*2+$_[$p]);$_[$p]=1}@_};

@res = f@ARGV;
print @res," H $p\n";

我只计算了这个函数，它需要一个字符串、一个状态编号和一个按指定顺序排列的位置。该函数以数组的形式返回新的磁带状态。

另一种变体 106 字符

sub f{($_,$S,$p)=@_;for(split//;7^$S;$p-=$S<=>3){$S=7&236053>>($S%4*6+$_[$p]*3);$_[$p++]=1;@_=(0,@_)}@_};`

@res = f(@ARGV);
print @res," H $p\n";

目前尚不清楚此人是否作弊。它给出了正确的结果并自动扩展磁带（没有固定限制），但为了避免测试是否有必要扩展磁带，它会在每一步都这样做并调整索引。

另一种变体 98 字符

这一个也在合并中，但以不同的方式。它只是使用全局变量在函数内部传递参数。因此，您将变量设置在函数外部而不是内部。因此从函数体中删除了 14 个字符。

sub f{for(split//;7^$S;@_=($p=0,@_)if($p-=$S<=>3)<0){$S=7&236053>>3*($S%4*2+$_[$p]);$_[$p]=1}@_};

($_,$S,$p) = @ARGV;
@res = f();
print @res," H $p\n";

score 3 · Accepted Answer

Perl 142 char（不包括在命令行上读取 args 和最终打印。嗯，大部分代码是海狸程序，引擎本身只有 46 char。

我更改了输入格式以将状态放在字符串中的位置。我一点也不感到内疚，否则大多数代码都会在头部出现问题时进行边界管理。即使在这个版本中，字符串边界管理也要花费 17 个字符......诀窍只是记住你可以将图灵机表示为马尔可夫链......我用正则表达式做了什么。

perl -e '$b=shift;%p=qw(A0|A$ 1B ^A1|0A1 C01 1A1 C11 0B0|^B0 A01 1B0|1B$ A11 B1 1B 0C0|^C0 B01 1C0|1C$ B11 C1 1H);while($b!~/H/){$b=~s/$_/$p{$_}/for keys%p}print"$b\n"' 00A1011

111H1111

注意：事实上，这还不是真正的高尔夫，而只是天真的第一次尝试。我可能会带着一些真正简短的东西回来。

score 3 · Accepted Answer

Golfscript - 102 个字符

{:s;{\:$;:^0<{0.:^$+:$}{^$}if.,@>!'0'*+.^=1&s.++:c;.^<1+\^)>+:$[^(^).^(^)^(]c=:^3"120113"c=3&:s-}do}:f

;
["1010" 3 0 f]p
["110100" 3 1 f]p
["1000000" 3 1 f]p

106 个字符

{:s;\:$;:i{0<{0.:i$+:$}{i$}if.,@>!'0'*+.i=1&s.++:c;.i<1+\i)>+:$;[i(i).i(i)i(]c=:i 3"120113"c=3&:s-}do$\}:f

113 个字符
从标准输入读取整个程序

' '/(:$;(~:i;~~:s;{0i>{0.:i$+:$}{i$}if.,@>!'0'*+.i=1&s.++:c;.i<1+\i)>+:$;[i(i).i(i)i(]c=:i;3"120113"c=3&:s-}do$`i

例子

$ echo -n 1010 3 0 |../golfscript.rb 图灵.gs
“1111”2
$ echo -n 110100 3 1 |../golfscript.rb 图灵.gs
“11111111”1

score 3 · Accepted Answer

C# - 157 个字符

void T(List<int>t,ref int p,int s){while(s!=3){if(p<0)t.Insert(0,p=0);if(p==t.Count)t.Add(0);var c=t[p]==1;t[p]=1;p+=s==0==c?1:-1;s=s==1==c?1:c?s==0?2:3:0;}}

该方法采用List<int>as 磁带，因此只要内存允许，就可以对其进行扩展。

断言：

List<int> tape;
int pos;

tape = "1010".Select(c => c - '0').ToList();
pos = 3;
T(tape, ref pos, 0);
Debug.Assert(String.Concat(tape.Select(n => n.ToString()).ToArray()) == "1111" && pos == 2);

tape = "110100".Select(c => c - '0').ToList();
pos = 3;
T(tape, ref pos, 1);
Debug.Assert(String.Concat(tape.Select(n => n.ToString()).ToArray()) == "11111111" && pos == 1);

如果我们作弊并从一开始就分配一个足够大的数组，107 个字符：

void X(int[]t,ref int p,int s){while(s!=3){var c=t[p]==1;t[p]=1;p+=s==0==c?1:-1;s=s==1==c?1:c?s==0?2:3:0;}}

score 2 · Accepted Answer

澄清一下，这个程序完全按照维基百科文章中的描述模拟繁忙的海狸图灵机，而不是 OP（OP 有 R 和 L 切换）

Python 255 字符

def f(k,i,s):
 t=map(int,k)
 while s<3:
    if i==len(t):t+=[0]
    if i<0:t=[0]+t;i=0
    x=t[i],s
    if x==(0,0):t[i]=1;i-=1;s=1
    if x==(0,1):t[i]=1;i+=1;s=0
    if x==(0,2):t[i]=1;i+=1;s=1
    if x==(1,0):i+=1;s=2
    if x==(1,1):i-=1;s=1
    if x==(1,2):i-=1;s=3
 return t,i

score 2 · Accepted Answer

Perl，97（确实是 96，因为最后的“;”对于子块是可选的）

sub f{($_,$a,pos)=@_;s/\G./$&+2*$a+2/e;1while s!(.?)(2|5)|(3|4|6)(.?)!$2?4+$1.1:8+$4+$3+5*/3/!e}
f@ARGV;
#output
s/7/1/;print;print " H ",(-1+length$`);

这个想法： $_ 变量包含 0 和 1，除了头部之外。在头部下方，A 状态 0 给出 2，A 状态 1 给出 3，B 状态 0 给出 4，B 状态 1 给出 5，C 状态 0 给出 6，C 状态 1 给出 7。

so following the first example "1010" (pos 3, state A) gives "1051" then "1411", "1131", "1117" (1111, state C, pos 3) and stop (plus move tape to right)

score 1 · Accepted Answer

卢阿：

半高尔夫版本：

a=arg
t=a[1]
i=a[2]+1
s=a[3]+0
r=string.rep
b=string.sub;z="0";o="1";while true do if i<1 then
        t=z..t
        i=1
    elseif i>#t then
        t=t..z
    end
    c=b(t,i,i)
    if i>0 then
        t=b(t,0,i-1)..o..b(t,i+1,#t)
    else
        t="1"..b(t,i+1,#t)
    end
    if s==0 then
        if c==z then
            i=i-1
            s=1
        elseif c==o then
            i=i+1
            s=2
        end
    elseif s==1 then
        if c==z then
            i=i+1
            s=0
        elseif c==o then
            i=i-1
        end
    elseif s==2 then
        if c==z then
            i=i+1
            s=1
        elseif c==o then
            i=i-1
            break
        end
    end
end
print(t,i-1)

压缩版重441 个字符：

a=arg t=a[1] i=a[2]+1 s=a[3]+0 r=string.rep b=string.sub;z="0";o="1";while true do if i<1 then t=z..t i=1 elseif i>#t then t=t..z end c=b(t,i,i) if i>0 then t=b(t,0,i-1)..o..b(t,i+1,#t) else t="1"..b(t,i+1,#t) end if s==0 then if c==z then i=i-1 s=1 elseif c==o then i=i+1 s=2 end elseif s==1 then if c==z then i=i+1 s=0 elseif c==o then i=i-1 end elseif s==2 then if c==z then i=i+1 s=1 elseif c==o then i=i-1 break end end end print(t,i-1)

以磁带、指令指针、状态的形式传递参数，如下所示：

turing.lua 1010 3 0

score 1 · Accepted Answer

F# - 275 个字符

好的，所以绝对不是最短的，而是学习。如果有人可以帮助让 String.mapi 使用 afunction而不是fun match with我将不胜感激，我会不断收到“未定义模式鉴别器 x”。任何人都知道一个详细说明function在 lambda 中使用关键字的规则的网站？

let rec t s i p=
    match s with
    |3->(p,i)
    |_->let g=[[(1,1);(-1,2)];[(-1,0);(1,1)];[(-1,1);(1,3)]]
        let p=match i with|_ when i<0 ->"0"+p|_ when i=p.Length->p+"0"|_->p
        let i=max 0 i
        let m,n=g.Item(s).Item((int p.[i])-48)
        String.mapi(fun x c->match x with|_ when x=i->'1'|_->c) p |> t n (i+m)

用法

t 1 2 "101011" |> printfn "%A"

为了便于阅读，这是一个扩展版本：

let rec tur state index tape =
    printfn "Index %d: State %d: Tape %s:" index state tape
    match state with
    |3 -> (tape, index)
    |_ -> let prog = [[(1,1);(-1,2)];[(-1,0);(1,1)];[(-1,1);(1,3)]]
          let tape = match index with |_ when index<0 ->"0"+tape |_ when index=tape.Length->tape+"0" |_->tape
          let index = max 0 index
          let move,newstate = prog.Item(state).Item((int tape.[index])-48)
          String.mapi (fun i c -> match i with |_ when i=index->'1' |_->c) tape
          |> tur newstate (index+move)

我还试图想出一种更好的方法来处理字符串的操作，而不是String.mapi. 欢迎和鼓励提出意见和建议（建设性的请）。

score 1 · Accepted Answer

卢阿，232

现在使用表查找。

j={{-1,1},{1,-1},{1,-1}}u={{1,2},{-1,0},{-1,1}}t,i,s=...i=i+1
s=s+1 z="0"o="1"while s<4 do if i<1 then t=z..t i=1
elseif i>#t then t=t..z end c=t:sub(i,i):byte()-47
t=t:sub(0,i-1)..o..t:sub(i+1)i=i+j[s][c]s=s+u[s][c]end print(t,i-1)

这只是RCIX重新打高尔夫球的答案，332 个字符。

t,i,s=...i=i+1 s=s+0 r=string.rep b=string.sub z="0"o="1"while s<3 do if i<1 then
t=z..t i=1 elseif i>#t then t=t..z end c=b(t,i,i)t=b(t,0,i-1)..o..b(t,i+1,#t)if
s<1 then i=i+(c==o and 1 or -1)s=c==z and 1 or 2 elseif s<2 then i=i+(c==o and
-1 or 1)s=c==z and 0 or s else i=i+(c==o and -1 or 1)s=c==z and 1 or 3 end end
print(t,i-1)

使用...运算符分配输入参数
较短时使用andandor而不是语句if
elseif仅else通过假设有效的输入/状态替换了一些
删除括号、椭圆运算符和结束引号后的空格

score 0 · Accepted Answer

红宝石，129

（当缩进被删除时）

def pr t,z,s      # DEBUG
  p [t,s]     # DEBUG
  p [' '*z + '^'] # DEBUG
end       # DEBUG


def q t,z,s
  s*=2
  (t=t.ljust z+1
    (t=' '+t;z=0)if z<0
    a=t[z]&1
    t[z]=?1
    b=s>0?1-a: a
    s="240226"[s|a]&7
    z+=b*2-1)while s!=6
  [t,z]
end

p q "1010",3,0
p q "110100",3,1