Verifikasi program Brainfuck

17

Namun masalah penguraian Brainfuck lain, tapi kali ini ... berbeda.

Anda bekerja di Infinite Monkeys Incorporated, perusahaan yang membuat program Brainfuck, untuk menyelesaikan berbagai masalah menarik (secara tidak sengaja, tidak kurang - setelah semua, perusahaan membuat program acak). Namun, tampaknya mesin Turing cepat Anda yang hanya menjalankan Brainfuck memiliki masalah kecil dan mahal dengan kesalahan sintaksis - membuat satu, dan komputer meledak. Ini mungkin cacat desain, tetapi tidak ada yang repot-repot menemukan mengapa itu terjadi.

Karena mesin Turing (terutama yang cepat) harganya mahal (bagaimanapun, mereka memiliki RAM tak terbatas yang biayanya), akan lebih baik untuk memastikan bahwa program tidak memiliki kesalahan sintaksis sebelum menjalankan kode. Perusahaan Anda akan menjalankan banyak kode, jadi verifikasi manual tidak akan berfungsi. Tulis program yang membaca STDIN untuk kode Brainfuck, dan keluar dengan status keluar yang diatur ke selain dari 0 (kesalahan) jika program memiliki kesalahan sintaksis (misalnya, ]adalah kesalahan sintaks, karena tidak ada yang cocok [). Keluar dengan status keluar diatur ke 0 jika program benar-benar baik-baik saja.

Pastikan program Anda memperhatikan kesalahan yang terjadi []. Anda tidak ingin komputer lain meledak, bukan? Oh, dan pastikan itu sesingkat mungkin - bos Anda membayar untuk program pendek (karena dia pikir itu cepat, atau sesuatu). Oh, dan Anda tidak perlu kode di Brainfuck (pada kenyataannya, Anda tidak bisa, karena Brainfuck tidak mendukung kode keluar) - kode Anda akan dijalankan pada komputer normal.

Jadi, seperti yang Anda lihat, tugas Anda adalah memeriksa apakah program Brainfuck "valid" (memiliki []simbol pasangan ). Harap dicatat bahwa program Brainfuck dapat memiliki karakter selain [], jadi jangan menolak program hanya karena memiliki perintah lain. Kode terkecil menang, tetapi mungkin Anda akan lebih peduli dengan upvote.

Konrad Borowski
sumber
1
Bagaimana dengan bahasa yang tidak memungkinkan pengaturan kode keluar proses?
Kendall Frey
1
@KendallFrey: Sederhana, gunakan sesuatu yang lain. Atau dalam GolfScript, sematkan kode Ruby. Mungkin ini memblokir beberapa bahasa pemrograman esoteris, tetapi yah ...
Konrad Borowski
1
Apakah saya tetap dapat mengatur kode kesalahan ke sesuatu selain 1 (asalkan bukan 0 tentu saja) pada kegagalan?
marinus
@marinus: Saya tidak tahu mengapa Anda menginginkan itu, tapi saya pikir tidak apa-apa.
Konrad Borowski
@GlitchMr: karena saya dapat menggunakan GCD(a,b)bukan 0 != a || b.
marinus

Jawaban:

6

GolfScript, 18 karakter

