Zdefiniujmy prosty język 2D, któremu nadamy niezwykle oryginalną nazwę befinge . Befinge ma 5 instrukcji:

• <>^v, jak w większości esolangów 2D, przekieruj wskaźnik instrukcji w odpowiednich kierunkach.
• . jest zakazem.

Wskaźnik instrukcji zaczyna się w lewym górnym rogu, po prawej stronie. Jeśli wskaźnik instrukcji dojdzie do krawędzi, program zatrzymuje się. Każdy program Befinge oczywiście zatrzyma się lub przejdzie w nieskończoną pętlę, która nic nie robi. Oto dwa przykłady:

Postojowy:

>.v
..<

Bez zatrzymania:

>....v
..v..<
..>v..
^..<..

Problemu zatrzymania nie da się rozwiązać w języku kompletnym Turinga, ale właśnie w tym. Twoim zadaniem jest napisanie programu (lub funkcji), który pobiera jako dane wejściowe ciąg znaków reprezentujący program befinge i zwraca wartość prawdy lub fałszu w zależności od tego, czy się zatrzyma, czy nie.

• Możesz założyć, że dane wejściowe będą składały się tylko z tych znaków i będą wypełnione spacjami, aby utworzyć prostokąt.
• Do instrukcji można użyć dowolnego zestawu pięciu znaków (np adws .).

Przypadki testowe

Postojowy:

.

v>
>^

....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.

v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<

Bez zatrzymania:

>..v
^..<

>v<
v<.
>v.
v<.
>.^

>.>.>.v
.><.<.<

To jest golf golfowy , więc wygrywa najkrótszy program (w bajtach).

ES6 (JavaScript), 111, 101 bajtów

EDYCJA: zmieniono wartości wyjściowe na prawda i fałsz , zamiast Y i N , aby zgolić jeszcze 10 bajtów

Grał w golfa

F=(I,M=[...I],c=0,i)=>(i={j:v=I.search`\n`+1,k:-v,h:-1,l:1,q:i,0:0}[M[c]])?F(I,M,c+i+(M[c]=0),i):i!=0

Test

F=(I,M=[...I],c=0,i)=>(i={j:v=I.search`\n`+1,k:-v,h:-1,l:1,q:i,0:0}[M[c]])?F(I,M,c+i+(M[c]=0),i):i!=0  

//Alphabet Map
tr={
'<':'h',
'>':'l',
'^':'k',
'v':'j',
'.':'q',
'\n':'\n'
};

//Test
T=(I,A)=>{
console.log({"Y":"#Halting","N":"#Non-Halting"}[A]);
console.log("I=\n",I,"\nF(I)=",O=F([...I].map(s=>tr[s]).join('')));
console.log('NY'[O*1] == A ? "OK !" : "NOT OK !");
}

//Halting
T(
`>.v
..<`
,'Y');

//Non-Halting
T(
`>....v
..v..<
..>v..
^..<..`
,'N');

//Halting
T(
`.`
,'Y')

//Halting
T(
`v>
>^`
,'Y');

//Halting
T(
`....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.`
,'Y');

//Halting
T(
`v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<`
,'Y');

//Non-Halting
T(
`>..v
^..<`
,'N');

//Non-Halting
T(
`>v<
v<.
>v.
v<.
>.^`
,'N');

//Non-Halting
T(
`>.>.>.v
.><.<.<`
,'N');

Przykładowe dane wyjściowe

#Halting
I=
>.v
..< 
F(I)= true
OK !    

#Non-Halting
I=
>....v
..v..<
..>v..
^..<.. 
F(I)= false
OK !

#Halting
I=
 . 
F(I)= true
OK !

#Halting
I=
v>
>^ 
F(I)= true
OK !

#Halting
I=
....v....
....>...v
.^..<....
.......v<
.......v.
....^..<. 
F(I)= true
OK !

#Halting
I=
v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^< 
F(I)= true
OK !

#Non-Halting
I=
>..v
^..< 
F(I)= false
OK !

#Non-Halting
I=
>v<
v<.
>v.
v<.
>.^ 
F(I)= false
OK !

#Non-Halting
I=
>.>.>.v
.><.<.< 
F(I)= false
OK !

Python 2 , 116 105 bajtów

x=1
X=Y=y=0
H=[]
G=input()
while(X,Y,x,y)not in H:H+=[(X,Y,x,y)];C=ord(G[Y][X]);x=C%3-1;y=C%5-1;X+=x;Y+=y

Wypróbuj online!

Wyzwanie jest stare, ale pomyślałem, że ponieważ jest to najkrótszy Python, opublikuję go. Dane wejściowe to lista ciągów znaków, ale użyte znaki są nietypowe.

> G
< B
v C
^ F
. L

Na przykład trzeci przykład zatrzymania zmienia się w ['LLLLCLLLL', 'LLLLGLLLC', 'LFLLBLLLL', 'LLLLLLLCB', 'LLLLLLLCL', 'LLLLFLLBL']. Wyjście odbywa się za pomocą kodu wyjścia, 0 (sukces) w przypadku braku zatrzymania i 1 (błąd) w przypadku zatrzymania. Doceniamy wszelkie porady i wskazówki.

