Ответ 1

Функция Perl 101 char

sub f{($_,$S,$p)[email protected]_;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. Эти два трюка подразумевают некоторое тривиальное декодирование вывода, но я считаю, что все в порядке. Я также не считал окончательную полуколону в своей функции, поскольку гнибблер не считал его в своем гольф-поле.

Если кто-то заинтересован, я могу также опубликовать другие мои попытки. Они немного дольше, но используют забавные трюки. Один из них представляет собой регулярное выражение, основанное, например, и работает непосредственно с лентой в качестве строки, другой - это своего рода бит-фу.

Функция Perl 112 char

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

@res = [email protected];
print @res," H $p\n";

Я подсчитал только функцию, и она принимает строку, состояние num и позицию в указанном порядке. Функция возвращает новое состояние ленты в виде массива.

Другой вариант 106 char

sub f{($_,$S,$p)[email protected]_;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";

Ответ 2

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

testcases

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

Ответ 3

C - 282 44 98 символов (включая все объявления цикла и таблицы внутри цикла)

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

Ответ 4

Perl 142 char (не считая чтения аргументов в командной строке и окончательной печати. ​​Ну, большая часть кода - это программа бобров, сам движок - только 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

Примечание: по сути, это еще не игра в гольф, а просто наивная первая попытка. Я могу вернуться с чем-то настоящим.

Ответ 5

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 Персонажи
Чтение всей программы из stdin

' '/(:$;(~: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 turing.gs 
"1111"2
$ echo -n 110100 3 1 |../golfscript.rb turing.gs 
"11111111"1

Ответ 6

С# - 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> как ленту, поэтому ее можно развернуть до тех пор, пока память ее позволяет.

Утверждение:

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

Ответ 7

Чтобы уточнить, эта программа имитирует машину Busy Beaver Turing точно так, как описано в статье wikipedia, а не OP (OP имеет R и L)

Python 255 char

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

Ответ 8

Perl, 97 (действительно, потому что final ";" является необязательным для субблока)

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

Идея: Переменная $_ содержит 0 и 1, кроме под головкой. Под головой, 0 в состоянии А дает 2, 1 в состоянии А дает 3, 0 в состоянии B дает 4, 1 в состоянии B дает 5, 0 в состоянии С дает 6, 1 в C-состоянии дает 7.

поэтому, следуя первому примеру "1010" (позиция 3, состояние A), выдается "1051", затем "1411", "1131", "1117" (1111, состояние C, позиция 3) и останавливается (плюс перемещает ленту на справа)

Ответ 9

Lua:

Полу-гольф версия:

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

Ответ 10

F # - 275 символов

Хорошо, так определенно не самое короткое, но обучение. Если кто-то может помочь получить String.mapi для использования function, а затем fun match with, я был бы признателен, я продолжаю получать "дискриминатор шаблона x не определен". Кто-нибудь знает сайт, в котором подробно описаны правила использования ключевого слова function в лямбда?

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. Комментарии и предложения (конструктивные просьбы) приветствуются и поощряются.

Ответ 11

Lua, 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 ответ re-golfed, 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)

• использует оператор ... для назначения входных параметров
• использует and и or вместо операторов if при сокращении
• заменил elseif на else только else, допустив допустимые входные/состояния
• удаленные пробелы после парнеров, оператор эллипса и конечные кавычки

Ответ 12

Ruby, 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