Hitungan "a" dan "b" harus sama. Apakah Anda mendapatkannya komputer?

75

Dalam buku ilmu komputer populer (dan esensial), Pengantar Bahasa Resmi dan Automata oleh Peter Linz, bahasa formal berikut ini sering dinyatakan:

definisi

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 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"
Komunitas
sumber
24
Bisakah input kosong? (Anda mengatakan itu bukan bagian dari bahasa, tetapi bukan apakah itu input yang perlu kita pertimbangkan.)
Martin Ender
1
Bagaimana jika bahasa kita tidak benar atau salah? Apakah empty string == truthydan non-empty string == falsydapat diterima?
DJMcMayhem
5
Tantangan yang bagus, tapi saya pikir judulnya bisa sedikit kurang ambigu (yaitu penyebutan a^n b^natau serupa, daripada hanya jumlah as yang menyamai jumlah bs)
Sp3000
1
@ Sp3000 Saya memilih judul ini karena terlihat menyenangkan. Saya dapat mengubahnya nanti ke sth lain ...
1
Saya sedikit terkejut bahwa dalam 50+ jawaban saya satu-satunya yang menggunakan generator paser. Untuk memastikan itu tidak sepenuhnya kompetitif panjang, tetapi masalah yang ditimbulkan adalah salah satu penguraian bahasa yang sederhana tapi non-sepele. Saya sangat ingin melihat jawaban dalam sintaks kompiler-kompiler lain karena saya tidak banyak tahu pilihan.
dmckee

Jawaban:

34

MATL , 5 4 byte

tSP-

Mencetak 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

t      Push a copy of the implicitly read input.
 S     Sort the copy.
  P    Reverse the sorted copy.
   -   Take the difference of the code point of the corresponding characters
       of the sorted string and the original.
Dennis
sumber
6
MATL jawaban kedua saya (berfungsi). :)
Dennis
2
Definisi aneh tentang kebenaran dan kepalsuan: 'aabb' memberi -1 -1 1 1 adalah kebenaran. 'aaabb' memberi -1 -1 0 1 1 dan
falsy
3
@ Etoplay Array yang tidak kosong dengan semua nilainya bukan nol adalah benar. Ini definisi yang digunakan dalam Matlab dan Oktaf
Luis Mendo
145

Python 3, 32 byte

eval(input().translate(")("*50))

Keluaran melalui kode keluar : Kesalahan untuk false, tidak ada kesalahan untuk True.

String dievaluasi sebagai kode Python, menggantikan parens (untuk adan )untuk b. Hanya ekspresi bentuk yang a^n b^nmenjadi 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 berhasil exec).

Konversi ( -> a, ) -> bselesai menggunakan str.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 sebagai

... Z[\]^_`abc
... )()()()()(

yang 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.

Tidak
sumber
58
Ok, itu pintar.
TLW
Apa yang *128dilakukan?
Erik the Outgolfer
5
128dapat diganti dengan 50(atau 99dalam hal ini) untuk menghemat satu byte.
isaacg
@ Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ: Saya pikir ini adalah penjumlah. Tapi saya tidak terlalu tahu Python dan belum menemukan dokumentasi apa pun tentang itu.
Titus
4
@isaacg Terima kasih, saya tidak menyadari bahwa itu berubah untuk Python 3.
xnor
28

Retina , 12 byte

Penghargaan kepada FryAmTheEggman yang menemukan solusi ini secara mandiri.

+`a;?b
;
^;$

Mencetak 1untuk input yang valid dan 0sebaliknya.

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

