Liczba „a” i „b” musi być równa. Masz komputer?


75

W popularnej (i niezbędnej) książce o informatyce An Introduction to Formal Languages ​​and Automata autorstwa Petera Linza często pojawia się następujący język formalny:

definicja

głównie dlatego, że ten język nie może być przetwarzany za pomocą automatów skończonych. Wyrażenie to oznacza „Język L składa się ze wszystkich ciągów„ a ”, po których następuje„ b ”, w których liczba„ a ”i„ b ”jest równa i niezerowa”.

Wyzwanie

Napisz działający program / funkcję, która pobiera ciąg znaków, zawierający tylko „a” i „b” , jako dane wejściowe i zwraca / wyprowadza wartość prawdy , mówiąc, że jeśli ten ciąg jest poprawny w języku formalnym L.

  • Twój program nie może używać żadnych zewnętrznych narzędzi obliczeniowych, w tym sieci, programów zewnętrznych itp. Powłoki są wyjątkiem od tej reguły; Bash np. Może korzystać z narzędzi wiersza poleceń.

  • Twój program musi zwrócić / wyprowadzić wynik w „logiczny” sposób, na przykład: zwrócić 10 zamiast 0, dźwięk „beep”, wyprowadzić na standardowe wyjście itp. Więcej informacji tutaj.

  • Obowiązują standardowe zasady gry w golfa.

To jest . Najkrótszy kod w bajtach wygrywa. Powodzenia!

Prawdziwe przypadki testowe

"ab"
"aabb"
"aaabbb"
"aaaabbbb"
"aaaaabbbbb"
"aaaaaabbbbbb"

Przypadki testowe Falsy

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

24
Czy dane wejściowe mogą być puste? (Mówisz, że to nie jest część języka, ale nie to, czy to wkład, który musimy wziąć pod uwagę.)
Martin Ender

1
Co jeśli nasz język nie ma prawdy ani fałszu? Czy empty string == truthyi non-empty string == falsydo zaakceptowania?
DJMcMayhem

5
Niezłe wyzwanie, ale myślę, że tytuł może być nieco mniej dwuznaczny (np. Wzmianka o a^n b^nlub podobna, a nie tylko liczba as równa liczbie bs)
Sp3000,

1
@ Sp3000 Wybrałem ten tytuł, ponieważ wyglądał zabawnie. Mogę zmienić to później na coś innego ...

1
Jestem trochę zaskoczony, że w ponad 50 odpowiedziach jako jedyny korzystam z generatora pasera. Aby mieć pewność, że nie jest ściśle konkurencyjny pod względem długości, ale problemem jest parsowanie prostego, ale nietrywialnego języka. Bardzo chciałbym zobaczyć odpowiedzi w innych składniach kompilator-kompilator, ponieważ nie znam się na wyborach.
dmckee,

Odpowiedzi:


34

MATL , 5 4 bajtów

tSP-

Drukuje niepustą tablicę 1 s, jeśli ciąg należy do L , a pustą tablicę lub tablicę z 0 s (oba fałsz) w przeciwnym razie.

Dzięki @LuisMendo za grę w golfa na 1 bajcie!

Wypróbuj online!

Jak to działa

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.

6
Moja druga (działająca) odpowiedź MATL. :)
Dennis

2
Dziwna definicja prawdy i fałszu: „aabb” daje -1 -1 1 1 jest prawdą. „aaabb” daje -1 -1 0 1 1 i jest falsy
Etoplay

3
@Etoplay Niepusta tablica ze wszystkimi wartościami niezerowymi jest prawdą. Jest to definicja zastosowana w Matlabie i Oktawie
Luis Mendo,

145

Python 3, 32 bajty

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

Dane wyjściowe za pośrednictwem kodu wyjścia : Błąd dla false, brak błędu dla true.

Ciąg jest oceniany jako kod Pythona, zastępując parens (dla ai )dla b. Tylko wyrażenia formy a^n b^nstają się dobrze sformułowanymi wyrażeniami w nawiasach, takimi jak ((()))ocena do krotki ().

