Die Anzahl von "a" und "b" muss gleich sein. Hast du es am Computer bekommen?

75

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:

Definition

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 . 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"
Gemeinschaft
quelle
24
Kann die Eingabe leer sein? (Sie sagen, es ist nicht Teil der Sprache, aber nicht, ob es eine Eingabe ist, die wir berücksichtigen müssen.)
Martin Ender
1
Was ist, wenn unsere Sprache nicht wahr oder falsch ist? Wäre empty string == truthyund non-empty string == falsywäre akzeptabel?
DJMcMayhem
5
Schöne Herausforderung, aber ich denke, der Titel könnte ein wenig weniger zweideutig sein (dh eine Erwähnung von a^n b^noder ähnlich, anstatt nur die Anzahl der as gleich der Anzahl der bs)
Sp3000
1
@ Sp3000 Ich habe diesen Titel gewählt, weil er lustig aussah. Ich kann es später zu etwas anderem ändern ...
1
Ich bin ein wenig überrascht, dass ich bei über 50 Antworten der einzige bin, der einen Pasergenerator verwendet. Um sicherzugehen, dass die Länge nicht streng konkurrenzfähig ist, aber das Problem ist das Parsen einer einfachen, aber nicht trivialen Sprache. Ich würde sehr gerne Antworten in anderen Compiler-Compiler-Syntaxen sehen, da ich mit den Auswahlmöglichkeiten nicht sehr vertraut bin.
DMCKEE

Antworten:

34

MATL , 5 4 Bytes

tSP-

Gibt 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

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
quelle
6
Meine zweite (funktionierende) MATL-Antwort. :)
Dennis
2
Seltsame Definition von Wahrhaftigkeit und Falschheit: 'aabb' gibt -1 -1 1 1 ist wahr. 'aaabb' gibt -1 -1 0 1 1 und ist falsch
Etoplay
3
@Etoplay Ein nicht leeres Array mit all seinen Werten ungleich Null ist wahr. Es ist die Definition in Matlab und Octave verwendet
Luis Mendo
145

Python 3, 32 Bytes

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

Ausgabe über Exit-Code : Fehler bei false, kein Fehler bei True.

Die Zeichenfolge wird als Python-Code ausgewertet und ersetzt Parens (für aund )für b. Nur Ausdrücke der Form a^n b^nwerden 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 sein exec).

Die Umwandlung ( -> a, ) -> berfolgt mit str.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 zu

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

das dauert ( -> a, ) -> b. In Python 2 müssen Konvertierungen für alle 256 ASCII-Werte bereitgestellt werden, die "ab"*128ein Byte länger sind. danke an isaacg für den hinweis.

xnor
quelle
58
Ok, das ist klug.
TLW
Was macht der *128?
Erik der Outgolfer
5
128kann durch 50(oder auch 99) ersetzt werden, um ein Byte zu speichern.
Isaacg
@ Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ: Ich denke, es ist ein Quantifizierer. Aber ich kenne Python nicht wirklich und habe noch keine Dokumentation dazu gefunden.
Titus
4
@isaacg Danke, mir war nicht bewusst, dass sich das für Python 3 geändert hat.
xnor
28

Retina , 12 Bytes

Dank an FryAmTheEggman, der diese Lösung unabhängig gefunden hat.

+`a;?b
;
^;$

Druckt 1 für gültige Eingabe und 0sonst.

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

+`a;?b
;

Das +weist Retina an, diese Phase in einer Schleife zu wiederholen, bis sich der Ausgang nicht mehr ändert. Es entspricht entweder aboder a;bund ersetzt es durch ;. Betrachten wir einige Fälle:

  • Wenn die as und die bs in der Zeichenkette nicht in der gleichen Art und Weise ausgeglichen werden , dass (und )müssen in der Regel sein, einige aoder bim String bleiben, da ba, oder b;anicht aufgelöst werden kann und eine einzelne aoder bauf eigene kann nicht entweder. Um all das as und das bs loszuwerden, muss es eines geben b, das dem Recht eines jeden entspricht a.
  • Wenn das aund das bnicht alle verschachtelt sind (z. B. wenn wir so etwas wie ababoder haben aabaabbb), erhalten wir mehrere ;(und möglicherweise einige as und bs), da die erste Iteration mehrere abs 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 0oder 1.)

