图灵机代码高尔夫

Question

好的,今天的目标是建立一个图灵机模拟器.对于那些不知道它是什么的人,请参阅维基百科文章.我们今天使用的状态表位于该页面的正式定义的末尾.

代码将采用一系列"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.

(希望)最终编辑: 我对这个问题造成的困惑和麻烦表示最诚挚的歉意:我误读了我列出的提供的状态表,然后向后看.我希望你能原谅我浪费你的时间; 这完全是无意的!

Answer 1

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)

Answer 2

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

Answer 3

Perl函数101 char

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没有把他的高尔夫球手计算在内.

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

Perl函数112 char

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

我只计算了函数,它按照指定的顺序接受字符串,状态num和位置.该函数将新磁带状态作为数组返回.

另一个变体106 char

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 char

这个也是合并但以不同的方式.它只是使用全局变量来传递函数内部的参数.因此,您将变量设置在函数外部而不是内部.从而从函数体中删除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";