.{[]`?)},~](`91?./

Kode ini berjalan dengan sukses dengan kode keluar 0 (dan mencetak beberapa sampah ke stdout) jika tanda kurung di input seimbang. Jika tidak, gagal dengan kode keluar yang tidak nol dan mencetak pesan kesalahan ke stderr, misalnya:

(eval):2:in `/': divided by 0 (ZeroDivisionError)

atau

(eval):1:in `initialize': undefined method `ginspect' for nil:NilClass (NoMethodError)

Karena tantangan tidak mengatakan apa pun tentang output ke stdout / stderr, saya pikir ini memenuhi syarat. Dalam kasus apa pun, Anda selalu dapat mengarahkan ulang ke /dev/null.

Penjelasan:

Kode {[]`?)},menghapus semuanya kecuali tanda kurung kotak dari input, dan ~mengevaluasi hasilnya sebagai kode GolfScript. Bagian yang sulit adalah tanda kurung yang tidak seimbang benar-benar legal di GolfScript (dan, memang, kode saya termasuk satu!), Jadi kita perlu cara lain untuk membuat kode mogok.

Trik yang saya gunakan adalah meninggalkan salinan input di bagian bawah tumpukan, mengumpulkan seluruh tumpukan ke dalam array (menggunakan yang tidak seimbang ]) dan menggeser elemen pertama. Pada titik ini, tiga hal dapat terjadi:

  • Jika input diakhiri dengan tertutup [, mencoba menggeser elemen dari array kosong akan membuat crash interpreter (yang, dalam hal ini, persis seperti yang kita inginkan!)
  • Jika tanda kurung di input seimbang, elemen yang bergeser akan menjadi string input asli.
  • Jika tidak (jika inputnya belum dibuka ]atau tidak [ditutup) akan berupa array.

Entri 14-char asli saya kemudian membandingkan nilai yang dialihkan dengan string, yang akan macet jika array bersarang. Sayangnya, ternyata membandingkan array flat (atau, khususnya, kosong) dengan string juga legal di GolfScript, jadi saya harus mengganti taktik.

Kiriman saya saat ini, sebagai gantinya, menggunakan metode yang sangat kasar untuk memberi tahu array dari string: un-eval mereka dan mencoba untuk menemukan kemunculan pertama [(kode ASCII 91), yang akan menjadi nol jika dan hanya jika un-evaled variabel adalah array. Jika demikian, membagi nol dengan dirinya sendiri memicu kehancuran yang diinginkan.

Ps. Dua solusi 18-char lainnya adalah:

.{[]`?)},{.}%~](n<

dan

.{[]`?)},~]([n]+n<

Sayangnya, saya belum menemukan cara yang lebih pendek untuk menyelesaikan "masalah array kosong".

Ilmari Karonen
sumber
apakah ini seimbang ?: ][(yaitu, apakah itu gagal dalam program Anda?)
Justin
@ Quincunx: Gagal, seperti seharusnya.
Ilmari Karonen
Namun, ternyata menerima [[]; Saya sudah memperbaikinya sekarang, dengan biaya 4 chars, dan itu melewati semua tes saya sekarang.
Ilmari Karonen
Jika saya mengerti Anda dengan benar, Anda memiliki solusi 14-char yang gagal membedakan antara string dan array hanya dalam kasus array kosong. 1+akan mengubah array kosong menjadi array yang tidak kosong, array yang tidak kosong menjadi array yang tidak kosong, dan string menjadi string.
Peter Taylor
@PeterTaylor: Ya, benar .{[]`?)},~](n<. Aku mencoba Anda 1+, tetapi tampaknya bahwa kebutuhan array yang mengandung sesuatu yang lain selain nomor (mungkin sehingga penafsir akan crash ketika mencoba untuk secara rekursif membandingkan karakter dengan array / string). Menggunakan n+tidak berfungsi, karena ia memaksa array ke string; [n]+ tidak bekerja, tetapi masih menempatkan saya pada 18 karakter.
Ilmari Karonen
17

Brainfuck 76 byte

>>+[<+++++++++[->---------<]+>-[--[[-]<->]<[<[->-]>[<+]<]>]<[-<+>]+>,]<<[<+]

Ini keluar dari ikatan itu jika tanda kurung siku tidak seimbang mengubah bf interpreter / compiler menjadi runtime gagal dan beberapa dari mereka memiliki kode keluar untuk mencerminkan itu.

membutuhkan eof = 0, nilai pembungkus dan jumlah sel yang terbatas

Di Ubuntu Anda dapat menggunakan penerjemah bf( sudo apt-get install bf)

% echo '[[[]' | bf -n bf_matching.bf
Error: Out of range! Youwanted to '<' below the first cell.
To solve, add some '>'s at the beginning, for example.
an error occured
% echo $? 
5
% bf -n bf_matching.bf < bf_matching.bf
% echo $?
0
Sylwester
sumber
5
Saya suka bagaimana Anda menggunakan Brainfuck meskipun pertanyaannya mengatakan itu tidak mungkin.
Bersepeda
Oh wow. Sejujurnya aku terkejut. Saya berasumsi itu tidak mungkin, tetapi tidak.
Konrad Borowski
1
@xfix: Brainfuck menyelesaikan-turing sehingga dapat melakukan apa saja (mengingat kendala I / O.)
marinus
2
Kelengkapan @marinus Turing hanya berarti dapat melakukan semua perhitungan. Brainfuckadalah Turing selesai tanpa I / O karena Anda dapat menjalankan program yang menghitung perhitungan apa pun dan melihat hasilnya dengan memeriksa ingatannya setelah berjalan. BF tanpa I / O akan membuat orang kurang tertarik karena akan sulit untuk membuat utilitas. misalnya saya tidak akan pernah bisa membuat juru bahasa saya .
Sylwester
14

Befunge 98 - 26 31 20 19 karakter

~:']-!\'[-!-+:0`j#q

Singkirkan beberapa persyaratan besar. Sekarang programnya bekerja sebagai berikut:

~:   read an input char and duplicate it

']-! push a 1 if the char is the ] char, 0 otherwise

\    swap the comparison value for the duplicated input char

'[-! push a 1 if the char is the [ char, 0 otherwise

-    subtract the two comparison values. If the second one is 1, the first is 0, 
     so the result is -1. Else if the second one is 0, the first is 1 and the result is
     1. Else, the first and the second are both 0 and the result is 0

+    Add the number to the counter (which is 0 if there is none already)

:0`  test if the counter is positive (that'd mean an invalid program). Pushes a 1 if 
     positive, 0 otherwise.

j#q  if the counter is positive, then this jumps to the q. Otherwise, it skips the q 
     and continues to the ~ at the beginning of the line. If there are no more chars in
     the input, then the IP will be sent back to the q. 

qkeluar dari program dan muncul nilai teratas sebagai nilai kesalahan. Nilai kesalahan adalah -1 1 jika terlalu banyak ], 0 jika seimbang, dan positif negatif jika terlalu banyak [. Jika angka itu positif negatif, maka banyak nilai absolut dari angka ]itu diperlukan untuk menyeimbangkan program.

Sunting: Peningkatan dan penurunan yang diaktifkan. [digunakan untuk menambah penghitung dan ]digunakan untuk menurunkannya. Dengan beralih, saya menghemat 1 char, karena untuk kondisi keluar, saya hanya perlu memeriksa apakah penghitungnya positif, bukan negatif.


Versi lama

~:'[-!j;\1+\#;']-!j;1-#;:0\`j#q

Kode ini berfungsi sebagai berikut:

~    read one char of input
:    duplicate it
'[-! push 1 if the character is [, 0 otherwise
j    jump that number of characters
;    skip until next ;
\1+\ increment counter

similarily for ].

#q when end of input is reached, ~ reflects the IP back. q ends the program with the error value on the stack.

Sunting: menyadari bahwa ini menerima input seperti ][, sekarang berakhir setiap kali penghitungan menjadi negatif, menggunakan

:0\`j
Justin
sumber
1
18 byte
Jo King
@JoKing itu cukup bagus, menggunakan jarak antara [dan ]untuk melakukan perbandingan dengan keduanya.
Justin
6

J ( 38 35)

exit({:+.<./)+/\+/1 _1*'[]'=/1!:1[3

Penjelasan:

  • 1!:1[3: baca stdin
  • '[]'=/: buat sebuah matriks di mana baris pertama adalah bitmask dari [s di input, dan baris kedua adalah ]s.
  • 1 _1*: kalikan baris pertama dengan 1 dan baris kedua dengan -1.
  • +/: jumlah kolom matriks bersama-sama, memberikan lekukan-indentasi per karakter
  • +/\: buat total running ini, memberikan level lekukan pada setiap karakter
  • ({:+.<./): kembalikan GCD dari elemen terakhir ( {:) dan elemen terkecil ( <./). Jika semua kawat gigi cocok, keduanya harus 0jadi ini akan kembali 0. Jika kawat gigi tidak cocok, itu akan mengembalikan nilai bukan nol.
  • exit: atur nilai keluar untuk itu dan keluar.
marinus
sumber
Kerusakan yang bagus ...
Chris Cashwell
6

ruby (64)

exit $<.read.tr('^[]','').tap{|x|0while x.gsub!('[]','')}.empty?

sebelumnya (68) itu adalah:

exit ARGF.read.tr('^[]','').tap{|x| 0 while x.gsub!('[]','')}.empty?

Solusi setara lainnya menggunakan

exit $<.read.tr('^[]','').tap{|x|0while x.gsub!('[]','')}.size>0

tidak dapat digunakan sizesendiri karena akan memberikan false negative (!!!) ketika jumlah total kurung tidak seimbang adalah kelipatan 256

ditulis ulang
sumber
Ini adalah codegolf. Saya yakin Anda dapat menghapus spasi putih di sini. Ruby agak sensitif ruang putih, tetapi dalam banyak kasus mengabaikannya. Untuk mulai dengan, Anda tidak perlu spasi putih di dekat =operator.
Konrad Borowski
versi yang lebih baik (agak terinspirasi oleh solusi sed + tr). Saya tidak yakin bisa menjadi lebih baik dari ini. Setidaknya memiliki serendah 4 spasi putih!
ditulis ulang
1
Namun, saya dapat menghapus keduanya.
Konrad Borowski
2
Saya pikir ruang di sekitar 0bisa pergi.
marinus
Trik luar biasa, terima kasih!
ditulis ulang
5

Perl, 30 karakter

Regex rekursif dasar Perl Anda untuk menyelamatkan:

perl -0ne 'exit!/^(([^][]|\[(?1)\])*)$/'

Bagi mereka yang tidak terbiasa dengan argumen baris perintah yang digunakan di sini: -0memungkinkan seseorang untuk mengatur karakter akhir baris untuk keperluan input file; menggunakan -0tanpa argumen menetapkan karakter akhir baris ke EOF. -nsecara otomatis membaca input (dalam hal ini, seluruh file) menjadi $_sebelumnya.

Jika regex cocok, ia mengembalikan nilai sebenarnya, yang dinegasikan ke 0 untuk kode keluar. Jika tidak, nilai pengembalian salah menghasilkan kode keluar 1.

kotak roti
sumber
Kira saya harus golf jawaban saya lebih baik untuk mengalahkan solusi 30 char ini.
Justin
Sana. Solusi saya sekarang jauh lebih pendek daripada sebelumnya. Solusi yang bagus. +1
Justin
4

bash (tr + sed) - 42

[ -z `tr -Cd []|sed ":a;s/\[\]//g;t a"` ]

Jika Anda tidak keberatan dengan pesan kesalahan maka Anda dapat menghapus ruang terakhir di antara `dan ]untuk mendapatkan panjang 41.