Martin Ender
quelle
25

Haskell, 31 Bytes

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

Die Liste Verständnis [c|c<-"ab",'a'<-s]macht eine Reihe von einem 'a'für jeden 'a'in s, gefolgt von einem 'b'für jede 'a'in s. 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.

xnor
quelle
Das ist schön. Ich vergesse oft, wie nützlich es ist, dass Haskell die Elemente eines Listenverständnisses auf eine konsistente und sehr spezifische Weise anordnet.
Vectornaut
Viel schöner als mein bester Versuch ( f=g.span id.map(=='a');g(a,b)=or a&&b==(not<$>a)). Gut gemacht.
Jules
Wow, ich wusste nicht, dass man eine Konstante in einer Liste verstehen kann!
Rubik
16

Schmutz , 12 Bytes

A=\aA?\b
e`A

Probieren Sie es online!

Erläuterung

Die erste Zeile definiert ein Nichtterminal A, das einem Buchstaben entspricht a, möglicherweise dem Nichtterminal Aund dann einem Buchstaben b. Die zweite Zeile vergleicht die gesamte Eingabe ( e) mit dem NichtterminalA .

Nicht konkurrierende 8-Byte-Version

e`\a_?\b

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

Zgarb
quelle
Warum hast du es nicht in J gemacht?
Undichte Nonne
@LeakyNun Ich wollte nur Grime vorführen. : P
Zgarb
Du hast diese Sprache gebaut?
Undichte Nonne
@LeakyNun Ja. Die Entwicklung ist langsam, aber kontinuierlich.
Zgarb
11

Brachylog , 23 19 Bytes

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

Probieren Sie es online!

Erläuterung

@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
Tödlich
quelle
8
Herzlichen Glückwunsch zum Einstieg bei tryitonline.net!
Undichte Nonne
10

05AB1E , 9 Bytes

Code:

.M{J¹ÔQ0r

Erläuterung:

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

Die letzten zwei Bytes können verworfen werden, wenn die Eingabe garantiert nicht leer ist.

Verwendet die CP-1252- Codierung. Probieren Sie es online! .

Adnan
quelle
Was passiert mit leerer Eingabe?
AdmBorkBork
2
Suchen Sie im Beitrag nach einem Wert ungleich Null . Es ist da drin :)
Lynn
@Lynn Sagt die Spezifikation nicht nur für eine gültige Sprache Null? Nicht über die Eingabe.
Emigna
Wahr. Dachte da falsch. Aber Sie können immer noch .M{J¹ÔQ0rfür Sie tun .
Emigna
@Emigna Danke, ich habe den Beitrag bearbeitet.
Adnan
9

Gelee , 6 Bytes

Ṣ=Ṛ¬Pȧ

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

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

Alternative Version, 4 Bytes (nicht konkurrierend)

ṢnṚȦ

Druckt 1 oder 0 . Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

Ṣ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
quelle
9

J, 17 Bytes

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

Dies funktioniert korrekt, um Falschgeld für die leere Zeichenfolge zu geben. Fehler ist falsch.

Alte Versionen:

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

Beweis und Erklärung

Das Hauptverb ist eine Gabelung, die aus diesen drei Verben besteht:

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

Dies bedeutet, "Je kleiner ( <.) die Länge ( #) und das Ergebnis der rechten Zinke ( (-:'ab'#~-:@#))".

Die rechte Spur ist ein 4-Zug , bestehend aus:

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

Lassen Sie sich kunsere Eingabe darstellen. Dann ist dies äquivalent zu:

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

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

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

Der rechte Zinken der Gabel halbiert ( -:) die Länge ( #) von k. Beachten Sie #:

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

Dies gilt knur 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.

Conor O'Brien
quelle
Ich habe es so geändert, 2&#-:'ab'#~#dass Sie den Fehler vermeiden und 0stattdessen nur ausgeben sollten, während Sie immer noch 12 Bytes verwenden.
Meilen
@miles Faszinierend! Ich habe nie so darüber nachgedacht.
Conor O'Brien
Behandelt dies die leere Zeichenfolge?
Zgarb
@Zgarb hat es behoben!
Conor O'Brien
9

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

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

Die Funktion sollte ziemlich offensichtlich sein, wenn Sie sie als formale Grammatik interpretieren können. Der Parser akzeptiert entweder aboder ein agefolgt 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 yylexund anrufen müsste getchar.

Kompilieren mit

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

(Die meisten Optionen für gcc sind systemspezifisch und sollten nicht gegen die Byteanzahl angerechnet werden. Vielleicht möchten Sie zählen, -std=c89wodurch der aufgeführte Wert um 8 erhöht wird.)

Laufen Sie mit

$ echo "aabb" | ./equal

oder gleichwertig.

Der Wahrheitswert wird an das Betriebssystem zurückgegeben und Fehler werden auch syntax erroran 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.

dmckee
quelle
7

Perl 5.10, 35 17 Bytes (mit -n Flag)

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

aStellt 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!

Paul Picard
quelle
Am nächsten komme ich damit zurecht, dass der nicht leere Testfall 18 Bytes umfasst: $_&&=y/a//==y/b//(benötigt -p), ohne den leeren könntest du den &&für 16 fallen lassen! So nah ...
Dom Hastings
1
Also kann ich noch 17 Bytes machen: echo -n 'aaabbb'|perl -pe '$_+=y/a//==y/b//'aber ich kann kein weiteres Byte verschieben ... Vielleicht muss ich das aufgeben!
Dom Hastings
7

JavaScript, 54 55 44

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

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

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
quelle
Das f=kann weggelassen werden.
Undichte Nonne
Ist ein Funktionsausdruck eine gültige Übermittlung oder muss sie tatsächlich funktionieren?
Scimonster
Eine Funktion ist eine gültige Übermittlung.
Undichte Nonne
@TimmyD Früher wurde true zurückgegeben, jetzt wird false zurückgegeben.
Scimonster
1
s=>s.match(`^a{${s.length/2}}b+$`)?
14.
5

C 57 53 Bytes

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

Alte 57 Byte lange Lösung:

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

Kompiliert mit gcc v. 4.8.2 @Ubuntu

Danke ugoren für Tips!

Probieren Sie es auf Ideone!

Jasmes
quelle
Da ich hier neu bin und andere Antworten noch nicht kommentieren kann, möchte ich nur darauf hinweisen, dass die 62b-Lösung von @Josh bei Zeichenfolgen wie "aaabab" falsch positiv ist.
Jasmes
Wechseln Sie (t+=2)zu t++++-1 Byte.
Owacoder
@owacoder t++++ist kein gültiger C-Code.
Jasmes
Sparen Sie einige mit t+=*s%2*2und:*s*!1[s]
ugoren
Sehr clevere Antwort! Bei Eingabe von "ba" schlägt
Josh
4

Retina , 22 Bytes

Eine weitere kürzere Antwort in derselben Sprache ist gerade eingetroffen ...

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

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.

Undichte Nonne
quelle
4

Befunge-93, 67 Bytes

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

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
3

MATL , 9 Bytes

vHI$e!d1=

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 .

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
quelle
2
Das ist eine bequeme Definition von Wahrheit. (Ich wusste über die Nicht-Null-Anforderung Bescheid, aber nicht über die Nicht-Leer-Anforderung.)
Dennis
3

x86-Maschinencode, 29 27 Bytes

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

Assembler-Code:

    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;

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

  1. Wenn der Zähler am Ende nicht 0 ist, stimmt die Zeichenfolge nicht überein
  2. Wenn das Byte, das der Folge von bs folgt, nicht 0 ist, stimmt die Zeichenfolge auch nicht überein

Dann muss es den Wahrheitswert "invertieren", indem eaxes 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 habe 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
quelle
1
Ich denke, Sie können Ihre Verneinung verbessern. Versuchen Sie: neg eaxdas Übertragsflag wie zuvor zu setzen, das Übertragsflag cmczu invertieren und salcAL 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.
Jules
Dasselbe gilt für string ops, wobei ESI auf die Eingabezeichenfolge zeigt und das Ergebnis in AL zurückgibt (SETcc verwendet, erfordert 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 Du solltest das in einer Antwort posten - es ist ausreichend anders als meine und ich vermute, es ist bedeutend kürzer!
Anatolyg
3

Ruby, 24 Bytes

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

(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 aund bauf [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, da nilnoch keine *Methode definiert wurde .

daniero
quelle
3

Sed, 38 + 2 = 40 Bytes

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

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 rund nFlags.

Erläuterung

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
jemandemmitpc
quelle
Netter Ansatz. Danke für die Panne.
Joeytwiddle
3

JavaScript, 44 42

Durchgestrichen 44 ist immer noch regulär 44; (

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

Funktioniert durch Abstreifen rekursiv die äußeren aund bund 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 ist ab.

Testfälle:

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
quelle
3

ANTLR, 31 Bytes

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

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.g4und führen Sie die folgenden Befehle aus:

$ antlr A.g4
$ javac A*.java

Dann teste, indem du STDIN eingibst, grun A rdamit es dir gefällt:

$ echo "aaabbb" | grun A r

Wenn die Eingabe gültig ist, wird nichts ausgegeben. wenn es ungültig ist, grunwird einen Fehler geben (entweder token recognition error, extraneous input, mismatched input, oder no viable alternative).

Anwendungsbeispiel:

$ echo "aabb" | grun A r
$ echo "abbb" | grun A r
line 1:2 mismatched input 'b' expecting {<EOF>, '
'}
Kupfer
quelle
Cleverer Trick, der die neue Zeile als Alternative in einer einzigen Regel hinzufügt. Ich denke, ich könnte auch ein paar auf diese Weise in yacc retten. Das grammerSchlüsselwort ist jedoch ein Stinker für das Golfen mit antlr. Ein bisschen wie mit Fortran .
DMCKEE
3

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 Zeichenkette
  • strcspn Gibt den ersten Index in der Zeichenfolge zurück, in dem sich die andere Zeichenfolge befindet
  • strchr Gibt einen Zeiger auf das erste Vorkommen eines Zeichens zurück
  • strrchr Gibt einen Zeiger auf das letzte Vorkommen eines Zeichens zurück

Ein großes Dankeschön an Titus!

Josh
quelle
1
Speichern Sie ein Byte mit >97anstelle von==98
Titus
2
Die 61-Byte-Lösung gibt für Zeichenfolgen wie "aaabab" ein falsches Positiv aus. Siehe ideone.com/nmT8rm
Jasmes
Ah, du hast Recht, Jasmes, danke. Ich muss das ein wenig überdenken.
Josh
Ich kehre zu der 69-Byte-Lösung zurück und bin mir nicht sicher, ob ich mit diesem Ansatz eine kürzere Lösung finden kann.
Josh
3

R, 64 61 55 Bytes, 73 67 Bytes (robust) oder 46 Bytes (wenn leere Zeichenfolgen zulässig sind)

  1. Wiederum wurde xnors Antwort überarbeitet. Wenn die Regeln implizieren, dass die Eingabe aus einer Zeichenfolge von as und bs besteht, sollte dies funktionieren: Gibt NULL zurück, wenn der Ausdruck gültig ist, Throws und Fehler oder sonst nichts.

    if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
    
  2. 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):

    if(length(y<-scan(,'')))is.null(eval(parse(t=chartr("ab","{}",y))))
    
  3. Wenn leere Zeichenfolgen zulässig sind, können wir die Bedingung für nicht leere Eingaben ignorieren:

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

    Wieder NULL, wenn Erfolg, alles andere.

Andreï Kostyrka
quelle
Ich weiß nicht R, was ist dein Ergebnis für leere Eingaben? (Sollte falsch sein)
Titus
Gibt es wirklich keinen kürzeren Weg, um auf Leereingaben zu testen?
Titus
Version 1: einfach nichts (korrekte Eingabe gibt nur NULL), Version 2: einfach nichts (korrekte Eingabe gibt nur TRUE), 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.
Andreï Kostyrka
Dies (Antwort 1) kann weiter auf 55 Bytes verbessert werden:if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
Giuseppe
3

Japt , 11 Bytes

©¬n eȦUg~Y

Probieren Sie es online!

Gibt entweder trueoder false, außer das"" gibt"" was in JS falsch ist.

Ausgepackt und wie es funktioniert

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

Übernahme aus der MATL-Lösung von Dennis .

Bubbler
quelle
2

C (Ansi), 65 75 Bytes

Golf gespielt:

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

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.

dj0wns
quelle
Gibt das nicht falsch positive Ergebnisse für Zeichenfolgen wie baoder abab?
Zgarb
Ahh ja, ich habe den Beitrag falsch gelesen, da ich das Bild nicht sehen konnte, da es für mich gesperrt ist. Es reparieren!
dj0wns
2

Batch, 133 Bytes

@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

Gibt ERRORLEVELbei 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.

Neil
quelle
2

PowerShell v2 +, 61 52 Bytes

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

Nimmt Eingaben $nals String, erstellt $xals half the length. Konstruiert einen -andbooleschen Vergleich zwischen $neinem -matchRegex-Operator und dem Regex einer gleichen Anzahl von a's und b' s. Gibt Boolean $TRUEoder aus $FALSE. Das $n-andist da, um ""= zu erklären $FALSE.

Alternative 35 Byte

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

Hierbei wird der reguläre Ausdruck aus Leakys Antwort verwendet , der auf .NET-Bilanzgruppen basiert und nur im PowerShell- -matchOperator eingekapselt ist . Gibt die Zeichenfolge für "Wahr" oder die leere Zeichenfolge für "Falsch" zurück.

AdmBorkBork
quelle
In der alternativen Version , die Sie bewerten sollten -matchgegen $args[0], sonst -matchwird als Filter arbeiten
Mathias R. Jessen
@ MathiasR.Jessen Im Produktionscode, ja, aber wir können das [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.
AdmBorkBork
2

Pyth - 13 Bytes

&zqzS*/lz2"ab

Erklärt:

  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
quelle
Sie können eine Zeichenfolge als Eingabe verwenden und diese dann erstellen&qS*/lQ2"ab
Leaky Nun
@LeakyNun danke für den Tipp! Können Sie erklären, wie / warum das funktioniert? Dies ist mein erstes Mal, dass ich Pyth
Cowabunghole
Zum Beispiel +4wird erweitert +4Q(implizites Ausfüllen von Argumenten)
Leaky Nun
2

Haskell, 39 Bytes

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

Anwendungsbeispiel: p "aabb"-> True.

scanl(\s _->'a':s++"b")"ab"xeine Liste aller baut ["ab", "aabb", "aaabbb", ...]mit insgesamt (length x)Elementen. elemprüft ob xin dieser Liste steht.

nimi
quelle
2

Python, 43 40 Bytes

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

fand die offensichtliche Lösung dank Leaky Nun

andere Idee, 45 Bytes:

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

-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

KarlKastor
quelle
Ja, Lambdas müssen nicht benannt werden.
Undichte Nonne
lambda s:list(s)==sorted("ab"*len(s)//2)(Python 3)
Undichte Nonne
lambda s:s=="a"*len(s)//2+"b"*len(s)//2(Python 3)
Undichte Nonne
Ja, das wurde mir beim Posten klar. Lol, die offensichtliche Lösung ist in Python 2 kürzer:
KarlKastor
1
Sie können dies tun, ''<anstatt s andden leeren Fall auszuschließen.
xnor