Memecahkan Masalah Pemutusan untuk Befinge

29

Mari kita mendefinisikan sederhana bahasa 2D, yang kami akan memberikan nama sangat asli befinge . Befinge memiliki 5 instruksi:

  • <>^v, seperti pada kebanyakan esolangs 2D, arahkan pointer instruksi ke arah masing-masing.
  • . adalah no-op.

Penunjuk instruksi dimulai di sudut kiri atas ke kanan. Jika penunjuk instruksi mencapai keunggulan, program berhenti. Setiap program Befinge jelas akan berhenti atau masuk ke loop tak terbatas yang tidak melakukan apa-apa. Berikut ini dua contoh:

Berhenti:

>.v
..<

Non-Berhenti:

>....v
..v..<
..>v..
^..<..

Masalah penghentian tidak bisa dipecahkan untuk bahasa Turing-lengkap, tetapi untuk yang ini. Tugas Anda adalah menulis sebuah program (atau fungsi) yang mengambil input string yang mewakili program befinge dan mengembalikan nilai true atau falsey tergantung pada apakah itu berhenti atau tidak.

  • Anda dapat mengasumsikan bahwa input hanya akan terdiri dari karakter-karakter ini dan akan diisi dengan spasi untuk membentuk persegi panjang.
  • Anda dapat menggunakan seperangkat lima karakter untuk instruksi (misalnya adws ).

Uji Kasus

Berhenti:

.

v>
>^

....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.

v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<

Non-Berhenti:

>..v
^..<

>v<
v<.
>v.
v<.
>.^

>.>.>.v
.><.<.<

Ini adalah , jadi program terpendek (dalam byte) menang.

Buah Esolanging
sumber
Bagaimana dengan 아희 (Aheui) ?
JungHwan Min
Beberapa uji kasus di mana tidak setiap panah dipukul akan bagus.
xnor
Turing membuktikan bahwa masalah Penghentian tidak dapat dipecahkan untuk bahasa Lengkap Turing, jadi saya harus membuat yang palsu yang bukan Turing lengkap. Bahasa yang pada akhirnya akan selalu berhenti adalah Turing tidak lengkap.
Buah Esolanging
1
Kami juga tidak memiliki contoh di mana jalurnya berbelok seperti >..>.atau 90 derajat ><.
xnor
2
@PyRulez Karena saya ingin memproses gerakan terarah menjadi bagian dari tantangan.
Buah Esolanging

Jawaban:

4

ES6 (JavaScript), 111, 101 byte

EDIT: mengubah nilai output menjadi true dan false , bukannya Y dan N , untuk memotong 10 byte lebih banyak

Golf

F=(I,M=[...I],c=0,i)=>(i={j:v=I.search`\n`+1,k:-v,h:-1,l:1,q:i,0:0}[M[c]])?F(I,M,c+i+(M[c]=0),i):i!=0

Uji

F=(I,M=[...I],c=0,i)=>(i={j:v=I.search`\n`+1,k:-v,h:-1,l:1,q:i,0:0}[M[c]])?F(I,M,c+i+(M[c]=0),i):i!=0  

//Alphabet Map
tr={
'<':'h',
'>':'l',
'^':'k',
'v':'j',
'.':'q',
'\n':'\n'
};

//Test
T=(I,A)=>{
console.log({"Y":"#Halting","N":"#Non-Halting"}[A]);
console.log("I=\n",I,"\nF(I)=",O=F([...I].map(s=>tr[s]).join('')));
console.log('NY'[O*1] == A ? "OK !" : "NOT OK !");
}

//Halting
T(
`>.v
..<`
,'Y');

//Non-Halting
T(
`>....v
..v..<
..>v..
^..<..`
,'N');

//Halting
T(
`.`
,'Y')

//Halting
T(
`v>
>^`
,'Y');

//Halting
T(
`....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.`
,'Y');

//Halting
T(
`v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<`
,'Y');

//Non-Halting
T(
`>..v
^..<`
,'N');

//Non-Halting
T(
`>v<
v<.
>v.
v<.
>.^`
,'N');

//Non-Halting
T(
`>.>.>.v
.><.<.<`
,'N');

Output Sampel

#Halting
I=
>.v
..< 
F(I)= true
OK !    

#Non-Halting
I=
>....v
..v..<
..>v..
^..<.. 
F(I)= false
OK !

#Halting
I=
 . 
F(I)= true
OK !