shiona
sumber
Kecuali saya melewatkan sesuatu, Anda memiliki penggunaan yang tidak berguna catdan $()(juga "[]"dapat ditulis sebagai []). Saya menerima jawaban ini, tetapi sampai saya akan melihat peningkatan panjangnya, saya tidak akan membatalkan ini, karena sementara pendek, itu bisa menjadi cara yang lebih pendek untuk bash.
Konrad Borowski
Yah, sebenarnya saya tidak tahu shell scripting dengan baik. Saya tidak dapat membuat sebagian besar dari pekerjaan itu. Saya diganti $()dengan backticks dan melakukan "[]"-> yang []Anda sarankan.
shiona
Masih ada gunanya menggunakan kucing .
Konrad Borowski
1
Aku bisa saja pedang, aku mencoba dan gagal ini, tapi aku salah.
shiona
3

Perl (56 karakter)

$/=0;$r=qr/[^][]*(\[(??{$r})\])*[^][]*/;<>=~m/^$r$/||die

Solusi Perl yang jelas: regex rekursif. Sayangnya itu adalah konstruksi yang agak bertele-tele.

Peter Taylor
sumber
3

Haskell (143)

import System.Exit
f=exitFailure
v c []|c==0=exitSuccess|True=f
v c (s:t)|c<0=f|s=='['=v(c+1)t|s==']'=v(c-1)t|True=v c t
main=getContents>>=v 0

