Pyth adalah bahasa golf yang didasarkan pada Python. Ini menggunakan notasi awalan, dengan setiap perintah memiliki arity yang berbeda (jumlah argumen yang diterimanya).
Tugas Anda adalah menulis pemeriksa sintaksis untuk bahasa yang mirip Pyth (tidak ada), Pith.
Sintaksis empulur
Empulur hanya memiliki 8 perintah char tunggal:
01234()"
01234
masing-masing memiliki arity dari angka yang sesuai, dan karenanya mengharapkan banyak argumen setelahnya. Sebagai contoh,
400010
adalah program empulur yang benar karena 4
diikuti oleh empat argumen 0
0
0
dan 10
, yang terakhir 1
diikuti oleh argumen tunggal 0
. Untuk memvisualisasikan ini, kita dapat melihat pohon berikut:
R
|
4
|
-------------
| | | |
0 0 0 1
|
0
di mana R
simpul root. Cara alternatif untuk memikirkan hal ini adalah bahwa setiap angka mengacu pada jumlah anak yang dimiliki simpul yang sesuai pada pohon di atas.
Berikut ini adalah program empulur lain yang valid, dengan lebih dari satu perintah dasar:
210010
sesuai dengan
R
|
-------------
| |
2 1
| |
--------- 0
| |
1 0
|
0
Di samping itu,
3120102100
adalah tidak program empulur yang benar karena awal 3
hanya memiliki dua argumen, yang dapat kita lihat dengan melihat pohon di bawah ini:
R
|
3
|
------------------------ ??
| |
1 2
| |
2 ------
| | |
------ 1 0
| | |
0 1 0
|
0
Selanjutnya (
dimulai tanpa batas, dan )
berakhir tanpa batas. Yang tidak terikat mengambil sejumlah argumen (dengan rakus), dan dianggap sebagai argumen tunggal untuk perintah induk mana pun. Setiap batasan yang masih terbuka pada akhir program akan ditutup secara otomatis. Sebuah )
perintah bukanlah kesalahan jika tidak ada unboundeds terbuka - itu hanya tidak apa-apa *.
Misalnya, program Empulur
)31(0)0(201000100
sesuai dengan pohon
R
|
3
|
------------------------------
| | |
1 0 (
| |
( -----------------------------
| | | | | |
0 2 0 0 1 0
| |
------- 0
| |
0 1
|
0
Kosong tanpa ()
batas tidak apa-apa, begitu juga program empulur yang valid.
Program empulur yang tidak valid dengan tidak terikat adalah
12(010
karena 2
hanya menerima satu argumen (yang tidak terikat).
Akhirnya, "
dimulai dan diakhiri string, yang selalu 0 arity dan dihitung sebagai argumen tunggal, misalnya
2"010""44)()4"
yang hanya 2
sedang melewati dua argumen string "010"
dan "44)()4"
. Seperti tidak terikat, string juga dapat kosong, dan string yang tidak tertutup pada akhir program secara otomatis ditutup.
* Bagian ini berbeda dengan Pyth asli yang sebenarnya tidak melakukan sesuatu dalam kasus seperti 1)
, mengakhiri 1-arity dan meningkatkan kesalahan.
Input output
Input akan berupa string tunggal yang tidak kosong yang hanya terdiri dari karakter 01234()"
. Anda dapat mengasumsikan bahwa tambahan baris baru tambahan selalu ada. Anda dapat menulis fungsi atau program lengkap untuk tantangan ini.
Anda harus menampilkan nilai kebenaran jika inputnya empati valid secara sintaksis, atau nilai palsu sebaliknya. Nilai kebenaran dan kepalsuan harus diperbaiki, sehingga Anda tidak dapat menampilkan 1
untuk satu program yang valid dan yang 2
lain.
Mencetak gol
Ini adalah kode-golf, jadi kode dalam byte paling sedikit menang.
Uji kasus
Benar:
0
)
(
"
()
""
10
400010
210010
("")00
3"""""
(0)))0)1)0
2(2(2(0)0)0)0
2"010""44)()4"
)31(0)0(201000100
())2)1))0"3())"))
3("4321("301(0)21100"4")"123"00)40"121"31000""01010
Falsy:
1
1(310
(1)0)
12(010
4"00010"
3120102100
20(2((0)(0)))
2(2(2(0)0)0)01)
4(0102)00)00000
2"00"("00"2(""))
sumber
[( [2 [0] [1 [0] ] ] [0] [1 [0]] [0] ]
? Yang Anda miliki memiliki cabang 2, 0, 0, 1 dan 0 - yang kedua tidak boleh ada.())2)1))0"3())"))
(yang seharusnya benar, saya pikir).()210""
dengan banyak no-ops)Jawaban:
CJam, 65 byte
Astaga, saya berharap CJam memiliki Regex, ini bisa diselesaikan dalam waktu kurang dari 50 byte
Ide utama adalah untuk menjaga mengurangi hal untuk
0
yaitu10
untuk0
,200
untuk0
dan sebagainya. Setelah itu selesai, kami mengurangi semua tanda kurung yang cocok ke0
, yaitu()
ke0
,(0)
ke0
,(00)
ke0
dan seterusnya. Kami mengulangi waktu siklusL
, di manaL
panjang input.String input awalnya melewati pemrosesan ekstra di mana kami menyesuaikan untuk yang tak tertandingi
"
dan menambahkan banyak)
untuk mengimbangi yang tidak cocok(
Ini memastikan bahwa setelah semua iterasi, kita seharusnya hanya
0
(dan tanpa op)
) yang tersisa dalam string.Perbarui - memperbaiki bug di mana
)
no-op tingkat atas dianggap berbahayaPerluasan kode
Cobalah online di sini atau jalankan seluruh rangkaian
sumber
Regex, rasa PCRE, 83 byte
Coba di sini.
Regex, rasa PCRE, 85 byte
Coba di sini.
Menggunakan beberapa ide dalam jawaban dan1111 ini .
Beberapa penjelasan tentang
(?2)*(()(?1))?
.sumber
(?2)*(()(?1))?
adalah potongan puzzle terakhir yang saya cari. Temuan yang bagus! ;)(?2)*(()(?1))?
bagian dengan benar,(()(?1))?
bagian itu tidak pernah cocok dengan apa pun, karena(?2)*
sudah memakan semua yang(()(?1))?
bisa cocok, dan konstruk ini digunakan untuk mengatur grup menangkap 3 ketika kita masuk(
dan tidak mengatur grup menangkap 3 ketika kita berada di luar()
konstruksi (untuk memungkinkan pencocokan tidak berpasangan)
).lex, 182 byte (157 w / tumpukan ukuran tetap)
Program-program ini membutuhkan input untuk menjadi string karakter baru yang diakhiri baris baru.
Program di atas akan segfault jika kehabisan memori, yang secara teoritis bisa terjadi jika Anda memberikannya cukup
(
. Tetapi karena segfault dianggap sebagai kegagalan, saya menganggapnya sebagai "falsey", meskipun deskripsi masalah tidak mengatakan apa yang harus dilakukan jika sumber daya tidak mencukupi.Saya memotong 157 byte dengan hanya menggunakan tumpukan ukuran tetap, tapi itu tampak seperti curang.
Untuk mengkompilasi:
Uji:
Output tes:
sumber
80386 Assembler, 97 byte
Hex dump:
Ini dijalankan melalui input sekali, mendorong angka lebih besar dari nol ke tumpukan dan menurunkannya ketika nol diproses. Tanpa batas diproses sebagai -1.
Prototipe fungsi (dalam C) (fungsi mengembalikan 0 jika tidak valid dan 1 jika valid):
Majelis Setara (NASM):
Kode berikut dalam C dapat digunakan dengan GCC pada sistem POSIX untuk menguji:
sumber
Python 2, 353 byte
Fungsi parse melangkah melalui token satu per satu dan membangun pohon struktur program. Program yang tidak valid memicu pengecualian yang menyebabkan angka nol (Falsy) dicetak, jika tidak hasil parsing akan berhasil.
Output dari tes menunjukkan output parser:
Kode sebelum minifier:
sumber
==
dalam tes - menempatkan string terlebih dahulu berarti Anda bisa melakukannyaif')'==q
. Saya percaya salah satubreak
pernyataan bisa digantif=0
, karena itu akan membuat Anda keluar dariwhile f
lingkaran juga. Akhirnya, alih-alihassert x==y
Anda dapat menggunakan1/(x==y)
untukZeroDivisionError
. ;)Pip ,
8872 byteIde diambil dari CJam Pengoptimal . Penusukan orisinal saya pada masalah dengan parser keturunan rekursif adalah ... agak lebih lama.
Diformat, dengan penjelasan:
Trik menarik:
0X,5
, misalnya, adalah0 X [0 1 2 3 4] == ["" "0" "00" "000" "0000"]
.R
operator ternary eplace dapat mengambil daftar untuk setiap argumennya:"abracadabra" R ["br" "ca"] 'b
memberiababdaba
, misalnya. Saya memanfaatkan fitur ini dengan baik diz
sini.""
kosong[]
, daftar kosong , dan skalar apa pun yang nol. Jadi,0
itu salah, tetapi juga0.0
dan"0000000"
. Fitur ini kadang-kadang tidak nyaman (untuk menguji apakah string kosong, seseorang harus menguji panjangnya karena"0"
salah juga), tetapi untuk masalah ini sempurna.sumber
Javascript (ES6),
289288285282278244241230 bytesumber