#Halting
I=
v>
>^ 
F(I)= true
OK !

#Halting
I=
....v....
....>...v
.^..<....
.......v<
.......v.
....^..<. 
F(I)= true
OK !

#Halting
I=
v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^< 
F(I)= true
OK !

#Non-Halting
I=
>..v
^..< 
F(I)= false
OK !

#Non-Halting
I=
>v<
v<.
>v.
v<.
>.^ 
F(I)= false
OK !

#Non-Halting
I=
>.>.>.v
.><.<.< 
F(I)= false
OK !
zeppelin
sumber
Anda tidak bisa hanya menggunakan Ydan Nsebagai output seperti dalam JavaScript mereka berdua benar .
ბიმო
3

Python 2 , 116 105 byte

x=1
X=Y=y=0
H=[]
G=input()
while(X,Y,x,y)not in H:H+=[(X,Y,x,y)];C=ord(G[Y][X]);x=C%3-1;y=C%5-1;X+=x;Y+=y

Cobalah online!

Tantangannya sudah tua, tetapi saya pikir karena ini adalah Python terpendek, saya akan mempostingnya. Input adalah daftar string, tetapi karakter yang digunakan tidak biasa.

> G
< B
v C
^ F
. L

Misalnya, contoh penghentian ketiga berubah menjadi ['LLLLCLLLL', 'LLLLGLLLC', 'LFLLBLLLL', 'LLLLLLLCB', 'LLLLLLLCL', 'LLLLFLLBL']. Output adalah melalui kode keluar, 0 (berhasil) untuk tidak berhenti, dan 1 (kesalahan) untuk berhenti. Setiap tips atau trik dihargai.

nedla2004
sumber
2

Befunge-98 (PyFunge) , 217 209 200 byte

#v10dpf1dp12dp3dpk
 >#v~:a-#v_$10dp1dg1+1dp >
v  >10dp;>0dg1dgp0dg1+0dp^;f1dp
>0dg1dgg:'^-#v_n1-v
^<v01_v#!->':<
  <   >:'<-#v_01-0>   v