to jgon: Menggunakan 2 penjaga tampaknya lebih padat daripada jika-maka-lain. Selain itu, menurut saya milik Anda tidak memeriksa bahwa tanda kurung berada dalam urutan yang benar ("] [" berlalu)

pengguna13350
sumber
oh wow, hanya melihat komentar ini ketika ditunjukkan hari ini. Memperbaiki kode saya, tapi ya bagus, penjaga tampaknya lebih padat (+1).
jgon
3

C, 73 64 karakter

Berkat saran dari kotak roti (walaupun ini mungkin membutuhkan little-endian untuk bekerja):

i;main(c){while(read(0,&c,1)*(i+1))i+=(c==91)-(c==93);return i;}

Bagaimana itu bekerja:

  • global int implisit iakan diinisialisasi ke 0
  • cmenjadi int implisit yang didapat argc(diinisialisasi ke 1 tetapi kami tidak peduli, asalkan bit yang lebih tinggi tidak disetel)
  • read(0,&c,1)membaca satu karakter ke byte rendah dari c (pada arsitektur little-endian) dan mengembalikan 0 pada EOF; i+1 != 0kecuali kutipan braket seimbang ke -1; mengalikannya bekerja sebagai boolean (aman) DAN yang membutuhkan satu karakter lebih sedikit daripada&&
  • c==91mengevaluasi ke 1 untuk '[', dan c==93mengevaluasi ke 1 untuk ']'. (Mungkin ada beberapa trik fiddly fiddly bit yang akan lebih kecil tapi aku tidak bisa memikirkan apa pun.)
  • return ikeluar dengan kode status 0 jika seimbang, tidak nol jika tidak. Mengembalikan -1 secara teknis melanggar POSIX tetapi tidak ada yang benar-benar peduli tentang itu.

