Resolver el problema de detención de Befinge

29

Vamos a definir un lenguaje sencillo 2D, que vamos a dar el nombre muy original, befinge . Befinge tiene 5 instrucciones:

  • <>^v, como en la mayoría de los esolangs 2D, redirija el puntero de instrucción en sus respectivas direcciones.
  • . es un no-op.

El puntero de instrucciones comienza en la esquina superior izquierda hacia la derecha. Si el puntero de instrucción llega a un borde, el programa se detiene. Cada programa Befinge obviamente se detendrá o entrará en un ciclo infinito que no hace nada. Aquí hay dos ejemplos:

Vacilante:

>.v
..<

Sin detenerse:

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

El problema de detención no se puede resolver para un lenguaje completo de Turing, pero sí para este. Su tarea es escribir un programa (o función) que tome como entrada una cadena que represente el programa befinge y devuelva un valor verdadero o falso dependiendo de si se detiene o no.

  • Puede suponer que la entrada consistirá solo en estos caracteres y se rellenará con espacios para formar un rectángulo.
  • Puede usar cualquier conjunto de cinco caracteres para las instrucciones (por ejemplo adws ).

Casos de prueba

Vacilante:

.

v>
>^

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

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

Sin detenerse:

>..v
^..<

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

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

Este es el , por lo que gana el programa más corto (en bytes).

Fruta Esolanging
fuente
¿Qué hay de 아희 (Aheui) ?
JungHwan Min
Algunos casos de prueba en los que no se golpea cada flecha serían buenos.
xnor
Turing demostró que el problema de Halting no se puede resolver para ningún lenguaje Turing-Complete, así que tuve que inventar uno falso que no estuviera completo. Un lenguaje que siempre se detendrá eventualmente no es Turing completo.
Esolanging Fruit
1
Tampoco tenemos ningún ejemplo en el que el camino realice un giro de no 90 grados como >..>.o ><.
xnor
2
@PyRulez Porque quería que el procesamiento del movimiento direccional fuera parte del desafío.
Esolanging Fruit

Respuestas:

4

ES6 (JavaScript), 111101 bytes

EDITAR: cambió los valores de salida a verdadero y falso , en lugar de Y y N , para reducir 10 bytes más

Golfed

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

Prueba

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

Salida de muestra

#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 !
zepelín
fuente
No puede simplemente usar Yy Ncomo salida como en JavaScript , ambos son verdaderos .
ბიმო
3

Python 2 , 116105 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

Pruébalo en línea!

El desafío es antiguo, pero pensé que, dado que este es el Python más corto, lo publicaré. La entrada es una lista de cadenas, pero los caracteres utilizados son inusuales.

> G
< B
v C
^ F
. L

Por ejemplo, el tercer ejemplo de detención se convierte en ['LLLLCLLLL', 'LLLLGLLLC', 'LFLLBLLLL', 'LLLLLLLCB', 'LLLLLLLCL', 'LLLLFLLBL']. La salida es a través del código de salida, 0 (éxito) para no detenerse y 1 (error) para detenerse. Cualquier consejo o truco apreciado.

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

Pruébalo en línea!

Un problema de detención de befinge necesita una solución previa. Devuelve 0 para la verdad y 1 para falsey. Pone la entrada en la cuadrícula a partir de 1,15 y luego se mueve en la parte superior, reemplazando las flechas con ceros. Tan pronto como lleguemos a cero, sabemos que se repite. Cualquier cosa además de> <^ v. y se considera cero para detener el programa, que incluye el borde de los espacios que obtenemos alrededor del programa al colocarlo en la cuadrícula ligeramente desplazado.

Una manera fácil de eliminar algunas picaduras sería usar números en lugar de> <^ v. pero no siento que valga la pena.

david
fuente
A befinge halting problem needs a befunge solution.Precisamente. +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],

Este programa toma E / S de manera diferente: finalice cada línea con un espacio, incluida la última. A Turtlèd no le gustan las nuevas líneas, ya que usa una cuadrícula para su segunda dimensión de caracteres.

Pruébalo en línea!

0 para bucles para siempre, 1 para paradas.

Explicación general:

Escribe la entrada en la cuadrícula, luego en realidad sigue el camino que hacen las flechas alrededor de la cuadrícula, reemplazando cada flecha con un * a medida que avanza, también guardando la dirección en el char var. Si encuentra un *, una flecha que golpeó antes, el programa no se detendrá, por lo que establece el char var para 0salir del bucle. De lo contrario, llegará al final de la cuadrícula y saldrá del bucle. Escribirá el char var. Si llega al final de la cuadrícula, usa la dirección almacenada en el char var para volver a la cuadrícula, y establece el char var en 1, para detenerse. Si el char var era realmente 0, no una dirección, no necesita volver, ya que todavía está allí, y lo vuelve a poner 0. Despeja la cuadrícula, luego escribe el char var, 1para detenerse, de lo contrario 0.

Limón Destructible
fuente
1

JavaScript (ES6), 158127 bytes

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

Toma la entrada como una matriz de caracteres bidimensionales y regresa truepara detener y falsepara un bucle infinito. Funciona configurando los caracteres de dirección visitados en ~s a medida que los atraviesa recursivamente. Editar: guardé 31 bytes actualizando mi vector de dirección antes de recurrir.

Abusar de los caracteres de instrucción ( 1=^ 4=< 5=. 6=> 9=v) me lleva a 101 bytes:

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
fuente
> Toma la entrada como una matriz de caracteres bidimensional ¿Se permite una entrada con formato diferente? (pasar de una cadena plana a una matriz también toma bytes).
zepelín
@zeppelin Creo que esto está permitido. Ver meta.codegolf.stackexchange.com/q/2214/17602 por ejemplo.
Neil
ReferenceError: f no está definido
l4m2
@ l4m2 Bah, lo he vuelto a hacer, he incluido el número f=de bytes pero no el código ...
Neil
1

SmileBASIC, 158 145 bytes

Si se encuentra la misma flecha más de una vez, el programa nunca se detendrá. Cuando el puntero de instrucción pasa una flecha, se reemplaza con un símbolo diferente, lo que hará que la función devuelva 0 si se alcanza nuevamente. Si la IP se sale de los límites, devuelve 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

Toma la entrada como una matriz de cadenas. <any non-digit chracter>, 1, 2, 3, 4= ., >, <, v,^

12Me21
fuente
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

Toma una matriz de cadenas como entrada. Tengo que jugar más al golf, pero por ahora es hora de estresarse por las elecciones.

Sin golf:

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
fuente
oye, ¿qué pasa si tomas la parte principal del intento y pones solo c = m [y] [x] en un intento y excepto? esto también le permitiría reemplazar el descanso con 1/0, así como reducir las sangrías.
Destructible Lemon
1
[-1,1][d=='v'] -> 2*(d>'>')-1y [-1,1][d=='>'] -> 2*(d>'<')-1guardar un total de 6 bytes.
Kade
Respuesta equivocada para["<>"]
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))

Una función con 4 argumentos de estado: posición p, velocidad v, índice de pasos iy tamaño de una línea s. Devuelve 1si no salimos de los límites en 10 ^ 9 pasos y de lo nilcontrario. En realidad, ¿cuántos pasos debemos verificar para estar seguros (count %)? Creo que es más que eso, ya que el mismo NOP puede atravesarse horizontal y verticalmente.

Se puede llamar así (toma cadenas normales como argumentos, getdevuelve nilcuando está fuera de límites):

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

Las transiciones de estado (+1, -1, + s, -s) están codificadas en el diccionario {\> 1\< -1\^(- s)\. v\v s}.

NikoNyrh
fuente
4 veces el número de caracteres de la cuadrícula debería ser suficiente: si el puntero vuelve al mismo carácter con la misma dirección entrante, entonces está en un bucle infinito.
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

Pruébalo en línea!

Da la respuesta correcta para ["<>"]

techo
fuente
Creo que puede guardar varios bytes cambiando de una función a un programa completo. Puede reemplazar def f(x):con una x=input()diferencia de 0 bytes, luego eliminar la sangría adicional (-8 bytes), luego reemplazar return xcon exit(x)(permitido por meta consenso ), para otros 2 bytes. De todos modos, buena solución!
Anfibológico
0

Java, 477

Sé que esto no está ganando, n = y probablemente se puede jugar más al golf, pero implica un método similar en cuanto a lo que usan las otras respuestas, pero este usa hashmap para realizar búsquedas. La entrada está usando los símbolos> <^ v y cualquier otra cosa que no sea para el no op. La entrada llega a través de args.

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

SIN GOLF

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

¡Explicación próximamente!

KrystosTheOverlord
fuente
Una pequeña cosa: se puede cambiar String a[]a String[]ay omitir el espacio.
Esolanging Fruit
También puede usarlo varen muchos lugares si usa Java 10.
Esolanging Fruit
410 bytes
ceilingcat