W duchu Rozwiąż problem zatrzymania Befinge , zdefiniujmy inny język 2D o nazwie Modilar SNISP . Modilar SNISP ma następujące sześć instrukcji:
\kieruje wskaźnikiem instrukcji w następujący sposób:- jeśli podejdziesz od góry, idź w prawo;
- jeśli podejdziesz z prawej, idź w górę;
- jeśli podejdziesz od dołu, idź w lewo;
- jeśli podejdziesz od lewej, zejdź na dół.
/kieruje wskaźnikiem instrukcji w następujący sposób:- jeśli podejdziesz od góry, idź w lewo;
- jeśli podejdziesz od lewej, idź w górę;
- jeśli podejdziesz od dołu, idź w prawo;
- jeśli podejdziesz z prawej, zejdź na dół.
!pomija następną instrukcję.@wypycha lokalizację i kierunek IP na stos wywołań.#wyświetla lokalizację i kierunek adresu IP ze stosu wywołań i przywraca je, a następnie przeskakuje do następnej instrukcji. Jeśli stos wywołań jest pusty, wykonywanie zostaje zatrzymane..nic nie robi.
Wskaźnik instrukcji zaczyna się w lewym górnym rogu, po prawej stronie. Jeśli kiedykolwiek opuści boisko, egzekucja zostanie przerwana.
Modilar SNISP nie może być silniejszy niż PDA , ponieważ jego jedynym źródłem nieograniczonej pamięci jest stos (stos wywołań) ze skończonym alfabetem (zbiór wszystkich par IP (lokalizacja, kierunek)). Problem zatrzymania jest rozstrzygalny w przypadku urządzeń PDA , więc wyzwanie to powinno być zawsze możliwe.
Wyzwanie
Twoim celem jest napisanie programu, który pobiera macierz znaków reprezentujących program Modilar SNISP i zwraca jedno z dwóch różnych wyników w zależności od tego, czy się zatrzyma, czy nie.
To jest golf golfowy , więc wygrywa najkrótszy prawidłowy program (mierzony w bajtach ).
Dane techniczne
- Sposób, w jaki bierzesz macierz znaków, jest elastyczny: akceptowalny jest ciąg oddzielony znakiem nowej linii, tablica ciągów, tablica tablic znaków, tablica 2d znaków, płaska tablica znaków z liczbą całkowitą reprezentującą szerokość itp. Przypadki testowe wybierają pierwszą z tych opcji.
- Możesz założyć, że matryca wejściowa będzie prostokątna (więc nie będziesz musiał wypełniać krótkich wierszy) i będzie miała niezerową długość i szerokość.
- Możesz wybrać dowolne dwa różne wyniki, nie tylko prawda / fałsz.
- Można założyć, że macierz wejściowa będzie składać się jedynie z ważnych poleceń (
\,/,!,@,#, i.). - Kiedy powie się polecenie „pomiń następną instrukcję”, możesz założyć, że będzie następna instrukcja do pominięcia. W szczególności nigdy go nie spotka się w okolicznościach, w których (1) leży na krawędzi boiska i (2) IP porusza się prostopadle do tej krawędzi, tak że „następna instrukcja” po nim leżałaby poza boiskiem.
Przypadki testowe
Poniższy fragment kodu można wykorzystać do testowania programów w języku. Zauważ, że jest to nieco bardziej liberalne niż rzeczywista specyfikacja podana tutaj (np. Dopuszcza znaki inne niż .brak operacji).
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>Niegolfowaną formę można znaleźć tutaj .
Postojowy
.
Najmniejszy możliwy program. Idzie dobrze.
\\
\/
Kręci się wokół programu i wychodzi na szczyt.
.\./.\
.\!/./
Idzie w pętli. Wiatry przechodzą przez część toru w dwóch różnych kierunkach.
@\!/#
.\@/#
Używa wszystkich sześciu poleceń.
@.@.@.@.@.@.@.@.@.#
Czas wykonywania tego programu jest wykładniczy pod względem liczby powtórzeń @., ale nadal się zatrzymuje.
Nie zatrzymujący się
!/\
.\/
Uważam, że jest to najkrótsza nieskończona pętla.
@!\\#/@\!\
//@//.#./.
.\#.!\./\.
#.\!@!\@//
/..@.@\/#!
\.@.#.\/@.
To owija się wokół toru, od czasu do czasu spawnując ramki stosu, zanim ostatecznie zostanie złapany w cyklu nieskończenie generującym ramki stosu. Nie wszystkie polecenia są faktycznie używane.
.!/@.@.@.@.@.\
/.@.@.@.@.@.@/
\@.@.@.@.@.@.\
/.@.@.@.@.@.@/
.@\@.@.@.@.@.\
\.@.@.@.@.@.@/
Ciągle tworzy ramki stosu, ale żadna z nich nigdy nie powraca.