Wszelkie niedopasowane pareny dają błąd, podobnie jak wiele grup (()()), ponieważ nie ma separatora. Pusty ciąg również się nie powiedzie (to się powiedzie exec).

Konwersja ( -> a, ) -> bodbywa się za pomocą str.translate, którego zastępuje znaków wskazanych przez ciąg, który służy jako tabeli konwersji. Biorąc pod uwagę ciąg o długości 100 ”) („ * 50, tabele odwzorowują pierwsze 100 wartości ASCII jako

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

która trwa ( -> a, ) -> b. W Pythonie 2 muszą być dostarczone konwersje dla wszystkich 256 wartości ASCII, wymagające "ab"*128dłuższego o jeden bajt; dzięki isaacg za zwrócenie na to uwagi.


58
Ok, to sprytne.
TLW

Czego *128zrobić?
Erik the Outgolfer

5
128można zastąpić 50(lub 99w tym przypadku), aby zapisać bajt.
isaacg

@ Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ: Myślę, że to kwantyfikator. Ale tak naprawdę nie znam Pythona i nie znalazłem jeszcze żadnej dokumentacji na ten temat.
Tytus

4
@isaacg Dzięki, nie zdawałem sobie sprawy, że zmieniło się to dla Python 3.
xnor

28

Siatkówka , 12 bajtów

Podziękowania dla FryAmTheEggman, który znalazł to rozwiązanie niezależnie.

+`a;?b
;
^;$

Drukuje 1dla poprawnych danych wejściowych i 0innych.

Wypróbuj online! (Pierwszy wiersz włącza pakiet testowy oddzielony od linii).

Wyjaśnienie

Grupy równoważące wymagają kosztownej składni, więc zamiast tego staram się ograniczyć prawidłowe dane wejściowe do prostej formy.

Scena 1

+`a;?b
;

+Mówi Retina powtórzyć ten etap w pętli aż wyjście przestaje się zmieniać. Pasuje do ablub a;bzastępuje go ;. Rozważmy kilka przypadków:

  • Jeśli aS i bS w struny nie są zrównoważone w taki sam sposób, (i )zwykle trzeba być, niektóre alub bpozostanie w łańcuchu, ponieważ baalbo b;anie może zostać rozwiązany i pojedynczy alub bna własną rękę nie może zarówno. Aby pozbyć się wszystkich as i bs nie musi być jeden odpowiadający bna prawo od siebie a.
  • Jeżeli ai bnie są zagnieżdżone (np jeśli mamy coś podobnego abablub aabaabbb) następnie będziemy skończyć z wielokrotności ;(i potencjalnie niektóre as oraz bs), ponieważ pierwsza iteracja znajdzie wielu abs, aby je włożyć i kolejne iteracje zachowa liczba ;w ciągu.

Stąd, jeśli i tylko jeśli dane wejściowe mają formę , otrzymamy jeden ciąg w ciągu.anbn;

Etap 2:

^;$

Sprawdź, czy wynikowy ciąg nie zawiera nic oprócz pojedynczego średnika. (Kiedy mówię „sprawdź”, mam na myśli, „policz liczbę dopasowań podanego wyrażenia regularnego, ale ponieważ to wyrażenie może się zgadzać co najwyżej z powodu zakotwiczeń, daje to albo 0albo 1.)


25

Haskell, 31 bajtów

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

Lista zrozumienie [c|c<-"ab",'a'<-s]sprawia ciąg jednym 'a'dla każdego 'a'w s, a następnie jednym 'b'dla każdego 'a'w s. Unika liczenia, dopasowując stałą i generując wynik dla każdego dopasowania.

Ten ciąg znaków jest sprawdzany, aby był równy oryginalnemu ciągowi, a oryginalny ciąg znaków jest sprawdzany jako niepusty.


To jest urocze. Często zapominam, jak użyteczne jest to, że Haskell porządkuje elementy listy w spójny i bardzo konkretny sposób.
Vectornaut,

O wiele ładniejsza niż moja najlepsza próba ( f=g.span id.map(=='a');g(a,b)=or a&&b==(not<$>a)). Dobra robota.
Jules

Wow, nie wiedziałem, że na podstawie listy można było znaleźć stałą!
rubik

16

Brud , 12 bajtów

A=\aA?\b
e`A

Wypróbuj online!

Wyjaśnienie

Pierwszy wiersz definiuje nieterminal A, który pasuje do jednej litery a, być może nieterminalnej A, a następnie do jednej litery b. Drugi wiersz dopasowuje całe wejście ( e) do nieterminala A.

8-bajtowa niekonkurencyjna wersja

e`\a_?\b

Po napisaniu pierwszej wersji tej odpowiedzi zaktualizowałem Grime, aby traktował go _jako nazwę wyrażenia najwyższego poziomu. To rozwiązanie jest równoważne z powyższym, ale pozwala uniknąć powtarzania etykiety A.


Dlaczego nie zrobiłeś tego w J?
Leaky Nun

@LeakyNun Chciałem tylko pochwalić się Grime. : P
Zgarb,

Zbudowałeś ten język?
Leaky Nun

@LeakyNun Tak. Rozwój jest powolny, ale trwa.
Zgarb,

11

Brachylog , 23 19 bajtów

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

Wypróbuj online!

Wyjaśnienie

@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

8
Gratulujemy wejścia na tryitonline.net!
Leaky Nun

10

05AB1E , 9 bajtów

Kod:

.M{J¹ÔQ0r

Wyjaśnienie:

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

Ostatnie dwa bajty można odrzucić, jeśli gwarantowane jest, że dane wejściowe są niepuste.

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .


Co dzieje się z pustymi danymi wejściowymi?
AdmBorkBork,

2
Poszukaj niezerowej w poście; jest tam :)
Lynn,

@Lynn Czy specyfikacja nie mówi jednak „zero” dla poprawnego języka? Nie chodzi o dane wejściowe.
Emigna,

Prawdziwe. Myślałem źle. Ale nadal możesz zrobić .M{J¹ÔQ0rdla swojego.
Emigna,

@Emigna Dzięki, edytowałem post.
Adnan

9

Galaretka , 6 bajtów

Ṣ=Ṛ¬Pȧ

Drukuje sam łańcuch, jeśli należy do L lub jest pusty, a 0 w przeciwnym razie.

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

Ṣ=Ṛ¬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 == "".

Alternatywna wersja, 4 bajty (niekonkurujące)

ṢnṚȦ

Drukuje 1 lub 0 . Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

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

9

J, 17 bajtów

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

Działa to poprawnie, dając falsey dla pustego łańcucha. Błąd to falsey.

Stare wersje:

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

Dowód i wyjaśnienie

Czasownik główny to rozwidlenie składające się z tych trzech czasowników:

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

Oznacza to: „Mniejszą ( <.) długość ( #) i wynik prawego palca ( (-:'ab'#~-:@#))”.

Prawym zębem jest 4-pociągowy , składający się z:

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

Niech kreprezentować nasz wkład. Zatem jest to równoważne z:

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

-:jest operatorem dopasowania, więc wiodącym -:testem na niezmienność pod widelcem monadycznym 'ab' #~ -:@#.

Ponieważ lewy ząb widelca jest czasownikiem, staje się stałą funkcją. Widelec odpowiada zatem:

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

Prawy ząb widelca dzieli połowę ( -:) na długość ( #) wynoszącą k. Obserwuj #:

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

Teraz dotyczy to ktylko poprawnych danych wejściowych, więc skończymy tutaj. #błędy dla łańcuchów o nieparzystej długości, które nigdy nie odpowiadają językowi, więc już to zrobiliśmy.

W połączeniu z mniejszą długością i tym, pusty ciąg znaków, który nie jest częścią naszego języka, daje jego długość 0i to wszystko.


Zmodyfikowałem go tak, 2&#-:'ab'#~#aby pozwolił uniknąć błędu i po prostu wyświetlał dane 0, wciąż używając 12 bajtów.
mile

@miles Fascynujące! Nigdy tak o tym nie myślałem.
Conor O'Brien

Czy to obsługuje pusty ciąg?
Zgarb,

@Zgarb naprawił to!
Conor O'Brien

9

Bison / YACC 60 (lub 29) bajtów

(Cóż, kompilacja programu YACC składa się z kilku kroków, więc może warto do tego dołączyć. Szczegóły poniżej.)

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

Ta funkcja powinna być dość oczywista, jeśli umiesz ją interpretować w kategoriach gramatyki formalnej. Analizator składni akceptuje jedną ablub anastępującą po niej dowolną akceptowalną sekwencję, po której następuje a b.

Ta implementacja opiera się na kompilatorze, który akceptuje semantykę K&R, aby stracić kilka znaków.

Jest bardziej słaby niż chciałbym z koniecznością definiowania yylexi dzwonienia getchar.

Połącz z

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

(większość opcji gcc jest specyficzna dla mojego systemu i nie powinna się liczyć z liczbą bajtów; warto policzyć, -std=c89co dodaje 8 do podanej wartości).

Biegnij z

$ echo "aabb" | ./equal

lub odpowiednik.

Wartość prawdy jest zwracana do systemu operacyjnego, a błędy zgłaszane są również syntax errordo wiersza poleceń. Jeśli mogę zliczyć tylko część kodu, która definiuje funkcję parsowania (to znaczy pomijam drugą %%i wszystko, co następuje), otrzymuję liczbę 29 bajtów.


7

Perl 5.10, 35 17 bajtów (z flagą -n )

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

Zapewnia, że ​​ciąg zaczyna się od as, a następnie powtarza na bs. Pasuje tylko wtedy, gdy obie długości są równe.

Podziękowania dla Martina Endera za zmniejszenie o połowę liczby bajtów i nauczenie mnie trochę o rekurencji w wyrażeniach regularnych: D

Zwraca cały ciąg, jeśli pasuje, i nic, jeśli nie.

Wypróbuj tutaj!


Najbliższe, którym mogę zarządzać, łącznie z niepustym przypadkiem testowym, to 18 bajtów: $_&&=y/a//==y/b//(wymaga -p), bez pustego miejsca możesz upuścić &&16! Tak blisko ...
Dom Hastings,

1
Mogę zrobić kolejne 17 bajtów: echo -n 'aaabbb'|perl -pe '$_+=y/a//==y/b//'ale nie mogę przesunąć kolejnego bajtu ... Może muszę się z tego zrezygnować!
Dom Hastings,

7

JavaScript, 54 55 44

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

Buduje prosty regex na podstawie długości łańcucha i testuje go. Dla łańcucha o długości 4 ( aabb) wyrażenie regularne wygląda następująco:^a{2}b{2}$

Zwraca wartość true lub falsey.

11 bajtów zapisanych dzięki Neilowi.

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(''))


f=Można pominąć.
Leaky Nun

Czy wyrażenie funkcyjne jest poprawnym przesłaniem, czy też musi być, funkcjonalne?
Scimonster,

Funkcja jest prawidłowym zgłoszeniem.
Leaky Nun

@TimmyD Kiedyś zwracał true, ale teraz zwraca false.
Scimonster,

1
s=>s.match(`^a{${s.length/2}}b+$`)?
l4m2

5

C, 57 53 bajtów

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

Stare rozwiązanie o długości 57 bajtów:

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

Skompilowane z gcc v. 4.8.2 @Ubuntu

Dzięki ugoren za wskazówki!

Wypróbuj na Ideone!


Ponieważ jestem tu nowy i nie mogę jeszcze komentować innych odpowiedzi, chcę tylko zauważyć, że rozwiązanie 62b od @Josh daje fałszywe pozytywne dla ciągów takich jak „aaabab”.
Jasmes

Zmień (t+=2)na t++++na -1 bajt.
owacoder

@owacoder t++++nie jest prawidłowym kodem C.
Jasmes,

Zaoszczędź dzięki t+=*s%2*2and:*s*!1[s]
ugoren,

Bardzo sprytna odpowiedź! Niestety nie powiedzie się na wejściu „ba”: ideone.com/yxixG2
Josh

4

Siatkówka , 22 bajty

Właśnie nadeszła kolejna krótsza odpowiedź w tym samym języku ...

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

Wypróbuj online!

Jest to prezentacja grup równoważących w wyrażeniach regularnych, co w pełni wyjaśnia Martin Ender .

Ponieważ moje wyjaśnienie nie zbliżyłoby się do połowy tego, po prostu połączę się z nim i nie będę próbował wyjaśniać, ponieważ byłoby to szkodliwe dla chwały jego wyjaśnienia.


4

Befunge-93, 67 bajtów

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

Wypróbuj tutaj! Może wyjaśnić, jak to działa później. Być może spróbuję zagrać w golfa jeszcze trochę, tylko dla kopnięć.


3

MATL , 9 bajtów

vHI$e!d1=

Wypróbuj online!

Tablica wyjściowa jest prawdziwa, jeśli nie jest pusta, a wszystkie jej wpisy są niezerowe. W przeciwnym razie jest to fałsz. Oto kilka przykładów .

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

2
To wygodna definicja prawdy. (Wiedziałem o wymaganiu niezerowym, ale nie o wymaganiu niepustym.)
Dennis

3

kod maszynowy x86, 29 27 bajtów

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

Kod zestawu:

    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;

Na początku iteruje abajty, a następnie kolejne bajty „b”. Pierwsza pętla zwiększa licznik, a druga zmniejsza. Następnie wykonuje bitowe LUB między następującymi warunkami:

  1. Jeśli licznik nie ma na końcu 0, łańcuch nie pasuje
  2. Jeśli bajt następujący po sekwencji bs nie jest równy 0, łańcuch również nie pasuje

Następnie musi „odwrócić” wartość prawdy eax- ustaw ją na 0, jeśli nie była równa 0, i odwrotnie. Okazuje się, że najkrótszym kodem do wykonania jest następujący 5-bajtowy kod, który ukradłem z danych wyjściowych mojego kompilatora C ++ dla 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

1
Myślę, że możesz poprawić swoją negację. Spróbuj: neg eaxustawić flagę przenoszenia jak poprzednio, cmcodwrócić flagę przenoszenia i salcustawić AL na FFh lub 0 w zależności od tego, czy flaga przeniesienia jest ustawiona, czy nie. Oszczędza 2 bajty, chociaż kończy się wynikiem 8-bitowym zamiast 32-bitowym.
Jules

To samo dotyczy operacji na łańcuchach znaków, z ESI wskazującymi na łańcuch wejściowy i zwracaniem wyniku w AL (używa SETcc, wymaga 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 Powinieneś zamieścić to w odpowiedzi - jest wystarczająco różny od mojego i podejrzewam, że jest znacznie krótszy!
anatolyg

3

Ruby, 24 bajty

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

(To po prostu genialny pomysł Xnora w formie Ruby. Moja inna odpowiedź to rozwiązanie, które sam wymyśliłem.)

Program trwa wejście, przekształca ai bna [i ]odpowiednio, i ocenia je.

Prawidłowe dane wejściowe utworzą zagnieżdżoną tablicę i nic się nie dzieje. Niezrównoważone wyrażenie spowoduje awarię programu. W Ruby puste dane wejściowe są oceniane jako nil, co spowoduje awarię, ponieważ nilnie zdefiniowano *metody.


3

Sed, 38 + 2 = 40 bajtów

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

Niepuste wyjście łańcuchowe jest zgodne z prawdą

Automaty skończone nie mogą tego zrobić, mówisz? Co z automatami skończonymi z pętlami . : P

Uruchom z flagami ri n.

Wyjaśnienie

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

Niezłe podejście. Dzięki za awarię.
joeytwiddle

3

JavaScript, 44 42

Przekreślone 44 jest nadal regularne 44; (

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

Prace rekurencyjnie usunięciu zewnętrznej ai brekurencyjnie za pomocą wartości wewnętrzną wybrany ale .+. Gdy po ^a.+b$lewej stronie nie ma żadnego dopasowania , końcowym wynikiem jest to, czy pozostały ciąg jest dokładną wartością ab.

Przypadki testowe:

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)

3

ANTLR, 31 bajtów

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

Używa tej samej koncepcji, co odpowiedź YACC @ dmckee , tylko nieco bardziej golfowa.

Aby przetestować, wykonaj czynności opisane w samouczku Wprowadzenie do ANTLR . Następnie umieść powyższy kod w pliku o nazwie A.g4i uruchom następujące polecenia:

$ antlr A.g4
$ javac A*.java

Następnie przetestuj, podając dane wejściowe STDIN, aby grun A r:

$ echo "aaabbb" | grun A r

Jeśli dane wejściowe są prawidłowe, nic nie zostanie wyprowadzone; jeżeli jest ona nieważna, grundaje błąd (albo token recognition error, extraneous input, mismatched input, lub no viable alternative).

Przykładowe użycie:

$ echo "aabb" | grun A r
$ echo "abbb" | grun A r
line 1:2 mismatched input 'b' expecting {<EOF>, '
'}

Sprytna sztuczka polegająca na dodaniu nowego wiersza jako alternatywy w jednej regule. Myślę, że mógłbym również zaoszczędzić kilka w ten sposób w yacc. grammerHasło to gnojek do golfa z antlr, choć. Trochę lubię używać fortran .
dmckee

3

C, 69 bajtów

69 bajtów:

#define f(s)strlen(s)==2*strcspn(s,"b")&strrchr(s,97)+1==strchr(s,98)

Dla osób nieznanych:

  • strlen określa długość łańcucha
  • strcspn zwraca pierwszy indeks w ciągu, w którym znaleziono drugi ciąg
  • strchr zwraca wskaźnik do pierwszego wystąpienia znaku
  • strrchr zwraca wskaźnik do ostatniego wystąpienia znaku

Ogromne podziękowania dla Tytusa!


1
zapisz jeden bajt >97zamiast==98
Tytus

2
Rozwiązanie 61 bajtów daje wynik fałszywie dodatni dla ciągów takich jak „aaabab”. Zobacz ideone.com/nmT8rm
Jasmes

Ach, masz rację Jasmes, dzięki. Będę musiał przemyśleć to trochę.
Josh

Wracając do 69-bajtowego rozwiązania, nie jestem pewien, czy uda mi się skrócić przy użyciu tego podejścia.
Josh

3

R, 64 61 55 bajtów, 73 67 bajtów (solidny) lub 46 bajtów (jeśli dozwolone są puste ciągi)

  1. Znów odpowiedź Xnora została przerobiona. Jeśli reguły sugerują, że dane wejściowe będą składać się z ciągu as i bs, powinno działać: zwraca NULL, jeśli wyrażenie jest poprawne, wyrzuca i błąd lub nic innego.

    if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
    
  2. Jeśli dane wejściowe nie są niezawodne i mogą zawierać śmieci, np. aa3bbNależy wziąć pod uwagę następującą wersję (należy zwrócić TRUEdla prawdziwych przypadków testowych, a nie NULL):

    if(length(y<-scan(,'')))is.null(eval(parse(t=chartr("ab","{}",y))))
    
  3. Wreszcie, jeśli dozwolone są puste ciągi, możemy zignorować warunek dla niepustych danych wejściowych:

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

    Ponownie, NULL, jeśli sukces, cokolwiek innego inaczej.


Nie wiem R, jaki jest twój wynik dla pustych danych wejściowych? (powinno być fałszem)
Tytus

Czy naprawdę nie ma krótszego sposobu na sprawdzenie pustych danych wejściowych?
Tytus

Wersja 1: po prostu nic (prawidłowe wejście zwraca tylko NULL), wersja 2: po prostu nic (prawidłowe wejście zwraca tylko TRUE), wersja 3 (zakładając puste struny są OK, jak państwo): NULL. R to statystyczny zorientowany obiektowo język, w którym wszystko jest w porządku, bez żadnego ostrzeżenia.
Andreï Kostyrka

To (odpowiedź 1) można dodatkowo ulepszyć do 55 bajtów:if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
Giuseppe

3

Japt , 11 bajtów

©¬n eȦUg~Y

Wypróbuj online!

Daje albo truealbo false, oprócz tego, że ""daje ""co jest falsy w JS.

Rozpakowane i jak to działa

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

Przyjęty z roztworem Mátl Dennisa .


2

C (Ansi), 65 75 bajtów

Gra w golfa:

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;}

Wyjaśnienie:

Ustawia wartość j i zwiększa wartość j na każdym b oraz zmniejsza wartość j na czymkolwiek innym. Sprawdzone, czy poprzedni list jest mniejszy lub równy następnemu, więc nie pozwól ababowi działać

Edycje

Dodano kontrole przypadków abab.


Czy to nie da fałszywych trafień na łańcuchy takie jak balub abab?
Zgarb,

Ach tak, źle odczytałem post, ponieważ nie widziałem zdjęcia, ponieważ jest dla mnie zablokowane. Naprawić to!
dj0wns,

2

Partia, 133 bajty

@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

Zwraca ERRORLEVEL0 w przypadku sukcesu, 1 w przypadku niepowodzenia. Batch nie lubi zastępować podciągów na pustych ciągach, więc musimy to sprawdzić z góry; jeśli pusty parametr był zgodny z prawem, wiersz 6 nie byłby potrzebny.


2

PowerShell v2 +, 61 52 bajtów

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

Pobiera dane wejściowe $njako ciąg znaków, tworzy $xjako half the length. Konstruuje -andlogiczne porównanie $ni -matchoperator wyrażenia regularnego z wyrażeniem regularnym równej liczby a„i b”. Wyprowadza wartość logiczną $TRUElub $FALSE. $n-andJest tam, aby wyjaśnić ""= $FALSE.

Alternatywnie, 35 bajtów

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

Wykorzystuje regex z odpowiedzi Leaky , opartej na grupach równoważących .NET, właśnie zamkniętych w -matchoperatorze PowerShell . Zwraca ciąg dla prawdy lub pusty ciąg dla falsey.


W alternatywnej wersji należy ocenić -matchprzed $args[0], w przeciwnym razie -matchbędzie działać jako filtr
Mathias R. Jessen

@ MathiasR.Jessen W kodzie produkcyjnym tak, ale możemy [0]tutaj zagrać w golfa , ponieważ otrzymaliśmy tylko jedno wejście i potrzebujemy tylko jednej wartości true / falsey jako wyniku. Ponieważ pusty ciąg znaków ma wartość falsey, a niepusty ciąg znaków jest zgodny z prawdą, możemy filtrować według tablicy i albo odzyskać ciąg wejściowy, albo nic, co spełnia wymagania wyzwania.
AdmBorkBork

2

Pyth - 13 bajtów

&zqzS*/lz2"ab

Wyjaśniono:

  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

Możesz użyć łańcucha jako danych wejściowych, a następnie uczynić go&qS*/lQ2"ab
Leaky Nun

@LeakyNun dzięki za wskazówkę! Czy możesz wyjaśnić, jak / dlaczego to działa? Po raz pierwszy korzystam z Pyth
Cowabunghole

Na przykład +4rozwinie się do +4Q(niejawne wypełnienie argumentów)
Leaky Nun

2

Haskell, 39 bajtów

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

Przykład użycia: p "aabb"-> True.

scanl(\s _->'a':s++"b")"ab"xzbudować listę wszystkich ["ab", "aabb", "aaabbb", ...]o łącznej liczbie (length x)elementów. elemsprawdza, czy xjest na tej liście.


2

Python, 43 40 bajtów

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

znalazło oczywiste rozwiązanie dzięki Leaky Nun

inny pomysł, 45 bajtów:

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

-4 bajty za pomocą len / 2 (pojawia się błąd, gdy połowa jest ostatnia)

teraz podaje false dla pustego ciągu

-3 bajty dzięki xnor


Tak, lambdas nie muszą być nazwane.
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

tak, zdałem sobie z tego sprawę podczas publikowania. lol, oczywiste rozwiązanie jest krótsze w Pythonie 2:
KarlKastor

1
Możesz zrobić ''<zamiast s andwykluczyć pustą skrzynkę.
xnor
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.