Le nombre de "a" et de "b" doit être égal. Avez-vous eu l'ordinateur?

75

Dans le livre d'informatique populaire (et essentiel), Une introduction aux langages formels et aux automates de Peter Linz, le langage formel suivant est fréquemment mentionné:

définition

principalement parce que ce langage ne peut pas être traité avec des automates à états finis. Cette expression signifie "La langue L consiste en toutes les chaînes de 'a suivies de' b's, dans lesquelles le nombre de 'a et de b est égal et non nul".

Défi

Ecrivez un programme / fonction de travail qui obtient une chaîne contenant uniquement "a" s et "b" s , puis renvoie / renvoie une valeur de vérité , en indiquant si cette chaîne est valide le langage formel L.

  • Votre programme ne peut utiliser aucun outil de calcul externe, y compris réseau, programmes externes, etc. Les shells sont une exception à cette règle; Bash, par exemple, peut utiliser des utilitaires de ligne de commande.

  • Votre programme doit renvoyer / afficher le résultat de manière "logique", par exemple: renvoyer 10 au lieu de 0, "bip", émettre vers stdout, etc. Pour plus d'informations, cliquez ici.

  • Les règles de golf standard sont appliquées.

Ceci est un . Le code le plus court en octets gagne. Bonne chance!

Cas de test de vérité

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

Cas de tests de fausseté

""
"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"
Communauté
la source
24
L' entrée peut-elle être vide? (Vous dites que cela ne fait pas partie de la langue, mais ne vous demandez pas si c'est une contribution à prendre en compte.)
Martin Ender
1
Et si notre langue n'a pas la vérité ou la fausseté? Serait empty string == truthyet non-empty string == falsyserait acceptable?
DJMcMayhem
5
Beau défi, mais je pense que le titre pourrait être un peu moins ambigu (c'est-à-dire une mention de a^n b^nou similaire, plutôt que juste le nombre de as égal au nombre de bs)
Sp3000
1
@ Sp3000 J'ai choisi ce titre parce qu'il avait l'air amusant. Je pourrais le changer plus tard pour qch sinon ...
1
Je suis un peu surpris que dans plus de 50 réponses, je suis le seul à utiliser un générateur de paser. Certes, la longueur n’est pas strictement concurrentielle, mais le problème consiste à analyser un langage simple mais non trivial. J'aimerais beaucoup voir des réponses dans d'autres syntaxes compilateur-compilateur car je ne suis pas très familiarisé avec les choix.
dmckee

Réponses:

34

MATL , 5 4 octets

tSP-

Imprime un tableau non vide de 1 s si la chaîne appartient à L , et un tableau vide ou un tableau avec 0 s (les deux sont faussés) sinon.

Merci à @LuisMendo pour le golf d'un octet!

Essayez-le en ligne!

Comment ça fonctionne

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
la source
6
Ma deuxième réponse (de travail) MATL. :)
Dennis
2
Étrange définition de la vérité et de la fausseté: 'aabb' donne -1 -1 1 1 est la vérité. 'aaabb' donne -1 -1 0 1 1 et est faux
Etoplay
3
@Etoplay Un tableau non vide avec toutes ses valeurs non nulles est la vérité. C'est la définition utilisée dans Matlab et Octave
Luis Mendo
145

Python 3, 32 octets

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

Sorties via le code de sortie : erreur pour faux, pas d'erreur pour vrai.

La chaîne est évaluée en tant que code Python, remplaçant les parenthèses (pour aet )pour b. Seules les expressions de la forme a^n b^ndeviennent des expressions bien formées de parenthèses telles que ((())), évaluées au tuple ().

Toute parenthèse mal assortie donne une erreur, de même que plusieurs groupes (()()), comme il n'y a pas de séparateur. La chaîne vide échoue également (elle réussirait exec).

La conversion ( -> a, ) -> best effectuée à l' aide str.translate, qui remplace les caractères comme indiqué par une chaîne qui sert de table de conversion. Étant donné la chaîne de 100 "" ("* 50), les tableaux mappent les 100 premières valeurs ASCII en tant que

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

qui prend ( -> a, ) -> b. Dans Python 2, les conversions pour toutes les 256 valeurs ASCII doivent être fournies, nécessitant "ab"*128un octet de plus; merci à isaacg pour l'avoir signalé.