Versi sebelumnya:

main(i){char c;i=0;while(read(0,&c,1)*(i+1))i+=(c==91)-(c==93);return i;}
halus
sumber
Menggunakan getchar()bukannya membaca akan mempersingkat kode dan memungkinkan Anda untuk menggunakan (implisit) intalih-alih charuntuk variabel Anda. Juga ingat bahwa global secara otomatis diinisialisasi ke nol.
kotak roti
Terima kasih, saya lupa tentang getchar (). Tidak yakin bagaimana init global membantu, - mendefinisikan int global saya membutuhkan lebih banyak karakter daripada menggunakan argc implisit.
Fluffy
1
Global juga bisa implisit. Di luar fungsi, c;mendefinisikan int global.
kotak roti
Sementara itu, getchar (c) akhirnya tidak membuatnya lebih pendek, setidaknya menggunakan pendekatan ini, karena perlu diuji untuk> = 0 dalam beberapa cara, dan int implisit untuk c diteruskan ke baca () tidak dijamin untuk bekerja karena endianness.
Fluffy
Bagaimana dengan ][? Saya yakin itu tidak seimbang. Tidakkah Anda harus melacak apakah hasilnya negatif setidaknya sekali?
vsz
2

Lua, 56

os.exit(("["..io.read"*a".."]"):match"^%b[]$"and 0 or 1)
mniip
sumber
"^%b[]$"apa ini? Bisakah Anda jelaskan? Tentunya, ini bukan regex?
Cruncher
@Cruncher: Tidak. Itu pola Lua, bukan regex (pola Lua mirip dengan regex, tetapi tidak). Dalam hal ini cocok dengan awal string ( ^), set seimbang [dan ]dengan apa pun di antara ( %b[]), dan akhir string ( $).
Konrad Borowski
1

GTB , 55

0→O:0→X[`I@I="[":X+1→X@I="]":X-1→X@X<0:1→O@!!Ig;e]l;e~O

Rindu []

Gunakan 0untuk berhenti.

Timtech
sumber
1

MATHEMATICA, 88 karakter

s = "[ [ my crazy code ] [ don't explode please! [] [ :)Ahh) ]  [] []]]";

r=StringReplace;
StringLength@FixedPoint[r[#,"[]"-> ""]&,r[s,Except@Characters["[]"]-> ""]]
Murta
sumber
Dengan fungsi s name like RegularExpression` dan StringLengthsaya tidak pernah bisa memenangkan konteks golf kode teks dengan Mathematica! :)
Murta
Saya tahu maksud Anda :) ToCharacterCodejauh lebih lama daripada ord... PS: Bagaimana dengan mengatur kode keluar?
Ajasja
Length[StringCases[s,"["|"]"]//.{x___,"[","]",y___}:>{x,y}]
alephalpha
1

Rubi, 59 58

Memindai untuk membuka dan menutup braket, menghitung [sebagai 1 dan ]-1, dan keluar jika jumlah turun di bawah 0.

b=0
$<.read.scan(/\]|\[/){exit 1if(b+=92-$&.ord)<0}
exit b
daniero
sumber
1
Diperbaharui, dan disingkat oleh satu karakter (saya menghapus spasi setelah exit 1Anda bertanya).
Konrad Borowski
1

Hassium , 104 Bytes

func main(){l=0;r=0;b=input();foreach (c in b){if(c=="[")l++;if(c=="]")r++;}if(!(r==l))exit(1);exit(0);}

Berkembang penuh (catatan tidak berfungsi dalam juru bahasa online karena input () dinonaktifkan) di sini

Yakub Misirian
sumber
1

Kode Mesin Turing, 286 276 byte

Sekali lagi, saya menggunakan sintaks tabel aturan yang didefinisikan di sini.

0 * * l 1
1 _ ! r Q
5 _ _ r 5
5 * * * W
W [ ! l E
W ] ! l T
W _ _ l I
W * ! r *
E ! ! l *
E * * * R
R _ [ r O
R * * l *
T ! ! l *
T * * * Y
Y _ _ r U
Y * * l *
U [ _ r O
U ! ! * halt-err
I ! ! l *
I _ _ r halt
I * * l halt-err
O ! ! r Q
O _ _ l I
O * * r *
Q ! ! r *
Q * * * W

Berakhir dalam status haltuntuk menerima input dan halt-errmenolaknya.

SuperJedi224
sumber
halt-errbisa lebih pendek, misalnya halt*misalnya.
Erik the Outgolfer
1

Pyth, 25 byte

Ilzv::z"[^[\]]"k"]\[""],[

Cobalah online!

Terjemahan Python 3:
import re
z=input()
if len(z):
 print(eval(re.sub("]\[","],[",re.sub("[^[\]]","",z))))
hakr14
sumber
1

Haskell ( 167 , 159)

Apakah ini sebagian besar untuk bersenang-senang, jika ada yang punya saran untuk membuatnya lebih pendek, saya akan senang mendengarnya :)

import System.Exit
p x y b|b=x|True=y
main=getContents>>=(return.all (>=0).scanl (\v->p (v-1) (v+1).(==']')) 0.filter (`elem`"[]"))>>=p exitSuccess exitFailure

Sunting: Memperbaiki masalah yang ditunjukkan kepada saya di komentar (ditambahkan 11 byte).

Sunting 2: Fungsi tambahan yang dibuat untuk menguji predikat menggunakan pelindung yang terinspirasi oleh user13350, menghapus 8 byte.

jgon
sumber
@ user202729 Itu poin yang sangat baik, itu sangat ceroboh. Cukup yakin itu sudah diperbaiki sekarang.
jgon
1

Stax , 14 11 karakter

╬Äτ↔EªÉs «Ü

Jalankan dan debug itu

Kredit ke @recursive untuk -3 byte.

Setara ASCII:

.[]Y|&{yz|egp!

Hapus semua karakter kecuali [], lalu hapus []sampai string tidak lagi berubah. Kembali 1jika string terakhir kosong.

Weijun Zhou
sumber
1
Bagus. Anda dapat menggunakan .[]|&untuk memfilter karakter, dan kemudian menggunakan kembali literal untuk 11
rekursif