Befunge-98 (PyFunge) , 217 209 200 bajtów

#v10dpf1dp12dp3dpk
 >#v~:a-#v_$10dp1dg1+1dp >
v  >10dp;>0dg1dgp0dg1+0dp^;f1dp
>0dg1dgg:'^-#v_n1-v
^<v01_v#!->':<
  <   >:'<-#v_01-0>   v
v^pd1+gd3gd1[:'v-#v_01>3dp2dpndg1dgp
>0dg2dg+0dp ^ @.!;>:'.-#;_

Wypróbuj online!

Problem zatrzymania befinge wymaga rozwiązania befunge. Zwraca 0 dla prawdy i 1 dla falsey. Umieszcza dane wejściowe na siatce, zaczynając od 1,15, a następnie przesuwa się na górę, zastępując strzałki zerami. Gdy tylko osiągniemy zero, wiemy, że się zapętla. Wszystko oprócz> <^ v. a zero jest uważane za zatrzymanie programu, który obejmuje granicę przestrzeni, które omijamy program, umieszczając go na siatce lekko przesuniętej.

Jednym łatwym sposobem na ogolenie kilku kęsów byłoby użycie liczb zamiast> <^ v. ale nie wydaje mi się, żeby było warto.

Turtlèd , 146 bajtów

!u[*.[ r+.]l[ l]dr_+]#*#[ u]d[ (.r)(>.r{.r}@>)(v.d{.d}@v)(<.l{.l}@<)(^.u{.u}@^)(*@0' )],@1(0@0)(v' d)(<' r)(>' l)(^' d)[ u]d[ l]r[ [ r]l[ ' l]dr],

Ten program ma inne wejścia / wyjścia: zakończ każdą linię spacją, w tym ostatnią. Turtlèd nie lubi nowych linii, ponieważ wykorzystuje siatkę dla swojego drugiego wymiaru znaków.

Wypróbuj online!

0 dla pętli na zawsze, 1 dla przerw.

Ogólne wyjaśnienie:

Zapisuje dane wejściowe na siatce, a następnie podąża ścieżką, którą strzałki robią wokół siatki, zastępując każdą strzałkę *, gdy idzie, zapisując również kierunek w char var. Jeśli napotka * strzałkę, którą wcześniej uderzył, program się nie zatrzyma, więc ustawia char var na 0, wyjście z pętli. W przeciwnym razie uderzy w koniec siatki i opuści pętlę. Napiszę char var. Jeśli trafi na koniec siatki, używa kierunku zapisanego w char var, aby wrócić do siatki i ustawia char var na 1, dla zatrzymań. Jeśli char var faktycznie wynosił 0, a nie kierunek, nie musi wracać, ponieważ nadal tam jest, i ustawia go z powrotem na 0. Czyści siatkę, a następnie zapisuje char var, 1dla przerw, w przeciwnym razie 0.

JavaScript (Node.js) , 80 bajtów

f=(a,v=1,x=0,[t,...u]=a,n=1+a.search`
`,c=a[x])=>t?f(a,v=+c?c-2||v:c+n,x-v,u):!c

Wypróbuj online!

JavaScript (Node.js) , 86 bajtów

f=(a,v=1,x=0,[t,...u]=a,n=1+a.search`
`,c=a[x])=>t?c>' '<=f(a,v=+c?c-2||v:c+n,x-v,u):0

Wypróbuj online!

JavaScript (ES6), 158 127 bajtów

f=(a,x=0,y=0,d=1,e=0,c=a[y]&&a[y][x])=>c<'~'?(c>'.'&&(a[y][x]='~',d=(c=='>')-(c=='<'),e=(c=='v')-(c=='^')),f(a,x+d,y+e,d,e)):!c

Pobiera dane wejściowe jako dwuwymiarową tablicę znaków i wraca truedo zatrzymania i falsedo nieskończonej pętli. Działa poprzez ustawienie odwiedzonych znaków kierunku na ~s, gdy rekurencyjnie je przemierza. Edycja: Zapisano 31 bajtów, aktualizując mój wektor kierunku przed rekurencją.

Nadużywanie znaków instrukcji ( 1=^ 4=< 5=. 6=> 9=v) prowadzi mnie do 101 bajtów:

f=(a,x=0,y=0,d=1,e=0,c=a[y]&&a[y][x])=>+c?(c-5&&(a[y][x]='0',d=~-c%4,e=~-(c>>2)),f(a,x+d,y+e,d,e)):!c

SmileBASIC, 158 145 bajtów

Jeśli ta sama strzałka zostanie napotkana więcej niż jeden raz, program nigdy się nie zatrzyma. Kiedy wskaźnik instrukcji mija strzałkę, jest zastępowany innym symbolem, co spowoduje, że funkcja zwróci 0, jeśli zostanie osiągnięta ponownie. Jeśli adres IP wykracza poza granice, zwraca 1.

DEF H P@L
C=VAL(P[Y][X])IF C>8THEN?0RETURN
IF C THEN D=C-1P[Y][X]="9
X=X+!D-(D==1)Y=Y+(D==2)-(D>2)IF X+1&&Y+1&&Y-LEN(P)&&X-LEN(P[0])GOTO@L
?1
END

Pobiera dane wejściowe jako tablicę ciągów. <any non-digit chracter>, 1, 2, 3, 4= ., >, <, v,^

Python 2, 182 bajty

m,v,d,x,y=input(),[],'>',0,0
try:
 while 1:
  if[x,y]in v:print 0;break
  c=m[y][x]
  if c!='.':d=c;v+=[[x,y]]
  if d in'><':x+=[-1,1][d=='>']
  else:y+=[-1,1][d=='v']
except:print 1

Pobiera tablicę ciągów jako dane wejściowe. Muszę to jeszcze bardziej pograć w golfa, ale na razie pora stresować się wyborami.

Nie golfowany:

input = input()

visited = [  ] 

dir = ">"
x=0
y=0

try:
    while True:
        if[x,y]in visited:print False;break
        char=input[y][x]
        if char!=".":
            dir=char
            visited+=[[x,y]]

        if dir==">":
            x+=1
        if dir=="<":
            x-=1
        if dir=="v":
            y+=1
        if dir=="^":
            x-=1
except:
    print True

Clojure, 143 bajty

#((fn[p v i s](if-let[v({\> 1\< -1\^(- s)\. v\v s}(get % p))](if(neg? i)1(recur(+ p v)v(dec i)s))))0 1 1e9(+(count(take-while(set"<>v^.")%))1))

Funkcja z 4 argumentami stanu: pozycja p, prędkość v, wskaźnik kroku ii rozmiar jednej linii s. Zwraca, 1jeśli nie przekroczyliśmy granic w 10 ^ 9 krokach i nilinaczej. W rzeczywistości ile kroków musimy sprawdzić, aby się upewnić (count %)? Myślę, że to coś więcej, ponieważ ten sam NOP może być przemierzany poziomo i pionowo.

Może być wywoływany w ten sposób (przyjmuje argumenty jako normalne ciągi znaków, getzwraca nilgdy jest poza zakresem):

(def f #( ... ))
(f ">....v\n..v..<\n..>v..\n^..<..")
(f "v>\n>^")
(f "....v....\n....>...v\n.^..<....\n.......v<\n.......v.\n....^..<.")

Przejścia stanu (+1, -1, + s, -s) są zakodowane w słowniku {\> 1\< -1\^(- s)\. v\v s}.

Python 2/3, 201 192 bajty

def f(x):
 X=Y=b=0;a=1;D={}
 while len(x)>Y>-1<X<len(x[Y]):
  try:
   a,b={'>':(1,0),'^':(0,-1),'<':(-1,0),'v':(0,1)}[x[Y][X]]
   if(X,Y)in D:return 0
  except:0
  D[X,Y]=0;X+=a;Y+=b
 return 1

Wypróbuj online!

Daje prawidłową odpowiedź dla ["<>"]

Java, 477

Wiem, że to nie wygrywa, n = i prawdopodobnie można w nią grać w golfa, ale implikuje podobną metodę do tego, co wykorzystują inne odpowiedzi, ale ta używa hashapy do wyszukiwania. W danych wejściowych używane są symbole> <^ v i cokolwiek innego niż to dla no op. Dane wejściowe pochodzą z argumentów.

GOLFED

import java.util.*;interface B{static void main(String[]a){HashMap<String,Byte>h=new HashMap<>();int x,y=0;for(String s:a){x=0;for(char c:s.toCharArray()){if("><^v".indexOf(c)>-1)h.put(x+","+y,(byte)c);x++;}y++;}x=0;y=0;int d=0;int D=0;while(x>-1&&x<a[0].length()&&y<a.length&&y>-1){Byte v=h.get(x+","+y);if(v!=null){if(v==0){System.out.print(0);return;}d=(v<85)?"<>".indexOf(v)*2-1:0;D=(v>84)?"^v".indexOf(v)*2-1:0;}h.replace(x+","+y,(byte)0);x+=d;y+=D;}System.out.print(1);}}

UNGOLFED

import java.util. *;

interface B{
    static void main(String a[]) {
        HashMap<String, Byte> h = new HashMap<>();
        int x, y = 0;
        for(String s : a) {
            x = 0;
            for(char c : s.toCharArray()) {
                if ("><^v".indexOf(c) > -1) h.put(x + "," + y, (byte) c);
                x++;
            }
            y++;
        }
        x = 0;
        y = 0;
        int d = 0;
        int D = 0;
        while(x > -1 && x < a[0].length() && y < a.length && y > -1) {
            Byte v = h.get(x + "," + y);
            if(v != null) {
                if(v == 0) {System.out.print(0); return;}
                d = (v < 85) ? "<>".indexOf(v)*2-1 : 0;
                D = (v > 84) ? "^v".indexOf(v)*2-1 : 0;
            }
            h.replace(x + "," + y, (byte) 0);
            x += d;
            y += D;
        }
        System.out.print(1);
    }
}

Wyjaśnienie już wkrótce!