Xnor
la source
58
Ok, c'est malin.
TLW
Qu'est-ce que le *128fait?
Erik the Outgolfer
5
128peut être remplacé par 50(ou 99d'ailleurs) pour sauvegarder un octet.
isaacg
@ Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ: Je pense que c'est un quantificateur. Mais je ne connais pas vraiment Python et je n’ai pas encore trouvé de documentation à ce sujet.
Titus
4
@isaacg Merci, je n'étais pas au courant de ce changement pour Python 3.
xnor
28

Rétine , 12 octets

Crédits à FryAmTheEggman qui a trouvé cette solution de manière indépendante.

+`a;?b
;
^;$

Imprime 1pour une entrée valide et 0autre.

Essayez-le en ligne! (La première ligne active une suite de tests séparée par saut de ligne.)

Explication

L'équilibrage des groupes nécessite une syntaxe coûteuse. J'essaie donc de réduire une entrée valide à un simple formulaire.

Étape 1

+`a;?b
;

Le +dit à Retina de répéter cette étape dans une boucle jusqu'à ce que la sortie cesse de changer. Il correspond à ou abou le a;bremplace par ;. Considérons quelques cas:

  • Si les as et les bs dans la chaîne ne sont pas équilibrés de la même manière que (et )doivent normalement être, certains aou bresteront dans la chaîne, car ba, ou b;ane peut pas être résolu et un seul aou bsur son propre ne peut pas Soit. Pour se débarrasser de tous les as et bs, il doit en exister un qui corresponde bà la droite de chacun a.
  • Si les aet bne sont pas tous imbriqués (par exemple si nous avons quelque chose comme ababou aabaabbb), nous nous retrouverons avec plusieurs ;(et potentiellement quelques as et bs), car la première itération trouvera plusieurs abs pour les insérer et les autres itérations seront préservées. le nombre de ;dans la chaîne.

Par conséquent, si et seulement si l'entrée est de la forme , nous en aurons un seul dans la chaîne.anbn;

Étape 2:

^;$

Vérifiez si la chaîne obtenue ne contient qu'un seul point-virgule. (Quand je dis "cocher" je veux dire en fait, "compte le nombre de correspondances de la regex donnée, mais puisque cette regex peut correspondre au maximum une fois en raison des ancres, cela donne l'un 0ou l' autre 1.)

Martin Ender
la source
25

Haskell, 31 octets

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

La compréhension de la liste [c|c<-"ab",'a'<-s]fait une chaîne d'un 'a'pour chaque 'a'en s, suivi d'un 'b'pour chaque 'a'en s. Cela évite de compter en faisant correspondre une constante et en produisant une sortie pour chaque correspondance.

Cette chaîne est vérifiée pour être égale à la chaîne d'origine et la chaîne d'origine est vérifiée pour être non-vide.

Xnor
la source
C'est adorable. J'oublie souvent à quel point il est utile que Haskell ordonne les éléments d'une liste de manière cohérente et très spécifique.
Vectornaut
Bien mieux que ma meilleure tentative ( f=g.span id.map(=='a');g(a,b)=or a&&b==(not<$>a)). Bien joué.
Jules
Wow, je ne savais pas que l'on pouvait correspondre à une constante dans une liste de compréhension!
rubik
16

Grime , 12 octets

A=\aA?\b
e`A

Essayez-le en ligne!

Explication

La première ligne définit un non terminal A, qui correspond à une lettre a, éventuellement le non terminal A, et ensuite à une lettre b. La deuxième ligne correspond à l'entrée entière ( e) par rapport au terminal A.

Version non compétitive de 8 octets

e`\a_?\b

Après avoir écrit la première version de cette réponse, j'ai mis à jour Grime afin qu'il prenne en compte _le nom de l'expression de niveau supérieur. Cette solution est équivalente à la précédente, mais évite de répéter l’étiquette A.

Zgarb
la source
Pourquoi ne l'as-tu pas fait en J?
Leaky Nun
@ LeakyNun Je voulais juste montrer Grime. : P
Zgarb
Vous avez construit cette langue?
Leaky Nun
@ LeakyNun Oui. Le développement est lent, mais en cours.
Zgarb
11

Brachylog , 23 19 octets

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

Essayez-le en ligne!

Explication

@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
Fataliser
la source
8
Félicitations pour avoir essayé tryitonline.net!
Leaky Nun
10

05AB1E , 9 octets

Code:

.M{J¹ÔQ0r

Explication:

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

Les deux derniers octets peuvent être supprimés s'il est garanti que l'entrée est non vide.

Utilise le codage CP-1252 . Essayez-le en ligne! .

Adnan
la source
Que se passe-t-il avec une entrée vide?
AdmBorkBork
2
Cherchez non-nul dans le post; c'est là-bas :)
Lynn
@ Lynn La spécification ne dit-elle pas seulement non-zéro pour une langue valide? Pas à propos de l'entrée.
Emigna
Vrai. Pensée mal là. Mais vous pouvez toujours faire .M{J¹ÔQ0rpour le vôtre.
Emigna
@ Emigna Merci, j'ai édité le post.
Adnan
9

Gelée , 6 octets

Ṣ=Ṛ¬Pȧ

Imprime la chaîne elle-même si elle appartient à L ou est vide, et 0 sinon.

Essayez-le en ligne! ou vérifier tous les cas de test .

Comment ça fonctionne

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

Version alternative, 4 octets (non concurrente)

ṢnṚȦ

Imprime 1 ou 0 . Essayez-le en ligne! ou vérifier tous les cas de test .

Comment ça fonctionne

Ṣ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
la source
9

J, 17 octets

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

Cela fonctionne correctement pour donner falsey à la chaîne vide. L'erreur est falsey.

Anciennes versions:

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

Preuve et explication

Le verbe principal est un fork composé de ces trois verbes:

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

Cela signifie "le moindre de ( <.) la longueur ( #) et le résultat de la tine droite ( (-:'ab'#~-:@#))".

La dent droite est un train à 4 trains , composé de:

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

Laissons kreprésenter notre contribution. Ensuite, cela équivaut à:

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

-:est l'opérateur de correspondance, donc les principaux -:tests d'invariance sous la fourche monadique 'ab' #~ -:@#.

Puisque la dent gauche de la fourche est un verbe, elle devient une fonction constante. Donc, la fourchette équivaut à:

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

La dent droite de la fourche réduit de moitié ( -:) la longueur ( #) de k. Observez #:

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

Maintenant, cela kne concerne que les entrées valides, nous avons donc terminé ici. #des erreurs pour des chaînes de longueur impaire, qui ne satisfont jamais la langue, nous avons donc également terminé.

Combinée avec le moindre de la longueur et celle-ci, la chaîne vide, qui ne fait pas partie de notre langage, donne sa longueur 0, et nous en avons terminé avec tout.

Conor O'Brien
la source
Je l'ai modifié, ce 2&#-:'ab'#~#qui devrait vous permettre d'éviter l'erreur et de générer une sortie 0tout en utilisant 12 octets.
miles
@miles fascinant! Je n'y ai jamais pensé comme ça.
Conor O'Brien
Est-ce que cela gère la chaîne vide?
Zgarb
@Zgarb l'a corrigé!
Conor O'Brien
9

Bison / YACC 60 (ou 29) octets

(Eh bien, la compilation d'un programme YACC se fait en deux étapes. Vous voudrez peut-être en inclure quelques-unes. Voir les détails ci-dessous.)

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

La fonction devrait être assez évidente si vous savez l’interpréter en termes de grammaire formelle. L'analyseur accepte soit abun asuivi suivi de toute séquence acceptable suivi d'un point b.

Cette implémentation repose sur un compilateur qui accepte la sémantique de K & R pour perdre quelques caractères.

C'est plus mot que je voudrais avec la nécessité de définir yylexet d'appeler getchar.

Compiler avec

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

(la plupart des options de gcc sont spécifiques à mon système et ne doivent pas être comptées dans le nombre d'octets; vous pouvez vouloir compter -std=c89ce qui ajoute 8 à la valeur indiquée).

Courir avec

$ echo "aabb" | ./equal

ou équivalent.

La valeur de vérité est renvoyée au système d'exploitation et les erreurs sont également signalées syntax errorà la ligne de commande. Si je ne peux compter que la partie du code qui définit la fonction d'analyse (c'est-à-dire négliger la seconde %%et tout ce qui suit), j'obtiens un compte de 29 octets.

dmckee
la source
7

Perl 5.10, 35 17 octets (avec l' indicateur -n )

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

Garantit que la chaîne commence par as, puis se répète sur bs. Il ne correspond que si les deux longueurs sont égales.

Merci à Martin Ender pour avoir réduit de moitié le nombre d'octets et m'avoir appris un peu plus sur la récursion dans les regexes: D

Il renvoie la chaîne entière si elle correspond, et rien sinon.

Essayez-le ici!

Paul picard
la source
Le plus proche que je puisse gérer, y compris le cas de test non vide est de 18 octets: $_&&=y/a//==y/b//(nécessite -p), sans le vide, vous pouvez déposer le &&pour 16! Si proche ...
Dom Hastings
1
Donc, je peux faire 17 octets supplémentaires: echo -n 'aaabbb'|perl -pe '$_+=y/a//==y/b//'mais je ne peux pas décaler un autre octet ... Il faudrait peut-être abandonner cela!
Dom Hastings
7

JavaScript, 54 55 44

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

Construit un regex simple basé sur la longueur de la chaîne et le teste. Pour une longueur de 4 chaînes ( aabb), l'expression régulière ressemble à ceci:^a{2}b{2}$

Renvoie une valeur de vérité ou de falsey.

11 octets sauvés grâce à 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
la source
Le f=peut être omis.
Leaky Nun
Une expression de fonction est-elle une soumission valide ou doit-elle réellement être fonctionnelle?
Scimonster
Une fonction est une soumission valide.
Leaky Nun
@TimmyD Cela retournait vrai, mais maintenant ça retourne faux.
Scimonster
1
s=>s.match(`^a{${s.length/2}}b+$`)?
l4m2
5

C, 57 53 octets

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

Ancienne solution longue de 57 octets:

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

Compilé avec gcc v. 4.8.2 @ Ubuntu

Merci Ugoren pour les conseils!

Essayez-le sur Ideone!

Jasmes
la source
Puisque je suis nouveau ici et que je ne peux pas encore commenter d’autres réponses, je tiens simplement à souligner que la solution 62b de @Josh donne des résultats faussement positifs sur des chaînes telles que "aaabab".
Jasmes
Passez (t+=2)à t++++-1 octet.
owacoder
@owacoder t++++n'est pas un code C valide.
Jasmes
Économisez avec t+=*s%2*2et:*s*!1[s]
ugoren le
Réponse très intelligente! Il échoue malheureusement sur l'entrée "ba": ideone.com/yxixG2
Josh
4

Rétine , 22 octets

Une autre réponse plus courte dans la même langue est arrivée ...

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

Essayez-le en ligne!

Ceci est une vitrine des groupes d'équilibrage dans regex, ce qui est expliqué en détail par Martin Ender .

Comme mon explication ne serait pas proche de la moitié de celle-ci, je me contenterai de la relier et de ne pas tenter de l'expliquer, car cela nuirait à la gloire de son explication.

Fuite Nun
la source
4

Befunge-93, 67 octets

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

Essayez-le ici! Peut-être expliquer comment cela fonctionne plus tard. Peut-être aussi essayer de jouer au golf juste un peu plus, juste pour les coups de pied.


la source
3

MATL , 9 octets

vHI$e!d1=

Essayez-le en ligne!

Le tableau en sortie est véridique s'il est non vide et que toutes ses entrées sont non nulles. Sinon c'est de la fausseté. Voici quelques exemples .

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
la source
2
C'est une définition commode de la vérité. (Je connaissais l'exigence de non-zéro, mais pas celle non-vide.)
Dennis
3

code machine x86, 29 à 27 octets

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

Code d'assemblage:

    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;

Itère sur les aoctets au début, puis sur les octets 'b' suivants. La première boucle augmente le compteur et la seconde le diminue. Ensuite, effectuez un OU au niveau du bit entre les conditions suivantes:

  1. Si le compteur n'est pas 0 à la fin, la chaîne ne correspond pas
  2. Si l'octet qui suit la séquence de bs n'est pas 0, la chaîne ne correspond pas non plus

Ensuite, il doit "inverser" la valeur de vérité en le eaxmettant à 0 si ce n'est pas 0, et vice versa. Il s'avère que le code le plus court est le code à 5 octets suivant, que j'ai volé dans la sortie de mon compilateur C ++ pour 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
la source
1
Je pense que vous pouvez améliorer votre négation. Essayez: neg eaxpour définir l’indicateur de retenue comme avant, cmcpour inverser l’indicateur de retenue et salcréglez AL sur FFh ou 0 selon que l’indicateur de retenue est activé ou non. Enregistre 2 octets, bien que le résultat obtenu soit un résultat sur 8 bits plutôt que sur 32 bits.
Jules
La même chose en utilisant string ops, avec ESI pointant sur la chaîne d'entrée et renvoyant le résultat en AL (utilise SETcc, nécessite 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 Vous devriez poster cela dans une réponse - c'est suffisamment différent de la mienne, et je suppose que c'est beaucoup plus court!
Anatolyg
3

Ruby, 24 octets

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

(Ce n'est que la brillante idée de xnor sous la forme ruby. Mon autre réponse est une solution que je me suis proposée.)

Le programme prend l'entrée, se transforme aet bà [et ]respectivement, et l' évalue.

Une entrée valide formera un tableau imbriqué et rien ne se passe. Une expression déséquilibrée fera planter le programme. En Ruby, l'entrée vide est évaluée en tant que nil, ce qui plantera car nilaucune *méthode n'a été définie .

Daniero
la source
3

Sed, 38 + 2 = 40 octets

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

Une sortie de chaîne non vide est vérité

Les automates finis ne peuvent pas faire cela, vous dites? Qu'en est-il des automates à états finis avec des boucles . : P

Courir avec ret des ndrapeaux.

Explication

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
quelqu'un avecpc
la source
Belle approche. Merci pour la ventilation.
joeytwiddle
3

JavaScript, 44 42

44 barré est toujours régulier 44;

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

Fonctionne en supprimant récursivement l'extérieur aet bet de manière récursive en utilisant la valeur interne sélectionnée, mais .+. Lorsqu'il n'y a pas de correspondance à ^a.+b$gauche, le résultat final est de savoir si la chaîne restante est la valeur exacte ab.

Cas de test:

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
la source
3

ANTLR, 31 octets

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

Utilise le même concept que la réponse YACC de @ dmckee , juste un peu plus joué.

Pour tester, suivez les étapes du didacticiel de prise en main d'ANTLR . Ensuite, placez le code ci-dessus dans un fichier nommé A.g4et exécutez les commandes suivantes:

$ antlr A.g4
$ javac A*.java

Puis testez en donnant une entrée sur STDIN pour grun A raimer ainsi:

$ echo "aaabbb" | grun A r

Si l'entrée est valide, rien ne sera généré. si elle est invalide, grundonnera une erreur (soit token recognition error, extraneous input, mismatched inputou no viable alternative).

Exemple d'utilisation:

$ echo "aabb" | grun A r
$ echo "abbb" | grun A r
line 1:2 mismatched input 'b' expecting {<EOF>, '
'}
Cuivre
la source
Astuce astucieuse: ajouter la nouvelle ligne comme alternative dans une seule règle. Je pense que je pourrais en économiser quelques-uns de cette façon à Yacc aussi. Le grammermot-clé est un frein au golf avec antlr, cependant. Un peu comme utiliser fortran .
dmckee
3

C, 69 octets

69 octets:

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

Pour les inconnus:

  • strlen détermine la longueur de la chaîne
  • strcspn renvoie le premier index de la chaîne où l'autre chaîne est trouvée
  • strchr renvoie un pointeur sur la première occurrence d'un caractère
  • strrchr renvoie un pointeur sur la dernière occurrence d'un caractère

Un grand merci à Titus!

Josh
la source
1
économiser un octet avec >97au lieu de==98
Titus
2
La solution de 61 octets donne des résultats faussement positifs sur des chaînes telles que "aaabab". Voir ideone.com/nmT8rm
Jasmes Le
Ah tu as raison Jasmes, merci. Je vais devoir repenser cela un peu.
Josh
Revenons à la solution de 69 octets, ne sachant pas si je peux être plus court avec cette approche.
Josh
3

R, 64 61 55 octets, 73 67 octets (robuste) ou 46 octets (si les chaînes vides sont autorisées)

  1. Encore une fois, la réponse de xnor retravaillée. Si les règles impliquent que l'entrée se compose d'une chaîne de as et de bs, cela devrait fonctionner: renvoie NULL si l'expression est valide, renvoie et erreur ou rien sinon.

    if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
    
  2. Si l'entrée n'est pas robuste et peut contenir des erreurs, par exemple aa3bb, la version suivante doit être considérée (doit renvoyer TRUEpour les vrais tests, pas NULL):

    if(length(y<-scan(,'')))is.null(eval(parse(t=chartr("ab","{}",y))))
    
  3. Enfin, si les chaînes vides sont autorisées, nous pouvons ignorer la condition pour une entrée non vide:

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

    Encore une fois, NULL en cas de succès, tout le reste.

Andreï Kostyrka
la source
Je ne sais pas R, quel est votre résultat pour une entrée vide? (devrait être faux)
Titus
N'y a-t-il vraiment pas de moyen plus court de tester l'entrée vide?
Titus
Version 1: juste rien (entrée correcte renvoie uniquement NULL), la version 2: il suffit de rien (retourne entrée correcte uniquement TRUE), la version 3 ( en supposant que les chaînes vides sont OK, comme état): NULL. R est un langage statistique orienté objet qui permet de tout dactylographier correctement, sans aucun avertissement.
Andreï Kostyrka
Cela (réponse 1) peut être encore amélioré à 55 octets:if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
Giuseppe
3

Japt , 11 octets

©¬n eȦUg~Y

Essayez-le en ligne!

Donne soit trueou false, sauf que ""donne"" qui est la fausseté dans JS.

Déballé et comment ça marche

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

Adopté de la solution MATL de Dennis .

Barboteur
la source
2

C (Ansi), 65 à 75 octets

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

Explication:

Définit une valeur j et incrémente j sur chaque b et décrémente j sur toute autre chose. Vérifié si la lettre précédente est inférieure ou égale à la lettre suivante afin d'éviter que l'abab ne fonctionne

Édite

Ajout de contrôles pour les cas d'abab.

dj0wns
la source
Est-ce que cela ne donnera pas de faux positifs sur des chaînes comme baou abab?
Zgarb
Ahh oui, j'ai mal lu le message car je ne pouvais pas voir la photo car elle est bloquée pour moi. Le réparer!
dj0wns
2

Lot, 133 octets

@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

Retourne un ERRORLEVEL0 en cas de succès, 1 en cas d'échec. Batch n'aime pas faire de remplacement de sous-chaîne sur des chaînes vides, nous devons donc vérifier cela d'avance; si un paramètre vide était légal, la ligne 6 ne serait pas nécessaire.

Neil
la source
2

PowerShell v2 +, 61 52 octets

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

Prend l'entrée $nsous forme de chaîne, crée en $xtant que half the length. Constructions une -andcomparaison booléenne entre $nun -matchopérateur de regex et le regex d'un nombre égal de a'et de b'. Sorties Booléenne $TRUEou $FALSE. Le $n-andest là pour rendre compte de ""= $FALSE.

Alternatif, 35 octets

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

Ceci utilise la regex de la réponse de Leaky , basée sur des groupes d'équilibrage .NET, juste encapsulés dans l' -matchopérateur PowerShell . Renvoie la chaîne pour vérité ou la chaîne vide pour falsey.

AdmBorkBork
la source
Dans la version alternative , vous devez évaluer -matchcontre $args[0], sinon -matchfonctionnera comme un filtre
R. Mathias Jessen
@ MathiasR.Jessen En code de production, oui, mais nous pouvons jouer [0]ici parce que nous ne recevons qu'une entrée et que nous n'avons besoin que d'une valeur de vérité / falsey en sortie. Puisqu'une chaîne vide est falsey et qu'une chaîne non vide est une vérité, nous pouvons filtrer le tableau et récupérer la chaîne d'entrée ou rien, ce qui satisfait aux exigences du défi.
AdmBorkBork
2

Pyth - 13 octets

&zqzS*/lz2"ab

A expliqué:

  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
la source
Vous pouvez utiliser une chaîne comme entrée puis la créer&qS*/lQ2"ab
Leaky Nun
@ LeakyNun merci pour le tuyau! Pouvez-vous expliquer comment / pourquoi cela fonctionne? C'est la première fois que j'utilise Pyth
Cowabunghole le
Par exemple, +4s'étendra à +4Q(remplissage implicite d'arguments)
Leaky Nun
2

Haskell, 39 octets

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

Exemple d'utilisation: p "aabb"-> True.

scanl(\s _->'a':s++"b")"ab"xconstruire une liste de tous ["ab", "aabb", "aaabbb", ...]avec un total d' (length x)éléments. elemvérifie si xest dans cette liste.

nimi
la source
2

Python, 43 à 40 octets

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

a identifié la solution évidente grâce à Leaky Nun

autre idée, 45 octets:

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

-4 octets en utilisant len ​​/ 2 (j'obtiens une erreur quand la moitié arrive en dernier)

donne maintenant faux pour la chaîne vide

-3 octets grâce à xnor

KarlKastor
la source
Oui, il n'est pas nécessaire de nommer les lambdas.
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
Oui, j'ai réalisé cela en le postant. lol, la solution évidente est plus courte en Python 2:
KarlKastor
1
Vous pouvez faire ''<au lieu d' s andéliminer le cas vide.
xnor