Lösen Sie das Halteproblem für Befinge

29

Definieren wir eine einfache 2D-Sprache, die den unglaublich ursprünglichen Namen enthält . Befinge hat 5 Anweisungen:

  • <>^vRichten Sie, wie in den meisten 2D-Esolangs, den Befehlszeiger in die entsprechenden Richtungen um.
  • . ist ein No-Op.

Der Anweisungszeiger beginnt oben links und geht nach rechts. Wenn der Befehlszeiger an eine Kante gelangt, wird das Programm angehalten. Jedes Befinge-Programm wird offensichtlich entweder anhalten oder in eine Endlosschleife geraten, die nichts bewirkt. Hier sind zwei Beispiele:

Anhalten:

>.v
..<

Nicht haltend:

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

Das Halteproblem ist für eine Turing-vollständige Sprache nicht lösbar, aber für diese. Ihre Aufgabe ist es, ein Programm (oder eine Funktion) zu schreiben, das / die eine Zeichenfolge als Eingabe verwendet, die das befinge- Programm darstellt, und einen Wahrheits- oder False-Wert zurückgibt, je nachdem, ob es anhält oder nicht.

  • Sie können davon ausgehen, dass die Eingabe nur aus diesen Zeichen besteht und mit Leerzeichen aufgefüllt wird, um ein Rechteck zu bilden.
  • Sie können einen beliebigen Satz von fünf Zeichen für die Anweisungen verwenden (z adws . B. ).

Testfälle

Anhalten:

.

v>
>^

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

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

Nicht haltend:

>..v
^..<

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

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

Das ist , also gewinnt das kürzeste Programm (in Bytes).

Esolanging Fruit
quelle
Was ist mit 아희 (Aheui) ?
JungHwan Min
Einige Testfälle, bei denen nicht jeder Pfeil getroffen wird, wären gut.
9.
Turing hat bewiesen, dass das Halting-Problem für keine Turing-Complete-Sprache lösbar ist, also musste ich mir eine Fälschung ausdenken, die nicht Turing-complete war. Eine Sprache, die immer irgendwann aufhört, ist nicht vollständig.
Esolanging Fruit
1
Wir haben auch keine Beispiele, bei denen der Pfad eine Nicht-90-Grad-Kurve wie >..>.oder macht ><.
9.
2
@PyRulez Weil ich wollte, dass die Verarbeitung von Richtungsbewegungen Teil der Herausforderung ist.
Esolanging Fruit

Antworten:

4

ES6 (JavaScript), 111101 Bytes

BEARBEITEN: Die Ausgabewerte wurden in " wahr" und " falsch" anstatt in " y" und " falsch" geändert N , um weitere 10 Byte zu sparen

Golf gespielt

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

Prüfung

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

Beispielausgabe

#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 !
Zeppelin
quelle
Sie können nicht nur verwenden Yund Nals Ausgabe wie in JavaScript sind sie beide wahr .
21.
3

Python 2 , 116 105 Bytes

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

Probieren Sie es online!

Die Herausforderung ist alt, aber ich dachte, da dies das kürzeste Python ist, werde ich es veröffentlichen. Die Eingabe ist eine Liste von Zeichenfolgen, die verwendeten Zeichen sind jedoch ungewöhnlich.

> G
< B
v C
^ F
. L

Zum Beispiel wird das dritte Beispiel zum Anhalten zu ['LLLLCLLLL', 'LLLLGLLLC', 'LFLLBLLLL', 'LLLLLLLCB', 'LLLLLLLCL', 'LLLLFLLBL']. Die Ausgabe erfolgt über den Exit-Code, 0 (Erfolg) für das Nicht-Anhalten und 1 (Fehler) für das Anhalten. Alle Tipps oder Tricks geschätzt.

nedla2004
quelle
2

Befunge-98 (PyFunge) , 217 209 200 Bytes

#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 ^ @.!;>:'.-#;_

Probieren Sie es online!

Ein befinge haltendes Problem braucht eine befunge Lösung. Gibt 0 für wahr und 1 für falsch zurück. Setzt die Eingabe ab 1,15 in das Raster und bewegt sich dann nach oben, wobei die Pfeile durch Nullen ersetzt werden. Sobald wir eine Null erreicht haben, wissen wir, dass es Schleifen gibt. Alles andere als> <^ v. und Null wird in Betracht gezogen, um das Programm anzuhalten. Dies schließt die Grenze der Leerzeichen ein, die wir um das Programm herum erhalten, indem wir es leicht versetzt auf das Raster setzen.

Ein einfacher Weg, um ein paar Bissen abzukratzen, wäre die Verwendung von Zahlen anstelle von> <^ v. aber ich glaube nicht, dass es sich lohnt.

David
quelle
A befinge halting problem needs a befunge solution.Genau. +1
Draco18s
1

Turtlèd , 146 Bytes

!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],

Dieses Programm verwendet E / A anders: Bitte schließen Sie jede Zeile mit einem Leerzeichen ab, einschließlich des letzten. Turtlèd mag keine Zeilenumbrüche, da ein Raster für die zweite Dimension der Zeichen verwendet wird.

Probieren Sie es online!

0 für Schleifen für immer, 1 für Pausen.

Allgemeine Erklärung:

Es schreibt die Eingabe in das Raster und folgt dann tatsächlich dem Pfad, den die Pfeile um das Raster legen. Dabei wird jeder Pfeil durch ein * ersetzt und die Richtung in der Zeichenvariable gespeichert. Wenn das Programm auf einen Pfeil (*) stößt, den es zuvor getroffen hat, wird es nicht gestoppt. Setzen Sie daher das Zeichen var auf 0, und beenden Sie die Schleife. Andernfalls wird das Ende des Gitters erreicht und die Schleife verlassen. Es wird das Zeichen var geschrieben. Wenn es das Ende des Rasters erreicht, verwendet es die in der char-Variable gespeicherte Richtung, um zum Raster zurückzukehren, und setzt die char-Variable 1für Pausen auf. Wenn das Zeichen var tatsächlich 0 war, keine Richtung, muss es nicht zurückgegeben werden, da es noch vorhanden ist, und setzt es zurück auf 0. Es löscht das Raster und schreibt dann die Zeichenvariable 1für Unterbrechungen 0.

