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:
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 golf golfowy . 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"
źródło
empty string == truthy
inon-empty string == falsy
do zaakceptowania?a^n b^n
lub podobna, a nie tylko liczbaa
s równa liczbieb
s)Odpowiedzi:
MATL ,
54 bajtówDrukuje 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
źródło
Python 3, 32 bajty
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
(
dlaa
i)
dlab
. Tylko wyrażenia formya^n b^n
stają 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ę powiedzieexec
).Konwersja
( -> a
,) -> b
odbywa 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 jakoktóra trwa
( -> a
,) -> b
. W Pythonie 2 muszą być dostarczone konwersje dla wszystkich 256 wartości ASCII, wymagające"ab"*128
dłuższego o jeden bajt; dzięki isaacg za zwrócenie na to uwagi.źródło
*128
zrobić?128
można zastąpić50
(lub99
w tym przypadku), aby zapisać bajt.Siatkówka , 12 bajtów
Podziękowania dla FryAmTheEggman, który znalazł to rozwiązanie niezależnie.
Drukuje
1
dla poprawnych danych wejściowych i0
innych.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
+
Mówi Retina powtórzyć ten etap w pętli aż wyjście przestaje się zmieniać. Pasuje doab
luba;b
zastępuje go;
. Rozważmy kilka przypadków:a
S ib
S w struny nie są zrównoważone w taki sam sposób,(
i)
zwykle trzeba być, niektórea
lubb
pozostanie w łańcuchu, ponieważba
albob;a
nie może zostać rozwiązany i pojedynczya
lubb
na własną rękę nie może zarówno. Aby pozbyć się wszystkicha
s ib
s nie musi być jeden odpowiadającyb
na prawo od siebiea
.a
ib
nie są zagnieżdżone (np jeśli mamy coś podobnegoabab
lubaabaabbb
) następnie będziemy skończyć z wielokrotności;
(i potencjalnie niektórea
s orazb
s), ponieważ pierwsza iteracja znajdzie wieluab
s, 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
0
albo1
.)źródło
Haskell, 31 bajtów
Lista zrozumienie
[c|c<-"ab",'a'<-s]
sprawia ciąg jednym'a'
dla każdego'a'
ws
, a następnie jednym'b'
dla każdego'a'
ws
. 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.
źródło
f=g.span id.map(=='a');g(a,b)=or a&&b==(not<$>a)
). Dobra robota.Brud , 12 bajtów
Wypróbuj online!
Wyjaśnienie
Pierwszy wiersz definiuje nieterminal
A
, który pasuje do jednej literya
, być może nieterminalnejA
, a następnie do jednej literyb
. Drugi wiersz dopasowuje całe wejście (e
) do nieterminalaA
.8-bajtowa niekonkurencyjna wersja
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 etykietyA
.źródło
Brachylog ,
2319 bajtówWypróbuj online!
Wyjaśnienie
źródło
05AB1E , 9 bajtów
Kod:
Wyjaśnienie:
Ostatnie dwa bajty można odrzucić, jeśli gwarantowane jest, że dane wejściowe są niepuste.
Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .
źródło
.M{J¹ÔQ0r
dla swojego.Galaretka , 6 bajtów
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
Alternatywna wersja, 4 bajty (niekonkurujące)
Drukuje 1 lub 0 . Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .
Jak to działa
źródło
J, 17 bajtów
Działa to poprawnie, dając falsey dla pustego łańcucha. Błąd to falsey.
Stare wersje:
Dowód i wyjaśnienie
Czasownik główny to rozwidlenie składające się z tych trzech czasowników:
Oznacza to: „Mniejszą (
<.
) długość (#
) i wynik prawego palca ((-:'ab'#~-:@#)
)”.Prawym zębem jest 4-pociągowy , składający się z:
Niech
k
reprezentować nasz wkład. Zatem jest to równoważne z:-:
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:
Prawy ząb widelca dzieli połowę (
-:
) na długość (#
) wynoszącąk
. Obserwuj#
:Teraz dotyczy to
k
tylko 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ść
0
i to wszystko.źródło
2&#-:'ab'#~#
aby pozwolił uniknąć błędu i po prostu wyświetlał dane0
, wciąż używając 12 bajtów.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.)
Ta funkcja powinna być dość oczywista, jeśli umiesz ją interpretować w kategoriach gramatyki formalnej. Analizator składni akceptuje jedną
ab
luba
następującą po niej dowolną akceptowalną sekwencję, po której następuje ab
.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
yylex
i dzwonieniagetchar
.Połącz z
(większość opcji gcc jest specyficzna dla mojego systemu i nie powinna się liczyć z liczbą bajtów; warto policzyć,
-std=c89
co dodaje 8 do podanej wartości).Biegnij z
lub odpowiednik.
Wartość prawdy jest zwracana do systemu operacyjnego, a błędy zgłaszane są również
syntax error
do 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.źródło
Perl 5.10,
3517 bajtów (z flagą -n )Zapewnia, że ciąg zaczyna się od
a
s, a następnie powtarza nab
s. 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!
źródło
$_&&=y/a//==y/b//
(wymaga-p
), bez pustego miejsca możesz upuścić&&
16! Tak blisko ...echo -n 'aaabbb'|perl -pe '$_+=y/a//==y/b//'
ale nie mogę przesunąć kolejnego bajtu ... Może muszę się z tego zrezygnować!JavaScript,
545544Buduje 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.
źródło
f=
Można pominąć.s=>s.match(`^a{${s.length/2}}b+$`)
?C,
5753 bajtówStare rozwiązanie o długości 57 bajtów:
Skompilowane z gcc v. 4.8.2 @Ubuntu
Dzięki ugoren za wskazówki!
Wypróbuj na Ideone!
źródło
(t+=2)
nat++++
na -1 bajt.t++++
nie jest prawidłowym kodem C.t+=*s%2*2
and:*s*!1[s]
Siatkówka , 22 bajty
Właśnie nadeszła kolejna krótsza odpowiedź w tym samym języku ...
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.
źródło
Befunge-93, 67 bajtów
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ęć.
źródło
MATL , 9 bajtów
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 .
źródło
kod maszynowy x86,
2927 bajtówHexdump:
Kod zestawu:
Na początku iteruje
a
bajty, 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:b
s nie jest równy 0, łańcuch również nie pasujeNastę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 ++ dlaresult = (result == 0)
:źródło
neg eax
ustawić flagę przenoszenia jak poprzednio,cmc
odwrócić flagę przenoszenia isalc
ustawić 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.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 bajty
(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
a
ib
na[
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żnil
nie zdefiniowano*
metody.źródło
Sed, 38 + 2 = 40 bajtów
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
r
in
.Wyjaśnienie
źródło
JavaScript,
4442Przekreślone 44 jest nadal regularne 44; (
Prace rekurencyjnie usunięciu zewnętrznej
a
ib
rekurencyjnie 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:
źródło
ANTLR, 31 bajtów
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.g4
i uruchom następujące polecenia:Następnie przetestuj, podając dane wejściowe STDIN, aby
grun A r
:Jeśli dane wejściowe są prawidłowe, nic nie zostanie wyprowadzone; jeżeli jest ona nieważna,
grun
daje błąd (albotoken recognition error
,extraneous input
,mismatched input
, lubno viable alternative
).Przykładowe użycie:
źródło
grammer
Hasło to gnojek do golfa z antlr, choć. Trochę lubię używać fortran .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ńcuchastrcspn
zwraca pierwszy indeks w ciągu, w którym znaleziono drugi ciągstrchr
zwraca wskaźnik do pierwszego wystąpienia znakustrrchr
zwraca wskaźnik do ostatniego wystąpienia znakuOgromne podziękowania dla Tytusa!
źródło
>97
zamiast==98
R,
646155 bajtów,7367 bajtów (solidny) lub 46 bajtów (jeśli dozwolone są puste ciągi)Znów odpowiedź Xnora została przerobiona. Jeśli reguły sugerują, że dane wejściowe będą składać się z ciągu
a
s ib
s, powinno działać: zwraca NULL, jeśli wyrażenie jest poprawne, wyrzuca i błąd lub nic innego.Jeśli dane wejściowe nie są niezawodne i mogą zawierać śmieci, np.
aa3bb
Należy wziąć pod uwagę następującą wersję (należy zwrócićTRUE
dla prawdziwych przypadków testowych, a nie NULL):Wreszcie, jeśli dozwolone są puste ciągi, możemy zignorować warunek dla niepustych danych wejściowych:
Ponownie, NULL, jeśli sukces, cokolwiek innego inaczej.
źródło
NULL
), wersja 2: po prostu nic (prawidłowe wejście zwraca tylkoTRUE
), 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.if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
Japt , 11 bajtów
Wypróbuj online!
Daje albo
true
albofalse
, oprócz tego, że""
daje""
co jest falsy w JS.Rozpakowane i jak to działa
Przyjęty z roztworem Mátl Dennisa .
źródło
C (Ansi),
6575 bajtówGra w golfa:
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.
źródło
ba
lubabab
?Partia, 133 bajty
Zwraca
ERRORLEVEL
0 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.źródło
PowerShell v2 +,
6152 bajtówPobiera dane wejściowe
$n
jako ciąg znaków, tworzy$x
jakohalf the length
. Konstruuje-and
logiczne porównanie$n
i-match
operator wyrażenia regularnego z wyrażeniem regularnym równej liczbya
„ib
”. Wyprowadza wartość logiczną$TRUE
lub$FALSE
.$n-and
Jest tam, aby wyjaśnić""
=$FALSE
.Alternatywnie, 35 bajtów
Wykorzystuje regex z odpowiedzi Leaky , opartej na grupach równoważących .NET, właśnie zamkniętych w
-match
operatorze PowerShell . Zwraca ciąg dla prawdy lub pusty ciąg dla falsey.źródło
-match
przed$args[0]
, w przeciwnym razie-match
będzie działać jako filtr[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.Pyth - 13 bajtów
Wyjaśniono:
źródło
&qS*/lQ2"ab
+4
rozwinie się do+4Q
(niejawne wypełnienie argumentów)Haskell, 39 bajtów
Przykład użycia:
p "aabb"
->True
.scanl(\s _->'a':s++"b")"ab"x
zbudować listę wszystkich["ab", "aabb", "aaabbb", ...]
o łącznej liczbie(length x)
elementów.elem
sprawdza, czyx
jest na tej liście.źródło
Python,
4340 bajtówznalazło oczywiste rozwiązanie dzięki Leaky Nun
inny pomysł, 45 bajtów:
-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
źródło
lambda s:list(s)==sorted("ab"*len(s)//2)
(Python 3)lambda s:s=="a"*len(s)//2+"b"*len(s)//2
(Python 3)''<
zamiasts and
wykluczyć pustą skrzynkę.