Dalam buku ilmu komputer populer (dan esensial), Pengantar Bahasa Resmi dan Automata oleh Peter Linz, bahasa formal berikut ini sering dinyatakan:
terutama karena bahasa ini tidak dapat diproses dengan automata negara-terbatas. Ungkapan ini berarti "Bahasa L terdiri dari semua string 'a diikuti oleh' b's, di mana jumlah 'a dan' b's sama dan tidak nol".
Tantangan
Tulis program / fungsi kerja yang hanya berupa string, yang mengandung "a" dan "b" , sebagai input dan mengembalikan / menampilkan nilai kebenaran , dengan mengatakan jika string ini valid, bahasa formal L.
Program Anda tidak dapat menggunakan alat perhitungan eksternal apa pun, termasuk jaringan, program eksternal, dll. Kerang adalah pengecualian dari aturan ini; Bash, misalnya, dapat menggunakan utilitas baris perintah.
Program Anda harus mengembalikan / menampilkan hasilnya dengan cara yang "logis", misalnya: mengembalikan 10 bukannya 0, "bip", mengeluarkan ke stdout dll . Info selengkapnya di sini.
Aturan golf kode standar berlaku.
Ini adalah kode-golf . Kode terpendek dalam byte menang. Semoga berhasil!
Kasus uji kebenaran
"ab"
"aabb"
"aaabbb"
"aaaabbbb"
"aaaaabbbbb"
"aaaaaabbbbbb"
Kasus uji palsu
""
"a"
"b"
"aa"
"ba"
"bb"
"aaa"
"aab"
"aba"
"abb"
"baa"
"bab"
"bba"
"bbb"
"aaaa"
"aaab"
"aaba"
"abaa"
"abab"
"abba"
"abbb"
"baaa"
"baab"
"baba"
"babb"
"bbaa"
"bbab"
"bbba"
"bbbb"
sumber
empty string == truthy
dannon-empty string == falsy
dapat diterima?a^n b^n
atau serupa, daripada hanya jumlaha
s yang menyamai jumlahb
s)Jawaban:
MATL ,
54 byteMencetak array non-kosong 1 s jika string milik L , dan array kosong atau array dengan 0 s (keduanya salah) sebaliknya.
Terima kasih kepada @LuisMendo karena bermain golf 1 byte!
Cobalah online!
Bagaimana itu bekerja
sumber
Python 3, 32 byte
Keluaran melalui kode keluar : Kesalahan untuk false, tidak ada kesalahan untuk True.
String dievaluasi sebagai kode Python, menggantikan parens
(
untuka
dan)
untukb
. Hanya ekspresi bentuk yanga^n b^n
menjadi ekspresi kurung seperti((()))
, yang dievaluasi ke tuple()
.Setiap parens yang tidak cocok memberikan kesalahan, seperti yang akan terjadi pada beberapa grup
(()())
, karena tidak ada pemisah. String kosong juga gagal (itu akan berhasilexec
).Konversi
( -> a
,) -> b
selesai menggunakanstr.translate
, yang menggantikan karakter seperti yang ditunjukkan oleh string yang berfungsi sebagai tabel konversi. Diberikan string 100-panjang ") (" * 50, tabel memetakan 100 nilai ASCII pertama sebagaiyang mengambil
( -> a
,) -> b
. Dalam Python 2, konversi untuk semua 256 nilai ASCII harus disediakan, membutuhkan"ab"*128
, satu byte lebih lama; terima kasih kepada isaacg untuk menunjukkan ini.sumber
*128
dilakukan?128
dapat diganti dengan50
(atau99
dalam hal ini) untuk menghemat satu byte.Retina , 12 byte
Penghargaan kepada FryAmTheEggman yang menemukan solusi ini secara mandiri.
Mencetak
1
untuk input yang valid dan0
sebaliknya.Cobalah online! (Baris pertama memungkinkan suite tes yang dipisahkan dengan linefeed.)
Penjelasan
Grup penyeimbang memerlukan sintaksis mahal, jadi alih-alih saya mencoba mengurangi input yang valid ke bentuk sederhana.
Tahap 1
The
+
memberitahu Retina mengulangi tahap ini dalam satu lingkaran sampai output berhenti berubah. Cocokab
atau ataua;b
menggantikannya dengan;
. Mari kita pertimbangkan beberapa kasus:a
s danb
s dalam string tidak seimbang dengan cara yang sama(
dan)
biasanya perlu, beberapaa
ataub
akan tetap dalam string, karenaba
, ataub;a
tidak dapat diselesaikan dan satua
ataub
sendiri tidak dapat antara. Untuk menyingkirkan semuaa
s danb
s harus ada satu yang sesuaib
dengan hak masing-masinga
.a
danb
tidak semuanya bersarang (mis. Jika kita memiliki sesuatu sepertiabab
atauaabaabbb
) maka kita akan berakhir dengan banyak;
(dan berpotensi beberapaa
s danb
s) karena iterasi pertama akan menemukan banyakab
s untuk menyisipkannya dan iterasi selanjutnya akan dipertahankan jumlah;
dalam string.Oleh karena itu, jika dan hanya jika inputnya berupa , kita akan berakhir dengan satu di string.
anbn
;
Tahap 2:
Periksa apakah string yang dihasilkan hanya berisi satu titik koma. (Ketika saya mengatakan "centang" yang sebenarnya saya maksudkan, "hitung jumlah kecocokan dari regex yang diberikan, tetapi karena regex itu dapat cocok paling banyak sekali karena jangkar, ini memberikan salah satu
0
atau1
.)sumber
Haskell, 31 byte
Pemahaman daftar
[c|c<-"ab",'a'<-s]
membuat string satu'a'
untuk masing-masing'a'
masuks
, diikuti oleh satu'b'
untuk masing-masing'a'
masuks
. Ini menghindari penghitungan dengan mencocokkan pada konstanta dan menghasilkan output untuk setiap kecocokan.String ini dicentang sama dengan string asli, dan string asli dicentang tidak kosong.
sumber
f=g.span id.map(=='a');g(a,b)=or a&&b==(not<$>a)
). Sudah selesai dilakukan dengan baik.Grime , 12 byte
Cobalah online!
Penjelasan
Baris pertama mendefinisikan nonterminal
A
, yang cocok dengan satu hurufa
, mungkin nonterminalA
, dan kemudian satu hurufb
. Baris kedua cocok dengan seluruh input (e
) terhadap nonterminalA
.8-byte versi yang tidak bersaing
Setelah menulis versi pertama dari jawaban ini, saya memperbarui Grime untuk dipertimbangkan
_
sebagai nama ekspresi tingkat atas. Solusi ini setara dengan yang di atas, tetapi menghindari pengulangan labelA
.sumber
Brachylog ,
2319 byteCobalah online!
Penjelasan
sumber
05AB1E , 9 byte
Kode:
Penjelasan:
Dua byte terakhir dapat dibuang jika inputnya dijamin tidak kosong.
Menggunakan pengkodean CP-1252 . Cobalah online! .
sumber
.M{J¹ÔQ0r
untuk Anda.Jelly , 6 byte
Mencetak string itu sendiri jika itu milik L atau kosong, dan 0 sebaliknya.
Cobalah online! atau verifikasi semua kasus uji .
Bagaimana itu bekerja
Versi alternatif, 4 byte (tidak bersaing)
Mencetak 1 atau 0 . Cobalah online! atau verifikasi semua kasus uji .
Bagaimana itu bekerja
sumber
J, 17 byte
Ini berfungsi dengan benar untuk memberikan falsey untuk string kosong. Kesalahan adalah falsey.
Versi lama:
Bukti dan penjelasan
Kata kerja utama adalah garpu yang terdiri dari tiga kata kerja ini:
Ini berarti, "Semakin kecil (
<.
) panjang (#
) dan hasil dari tine kanan ((-:'ab'#~-:@#)
)".Tine kanan adalah 4-kereta , yang terdiri dari:
Biarkan
k
mewakili masukan kami. Kemudian, ini setara dengan:-:
adalah operator pertandingan, jadi-:
tes utama untuk invarian di bawah garpu monadik'ab' #~ -:@#
.Karena tine kiri dari fork adalah kata kerja, itu menjadi fungsi konstan. Jadi, garpu itu setara dengan:
Garis kanan dari garpu membagi dua (
-:
) panjang (#
) darik
. Amati#
:Sekarang, ini
k
hanya pada input yang valid, jadi kita selesai di sini.#
kesalahan untuk string panjang ganjil, yang tidak pernah memuaskan bahasa, jadi kami juga selesai.Dikombinasikan dengan yang lebih pendek dari panjang dan ini, string kosong, yang bukan merupakan bagian dari bahasa kita, menghasilkan panjangnya
0
,, dan kita selesai dengan semuanya.sumber
2&#-:'ab'#~#
yang seharusnya membuat Anda menghindari kesalahan dan hanya menghasilkan output0
sementara masih menggunakan 12 byte.Bison / YACC 60 (atau 29) byte
(Ya, kompilasi untuk program YACC adalah beberapa langkah jadi mungkin ingin memasukkan beberapa untuk itu. Lihat di bawah untuk detailnya.)
Fungsi ini harus cukup jelas jika Anda tahu menafsirkannya dalam hal tata bahasa formal. Parser menerima salah satu
ab
ataua
diikuti oleh urutan yang dapat diterima diikuti oleh ab
.Implementasi ini bergantung pada kompiler yang menerima semantik K&R untuk kehilangan beberapa karakter.
Itu lebih banyak kata daripada yang saya inginkan dengan kebutuhan untuk mendefinisikan
yylex
dan memanggilgetchar
.Kompilasi dengan
(sebagian besar opsi untuk gcc khusus untuk sistem saya dan tidak boleh dihitung terhadap jumlah byte; Anda mungkin ingin menghitung
-std=c89
yang menambahkan 8 ke nilai yang tercantum).Jalankan dengan
atau setara.
Nilai kebenaran dikembalikan ke OS dan kesalahan juga dilaporkan
syntax error
ke baris perintah. Jika saya bisa menghitung hanya bagian dari kode yang mendefinisikan fungsi parsing (yaitu mengabaikan yang kedua%%
dan semua yang mengikuti) saya mendapatkan hitungan 29 byte.sumber
Perl 5.10,
3517 byte (dengan flag -n )Pastikan string dimulai dengan
a
s dan kemudian berulang padab
s. Hanya cocok jika kedua panjangnya sama.Terima kasih kepada Martin Ender untuk mengurangi separuh jumlah byte dan mengajari saya sedikit tentang rekursi di regex: D
Ini mengembalikan seluruh string jika cocok, dan tidak ada jika tidak.
Coba di sini!
sumber
$_&&=y/a//==y/b//
(membutuhkan-p
), tanpa kosong Anda bisa menjatuhkan&&
16! Begitu dekat ...echo -n 'aaabbb'|perl -pe '$_+=y/a//==y/b//'
tapi saya tidak bisa menggeser byte lain ... Mungkin harus menyerah!JavaScript,
545544Membangun regex sederhana berdasarkan panjang string dan mengujinya. Untuk string 4 panjang (
aabb
) regex terlihat seperti:^a{2}b{2}$
Mengembalikan nilai truey atau falsey.
11 byte disimpan berkat Neil.
sumber
f=
dapat dihilangkan.s=>s.match(`^a{${s.length/2}}b+$`)
?C,
5753 BytesSolusi lama 57 byte:
Dikompilasi dengan gcc v. 4.8.2 @Ubuntu
Terima kasih ugoren untuk tipsnya!
Cobalah di Ideone!
sumber
(t+=2)
ket++++
untuk -1 byte.t++++
bukan kode C yang valid.t+=*s%2*2
dan:*s*!1[s]
Retina , 22 byte
Jawaban lain yang lebih pendek dalam bahasa yang sama baru saja datang ...
Cobalah online!
Ini adalah pameran kelompok penyeimbang di regex, yang dijelaskan sepenuhnya oleh Martin Ender .
Karena penjelasan saya tidak akan mendekati setengahnya, saya hanya akan menghubungkannya dan tidak berusaha menjelaskan, karena itu akan merusak kemuliaan penjelasannya.
sumber
Befunge-93, 67 byte
Coba di sini! Bisa jelaskan cara kerjanya nanti. Mungkin juga mencoba untuk golf itu sedikit lebih, hanya untuk iseng.
sumber
MATL , 9 byte
Cobalah online!
Array output benar jika tidak kosong dan semua entri adalah nol. Kalau tidak, itu palsu. Berikut ini beberapa contohnya .
sumber
kode mesin x86,
2927 byteHexdump:
Kode perakitan:
Iterasi atas
a
byte pada awalnya, lalu atas byte 'b' berikut. Loop pertama meningkatkan penghitung, dan loop kedua menguranginya. Setelah itu, lakukan bitwise ATAU antara kondisi berikut:b
s bukan 0, string juga tidak cocokKemudian, itu harus "membalikkan" nilai kebenaran di
eax
- set ke 0 jika bukan 0, dan sebaliknya. Ternyata kode terpendek untuk melakukannya adalah kode 5-byte berikut, yang saya curi dari output kompiler C ++ saya untukresult = (result == 0)
:sumber
neg eax
untuk mengatur flag carry seperti sebelumnya,cmc
untuk membalik flag carry dansalc
untuk mengatur AL ke FFh atau 0 tergantung pada apakah flag carry diset atau tidak. Menghemat 2 byte, meskipun berakhir dengan hasil 8-bit daripada 32-bit.xor eax,eax | xor ecx,ecx | l1: inc ecx | lodsb | cmp al, 'a' | jz l1 | dec esi | l2: lodsb | cmp al,'b' | loopz l2 | or eax,ecx | setz al | ret
Ruby, 24 byte
(Ini hanya ide brilian xnor dalam bentuk Ruby. Jawaban saya yang lain adalah solusi yang sebenarnya saya buat sendiri.)
Program mengambil input, mentransformasikan
a
danb
ke masing[
-]
masing, dan mengevaluasinya.Input yang valid akan membentuk array bersarang, dan tidak ada yang terjadi. Ekspresi yang tidak seimbang akan membuat program macet. Dalam Ruby input kosong dievaluasi sebagai
nil
, yang akan macet karenanil
belum menentukan*
metode.sumber
Sed, 38 + 2 = 40 byte
Output string yang tidak kosong benar
Automata negara terbatas tidak bisa melakukan ini, katamu? Bagaimana dengan automata keadaan terbatas dengan loop . : P
Jalankan dengan
r
dann
bendera.Penjelasan
sumber
JavaScript,
4442Dicoret 44 masih teratur 44; (
Bekerja dengan rekursif melucuti luar
a
danb
dan secara rekursif menggunakan nilai dalam dipilih tapi.+
. Ketika tidak ada kecocokan di^a.+b$
sebelah kiri, maka hasil akhirnya adalah apakah string yang tersisa adalah nilai yang tepatab
.Kasus uji:
sumber
ANTLR, 31 byte
Menggunakan konsep yang sama dengan jawaban YACC @ dmckee , hanya sedikit lebih golf.
Untuk mengujinya, ikuti langkah-langkah dalam tutorial Memulai ANTLR . Kemudian, masukkan kode di atas ke dalam file bernama
A.g4
dan jalankan perintah ini:Kemudian uji dengan memberikan input pada STDIN agar
grun A r
seperti:Jika input valid, tidak ada yang akan dihasilkan; jika tidak valid,
grun
akan memberikan kesalahan (baiktoken recognition error
,extraneous input
,mismatched input
, atauno viable alternative
).Contoh penggunaan:
sumber
grammer
kunci ini lebih buruk untuk bermain golf dengan antlr. Agak suka menggunakan fortran .C, 69 byte
69 byte:
#define f(s)strlen(s)==2*strcspn(s,"b")&strrchr(s,97)+1==strchr(s,98)
Bagi mereka yang tidak terbiasa:
strlen
menentukan panjang stringstrcspn
mengembalikan indeks pertama dalam string di mana string lain ditemukanstrchr
mengembalikan pointer ke kemunculan pertama karakterstrrchr
mengembalikan pointer ke kemunculan karakter terakhirTerima kasih banyak untuk Titus!
sumber
>97
bukannya==98
R,
646155 byte,7367 byte (kuat) atau 46 byte (jika string kosong diizinkan)Sekali lagi, jawaban xnor dikerjakan ulang. Jika tersirat oleh aturan bahwa input akan terdiri dari string
a
s danb
s, itu harus berfungsi: mengembalikan NULL jika ekspresi valid, melempar dan kesalahan atau tidak sama sekali.Jika input tidak kuat dan mungkin mengandung beberapa sampah, misalnya
aa3bb
, maka versi berikut harus dipertimbangkan (harus mengembalikanTRUE
untuk kasus uji yang benar, bukan NULL):Akhirnya, jika string kosong diizinkan, kita dapat mengabaikan kondisi untuk input tidak kosong:
Sekali lagi, NULL jika sukses, apa pun sebaliknya.
sumber
NULL
), versi 2: hanya apa-apa (input yang benar mengembalikan hanyaTRUE
), versi 3 (dengan asumsi string kosong adalah OK, sebagai negara):NULL
. R adalah bahasa berorientasi objek statistik yang typecasts semuanya OK, tanpa peringatan.if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
Japt , 11 byte
Cobalah online!
Memberi salah satu
true
ataufalse
, kecuali yang""
memberi""
yang palsu di JS.Dibongkar & Cara kerjanya
Diadopsi dari solusi MATL Dennis .
sumber
C (Ansi),
6575 BytesGolf:
Penjelasan:
Tetapkan nilai j dan kenaikan j pada setiap b dan penurunan j pada hal lain. Diperiksa apakah surat sebelumnya kurang dari atau sama dengan surat berikutnya sehingga mencegah abab bekerja
Suntingan
Menambahkan cek untuk kasus abab.
sumber
ba
atauabab
?Batch, 133 byte
Mengembalikan nilai
ERRORLEVEL
0 pada kesuksesan, 1 pada kegagalan. Batch tidak suka melakukan penggantian substring pada string kosong, jadi kami harus memeriksanya di depan; jika parameter kosong legal, baris 6 tidak perlu.sumber
PowerShell v2 +,
6152 byteMengambil input
$n
sebagai string, membuat$x
sebagaihalf the length
. Membangun-and
perbandingan Boolean antara$n
dan-match
operator regex terhadap regex dengan jumlah yang sama daria
danb
. Output Boolean$TRUE
atau$FALSE
. Apakah$n-and
ada untuk memperhitungkan""
=$FALSE
.Alternatif, 35 byte
Ini menggunakan regex dari jawaban Leaky , berdasarkan pada kelompok penyeimbang .NET, baru saja dienkapsulasi dalam
-match
operator PowerShell . Mengembalikan string untuk kebenaran, atau string kosong untuk falsey.sumber
-match
terhadap$args[0]
, jika tidak-match
akan berfungsi sebagai filter[0]
sini karena kita hanya diberi satu input dan kita hanya perlu satu nilai true / falsey sebagai output. Karena string kosong adalah falsey dan string non-kosong adalah benar, kita dapat memfilter terhadap array dan mendapatkan kembali string input atau tidak sama sekali, yang memenuhi persyaratan tantangan.Pyth - 13 byte
Dijelaskan:
sumber
&qS*/lQ2"ab
+4
akan diperluas ke+4Q
(pengisian argumen secara implisit)Haskell, 39 byte
Contoh penggunaan:
p "aabb"
->True
.scanl(\s _->'a':s++"b")"ab"x
buat daftar semua["ab", "aabb", "aaabbb", ...]
dengan total(length x)
elemen.elem
memeriksa apakahx
ada dalam daftar ini.sumber
Python,
4340 Bytesmenghubungkan solusi yang jelas berkat Leaky Nun
ide lain, 45 byte:
-4 byte dengan menggunakan len / 2 (saya mendapatkan kesalahan ketika setengahnya terakhir)
sekarang memberi false untuk string kosong
-3 byte terima kasih kepada xnor
sumber
lambda s:list(s)==sorted("ab"*len(s)//2)
(Python 3)lambda s:s=="a"*len(s)//2+"b"*len(s)//2
(Python 3)''<
alih - alihs and
mengesampingkan kasing kosong.