Zerstörbare Zitrone
quelle
1

JavaScript (ES6), 158 127 Byte

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

Nimmt die Eingabe als zweidimensionales Zeichenarray und gibt sie truezum Anhalten und falsefür eine Endlosschleife zurück. Arbeitet, indem besuchte Richtungszeichen auf ~s gesetzt werden, während sie rekursiv durchlaufen werden. Bearbeiten: Speichert 31 Bytes, indem mein Richtungsvektor vor der Rekursion aktualisiert wird.

Durch den Missbrauch der Anweisungszeichen ( 1=^ 4=< 5=. 6=> 9=v) kann ich auf 101 Bytes reduzieren :

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
Neil
quelle
> Nimmt die Eingabe als zweidimensionales Zeichenfeld an. Ist eine anders formatierte Eingabe zulässig? (Wenn Sie von einer flachen Zeichenfolge zu einem Array wechseln, benötigen Sie auch Bytes).
Zeppelin
@zeppelin Ich glaube, dass das erlaubt ist. Siehe zum Beispiel meta.codegolf.stackexchange.com/q/2214/17602 .
Neil
ReferenceError: f ist nicht definiert
14m2
@ l4m2 Bah, ich habe es wieder getan, ich habe die f=in die Byteanzahl aufgenommen, aber nicht den Code ...
Neil
1

SmileBASIC, 158 145 Bytes

Wenn derselbe Pfeil mehr als einmal vorkommt, wird das Programm niemals angehalten. Wenn der Befehlszeiger einen Pfeil übergibt, wird er durch ein anderes Symbol ersetzt, wodurch die Funktion bei erneutem Erreichen den Wert 0 zurückgibt. Wenn die IP-Adresse überschritten wird, wird 1 zurückgegeben.

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

Nimmt Eingaben als ein Array von Zeichenfolgen. <any non-digit chracter>, 1, 2, 3, 4= ., >, <, v,^

12Me21
quelle
0

Python 2, 182 Bytes

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

Nimmt ein String-Array als Eingabe. Ich muss das mehr Golf spielen, aber jetzt ist es Zeit, über die Wahlen nachzudenken.

Ungolfed:

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
Daniel
quelle
hey, was wäre, wenn Sie den Hauptteil aus dem Versuch herausgenommen und nur c = m [y] [x] in einen Versuch eingesetzt hätten und ausnahmen? Dies würde es Ihnen auch ermöglichen, break durch 1/0 zu ersetzen und Einrückungen zu reduzieren.
Destructible Lemon
1
[-1,1][d=='v'] -> 2*(d>'>')-1und [-1,1][d=='>'] -> 2*(d>'<')-1speichern Sie insgesamt 6 Bytes.
Kade
Falsche Antwort für["<>"]
feersum
0

Clojure, 143 Bytes

#((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))

Eine Funktion mit 4 Zustandsargumenten: Position p, Geschwindigkeit v, Schrittindex iund Größe einer Zeile s. Kehrt zurück1 wenn wir die Grenzen nicht in 10 ^ 9 Schritten nilüberschritten haben. Wie viele Schritte müssen wir tatsächlich überprüfen, um sicherzugehen (count %)? Ich denke, es ist mehr als das, da derselbe NOP horizontal und vertikal durchlaufen werden kann.

Kann wie folgt aufgerufen werden (nimmt normale Strings als Argumente und gibt getzurück, nilwenn sie außerhalb der Grenzen liegen):

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

Zustandsübergänge (+1, -1, + s, -s) werden im Wörterbuch codiert {\> 1\< -1\^(- s)\. v\v s}.

NikoNyrh
quelle
Das Vierfache der Anzahl der Rasterzeichen sollte ausreichen: Wenn der Zeiger mit derselben Eingangsrichtung auf dasselbe Zeichen zurückkehrt, befindet er sich in einer Endlosschleife.
Greg Martin
0

Python 2/3, 201 192 Bytes

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

Probieren Sie es online!

Gibt die richtige Antwort für ["<>"]

Ceilingcat
quelle
Ich glaube, Sie können mehrere Bytes sparen, indem Sie von einer Funktion zu einem vollständigen Programm wechseln. Sie können ersetzen def f(x):mit x=input()mit 0 Byte Differenz, dann die zusätzliche Vertiefung entfernen (-8 Bytes), dann ersetzen return xmit exit(x)(erlaubt pro Meta - Konsens ), für weitere 2 Byte. Wie auch immer, schöne Lösung!
Amphibological
0

Java, 477

Ich weiß, dass dies nicht gewinnt, n = und wahrscheinlich mehr Golf gespielt werden kann, aber es implementiert eine ähnliche Methode wie die anderen Antworten, aber diese verwendet Hashmap, um Lookups durchzuführen. Die Eingabe verwendet die Symbole> <^ v und alles andere als das für die No-Op. Die Eingabe erfolgt über Argumente.

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

Erklärung folgt in Kürze!

KrystosTheOverlord
quelle
Eine kleine Sache: Sie ändern können , String a[]um String[]aund lassen Sie den Raum.
Esolanging Fruit
Sie können es auch varan vielen Orten verwenden, wenn Sie Java 10 verwenden.
Esolanging Fruit
410 Bytes
Ceilingcat