En el espíritu de Resolver el problema de detención de Befinge , definamos otro lenguaje 2D llamado Modilar SNISP . Modilar SNISP tiene las siguientes seis instrucciones:

• \ dirige el puntero de instrucciones de la siguiente manera:
  • si te acercas desde la cima, ve a la derecha;
  • si se aproxima desde la derecha, sube;
  • si te acercas desde abajo, ve a la izquierda;
  • si te acercas por la izquierda, baja.
• / dirige el puntero de instrucciones de la siguiente manera:
  • si te acercas desde arriba, ve a la izquierda;
  • si se acerca desde la izquierda, sube;
  • si te acercas desde abajo, ve a la derecha;
  • si te acercas por la derecha, baja.
• ! salta la siguiente instrucción.
• @ empuja la ubicación y dirección IP en la pila de llamadas.
• #muestra una ubicación y dirección IP de la pila de llamadas y las restaura, luego salta la siguiente instrucción. Si la pila de llamadas está vacía, la ejecución se detiene.
• . no hace nada.

El puntero de instrucciones comienza en la esquina superior izquierda hacia la derecha. Si alguna vez sale del campo de juego, la ejecución se detiene.

El SNISP modular no puede ser más poderoso que un PDA , porque su única fuente de almacenamiento ilimitado es una pila (la pila de llamadas) con un alfabeto finito (el conjunto de todos los pares de IP (ubicación, dirección)). El problema de detención es decidible para las PDA , por lo que este desafío siempre debería ser posible.

El reto

Su objetivo es escribir un programa que tome una matriz de caracteres que represente un programa Modilar SNISP y devuelva una de las dos salidas distintas dependiendo de si se detiene o no.

Este es el código de golf , por lo que gana el programa válido más corto (medido en bytes ).

Especificaciones

