Dalam semangat Memecahkan Masalah Pemutusan untuk Befinge , mari kita mendefinisikan bahasa 2D lain yang disebut Modilar SNISP . Modilar SNISP memiliki enam instruksi berikut:

• \ mengarahkan penunjuk instruksi sebagai berikut:
  • jika didekati dari atas, ke kanan;
  • jika didekati dari kanan, naiklah;
  • jika didekati dari bawah, ke kiri;
  • jika didekati dari kiri, turunlah.
• / mengarahkan penunjuk instruksi sebagai berikut:
  • jika didekati dari atas, ke kiri;
  • jika didekati dari kiri, naik;
  • jika didekati dari bawah, ke kanan;
  • jika didekati dari kanan, turunlah.
• ! melompati instruksi selanjutnya.
• @ mendorong lokasi dan arah IP ke tumpukan panggilan.
• #memunculkan lokasi dan arah IP dari tumpukan panggilan dan mengembalikannya, lalu melompati instruksi selanjutnya. Jika tumpukan panggilan kosong, eksekusi terhenti.
• . tidak melakukan apa-apa.

Penunjuk instruksi dimulai di sudut kiri atas ke kanan. Jika itu pernah meninggalkan playfield, eksekusi terhenti.

SNSP Modilar tidak bisa lebih kuat dari PDA , karena satu-satunya sumber penyimpanan tidak terbatas adalah tumpukan (panggilan stack) dengan alfabet terbatas (himpunan semua pasangan IP (lokasi, arah) pasangan). Masalah penghentian adalah decidable untuk PDA , jadi tantangan ini harus selalu dimungkinkan.

Tantangan

Tujuan Anda adalah untuk menulis sebuah program yang mengambil matriks karakter yang mewakili program SNISP Modilar dan mengembalikan salah satu dari dua output yang berbeda tergantung pada apakah itu berhenti atau tidak.

Ini adalah kode-golf , sehingga program terpendek yang valid (diukur dalam byte ) menang.

Spesifikasi

