Dans l'esprit de Solve the Halting Problem for Befinge , définissons un autre langage 2D appelé Modilar SNISP . Modilar SNISP contient les six instructions suivantes:

• \ dirige le pointeur d'instruction comme suit:
  • si approché par le haut, allez à droite;
  • si approché par la droite, montez;
  • si approché par le bas, allez à gauche;
  • si approché par la gauche, descendez.
• / dirige le pointeur d'instruction comme suit:
  • si approché par le haut, allez à gauche;
  • si approché par la gauche, montez;
  • si approché par le bas, allez à droite;
  • si approché par la droite, descendez.
• ! saute l'instruction suivante.
• @ pousse l'emplacement et la direction IP sur la pile d'appels.
• #affiche un emplacement IP et une direction à partir de la pile d'appels et les restaure, puis ignore l'instruction suivante. Si la pile d'appels est vide, l'exécution s'arrête.
• . ne fait rien.

Le pointeur d'instructions commence dans le coin supérieur gauche en allant vers la droite. S'il quitte le terrain de jeu, l'exécution s'arrête.

Modilar SNISP ne peut pas être plus puissant qu'un PDA , car sa seule source de stockage illimité est une pile (la pile des appels) avec un alphabet fini (l'ensemble de toutes les paires IP (emplacement, direction)). Le problème d'arrêt est décidable pour les PDA , donc ce défi devrait toujours être possible.

Le défi

Votre objectif est d'écrire un programme qui prend une matrice de caractères représentant un programme SNISP Modilar et renvoie l'une des deux sorties distinctes selon qu'il s'arrête ou non.

Il s'agit de code-golf , donc le programme valide le plus court (mesuré en octets ) l'emporte.

Caractéristiques

• La façon dont vous prenez une matrice de caractères est flexible: une chaîne séparée par des sauts de ligne, un tableau de chaînes, un tableau de tableaux de caractères, un tableau 2D de caractères, un tableau plat de caractères avec un entier représentant la largeur, etc. sont tous acceptables. Les cas de test optent pour le premier de ces choix.
• Vous pouvez supposer que la matrice d'entrée sera rectangulaire (vous n'aurez donc pas à remplir de lignes courtes) et qu'elle aura une longueur et une largeur différentes de zéro.
• Vous pouvez choisir deux sorties distinctes, pas seulement véridique / falsifiée.
• On peut supposer que la matrice d'entrée se compose uniquement de commandes valides ( \, /, !, @, #, et .).
• Lorsqu'une commande dit "sauter la prochaine instruction", vous pouvez supposer qu'il y aura une prochaine instruction à sauter. En particulier, il ne sera jamais rencontré dans des circonstances où (1) il se trouve sur le bord du terrain de jeu et (2) l'IP se déplace perpendiculairement à ce bord, de sorte que la "prochaine instruction" après qu'il se trouverait en dehors du terrain de jeu.

Cas de test

L'extrait de code suivant peut être utilisé pour tester des programmes dans la langue. Notez qu'il est légèrement plus permissif que la spécification réelle donnée ici (par exemple, il autorise les caractères autres que .non-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 forme non golfée peut être trouvée ici .

Arrêt

.

Le plus petit programme possible. Sort par la droite.

\\
\/

Enroule le programme et sort par le haut.

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

Va en boucle. Enroule une partie de la piste dans deux directions différentes.

@\!/#
.\@/#

Utilise les six commandes.

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

Le temps d'exécution de ce programme est exponentiel dans le nombre de répétitions de @., mais il s'arrête toujours.

Sans arrêt

!/\
.\/

Je pense que c'est la boucle infinie la plus courte.

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

Cela serpente autour de la piste, engendrant des cadres de pile de temps en temps, avant de se retrouver finalement pris dans un cycle générant des cadres de pile à l'infini. Toutes les commandes ne sont pas réellement utilisées.

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

Continue de créer des cadres de pile, mais aucun d'eux ne revient jamais.

Python 3 , 639 octets 630 octets 593 octets

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

Essayez-le en ligne!

J'ai l'impression que c'est plus une source minifiée que le golf ... Je suis sûr qu'il y a une meilleure façon d'y arriver.

Le programme fonctionne comme un interprète complet pour la langue. Il s'arrête soit lorsque:

1. Nous quittons le programme
2. Nous détectons que nous sommes dans une boucle.

La détection de boucle est quelque peu naïve (et lourde en mémoire). Avant d'évaluer chaque mouvement, nous mettons en cache notre direction, position et pile actuelles. Si nous voyons que nous sommes arrivés à une position dans laquelle nous nous sommes déjà rendus, en déplaçant la même direction, et que notre pile actuelle est un super ensemble d'une pile précédente à cette position + direction, alors nous savons que nous sommes dans une boucle et la pile grandit (ou reste constante).

Edit 1 - Merci à Herman L pour avoir coupé "pass". Coupez également "True".

Edit 2 - Lambda-ified certaines fonctions. Nombre de retours réduit. Renvoie "True" pour la terminaison et "False" pour la non-terminaison. Exploité la classe O existante en tant qu'objet de suivi, éliminant ainsi le besoin d'une classe N.

JavaScript (ES6), 258 254 octets

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

Attend un programme non vide comme un tableau de chaînes, où chaque élément représente une ligne de Modilar SNISP. Sorties 1si le programme donné s'arrête, et 0sinon.

Même logique que la réponse de @ machina.widmo . Quelques tentatives infructueuses de méthodes alternatives m'ont amené à conclure qu'elles produiraient de toute façon un code plus long!

Essayez-le en ligne!

Explication

Semblable à l'autre réponse, cette fonction se termine avec:

• 1 si le programme s'arrête (par exemple, l'IP quitte la grille ou une pile vide est sautée)
• 0si l'IP atteint une position qu'il a déjà visitée, se déplaçant dans la même direction et avec un surensemble de la pile présent lors de la visite précédente.

Pourquoi la même direction?

 1
!\/

Le programme ci-dessus s'arrête, mais atteint la même position (caractère 1), avec une pile identique, mais dans une direction différente.

Pourquoi un surensemble et pas seulement une taille de pile?

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

Cela s'arrête également et l'IP frappe le caractère 4 à partir d'une direction cohérente quatre fois, avec les états de pile suivants ( *indique le haut de la pile):

• taille = 2 [a, b] *
• taille = 1 [a] *
• taille = 1 [b] *
• taille = 0 [] *

Comment fonctionne l'interprète

Les instructions ( q) sont traduites en binary ( c) comme suit (avec tous les autres caractères, .ou autrement, servant de nops):

1 2 4 8 16
\ ! @ / #

La direction ( d) est représentée par un champ de bits:

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

Les miroirs ( \/) transforment la direction:

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

d/4 | 4*d&12

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

(d+5) % 10

De nouvelles directions transforment la position:

x += d>>2 - 1

y += d&3 - 1

Autres variables globales

• x, y: Position IP
• r: détient la valeur extraite de la pile
• k: falsification si vous sautez l'instruction suivante (par exemple de !#)
• s: pile
• v: cache les positions visitées, direction, instantané de la pile
• w: [x, y, d], la valeur stockée sur la pile et utilisée comme valeur de clé pourv
• e: faux si le programme ne s'arrête pas en raison d'une correspondance de cache

Non 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