+`a;?b
;

The +memberitahu Retina mengulangi tahap ini dalam satu lingkaran sampai output berhenti berubah. Cocok abatau atau a;bmenggantikannya dengan ;. Mari kita pertimbangkan beberapa kasus:

  • Jika as dan bs dalam string tidak seimbang dengan cara yang sama (dan )biasanya perlu, beberapa aatau bakan tetap dalam string, karena ba, atau b;atidak dapat diselesaikan dan satu aatau bsendiri tidak dapat antara. Untuk menyingkirkan semua as dan bs harus ada satu yang sesuai bdengan hak masing-masing a.
  • Jika tanda adan btidak semuanya bersarang (mis. Jika kita memiliki sesuatu seperti ababatau aabaabbb) maka kita akan berakhir dengan banyak ;(dan berpotensi beberapa as dan bs) karena iterasi pertama akan menemukan banyak abs 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 0atau 1.)

Martin Ender
sumber
25

Haskell, 31 byte

f s=s==[c|c<-"ab",'a'<-s]&&s>""

Pemahaman daftar [c|c<-"ab",'a'<-s]membuat string satu 'a'untuk masing-masing 'a'masuk s, diikuti oleh satu 'b'untuk masing-masing 'a'masuk s. 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.

Tidak
sumber
Ini indah. Saya sering lupa betapa bergunanya Haskell memerintahkan elemen-elemen pemahaman daftar dengan cara yang konsisten dan sangat spesifik.
Vectornaut
Jauh lebih bagus daripada upaya terbaik saya ( f=g.span id.map(=='a');g(a,b)=or a&&b==(not<$>a)). Sudah selesai dilakukan dengan baik.
Jules
Wow, saya tidak tahu orang bisa mencocokkan konstanta dalam pemahaman daftar!
rubik
16

Grime , 12 byte

A=\aA?\b
e`A

Cobalah online!

Penjelasan

Baris pertama mendefinisikan nonterminal A, yang cocok dengan satu huruf a, mungkin nonterminal A, dan kemudian satu huruf b. Baris kedua cocok dengan seluruh input ( e) terhadap nonterminal A.

8-byte versi yang tidak bersaing