v^pd1+gd3gd1[:'v-#v_01>3dp2dpndg1dgp
>0dg2dg+0dp ^ @.!;>:'.-#;_

Cobalah online!

Masalah penghentian sementara waktu membutuhkan solusi befunge. Mengembalikan 0 untuk truey dan 1 untuk falsey. Letakkan input di grid mulai dari 1,15 dan kemudian bergerak di atas, mengganti panah dengan nol. Begitu kita mencapai nol, kita tahu itu loop. Apa pun selain> <^ v. dan nol dipertimbangkan untuk menghentikan program, yang mencakup batas ruang yang kita dapatkan di sekitar program dengan menempatkannya di grid sedikit diimbangi.

Satu cara mudah untuk mengurangi beberapa gigitan adalah dengan menggunakan angka alih-alih> <^ v. tapi saya tidak merasa itu sepadan.

David
sumber
A befinge halting problem needs a befunge solution.Tepat. +1
Draco18s
1

Turtlèd , 146 byte

!u[*.[ r+.]l[ l]dr_+]#*#[ u]d[ (.r)(>.r{.r}@>)(v.d{.d}@v)(<.l{.l}@<)(^.u{.u}@^)(*@0' )],@1(0@0)(v' d)(<' r)(>' l)(^' d)[ u]d[ l]r[ [ r]l[ ' l]dr],

Program ini menggunakan I / O secara berbeda: silakan akhiri setiap baris dengan spasi, termasuk yang terakhir. Turtlèd tidak suka baris baru, karena menggunakan kisi untuk dimensi karakter kedua.

Cobalah online!

0 untuk loop selamanya, 1 untuk stop.

Penjelasan umum:

Ia menulis input pada grid, lalu benar-benar mengikuti jalur yang dibuat panah di sekitar grid, mengganti setiap panah dengan * saat berjalan, juga menyimpan arah di char var. Jika bertemu dengan *, panah yang mengenai sebelumnya, program tidak akan berhenti, sehingga mengatur char var untuk 0, keluar dari loop. Jika tidak, itu akan mengenai ujung grid dan keluar dari loop. Ini akan menulis char var. Jika itu mengenai ujung grid, ia menggunakan arah yang disimpan di char var untuk kembali ke grid, dan mengatur char var ke 1, untuk berhenti. Jika char var sebenarnya 0, bukan arah, itu tidak perlu kembali, karena masih ada, dan itu mengaturnya kembali 0. Itu membersihkan grid, lalu menulis char var, 1untuk berhenti, yang lain 0.

Lemon dirusak
sumber
1

JavaScript (ES6), 158 127 byte

f=(a,x=0,y=0,d=1,e=0,c=a[y]&&a[y][x])=>c<'~'?(c>'.'&&(a[y][x]='~',d=(c=='>')-(c=='<'),e=(c=='v')-(c=='^')),f(a,x+d,y+e,d,e)):!c

Mengambil input sebagai array karakter dua dimensi dan mengembalikan trueuntuk penghentian dan falseuntuk loop tak terbatas. Bekerja dengan menyetel karakter arah yang dikunjungi ke ~s saat secara traverse melintasi mereka. Sunting: Disimpan 31 byte dengan memperbarui vektor arah saya sebelum berulang.

Menyalahgunakan karakter instruksi ( 1=^ 4=< 5=. 6=> 9=v) membawa saya ke 101 byte:

f=(a,x=0,y=0,d=1,e=0,c=a[y]&&a[y][x])=>+c?(c-5&&(a[y][x]='0',d=~-c%4,e=~-(c>>2)),f(a,x+d,y+e,d,e)):!c
Neil
sumber
> Mengambil input sebagai array karakter dua dimensi. Apakah input yang diformat berbeda diizinkan? (pergi dari string datar ke array jangan mengambil byte juga).
zeppelin
@zeppelin Keyakinan saya adalah bahwa ini diizinkan. Lihat meta.codegolf.stackexchange.com/q/2214/17602 misalnya.
Neil
ReferenceError: f tidak didefinisikan
l4m2
@ l4m2 Bah, saya sudah melakukannya lagi, saya sudah memasukkan f=dalam byte byte tetapi bukan kode ...
Neil
1

SmileBASIC, 158 145 byte

Jika panah yang sama ditemukan lebih dari sekali, program tidak akan pernah berhenti. Ketika penunjuk instruksi melewati panah, itu diganti dengan simbol yang berbeda, yang akan menyebabkan fungsi kembali 0 jika tercapai lagi. Jika IP melampaui batas, ia mengembalikan 1.

DEF H P@L
C=VAL(P[Y][X])IF C>8THEN?0RETURN
IF C THEN D=C-1P[Y][X]="9
X=X+!D-(D==1)Y=Y+(D==2)-(D>2)IF X+1&&Y+1&&Y-LEN(P)&&X-LEN(P[0])GOTO@L
?1
END

Mengambil input sebagai array string. <any non-digit chracter>, 1, 2, 3, 4= ., >, <, v,^

12Me21
sumber
0

Python 2, 182 byte

m,v,d,x,y=input(),[],'>',0,0
try:
 while 1:
  if[x,y]in v:print 0;break
  c=m[y][x]
  if c!='.':d=c;v+=[[x,y]]
  if d in'><':x+=[-1,1][d=='>']
  else:y+=[-1,1][d=='v']
except:print 1

Mengambil array string sebagai input. Saya harus bermain golf ini lebih banyak tetapi untuk sekarang saatnya menekankan pada pemilihan.

Tidak Terkumpul:

input = input()

visited = [  ] 

dir = ">"
x=0
y=0

try:
    while True:
        if[x,y]in visited:print False;break
        char=input[y][x]
        if char!=".":
            dir=char
            visited+=[[x,y]]

        if dir==">":
            x+=1
        if dir=="<":
            x-=1
        if dir=="v":
            y+=1
        if dir=="^":
            x-=1
except:
    print True
Daniel
sumber
hei, bagaimana jika Anda mengambil bagian utama dari percobaan, dan hanya menaruh c = m [y] [x] dalam percobaan dan kecuali? ini juga akan memungkinkan Anda untuk mengganti break dengan 1/0, serta mengurangi indentasi.
Destructible Lemon
1
[-1,1][d=='v'] -> 2*(d>'>')-1dan [-1,1][d=='>'] -> 2*(d>'<')-1simpan total 6 byte.
Kade
Jawaban salah untuk["<>"]
feersum
0

Clojure, 143 byte

#((fn[p v i s](if-let[v({\> 1\< -1\^(- s)\. v\v s}(get % p))](if(neg? i)1(recur(+ p v)v(dec i)s))))0 1 1e9(+(count(take-while(set"<>v^.")%))1))

Fungsi dengan 4 argumen negara: posisi p, kecepatan v, indeks langkah idan ukuran satu baris s. Kembali 1jika kita tidak keluar batas dalam 10 ^ 9 langkah dan nilsebaliknya. Sebenarnya berapa langkah yang perlu kita periksa untuk memastikan (count %),? Saya pikir ini lebih dari itu karena NOP yang sama dapat dilalui secara horizontal dan vertikal.

Dapat disebut seperti ini (mengambil string normal sebagai argumen, getkembali nilketika di luar batas):

(def f #( ... ))
(f ">....v\n..v..<\n..>v..\n^..<..")
(f "v>\n>^")
(f "....v....\n....>...v\n.^..<....\n.......v<\n.......v.\n....^..<.")

Transisi status (+1, -1, + s, -s) dikodekan dalam kamus {\> 1\< -1\^(- s)\. v\v s}.

NikoNyrh
sumber
4 kali jumlah karakter kotak harus cukup: jika pointer kembali ke karakter yang sama dengan arah masuk yang sama, maka itu dalam loop tak terbatas.
Greg Martin
0

Python 2/3, 201 192 byte

def f(x):
 X=Y=b=0;a=1;D={}
 while len(x)>Y>-1<X<len(x[Y]):
  try:
   a,b={'>':(1,0),'^':(0,-1),'<':(-1,0),'v':(0,1)}[x[Y][X]]
   if(X,Y)in D:return 0
  except:0
  D[X,Y]=0;X+=a;Y+=b
 return 1

Cobalah online!

Memberikan jawaban yang benar untuk ["<>"]

plafon
sumber
Saya percaya Anda dapat menyimpan beberapa byte dengan mengubah dari fungsi ke program penuh Anda dapat mengganti def f(x):dengan x=input()dengan perbedaan 0 byte, lalu menghapus lekukan ekstra (-8 byte), lalu ganti return xdengan exit(x)(diizinkan per konsensus meta ), untuk 2 byte lainnya. Bagaimanapun, solusi yang bagus!
Amfibologis
0

Jawa, 477

Saya tahu ini bukan kemenangan, n = dan mungkin bisa lebih banyak golf, tetapi menerapkan metode yang sama seperti apa yang digunakan jawaban lain, tetapi yang ini menggunakan hashmap untuk melakukan pencarian. Input menggunakan simbol> <^ v dan apa pun selain itu untuk no op. Input datang melalui args.

TERLENGKAP

import java.util.*;interface B{static void main(String[]a){HashMap<String,Byte>h=new HashMap<>();int x,y=0;for(String s:a){x=0;for(char c:s.toCharArray()){if("><^v".indexOf(c)>-1)h.put(x+","+y,(byte)c);x++;}y++;}x=0;y=0;int d=0;int D=0;while(x>-1&&x<a[0].length()&&y<a.length&&y>-1){Byte v=h.get(x+","+y);if(v!=null){if(v==0){System.out.print(0);return;}d=(v<85)?"<>".indexOf(v)*2-1:0;D=(v>84)?"^v".indexOf(v)*2-1:0;}h.replace(x+","+y,(byte)0);x+=d;y+=D;}System.out.print(1);}}

UNGOLFED

import java.util. *;

interface B{
    static void main(String a[]) {
        HashMap<String, Byte> h = new HashMap<>();
        int x, y = 0;
        for(String s : a) {
            x = 0;
            for(char c : s.toCharArray()) {
                if ("><^v".indexOf(c) > -1) h.put(x + "," + y, (byte) c);
                x++;
            }
            y++;
        }
        x = 0;
        y = 0;
        int d = 0;
        int D = 0;
        while(x > -1 && x < a[0].length() && y < a.length && y > -1) {
            Byte v = h.get(x + "," + y);
            if(v != null) {
                if(v == 0) {System.out.print(0); return;}
                d = (v < 85) ? "<>".indexOf(v)*2-1 : 0;
                D = (v > 84) ? "^v".indexOf(v)*2-1 : 0;
            }
            h.replace(x + "," + y, (byte) 0);
            x += d;
            y += D;
        }
        System.out.print(1);
    }
}

Penjelasan segera hadir!

KrystosTheOverlord
sumber
Satu hal kecil: Anda dapat mengubah String a[]ke String[]adan menghilangkan ruang.
Buah Esolanging
Anda juga dapat menggunakan vardi banyak tempat jika Anda menggunakan Java 10.
Esolanging Fruit
410 byte
ceilingcat