• La forma en que toma una matriz de caracteres es flexible: se aceptan una cadena separada por una nueva línea, una matriz de cadenas, una matriz de matrices de caracteres, una matriz 2D de caracteres, una matriz plana de caracteres con un número entero que representa el ancho, etc. Los casos de prueba optan por la primera de esas opciones.
• Puede suponer que la matriz de entrada será rectangular (por lo que no tiene que rellenar filas cortas) y será de longitud y ancho distintos de cero.
• Puede elegir dos salidas distintas, no solo verdadero / falso.
• Se puede suponer que la matriz de entrada consistirá solamente de comandos válidos ( \, /, !, @, #, y .).
• Cuando se dice que un comando "omite la siguiente instrucción", puede suponer que habrá una próxima instrucción que omitir. En particular, nunca se encontrará en circunstancias en las que (1) se encuentre en el borde del campo de juego y (2) la IP se mueva perpendicular a ese borde, de modo que la "siguiente instrucción" después de que se encuentre fuera del campo de juego.

Casos de prueba

El siguiente fragmento se puede utilizar para probar programas en el idioma. Tenga en cuenta que es un poco más permisivo que la especificación real dada aquí (por ejemplo, permite caracteres que .no sean como no-ops).

function htmlEscape(t){let i=document.createElement("span");return i.innerText=t,i.innerHTML}function tick(){snisp.tick(),snisp.update()}function run(){runButton.style.display="none",stopButton.style.display="",code.style.display="none",executionArea.style.display="",snisp.initialize(),intervalId=setInterval(tick,INTERVAL_MS)}function stop(){runButton.style.display="",stopButton.style.display="none",code.style.display="",executionArea.style.display="none",clearInterval(intervalId)}let TICKS_PER_SECOND=5,INTERVAL_MS=1e3/TICKS_PER_SECOND,runButton=document.getElementById("run-button"),stopButton=document.getElementById("stop-button"),code=document.getElementById("code"),executionArea=document.getElementById("execution-display"),intervalId,snisp={x:null,y:null,direction:null,callStack:null,stopped:null,playfield:null,padRows:function(){let t=Math.max(...this.playfield.map(t=>t.length));for(let i=0;i<this.playfield.length;i++)this.playfield[i]=this.playfield[i].padEnd(t,".")},initialize:function(){this.x=0,this.y=0,this.direction="right",this.callStack=[],this.stopped=!1,this.playfield=code.value.split("\n"),this.padRows(),this.update()},getCurrentChar:function(){let t=this.playfield[this.y];if(void 0!=t)return t[this.x]},backslashMirror:function(){let t={up:"left",right:"down",down:"right",left:"up"};this.direction=t[this.direction]},slashMirror:function(){let t={up:"right",right:"up",down:"left",left:"down"};this.direction=t[this.direction]},forward:function(){switch(this.direction){case"up":this.y-=1;break;case"down":this.y+=1;break;case"left":this.x-=1;break;case"right":this.x+=1;break;default:throw"direction is invalid"}},pushState:function(){this.callStack.push({x:this.x,y:this.y,direction:this.direction})},restoreState:function(){let t=this.callStack.pop();void 0!=t?(this.x=t.x,this.y=t.y,this.direction=t.direction):this.stopped=!0},tick:function(){if(this.stopped)return;let t=this.getCurrentChar();if(void 0!=t){switch(t){case"\\":this.backslashMirror();break;case"/":this.slashMirror();break;case"!":this.forward();break;case"@":this.pushState();break;case"#":this.restoreState(),this.forward()}this.forward()}else this.stopped=!0},generatePlayfieldHTML:function(t,i){let e=[];for(let n=0;n<this.playfield.length;n++){let s=[],l=this.playfield[n];for(let e=0;e<l.length;e++){let a=htmlEscape(l[e]);e==t&&n==i&&(a='<span class="highlight">'+a+"</span>"),s.push(a)}e.push(s.join(""))}return e.join("<br>")},update:function(){let t=[];for(let i=0;i<this.callStack.length;i++){let e=this.callStack[i];t.push(this.generatePlayfieldHTML(e.x,e.y))}t.push(this.generatePlayfieldHTML(this.x,this.y));let i=t.join("<br><br>");executionArea.innerHTML=i}};

#code{font-family:monospace;}#execution-display{font-family:monospace;white-space:pre;}.highlight{background-color:yellow;}

<b>Code:</b><br/><textarea id="code" width="300" height="300"></textarea><br/><button id="run-button" onclick="run()">Run</button><button id="stop-button" onclick="stop()" style="display: none;">Stop</button><br/><div id="execution-display"></div>

La forma no golfizada se puede encontrar aquí .

Vacilante

.

El programa más pequeño posible. Sale por la derecha.

\\
\/

Se enrolla alrededor del programa y sale por la parte superior.

.\./.\
.\!/./

Entra en un bucle. Vientos a través de parte de la pista en dos direcciones diferentes.

@\!/#
.\@/#

Utiliza los seis comandos.

@.@.@.@.@.@.@.@.@.#

El tiempo de ejecución de este programa es exponencial en el número de repeticiones de @., pero aún se detiene.

Sin parar

!/\
.\/

Creo que este es el bucle infinito más corto.

@!\\#/@\!\
//@//.#./.
.\#.!\./\.
#.\!@!\@//
/..@.@\/#!
\.@.#.\/@.

Esto se enrolla alrededor de la pista, generando cuadros de pila ocasionalmente, antes de quedar atrapado en un ciclo que genera infinitamente cuadros de pila. No todos los comandos se utilizan realmente.

.!/@.@.@.@.@.\
/.@.@.@.@.@.@/
\@.@.@.@.@.@.\
/.@.@.@.@.@.@/
.@\@.@.@.@.@.\
\.@.@.@.@.@.@/

Sigue creando marcos de pila, pero ninguno de ellos regresa.

Python 3 , 639 bytes 630 bytes 593 bytes

def e(I):
 m=[(0,-1),(0,1),(1,1),(1,-1)];a=lambda i:(tuple(i[0]),i[1]);b=lambda s,q:s.s==q.s and s.S&q.S==q.S
 class O():i=[[0,0],2];S=[];A={}
 def z():d=m[O.i[1]];O.i[0][d[0]]+=d[1]
 def y():O.i=O.S.pop();z()
 def x():O.i[1]=[3,2,1,0][O.i[1]]
 def w():O.i[1]=[2,3,0,1][O.i[1]]
 def v():O.S+=[[O.i[0][:],O.i[1]]]
 while 1:
  p=O();p.s=a(O.i);p.S={a(i)for i in O.S};l=O.A.setdefault(p.s,[]);c=any((b(p,s)for s in l));l+=[p];e=O.i[0];d=not((0<=e[0]<len(I))and(0<=e[1]<len(I[0])))or((x,w,z,v,lambda:len(O.S)==0 or y(),lambda:0)["\\/!@#.".find(I[e[0]][e[1]])]()==1);z()
  if d!=c:return not c or d

Pruébalo en línea!

Siento que esto es más una fuente minificada que el golf ... Estoy seguro de que hay una mejor manera de llegar allí.

El programa funciona como un intérprete completo para el idioma. Se detiene cuando:

1. Salimos del programa
2. Detectamos que estamos en un bucle.

La detección de bucle es algo ingenua (y tiene mucha memoria). Antes de evaluar cada movimiento, almacenamos en caché nuestra Dirección, Posición y Pila actuales. Si vemos que hemos llegado a una posición en la que hemos estado antes, moviéndonos en la misma dirección, y nuestra pila actual es un superconjunto de una pila anterior en esta posición + dirección, entonces sabemos que estamos en un bucle y la pila está creciendo (o permaneciendo constante).

Edición 1 - Gracias a Herman L por cortar "pasar". También corte "True".

Edición 2 - Lambda-ified algunas funciones. Número reducido de devoluciones. Devuelve "Verdadero" para terminar y "Falso" para no terminar. Aprovechó la clase O existente como objeto de seguimiento, eliminando la necesidad de la clase N.

JavaScript (ES6), 258254 bytes

p=>(d=>{for(x=y=r=k=1,s=[],v={};w=[--x,--y,d],c=1<<"\\!@/#".indexOf(q=(p[y]||0)[x]),q&&r&&(e=v[w]?v[w].some(u=>!s.some(t=>u+0==t+0)):1);x+=d>>2,y+=d&3)v[w]=[...s],k=k?c&9?d=c&1?d/4|4*d&12:(d+5)%10:c&4?s.push(w):c&16?(r=s.pop())&&!([x,y,d]=r):c-2:1})(9)|e

Espera un programa no vacío como una matriz de cadenas, donde cada elemento representa una línea de Modilar SNISP. Salidas 1si el programa dado se detiene, y de lo 0contrario.

La misma lógica que la respuesta de @ machina.widmo . ¡Algunos intentos fallidos de métodos alternativos me llevaron a concluir que de todos modos producirían un código más largo!

Pruébalo en línea!

Explicación

Similar a la otra respuesta, esta función sale con:

• 1 si el programa se detiene (por ejemplo, la IP se mueve fuera de la cuadrícula o aparece una pila vacía)
• 0si la IP alcanza una posición que ya ha visitado, se mueve en la misma dirección y con un superconjunto de la pila presente en la visita anterior.

¿Por qué la misma dirección?

 1
!\/

El programa anterior se detiene, pero alcanza la misma posición (carácter 1), con una pila idéntica, pero desde una dirección diferente.

¿Por qué un superconjunto y no simplemente un tamaño de pila?

  ab4
!/@@.\
.\..#/

Esto también se detiene, y la IP golpea el carácter 4 desde una dirección constante cuatro veces, con los siguientes estados de pila ( *indica la parte superior de la pila):

• tamaño = 2 [a, b] *
• tamaño = 1 [a] *
• tamaño = 1 [b] *
• tamaño = 0 [] *

Cómo funciona el intérprete

Las instrucciones ( q) se traducen a binario ( c) de la siguiente manera (con todos los demás caracteres, .o de otro modo, sirviendo como nops):

1 2 4 8 16
\ ! @ / #

Dirección ( d) se representa como un campo de bits:

9 -> right : 1001
1 -> left  : 0001
6 -> down  : 0110
4 -> up    : 0100

Los espejos ( \/) transforman la dirección:

\: 6-> 9 9-> 6 4-> 1 1-> 4

d/4 | 4*d&12

/: 1-> 6 6-> 1 4-> 9 9-> 4

(d+5) % 10

Nuevas direcciones transforman la posición:

x += d>>2 - 1

y += d&3 - 1

Otras variables globales

• x, y: Posición IP
• r: mantiene el valor extraído de la pila
• k: falso si se salta la siguiente instrucción (por ejemplo, de !#)
• s: apilar
• v: cachés visitadas posiciones, dirección, instantánea de la pila
• w: [x, y, d], el valor almacenado en la pila y utilizado como valor clave parav
• e: falso si el programa no se detiene debido a una coincidencia de caché

Sin golf

p => (d => {                                                  // set initial direction and avoid a verbose `return` statement
    for (
        x = y = r = k = 1,
        s = [],
        v = {};
        w = [--x, --y, d],                                    // decrement positions early so that x,y 
                                                              // do not require a separate assignment to 0
        c = 1 << "\\!@/#".indexOf(q = (p[y]||0)[x]),          // taking an index of undefined produces an error; using 0 does not
        q && r && (
            e = v[w]
                ? v[w].some(u => !s.some(t => u+0 == t+0))    // in order to compare two arrays, must coerce to strings
                : 1
        );
        x += d>>2,
        y += d&3
    )
        v[w] = [...s],                         // clone stack
        k = k
            ?
                c&9                            // if \ or /
                    ? d = c&1
                        ? d/4 | 4*d&12
                        : (d+5) % 10
                : c&4                          // if @
                    ? s.push(w)
                : c&16                         // if #
                    ? (r = s.pop())
                        && !([x, y, d] = r)    // destructure value in stack if any exists
                : c-2                          // 0 if !
            : 1
})(9) | e