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.

Python 3 , 639 bajtów 630 bajtów 593 bajtów

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

Wypróbuj online!

Wydaje mi się, że to bardziej zminimalizowane źródło niż golf ... Jestem pewien, że jest lepszy sposób, aby się tam dostać.

Program działa jako pełny tłumacz języka. Zatrzymuje się, gdy:

1. Opuszczamy program
2. Wykryliśmy, że jesteśmy w pętli.

Wykrywanie pętli jest nieco naiwne (a pamięć bardzo obciążona). Zanim ocenimy każdy ruch, zbuforujemy nasz bieżący kierunek, pozycję i stos. Jeśli widzimy, że doszliśmy do pozycji, w której byliśmy wcześniej, poruszając się w tym samym kierunku, a nasz obecny stos jest super zestawem poprzedniego stosu w tej pozycji + kierunku, to wiemy, że jesteśmy w pętli i stos albo rośnie (albo pozostaje na stałym poziomie).

Edycja 1 - Podziękowania dla Hermana L za wycięcie „przejścia”. Wytnij także „True”.

Edycja 2 - Lambda ified niektóre funkcje. Zmniejszona liczba zwrotów. Zwraca „Prawda” dla zakończenia i „Fałsz” dla braku zakończenia. Wykorzystano istniejącą klasę O jako obiekt śledzenia, eliminując potrzebę posiadania klasy N.

JavaScript (ES6), 258 254 bajtów

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

Oczekuje, że niepusty program jako tablica ciągów znaków, gdzie każdy element reprezentuje linię Modilar SNISP. Wyprowadza, 1jeśli dany program się zatrzyma, i 0inaczej.

Ta sama logika, co odpowiedź @ machina.widmo . Kilka nieudanych prób zastosowania alternatywnych metod doprowadziło mnie do wniosku, że i tak produkują dłuższy kod!

Wypróbuj online!

Wyjaśnienie

Podobnie jak w przypadku innej odpowiedzi, funkcja wychodzi z:

• 1 jeśli program się zatrzyma (np. IP zejdzie z siatki lub wyskoczy pusty stos)
• 0jeśli adres IP osiągnie pozycję , którą już odwiedził, poruszając się w tym samym kierunku i z nadzbiorem stosu obecnego podczas poprzedniej wizyty.

Dlaczego ten sam kierunek?

 1
!\/

Powyższy program zatrzymuje się, ale uderza w tę samą pozycję (znak 1), z identycznym stosem, ale z innego kierunku.

Dlaczego nadzbiór, a nie tylko rozmiar stosu?

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

To także zatrzymuje się, a IP trafia w postać 4 ze spójnego kierunku cztery razy, z następującymi stanami stosu ( *wskazuje górę stosu):

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

Jak działa tłumacz

Instrukcje ( q) są tłumaczone na binarne ( c) w następujący sposób (ze wszystkimi innymi znakami .lub w inny sposób, służąc jako nops):

1 2 4 8 16
\ ! @ / #

Kierunek ( d) jest reprezentowany jako pole bitowe:

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

Mirrors ( \/) przekształcają kierunek:

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

d/4 | 4*d&12

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

(d+5) % 10

Nowe kierunki przekształcają pozycję:

x += d>>2 - 1

y += d&3 - 1

Inne zmienne globalne

• x, y: Pozycja IP
• r: zawiera wartość wyskakującą ze stosu
• k: falsy, jeśli pomija się następną instrukcję (np. z !#)
• s: stos
• v: buforuje odwiedzone pozycje, kierunek, migawkę stosu
• w: [x, y, d], wartość przechowywana na stosie i używana jako wartość klucza dlav
• e: falsy, jeśli program nie zatrzymuje się z powodu dopasowania pamięci podręcznej

Nie golfił

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