e`\a_?\b

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 label A.

Zgarb
sumber
Kenapa kau tidak melakukannya di J?
Leaky Nun
@ LeakyNun Saya hanya ingin memamerkan Grime. : P
Zgarb
Anda membangun bahasa ini?
Leaky Nun
@ LeakyNun Ya. Pembangunan lambat, tetapi sedang berlangsung.
Zgarb
11

Brachylog , 23 19 byte

@2L,?lye:"ab"rz:jaL

Cobalah online!

Penjelasan

@2L,                  Split the input in two, the list containing the two halves is L
    ?lye              Take a number I between 0 and the length of the input              
        :"ab"rz       Zip the string "ab" with that number, resulting in [["a":I]:["b":I]]
               :jaL   Apply juxtapose with that zip as input and L as output
                        i.e. "a" concatenated I times to itself makes the first string of L
                        and "b" concatenated I times to itself makes the second string of L
Fatalisasi
sumber
8
Selamat telah mendapatkan di tryitonline.net!
Leaky Nun
10

05AB1E , 9 byte

Kode:

.M{J¹ÔQ0r

Penjelasan:

.M         # Get the most frequent element from the input. If the count is equal, this
           results into ['a', 'b'] or ['b', 'a'].
  {        # Sort this list, which should result into ['a', 'b'].
   J       # Join this list.
    Ô      # Connected uniquified. E.g. "aaabbb" -> "ab" and "aabbaa" -> "aba".
     Q     # Check if both strings are equal.
      0r   # (Print 0 if the input is empty).

Dua byte terakhir dapat dibuang jika inputnya dijamin tidak kosong.

Menggunakan pengkodean CP-1252 . Cobalah online! .

Adnan
sumber
Apa yang terjadi dengan input kosong?
AdmBorkBork
2
Cari yang bukan nol di pos; ada di sana :)
Lynn
@ Lynn Bukankah spec hanya mengatakan tidak-nol untuk bahasa yang valid? Bukan tentang input.
Emigna
Benar. Ada yang salah di sana. Tetapi Anda masih bisa melakukannya .M{J¹ÔQ0runtuk Anda.
Emigna
@Emigna Terima kasih, saya telah mengedit posting.
Adnan
9

Jelly , 6 byte

Ṣ=Ṛ¬Pȧ

Mencetak string itu sendiri jika itu milik L atau kosong, dan 0 sebaliknya.

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

Ṣ=Ṛ¬Pȧ  Main link. Argument: s (string)

Ṣ       Yield s, sorted.
  Ṛ     Yield s, reversed.
 =      Compare each character of sorted s with each character of reversed s.
   ¬    Take the logical NOT of each resulting Boolean.
    P   Take the product of the resulting Booleans.
        This will yield 1 if s ∊ L or s == "", and 0 otherwise.
     ȧ  Take the logical AND with s.
       This will replace 1 with s. Since an empty string is falsy in Jelly,
       the result is still correct if s == "".

Versi alternatif, 4 byte (tidak bersaing)

ṢnṚȦ

Mencetak 1 atau 0 . Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

ṢnṚȦ  Main link. Argument: s (string)

Ṣ     Yield s, sorted.
  Ṛ   Yield s, reversed.
 n    Compare each character of the results, returning 1 iff they're not equal.
   Ȧ  All (Octave-style truthy); return 1 if the list is non-empty and all numbers
      are non-zero, 0 in all other cases.
Dennis
sumber
9

J, 17 byte

#<.(-:'ab'#~-:@#)

Ini berfungsi dengan benar untuk memberikan falsey untuk string kosong. Kesalahan adalah falsey.

Versi lama:

-:'ab'#~-:@#
2&#-:'ab'#~#   NB. thanks to miles

Bukti dan penjelasan

Kata kerja utama adalah garpu yang terdiri dari tiga kata kerja ini:

# <. (-:'ab'#~-:@#)

Ini berarti, "Semakin kecil ( <.) panjang ( #) dan hasil dari tine kanan ( (-:'ab'#~-:@#))".

Tine kanan adalah 4-kereta , yang terdiri dari:

(-:) ('ab') (#~) (-:@#)

Biarkan kmewakili masukan kami. Kemudian, ini setara dengan:

k -: ('ab' #~ -:@#) k

-: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:

'ab' #~ (-:@# k)

Garis kanan dari garpu membagi dua ( -:) panjang ( #) dari k. Amati #:

   1 # 'ab'
'ab'
   2 # 'ab'
'aabb'
   3 # 'ab'
'aaabbb'
   'ab' #~ 3
'aaabbb'

Sekarang, ini khanya 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.

Conor O'Brien
sumber
Saya memodifikasinya menjadi 2&#-:'ab'#~#yang seharusnya membuat Anda menghindari kesalahan dan hanya menghasilkan output 0sementara masih menggunakan 12 byte.
mil
@miles Menarik! Saya tidak pernah memikirkannya seperti itu.
Conor O'Brien
Apakah ini menangani string kosong?
Zgarb
@ Zgarb memperbaikinya!
Conor O'Brien
9

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.)

%%
l:c'\n';
c:'a''b'|'a'c'b';
%%
yylex(){return getchar();}

Fungsi ini harus cukup jelas jika Anda tahu menafsirkannya dalam hal tata bahasa formal. Parser menerima salah satu abatau adiikuti oleh urutan yang dapat diterima diikuti oleh a b.

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 yylexdan memanggil getchar.

Kompilasi dengan

$ yacc equal.yacc
$ gcc -m64 --std=c89 y.tab.c -o equal -L/usr/local/opt/bison/lib/ -ly

(sebagian besar opsi untuk gcc khusus untuk sistem saya dan tidak boleh dihitung terhadap jumlah byte; Anda mungkin ingin menghitung -std=c89yang menambahkan 8 ke nilai yang tercantum).

Jalankan dengan

$ echo "aabb" | ./equal

atau setara.

Nilai kebenaran dikembalikan ke OS dan kesalahan juga dilaporkan syntax errorke 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.

dmckee
sumber
7

Perl 5.10, 35 17 byte (dengan flag -n )

say/^(a(?1)?b)$/

Pastikan string dimulai dengan as dan kemudian berulang pada bs. 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!

Paul Picard
sumber
Paling dekat yang bisa saya kelola termasuk test case non-kosong adalah 18 byte: $_&&=y/a//==y/b//(membutuhkan -p), tanpa kosong Anda bisa menjatuhkan &&16! Begitu dekat ...
Dom Hastings
1
Jadi saya bisa melakukan 17 byte lagi: echo -n 'aaabbb'|perl -pe '$_+=y/a//==y/b//'tapi saya tidak bisa menggeser byte lain ... Mungkin harus menyerah!
Dom Hastings
7

JavaScript, 54 55 44

s=>s&&s.match(`^a{${l=s.length/2}}b{${l}}$`)

Membangun 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.

f=s=>s&&s.match(`^a{${l=s.length/2}}b{${l}}$`)
// true
console.log(f('ab'), !!f('ab'))
console.log(f('aabb'), !!f('aabb'))
console.log(f('aaaaabbbbb'), !!f('aaaaabbbbb'))
// false
console.log(f('a'), !!f('a'))
console.log(f('b'), !!f('b'))
console.log(f('ba'), !!f('ba'))
console.log(f('aaab'), !!f('aaab'))
console.log(f('ababab'), !!f('ababab'))
console.log(f('c'), !!f('c'))
console.log(f('abc'), !!f('abc'))
console.log(f(''), !!f(''))

Scimonster
sumber
The f=dapat dihilangkan.
Leaky Nun
Apakah ekspresi fungsi adalah pengajuan yang valid, atau haruskah itu sebenarnya, ahem, fungsional?
Scimonster
Fungsi adalah pengiriman yang valid.
Leaky Nun
@TimmyD Dulu mengembalikan true, tapi sekarang kembali false.
Scimonster
1
s=>s.match(`^a{${s.length/2}}b+$`)?
14m2
5

C, 57 53 Bytes

t;x(char*s){t+=*s%2*2;return--t?*s&&x(s+1):*s*!1[s];}

Solusi lama 57 byte:

t;x(char*s){*s&1&&(t+=2);return--t?*s&&x(s+1):*s&&!1[s];}

Dikompilasi dengan gcc v. 4.8.2 @Ubuntu

Terima kasih ugoren untuk tipsnya!

Cobalah di Ideone!

Jasmes
sumber
Karena saya baru di sini dan belum dapat mengomentari jawaban lain, saya hanya ingin menunjukkan bahwa solusi 62b dari @Josh memberikan false positive pada string seperti "aaabab".
Jasmes
Ubah (t+=2)ke t++++untuk -1 byte.
owacoder
@owacoder t++++bukan kode C yang valid.
Jasmes
Simpan beberapa dengan t+=*s%2*2dan:*s*!1[s]
ugoren
Jawaban yang sangat pintar! Sayangnya gagal pada input "ba": ideone.com/yxixG2
Josh
4

Retina , 22 byte

Jawaban lain yang lebih pendek dalam bahasa yang sama baru saja datang ...

^(a)+(?<-1>b)+(?(1)c)$

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.

Biarawati Bocor
sumber
4

Befunge-93, 67 byte

0v@.<  0<@.!-$<  >0\v
+>~:0`!#^_:"a" -#^_$ 1
~+1_^#!-"b" _ ^#`0: <

