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 código de golf , por lo que gana el programa más corto (en bytes).
fuente
>..>.
o><
.Respuestas:
ES6 (JavaScript),
111101 bytesEDITAR: cambió los valores de salida a verdadero y falso , en lugar de Y y N , para reducir 10 bytes más
Golfed
Prueba
Salida de muestra
fuente
Y
yN
como salida como en JavaScript , ambos son verdaderos .Python 2 ,
116105bytesPrué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.
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.fuente
Befunge-98 (PyFunge) ,
217209200 bytesPrué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.
fuente
A befinge halting problem needs a befunge solution.
Precisamente. +1Turtlèd , 146 bytes
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
0
salir 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 en1
, 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 poner0
. Despeja la cuadrícula, luego escribe el char var,1
para detenerse, de lo contrario0
.fuente
JavaScript (Node.js) , 80 bytes
Pruébalo en línea!
JavaScript (Node.js) , 86 bytes
Pruébalo en línea!
fuente
JavaScript (ES6),
158127bytesToma la entrada como una matriz de caracteres bidimensionales y regresa
true
para detener yfalse
para 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:fuente
f=
de bytes pero no el código ...SmileBASIC,
158145 bytesSi 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.
Toma la entrada como una matriz de cadenas.
<any non-digit chracter>
,1
,2
,3
,4
=.
,>
,<
,v
,^
fuente
Python 2, 182 bytes
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:
fuente
[-1,1][d=='v'] -> 2*(d>'>')-1
y[-1,1][d=='>'] -> 2*(d>'<')-1
guardar un total de 6 bytes.["<>"]
Clojure, 143 bytes
Una función con 4 argumentos de estado: posición
p
, velocidadv
, índice de pasosi
y tamaño de una líneas
. Devuelve1
si no salimos de los límites en 10 ^ 9 pasos y de lonil
contrario. 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,
get
devuelvenil
cuando está fuera de límites):Las transiciones de estado (+1, -1, + s, -s) están codificadas en el diccionario
{\> 1\< -1\^(- s)\. v\v s}
.fuente
Python 2/3,
201192 bytesPruébalo en línea!
Da la respuesta correcta para
["<>"]
fuente
def f(x):
con unax=input()
diferencia de 0 bytes, luego eliminar la sangría adicional (-8 bytes), luego reemplazarreturn x
conexit(x)
(permitido por meta consenso ), para otros 2 bytes. De todos modos, buena solución!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
SIN GOLF
import java.util. *;
¡Explicación próximamente!
fuente
String a[]
aString[]a
y omitir el espacio.var
en muchos lugares si usa Java 10.