• Cara Anda mengambil matriks karakter fleksibel: string yang dipisahkan baris baru, array string, array array karakter, array karakter 2d, array karakter datar dengan integer yang mewakili lebar, dll. Semuanya dapat diterima. Kasing uji memilih yang pertama dari pilihan itu.
• Anda dapat mengasumsikan bahwa matriks input akan berbentuk persegi panjang (jadi Anda tidak perlu mengisi baris pendek) dan akan memiliki panjang dan lebar yang tidak nol.
• Anda dapat memilih dua output berbeda, bukan hanya kebenaran / kepalsuan.
• Anda dapat mengasumsikan bahwa matriks input akan hanya terdiri dari perintah yang sah ( \, /, !, @, #, dan .).
• Ketika sebuah perintah dikatakan "lewati instruksi selanjutnya," Anda dapat mengasumsikan bahwa akan ada instruksi berikutnya untuk melewati. Secara khusus, itu tidak akan pernah ditemui dalam keadaan di mana (1) ia terletak di tepi playfield dan (2) IP bergerak tegak lurus ke tepi itu, sehingga "instruksi berikutnya" setelah itu akan berada di luar playfield.

Uji Kasus

Cuplikan berikut dapat digunakan untuk menguji program dalam bahasa. Perhatikan bahwa ini sedikit lebih permisif daripada spesifikasi sebenarnya yang diberikan di sini (mis. Itu memungkinkan karakter selain .sebagai 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>

Bentuk tanpa ungolf dapat ditemukan di sini .

Berhenti

.

Program sekecil mungkin. Keluar benar.

\\
\/

Angin di sekitar program dan keluar di atas.

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

Berputar. Angin melalui bagian trek dalam dua arah yang berbeda.

@\!/#
.\@/#

Menggunakan semua enam perintah.

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

Waktu pelaksanaan program ini eksponensial dalam jumlah pengulangan @., tetapi masih terhenti.

Non-Berhenti

!/\
.\/

Saya percaya ini adalah loop tak terbatas terpendek.

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

Ini berputar di sekitar trek, memunculkan frame stack sesekali, sebelum akhirnya terjebak dalam siklus yang menghasilkan frame stack secara tak terbatas. Tidak semua perintah benar-benar digunakan.

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

Terus membuat bingkai tumpukan, tetapi tidak ada yang kembali.

Python 3 , 639 byte, 630 byte, 593 byte

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

Cobalah online!

Saya merasa ini lebih merupakan sumber yang diperkecil daripada golf ... Saya yakin ada cara yang lebih baik untuk sampai ke sana.

Program berfungsi sebagai penerjemah penuh untuk bahasa tersebut. Itu berhenti baik ketika:

1. Kami keluar dari program
2. Kami mendeteksi bahwa kami berada dalam satu lingkaran.

Deteksi loop agak naif (dan memori banyak). Sebelum kami mengevaluasi setiap gerakan, kami menyimpan arah, Posisi, dan Stack kami saat ini. Jika kita melihat kita telah sampai pada posisi yang pernah kita kunjungi sebelumnya, bergerak ke arah yang sama, dan tumpukan kita saat ini adalah kumpulan super dari tumpukan sebelumnya pada posisi + arah ini, maka kita tahu bahwa kita berada dalam satu lingkaran dan tumpukan tumbuh (atau tetap konstan).

Sunting 1 - Terima kasih kepada Herman L untuk memotong "lulus". Potong juga "Benar".

Sunting 2 - Lambda-ified beberapa fungsi. Pengurangan jumlah pengembalian. Mengembalikan "Benar" untuk mengakhiri dan "Salah" untuk tidak mengakhiri. Memanfaatkan kelas O yang ada sebagai objek pelacakan, menghilangkan kebutuhan untuk kelas N.

JavaScript (ES6), 258 254 byte

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

Mengharapkan program yang tidak kosong sebagai array string, di mana setiap elemen mewakili garis Modilar SNISP. Keluaran 1jika program yang diberikan berhenti, dan 0sebaliknya.

Logika yang sama dengan jawaban @ machina.widmo . Beberapa upaya yang gagal pada metode alternatif membuat saya menyimpulkan bahwa mereka akan menghasilkan kode yang lebih lama!

Cobalah online!

Penjelasan

Mirip dengan jawaban lain, fungsi ini keluar dengan:

• 1 jika program berhenti (misalnya IP bergerak dari grid atau tumpukan kosong muncul)
• 0jika IP mencapai posisi yang telah dikunjungi, bergerak ke arah yang sama , dan dengan superset dari tumpukan yang ada di kunjungan sebelumnya.

Kenapa arahnya sama?

 1
!\/

Program di atas terhenti, tetapi mengenai posisi yang sama (karakter 1), dengan tumpukan yang sama, tetapi dari arah yang berbeda.

Mengapa superset dan tidak hanya menumpuk ukuran?

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

Ini juga berhenti, dan IP mengenai karakter 4 dari arah yang konsisten empat kali, dengan status tumpukan berikut ( *menunjukkan bagian atas tumpukan):

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

Bagaimana cara kerja penerjemah

Instruksi ( q) diterjemahkan ke dalam biner ( c) sebagai berikut (dengan semua karakter lain, .atau sebaliknya, berfungsi sebagai nops):

1 2 4 8 16
\ ! @ / #

Direction ( d) direpresentasikan sebagai bidang bit:

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

Mirror ( \/) mengubah arah:

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

d/4 | 4*d&12

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

(d+5) % 10

Arah baru mengubah posisi:

x += d>>2 - 1

y += d&3 - 1

Variabel global lainnya

• x, y: Posisi IP
• r: memegang nilai muncul dari tumpukan
• k: falsy jika melewatkan instruksi selanjutnya (misalnya dari !#)
• s: tumpukan
• v: cache posisi yang dikunjungi, arah, snapshot tumpukan
• w: [x, y, d], nilai yang disimpan di tumpukan dan digunakan sebagai nilai kunci untukv
• e: falsy jika program tidak berhenti karena kecocokan cache

Tidak disatukan

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