Coba di sini! Bisa jelaskan cara kerjanya nanti. Mungkin juga mencoba untuk golf itu sedikit lebih, hanya untuk iseng.


sumber
3

MATL , 9 byte

vHI$e!d1=

Cobalah online!

Array output benar jika tidak kosong dan semua entri adalah nol. Kalau tidak, itu palsu. Berikut ini beberapa contohnya .

v     % concatenate the stack. Since it's empty, pushes the empty array, []
H     % push 2
I$    % specify three inputs for next function
e     % reshape(input, [], 2): this takes the input implicitly and reshapes it in 2
      % columns in column major order. If the input has odd length a zero is padded at
      % the end. For input 'aaabbb' this gives the 2D char array ['ab;'ab';'ab']
!     % transpose. This gives ['aaa;'bbb']
d     % difference along each column
1=    % test if all elements are 1. If so, that means the first tow contains 'a' and
      % the second 'b'. Implicitly display
Luis Mendo
sumber
2
Itu beberapa definisi yang tepat tentang kebenaran. (Saya tahu tentang persyaratan non-nol, tetapi bukan tentang persyaratan non-kosong.)
Dennis
3

kode mesin x86, 29 27 byte

Hexdump:

33 c0 40 41 80 79 ff 61 74 f8 48 41 80 79 fe 62
74 f8 0a 41 fe f7 d8 1b c0 40 c3

Kode perakitan:

    xor eax, eax;
loop1:
    inc eax;
    inc ecx;
    cmp byte ptr [ecx-1], 'a';
    je loop1;

loop2:
    dec eax;
    inc ecx;
    cmp byte ptr [ecx-2], 'b';
    je loop2;

    or al, [ecx-2];
    neg eax;
    sbb eax, eax;
    inc eax;
done:
    ret;

Iterasi atas abyte pada awalnya, lalu atas byte 'b' berikut. Loop pertama meningkatkan penghitung, dan loop kedua menguranginya. Setelah itu, lakukan bitwise ATAU antara kondisi berikut:

  1. Jika penghitung tidak 0 pada akhirnya, string tidak cocok
  2. Jika byte yang mengikuti urutan bs bukan 0, string juga tidak cocok

Kemudian, 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 untuk result = (result == 0):

    neg eax;      // negate eax; set C flag to 1 if it was nonzero
    sbb eax, eax; // subtract eax and the C flag from eax
    inc eax;      // increase eax
anatolyg
sumber
1
Saya pikir Anda dapat meningkatkan negasi Anda. Coba: neg eaxuntuk mengatur flag carry seperti sebelumnya, cmcuntuk membalik flag carry dan salcuntuk 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.
Jules
Hal yang sama menggunakan ops string, dengan ESI menunjuk ke input string, dan mengembalikan hasilnya dalam AL (menggunakan SETcc, membutuhkan 386+):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
ninjalj
@ninjalj Anda harus memposting itu dalam jawaban - itu cukup berbeda dari saya, dan saya kira secara signifikan lebih pendek!
anatolyg
3

Ruby, 24 byte

eval(gets.tr'ab','[]')*1

(Ini hanya ide brilian xnor dalam bentuk Ruby. Jawaban saya yang lain adalah solusi yang sebenarnya saya buat sendiri.)

Program mengambil input, mentransformasikan adan bke 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 karena nilbelum menentukan *metode.

daniero
sumber
3

Sed, 38 + 2 = 40 byte

s/.*/c&d/;:x;s/ca(.*)bd/c\1d/;tx;/cd/p

Output string yang tidak kosong benar

Automata negara terbatas tidak bisa melakukan ini, katamu? Bagaimana dengan automata keadaan terbatas dengan loop . : P

Jalankan dengan rdan nbendera.

Penjelasan

s/.*/c&d/        #Wrap the input in 'c' and 'd' (used as markers)
:x               #Define a label named 'x'
s/ca(.*)bd/c\1d/ #Deletes 'a's preceded by 'c's and equivalently for 'b's and 'd's. This shifts the markers to the center
tx               #If the previous substitution was made, jump to label x
/cd/p            #If the markers are next to one another, print the string
seseorang dengan pc
sumber
Pendekatan yang bagus. Terima kasih atas gangguannya.
joeytwiddle
3

JavaScript, 44 42

Dicoret 44 masih teratur 44; (

f=s=>(z=s.match`^a(.+)b$`)?f(z[1]):s=="ab"

Bekerja dengan rekursif melucuti luar adan bdan 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 tepat ab.

Kasus uji:

console.log(["ab","aabb","aaabbb","aaaabbbb","aaaaabbbbb","aaaaaabbbbbb"].every(f) == true)
console.log(["","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"].some(f) == false)
apsillers
sumber
3

ANTLR, 31 byte

grammar A;r:'ab'|'a'r'b'|r'\n';

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.g4dan jalankan perintah ini:

$ antlr A.g4
$ javac A*.java

Kemudian uji dengan memberikan input pada STDIN agar grun A rseperti:

$ echo "aaabbb" | grun A r

Jika input valid, tidak ada yang akan dihasilkan; jika tidak valid, grunakan memberikan kesalahan (baik token recognition error, extraneous input, mismatched input, atau no viable alternative).

Contoh penggunaan:

$ echo "aabb" | grun A r
$ echo "abbb" | grun A r
line 1:2 mismatched input 'b' expecting {<EOF>, '
'}
Tembaga
sumber
Trik cerdas menambahkan baris baru sebagai alternatif dalam satu aturan. Saya pikir saya bisa menghemat beberapa cara di yacc juga. Kata grammerkunci ini lebih buruk untuk bermain golf dengan antlr. Agak suka menggunakan fortran .
dmckee
3

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 string
  • strcspn mengembalikan indeks pertama dalam string di mana string lain ditemukan
  • strchr mengembalikan pointer ke kemunculan pertama karakter
  • strrchr mengembalikan pointer ke kemunculan karakter terakhir

Terima kasih banyak untuk Titus!

Josh
sumber
1
simpan satu byte dengan >97bukannya==98
Titus
2
Solusi 61 byte memberikan false positive pada string seperti "aaabab". Lihat ideone.com/nmT8rm
Jasmes
Ah Anda benar Jasmes, terima kasih. Saya harus memikirkan kembali ini sedikit.
Josh
Mengembalikan kembali ke solusi 69 byte, tidak yakin apakah saya bisa mendapatkan lebih pendek menggunakan pendekatan ini.
Josh
3

R, 64 61 55 byte, 73 67 byte (kuat) atau 46 byte (jika string kosong diizinkan)

  1. Sekali lagi, jawaban xnor dikerjakan ulang. Jika tersirat oleh aturan bahwa input akan terdiri dari string as dan bs, itu harus berfungsi: mengembalikan NULL jika ekspresi valid, melempar dan kesalahan atau tidak sama sekali.

    if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
    
  2. Jika input tidak kuat dan mungkin mengandung beberapa sampah, misalnya aa3bb, maka versi berikut harus dipertimbangkan (harus mengembalikan TRUEuntuk kasus uji yang benar, bukan NULL):

    if(length(y<-scan(,'')))is.null(eval(parse(t=chartr("ab","{}",y))))
    
  3. Akhirnya, jika string kosong diizinkan, kita dapat mengabaikan kondisi untuk input tidak kosong:

    eval(parse(text=chartr("ab","{}",scan(,''))))
    

    Sekali lagi, NULL jika sukses, apa pun sebaliknya.

Andreï Kostyrka
sumber
Saya tidak tahu R, apa hasil Anda untuk input kosong? (harus palsu)
Titus
Apakah benar-benar tidak ada cara yang lebih singkat untuk menguji input kosong?
Titus
Versi 1: hanya apa-apa (input yang benar mengembalikan hanya NULL), versi 2: hanya apa-apa (input yang benar mengembalikan hanya TRUE), versi 3 (dengan asumsi string kosong adalah OK, sebagai negara): NULL. R adalah bahasa berorientasi objek statistik yang typecasts semuanya OK, tanpa peringatan.
Andreï Kostyrka
Ini (jawaban 1) dapat lebih ditingkatkan menjadi 55 byte:if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
Giuseppe
3

Japt , 11 byte

©¬n eȦUg~Y

Cobalah online!

Memberi salah satu trueatau false, kecuali yang ""memberi ""yang palsu di JS.

Dibongkar & Cara kerjanya

U&&Uq n eXYZ{X!=Ug~Y

U&&     The input string is not empty, and...
Uq n    Convert to array of chars and sort
eXYZ{   Does every element satisfy...?
X!=       The sorted char does not equal...
Ug~Y      the char at the same position on the original string reversed

Diadopsi dari solusi MATL Dennis .

Bubbler
sumber
2

C (Ansi), 65 75 Bytes

Golf:

l(b,i,j,k)char*b;{for(i=j=0;(k=b[i++])>0&k<=b[i];)j+=2*(k>97)-1;return !j;}

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.

dj0wns
sumber
Tidakkah ini akan memberikan hasil positif palsu pada string seperti baatau abab?
Zgarb
Ahh ya, saya salah membaca posting karena saya tidak bisa melihat gambarnya karena sudah diblokir untuk saya. Memperbaikinya!
dj0wns
2

Batch, 133 byte

@if ""=="%1" exit/b1        Fail if the input is empty
@set a=%1                   Grab the input into a variable for processing
@set b=%a:ab=%              Remove all `ab` substrings
@if "%a%"=="%b%" exit/b1    Fail if we didn't remove anything
@if not %a%==a%b%b exit/b1  Fail if we removed more than one `ab`
@if ""=="%b%" exit/b0       Success if there's nothing left to check
@%0 %b%                     Rinse and repeat

Mengembalikan nilai ERRORLEVEL0 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.

Neil
sumber
2

PowerShell v2 +, 61 52 byte

param($n)$x=$n.length/2;$n-and$n-match"^a{$x}b{$x}$"

Mengambil input $nsebagai string, membuat $xsebagai half the length. Membangun -andperbandingan Boolean antara $ndan -matchoperator regex terhadap regex dengan jumlah yang sama dari adan b. Output Boolean $TRUEatau $FALSE. Apakah $n-andada untuk memperhitungkan ""= $FALSE.

Alternatif, 35 byte

$args-match'^(a)+(?<-1>b)+(?(1)c)$'

Ini menggunakan regex dari jawaban Leaky , berdasarkan pada kelompok penyeimbang .NET, baru saja dienkapsulasi dalam -matchoperator PowerShell . Mengembalikan string untuk kebenaran, atau string kosong untuk falsey.

AdmBorkBork
sumber
Dalam versi alternatif Anda harus mengevaluasi -matchterhadap $args[0], jika tidak -matchakan berfungsi sebagai filter
Mathias R. Jessen
@ MathiasR.Jessen Dalam kode produksi, ya, tapi kita bisa bermain golf di [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.
AdmBorkBork
2

Pyth - 13 byte

&zqzS*/lz2"ab

Dijelaskan:

  qz          #is input equal to
          "ab #the string "ab"
     *        #multiplied by
      /lz2    #length of input / 2
    S         #and sorted?
&z            #(implicitly) print if the above is true and z is not empty
Cowabunghole
sumber
Anda dapat menggunakan string sebagai input dan kemudian membuatnya&qS*/lQ2"ab
Leaky Nun
@ LeakyNun terima kasih atas tipnya! Bisakah Anda menjelaskan bagaimana / mengapa itu berhasil? Ini adalah pertama kalinya saya menggunakan Pyth
Cowabunghole
Misalnya, +4akan diperluas ke +4Q(pengisian argumen secara implisit)
Leaky Nun
2

Haskell, 39 byte

p x=elem x$scanl(\s _->'a':s++"b")"ab"x

Contoh penggunaan: p "aabb"-> True.

scanl(\s _->'a':s++"b")"ab"xbuat daftar semua ["ab", "aabb", "aaabbb", ...]dengan total (length x)elemen. elemmemeriksa apakah xada dalam daftar ini.

nimi
sumber
2

Python, 43 40 Bytes

lambda s:''<s==len(s)/2*"a"+len(s)/2*"b"

menghubungkan solusi yang jelas berkat Leaky Nun

ide lain, 45 byte:

lambda s:s and list(s)==sorted(len(s)/2*"ab")

-4 byte dengan menggunakan len / 2 (saya mendapatkan kesalahan ketika setengahnya terakhir)

sekarang memberi false untuk string kosong

-3 byte terima kasih kepada xnor

KarlKastor
sumber
Ya, lambdas tidak harus disebutkan namanya.
Leaky Nun
lambda s:list(s)==sorted("ab"*len(s)//2)(Python 3)
Leaky Nun
lambda s:s=="a"*len(s)//2+"b"*len(s)//2(Python 3)
Leaky Nun
ya, saya menyadari itu ketika mempostingnya. lol, solusi yang jelas lebih pendek dalam Python 2:
KarlKastor
1
Anda dapat melakukan ''<alih - alih s andmengesampingkan kasing kosong.
xnor