In dem populären (und essentiellen) Informatikbuch Eine Einführung in formale Sprachen und Automaten von Peter Linz wird häufig die folgende formale Sprache angegeben:
hauptsächlich, weil diese Sprache nicht mit endlichen Automaten verarbeitet werden kann. Dieser Ausdruck bedeutet "Sprache L besteht aus allen Folgen von 'a', gefolgt von 'b', in denen die Anzahl von 'a' und 'b' gleich und ungleich Null ist".
Herausforderung
Schreiben Sie ein Arbeitsprogramm / eine Funktion, die eine Zeichenkette erhält, die nur "a" s und "b" s enthält , als Eingabe und gibt einen Wahrheitswert zurück / gibt einen Wahrheitswert aus und sagt, ob diese Zeichenkette gültig ist, die formale Sprache L.
Ihr Programm kann keine externen Berechnungstools verwenden, einschließlich Netzwerk, externe Programme usw. Shells bilden eine Ausnahme von dieser Regel. Bash kann z. B. Befehlszeilendienstprogramme verwenden.
Ihr Programm muss das Ergebnis auf "logische" Weise zurückgeben / ausgeben, z. B. 10 anstelle von 0, Signalton, Ausgabe auf Standardausgabe usw. Weitere Informationen hier.
Es gelten die Standard-Code-Golfregeln.
Dies ist ein Code-Golf . Kürzester Code in Bytes gewinnt. Viel Glück!
Wahrheitstestfälle
"ab"
"aabb"
"aaabbb"
"aaaabbbb"
"aaaaabbbbb"
"aaaaaabbbbbb"
Falsche Testfälle
""
"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"
quelle
empty string == truthy
undnon-empty string == falsy
wäre akzeptabel?a^n b^n
oder ähnlich, anstatt nur die Anzahl dera
s gleich der Anzahl derb
s)Antworten:
MATL ,
54 BytesGibt ein nicht leeres Array von 1 s aus, wenn der String zu L gehört , und ein leeres Array oder ein Array mit 0 s (ansonsten beide falsch).
Vielen Dank an @LuisMendo für das Golfen ab 1 Byte!
Probieren Sie es online!
Wie es funktioniert
quelle
Python 3, 32 Bytes
Ausgabe über Exit-Code : Fehler bei false, kein Fehler bei True.
Die Zeichenfolge wird als Python-Code ausgewertet und ersetzt Parens
(
füra
und)
fürb
. Nur Ausdrücke der Forma^n b^n
werden wohlgeformte Ausdrücke von Klammern((()))
, die das Tupel ergeben()
.Alle nicht übereinstimmenden Parens geben einen Fehler, wie dies auch für mehrere Gruppen der Fall ist
(()())
, da es kein Trennzeichen gibt. Die leere Zeichenfolge schlägt ebenfalls fehl (dies würde am erfolgreich seinexec
).Die Umwandlung
( -> a
,) -> b
erfolgt mitstr.translate
, welche Zeichen ersetzt , wie durch eine Zeichenfolge angegeben, die als Umwandlungstabelle dient. Wenn die Zeichenfolge mit der Länge 100 ") (" * 50 angegeben wird, ordnet die Tabelle die ersten 100 ASCII-Werte zudas dauert
( -> a
,) -> b
. In Python 2 müssen Konvertierungen für alle 256 ASCII-Werte bereitgestellt werden, die"ab"*128
ein Byte länger sind. danke an isaacg für den hinweis.quelle
*128
?128
kann durch50
(oder auch99
) ersetzt werden, um ein Byte zu speichern.Retina , 12 Bytes
Dank an FryAmTheEggman, der diese Lösung unabhängig gefunden hat.
Druckt
1
für gültige Eingabe und0
sonst.Probieren Sie es online!(Die erste Zeile aktiviert eine durch Zeilenvorschub getrennte Testsuite.)
Erläuterung
Balancing Groups erfordern eine teure Syntax. Stattdessen versuche ich, eine gültige Eingabe auf ein einfaches Formular zu reduzieren.
Bühne 1
Das
+
weist Retina an, diese Phase in einer Schleife zu wiederholen, bis sich der Ausgang nicht mehr ändert. Es entspricht entwederab
odera;b
und ersetzt es durch;
. Betrachten wir einige Fälle:a
s und dieb
s in der Zeichenkette nicht in der gleichen Art und Weise ausgeglichen werden , dass(
und)
müssen in der Regel sein, einigea
oderb
im String bleiben, daba
, oderb;a
nicht aufgelöst werden kann und eine einzelnea
oderb
auf eigene kann nicht entweder. Um all dasa
s und dasb
s loszuwerden, muss es eines gebenb
, das dem Recht eines jeden entsprichta
.a
und dasb
nicht alle verschachtelt sind (z. B. wenn wir so etwas wieabab
oder habenaabaabbb
), erhalten wir mehrere;
(und möglicherweise einigea
s undb
s), da die erste Iteration mehrereab
s zum Einfügen findet und weitere Iterationen beibehalten werden die Nummer von;
in der Zeichenfolge.Wenn die Eingabe also genau so aussieht wie die Eingabe in der Form , erhalten wir eine einzige in der Zeichenfolge.
anbn
;
Stufe 2:
Überprüfen Sie, ob die resultierende Zeichenfolge nur ein einzelnes Semikolon enthält. (Wenn ich "check" sage, meine ich "count" die Anzahl der Übereinstimmungen des angegebenen regulären Ausdrucks, aber da dieser reguläre Ausdruck aufgrund der Anker höchstens einmal übereinstimmen kann, gibt dies entweder
0
oder1
.)quelle
Haskell, 31 Bytes
Die Liste Verständnis
[c|c<-"ab",'a'<-s]
macht eine Reihe von einem'a'
für jeden'a'
ins
, gefolgt von einem'b'
für jede'a'
ins
. Es vermeidet das Zählen, indem es auf eine Konstante passt und für jede Übereinstimmung eine Ausgabe erzeugt.Diese Zeichenfolge muss der ursprünglichen Zeichenfolge entsprechen, und die ursprüngliche Zeichenfolge darf nicht leer sein.
quelle
f=g.span id.map(=='a');g(a,b)=or a&&b==(not<$>a)
). Gut gemacht.Schmutz , 12 Bytes
Probieren Sie es online!
Erläuterung
Die erste Zeile definiert ein Nichtterminal
A
, das einem Buchstaben entsprichta
, möglicherweise dem NichtterminalA
und dann einem Buchstabenb
. Die zweite Zeile vergleicht die gesamte Eingabe (e
) mit dem NichtterminalA
.Nicht konkurrierende 8-Byte-Version
Nachdem ich die erste Version dieser Antwort geschrieben hatte, aktualisierte ich Grime,
_
um den Namen des Ausdrucks der obersten Ebene zu übernehmen. Diese Lösung entspricht der obigen, vermeidet jedoch das Wiederholen des EtikettsA
.quelle
Brachylog ,
2319 BytesProbieren Sie es online!
Erläuterung
quelle
05AB1E , 9 Bytes
Code:
Erläuterung:
Die letzten zwei Bytes können verworfen werden, wenn die Eingabe garantiert nicht leer ist.
Verwendet die CP-1252- Codierung. Probieren Sie es online! .
quelle
.M{J¹ÔQ0r
für Sie tun .Gelee , 6 Bytes
Gibt die Zeichenfolge selbst aus, wenn sie zu L gehört oder leer ist, andernfalls 0 .
Probieren Sie es online! oder überprüfen Sie alle Testfälle .
Wie es funktioniert
Alternative Version, 4 Bytes (nicht konkurrierend)
Druckt 1 oder 0 . Probieren Sie es online! oder überprüfen Sie alle Testfälle .
Wie es funktioniert
quelle
J, 17 Bytes
Dies funktioniert korrekt, um Falschgeld für die leere Zeichenfolge zu geben. Fehler ist falsch.
Alte Versionen:
Beweis und Erklärung
Das Hauptverb ist eine Gabelung, die aus diesen drei Verben besteht:
Dies bedeutet, "Je kleiner (
<.
) die Länge (#
) und das Ergebnis der rechten Zinke ((-:'ab'#~-:@#)
)".Die rechte Spur ist ein 4-Zug , bestehend aus:
Lassen Sie sich
k
unsere Eingabe darstellen. Dann ist dies äquivalent zu:-:
ist der Match Operator, also der führende-:
Test für Invarianz unter der Monadengabel'ab' #~ -:@#
.Da der linke Zinken der Gabel ein Verb ist, wird es zu einer konstanten Funktion. Die Gabel entspricht also:
Der rechte Zinken der Gabel halbiert (
-:
) die Länge (#
) vonk
. Beachten Sie#
:Dies gilt
k
nur für gültige Eingaben, daher sind wir hier fertig.#
Fehler für Strings ungerader Länge, die nie die Sprache befriedigen, also sind wir auch fertig.In Kombination mit der kürzeren Länge ergibt die leere Zeichenfolge, die nicht Teil unserer Sprache ist, ihre Länge
0
, und wir sind mit allem fertig.quelle
2&#-:'ab'#~#
dass Sie den Fehler vermeiden und0
stattdessen nur ausgeben sollten, während Sie immer noch 12 Bytes verwenden.Bison / YACC 60 (oder 29) Bytes
(Nun, die Kompilierung für ein YACC-Programm besteht aus ein paar Schritten. Vielleicht möchten Sie einige dazu hinzufügen. Weitere Informationen finden Sie weiter unten.)
Die Funktion sollte ziemlich offensichtlich sein, wenn Sie sie als formale Grammatik interpretieren können. Der Parser akzeptiert entweder
ab
oder eina
gefolgt von einer akzeptablen Sequenz gefolgt von einemb
.Diese Implementierung basiert auf einem Compiler, der K & R-Semantik akzeptiert, um einige Zeichen zu verlieren.
Es ist wortreicher als ich es gerne hätte, wenn ich definieren
yylex
und anrufen müsstegetchar
.Kompilieren mit
(Die meisten Optionen für gcc sind systemspezifisch und sollten nicht gegen die Byteanzahl angerechnet werden. Vielleicht möchten Sie zählen,
-std=c89
wodurch der aufgeführte Wert um 8 erhöht wird.)Laufen Sie mit
oder gleichwertig.
Der Wahrheitswert wird an das Betriebssystem zurückgegeben und Fehler werden auch
syntax error
an die Befehlszeile gemeldet . Wenn ich nur den Teil des Codes zählen kann, der die Parsing-Funktion definiert (das heißt, vernachlässigen Sie die zweite%%
und alles, was folgt), erhalte ich eine Anzahl von 29 Bytes.quelle
Perl 5.10,
3517 Bytes (mit -n Flag)a
Stellt sicher, dass die Zeichenfolge mit " s" beginnt und dann erneut vorkommtb
. Es stimmt nur überein, wenn beide Längen gleich sind.Vielen Dank an Martin Ender für die Halbierung der Byteanzahl und die Einführung in die Rekursion in regulären Ausdrücken: D
Es gibt die gesamte Zeichenfolge zurück, wenn sie übereinstimmt, und nichts, wenn nicht.
Probieren Sie es hier aus!
quelle
$_&&=y/a//==y/b//
(benötigt-p
), ohne den leeren könntest du den&&
für 16 fallen lassen! So nah ...echo -n 'aaabbb'|perl -pe '$_+=y/a//==y/b//'
aber ich kann kein weiteres Byte verschieben ... Vielleicht muss ich das aufgeben!JavaScript,
545544Erstellt einen einfachen regulären Ausdruck basierend auf der Länge des Strings und testet ihn. Für eine Länge von 4 Zeichen (
aabb
) sieht der reguläre Ausdruck folgendermaßen aus:^a{2}b{2}$
Gibt einen wahrheitsgemäßen oder falschen Wert zurück.
Neil hat 11 Bytes gespart.
quelle
f=
kann weggelassen werden.s=>s.match(`^a{${s.length/2}}b+$`)
?C
5753 BytesAlte 57 Byte lange Lösung:
Kompiliert mit gcc v. 4.8.2 @Ubuntu
Danke ugoren für Tips!
Probieren Sie es auf Ideone!
quelle
(t+=2)
zut++++
-1 Byte.t++++
ist kein gültiger C-Code.t+=*s%2*2
und:*s*!1[s]
Retina , 22 Bytes
Eine weitere kürzere Antwort in derselben Sprache ist gerade eingetroffen ...
Probieren Sie es online!
Dies ist ein Schaufenster der Bilanzkreise in Regex, das von Martin Ender ausführlich erklärt wird .
Da meine Erklärung nicht annähernd der Hälfte davon entsprechen würde, werde ich nur darauf verweisen und nicht versuchen, sie zu erklären, da dies den Ruhm seiner Erklärung beeinträchtigen würde.
quelle
Befunge-93, 67 Bytes
Probieren Sie es hier aus! Könnte später erklären, wie es funktioniert. Könnte auch versuchen, ein bisschen mehr Golf zu spielen, nur für Kicks.
quelle
MATL , 9 Bytes
Probieren Sie es online!
Das Ausgabearray ist wahr, wenn es nicht leer ist und alle seine Einträge ungleich Null sind. Sonst ist es falsch. Hier sind einige Beispiele .
quelle
x86-Maschinencode,
2927 BytesHexdump:
Assembler-Code:
Iteriert
a
am Anfang über die Bytes und dann über die folgenden 'b'-Bytes. Die erste Schleife erhöht einen Zähler und die zweite Schleife verringert ihn. Führt danach ein bitweises ODER zwischen den folgenden Bedingungen aus:b
s folgt, nicht 0 ist, stimmt die Zeichenfolge auch nicht übereinDann muss es den Wahrheitswert "invertieren", indem
eax
es auf 0 gesetzt wird, wenn es nicht 0 war, und umgekehrt. Es stellt sich heraus, dass der kürzeste Code dafür der folgende 5-Byte-Code ist, den ich aus der Ausgabe meines C ++ - Compilers gestohlen haberesult = (result == 0)
:quelle
neg eax
das Übertragsflag wie zuvor zu setzen, das Übertragsflagcmc
zu invertieren undsalc
AL auf FFh oder 0 zu setzen, je nachdem, ob das Übertragsflag gesetzt ist oder nicht. Spart 2 Bytes, obwohl dies zu einem 8-Bit-Ergebnis anstelle von 32-Bit führt.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 Bytes
(Dies ist nur die geniale Idee von xnor in Ruby-Form. Meine andere Antwort ist eine Lösung, die ich mir selbst habe.)
Das Programm nimmt die Eingabe, transformiert
a
undb
auf[
und]
sind, und wertet sie aus .Eine gültige Eingabe bildet ein verschachteltes Array, und es geschieht nichts. Ein unausgeglichener Ausdruck bringt das Programm zum Absturz. In Ruby wird leere Eingabe als ausgewertet
nil
, was zum Absturz führt, danil
noch keine*
Methode definiert wurde .quelle
Sed, 38 + 2 = 40 Bytes
Eine nicht leere String-Ausgabe ist wahr
Endliche Zustandsautomaten können das nicht, sagen Sie? Was ist mit Automaten mit endlichen Zuständen und Schleifen ? . : P
Laufen Sie mit
r
undn
Flags.Erläuterung
quelle
JavaScript,
4442Durchgestrichen 44 ist immer noch regulär 44; (
Funktioniert durch Abstreifen rekursiv die äußeren
a
undb
und rekursiv den inneren Wert mit ausgewählten aber.+
. Wenn es keine Übereinstimmung^a.+b$
mehr gibt, ist das Endergebnis, ob die verbleibende Zeichenfolge der genaue Wert istab
.Testfälle:
quelle
ANTLR, 31 Bytes
Verwendet dasselbe Konzept wie die YACC-Antwort von @ dmckee , nur etwas mehr Golf.
Befolgen Sie zum Testen die Schritte im Tutorial Erste Schritte von ANTLR . Fügen Sie dann den obigen Code in eine Datei mit dem Namen ein
A.g4
und führen Sie die folgenden Befehle aus:Dann teste, indem du STDIN eingibst,
grun A r
damit es dir gefällt:Wenn die Eingabe gültig ist, wird nichts ausgegeben. wenn es ungültig ist,
grun
wird einen Fehler geben (entwedertoken recognition error
,extraneous input
,mismatched input
, oderno viable alternative
).Anwendungsbeispiel:
quelle
grammer
Schlüsselwort ist jedoch ein Stinker für das Golfen mit antlr. Ein bisschen wie mit Fortran .C 69 Bytes
69 Bytes:
#define f(s)strlen(s)==2*strcspn(s,"b")&strrchr(s,97)+1==strchr(s,98)
Für Unbekannte:
strlen
bestimmt die Länge der Zeichenkettestrcspn
Gibt den ersten Index in der Zeichenfolge zurück, in dem sich die andere Zeichenfolge befindetstrchr
Gibt einen Zeiger auf das erste Vorkommen eines Zeichens zurückstrrchr
Gibt einen Zeiger auf das letzte Vorkommen eines Zeichens zurückEin großes Dankeschön an Titus!
quelle
>97
anstelle von==98
R,
646155 Bytes,7367 Bytes (robust) oder 46 Bytes (wenn leere Zeichenfolgen zulässig sind)Wiederum wurde xnors Antwort überarbeitet. Wenn die Regeln implizieren, dass die Eingabe aus einer Zeichenfolge von
a
s undb
s besteht, sollte dies funktionieren: Gibt NULL zurück, wenn der Ausdruck gültig ist, Throws und Fehler oder sonst nichts.Wenn die Eingabe nicht robust ist und beispielsweise Müll enthalten kann
aa3bb
, sollte die folgende Version in Betracht gezogen werden (muss zurückgeben)TRUE
für echte Testfälle zurückgegeben werden, nicht NULL):Wenn leere Zeichenfolgen zulässig sind, können wir die Bedingung für nicht leere Eingaben ignorieren:
Wieder NULL, wenn Erfolg, alles andere.
quelle
NULL
), Version 2: einfach nichts (korrekte Eingabe gibt nurTRUE
), Version 3 (unter der Annahme , leere Zeichenfolge sind in Ordnung, als Zustand):NULL
. R ist eine statistische objektorientierte Sprache, die ohne Vorwarnung alles in Ordnung bringt.if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
Japt , 11 Bytes
Probieren Sie es online!
Gibt entweder
true
oderfalse
, außer das""
gibt""
was in JS falsch ist.Ausgepackt und wie es funktioniert
Übernahme aus der MATL-Lösung von Dennis .
quelle
C (Ansi),
6575 BytesGolf gespielt:
Erläuterung:
Setzt einen Wert j und erhöht j für jedes b und verringert j für alles andere. Überprüft, ob der vorherige Buchstabe kleiner oder gleich dem nächsten Buchstaben ist, um zu verhindern, dass abab funktioniert
Bearbeitungen
Überprüfungen für abab Fälle hinzugefügt.
quelle
ba
oderabab
?Batch, 133 Bytes
Gibt
ERRORLEVEL
bei Erfolg eine von 0 und bei Misserfolg eine von 1 zurück. Batch führt keinen Teilstringaustausch für leere Strings durch, daher müssen wir dies im Voraus überprüfen. Wenn ein leerer Parameter zulässig wäre, wäre Zeile 6 nicht erforderlich.quelle
PowerShell v2 +,
6152 BytesNimmt Eingaben
$n
als String, erstellt$x
alshalf the length
. Konstruiert einen-and
booleschen Vergleich zwischen$n
einem-match
Regex-Operator und dem Regex einer gleichen Anzahl vona
's undb
' s. Gibt Boolean$TRUE
oder aus$FALSE
. Das$n-and
ist da, um""
= zu erklären$FALSE
.Alternative 35 Byte
Hierbei wird der reguläre Ausdruck aus Leakys Antwort verwendet , der auf .NET-Bilanzgruppen basiert und nur im PowerShell-
-match
Operator eingekapselt ist . Gibt die Zeichenfolge für "Wahr" oder die leere Zeichenfolge für "Falsch" zurück.quelle
-match
gegen$args[0]
, sonst-match
wird als Filter arbeiten[0]
hier spielen, weil wir nur eine Eingabe haben und wir nur einen Wahrheitswert als Ausgabe brauchen. Da eine leere Zeichenfolge falsch und eine nicht leere Zeichenfolge wahr ist, können wir nach dem Array filtern und entweder die Eingabezeichenfolge oder nichts zurückerhalten, was die Herausforderungsanforderungen erfüllt.Pyth - 13 Bytes
Erklärt:
quelle
&qS*/lQ2"ab
+4
wird erweitert+4Q
(implizites Ausfüllen von Argumenten)Haskell, 39 Bytes
Anwendungsbeispiel:
p "aabb"
->True
.scanl(\s _->'a':s++"b")"ab"x
eine Liste aller baut["ab", "aabb", "aaabbb", ...]
mit insgesamt(length x)
Elementen.elem
prüft obx
in dieser Liste steht.quelle
Python,
4340 Bytesfand die offensichtliche Lösung dank Leaky Nun
andere Idee, 45 Bytes:
-4 Bytes mit len / 2 (ich bekomme eine Fehlermeldung, wenn die Hälfte zuletzt kommt)
Jetzt gibt false für die leere Zeichenfolge
-3 Bytes dank xnor
quelle
lambda s:list(s)==sorted("ab"*len(s)//2)
(Python 3)lambda s:s=="a"*len(s)//2+"b"*len(s)//2
(Python 3)''<
anstatts and
den leeren Fall auszuschließen.