In the spirit of Solve the Halting Problem for Befinge, let's define another 2D language called Modilar SNISP. Modilar SNISP has the following six instructions:
\
directs the instruction pointer as follows:- if approached from the top, go right;
- if approached from the right, go up;
- if approached from the bottom, go left;
- if approached from the left, go down.
/
directs the instruction pointer as follows:- if approached from the top, go left;
- if approached from the left, go up;
- if approached from the bottom, go right;
- if approached from the right, go down.
!
skips over the next instruction.@
pushes the IP location and direction onto the call stack.#
pops an IP location and direction from the call stack and restores them, then skips over the next instruction. If the call stack is empty, execution halts..
does nothing.
The instruction pointer starts at the top left corner going right. If it ever leaves the playfield, execution halts.
Modilar SNISP cannot be more powerful than a PDA, because its only source of unbounded storage is a stack (the call stack) with a finite alphabet (the set of all IP (location, direction) pairs). The halting problem is decidable for PDAs, so this challenge should always be possible.
The Challenge
Your goal is to write a program that takes a matrix of characters representing a Modilar SNISP program and returns one of two distinct outputs depending on whether it halts or not.
This is code-golf, so the shortest valid program (measured in bytes) wins.
Specifications
- The way you take a matrix of character is flexible: a newline-separated string, array of strings, array of arrays of characters, 2d array of characters, flat array of characters with an integer representing width, etc. are all acceptable. The test cases opt for the first of those choices.
- You can assume that the input matrix will be rectangular (so you don't have to pad short rows) and will be of nonzero length and width.
- You can choose any two distinct outputs, not just truthy/falsy.
- You can assume that the input matrix will consist only of valid commands (
\
,/
,!
,@
,#
, and.
). - When a command is said to "skip the next instruction," you can assume that there will be a next instruction to skip. In particular, it will never be encountered in circumstances where (1) it lies on the playfield's edge and (2) the IP is moving perpendicular to that edge, such that the "next instruction" after it would lie outside the playfield.
Test Cases
The following snippet can be used to test programs in the language. Note that it is slightly more permissive than the actual specification given here (e.g. it permits characters other than .
as 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>
The ungolfed form can be found here.
Halting
.
The smallest program possible. Goes out the right.
\\
\/
Winds around the program and goes out the top.
.\./.\
.\!/./
Goes in a loop. Winds through part of the track in two different directions.
@\!/#
.\@/#
Uses all six commands.
@.@.@.@.@.@.@.@.@.#
This program's execution time is exponential in the number of repetitions of @.
, but it still halts.
Non-Halting
!/\
.\/
I believe this is the shortest infinite loop.
@!\\#/@\!\
//@//.#./.
.\#.!\./\.
#.\!@!\@//
/..@.@\/#!
\.@.#.\/@.
This winds around the track, spawning stack frames occasionally, before eventually getting caught in a cycle infinitely generating stack frames. Not all commands are actually used.
.!/@.@.@.@.@.\
/.@.@.@.@.@.@/
\@.@.@.@.@.@.\
/.@.@.@.@.@.@/
.@\@.@.@.@.@.\
\.@.@.@.@.@.@/
Keeps creating stack frames, but none of them ever return.