A contagem de "a" e "b" s deve ser igual. Você conseguiu computador?

75

No popular (e essencial) livro de ciência da computação, Uma Introdução às Línguas Formais e Autômatos, de Peter Linz, a seguinte linguagem formal é freqüentemente declarada:

definição

principalmente porque esse idioma não pode ser processado com autômatos de estado finito. Essa expressão significa "A linguagem L consiste em todas as cadeias de 'a's seguidas de' b's, nas quais o número de 'a's e' b's é igual e diferente de zero".

Desafio

Escreva um programa / função de trabalho que obtenha uma string, contendo apenas "a" se "b" s , como entrada e retorna / gera um valor verdade , dizendo se essa string é válida na linguagem formal L.

  • Seu programa não pode usar nenhuma ferramenta de computação externa, incluindo rede, programas externos, etc. Os shells são uma exceção a esta regra; O Bash, por exemplo, pode usar utilitários de linha de comando.

  • Seu programa deve retornar / produzir o resultado de uma maneira "lógica", por exemplo: retornando 10 em vez de 0, som de "bipe", saída para stdout etc. Mais informações aqui.

  • Aplicam-se regras de código padrão de golfe.

Este é um . O menor código em bytes vence. Boa sorte!

Casos de teste de verdade

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

Casos de teste de falsidade

""
"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"
Comunidade
fonte
24
A entrada pode estar vazia? (Você está dizendo que não é parte da linguagem, mas não quer se trate de uma entrada precisamos considerar.)
Martin Ender
1
E se a nossa linguagem não tiver verdade ou falsidade? Seria empty string == truthye non-empty string == falsyseria aceitável?
DJMcMayhem
5
Bom desafio, mas acho que o título poderia ser um pouco menos ambígua (ou seja, uma menção a^n b^nou similar, ao invés de apenas o número de as igualando o número de bs)
SP3000
1
@ Sp3000 Eu escolhi este título porque parecia divertido. Eu posso mudá-lo mais tarde para sth outra coisa ...
1
Estou um pouco surpreso que, em mais de 50 respostas, sou o único a usar um gerador de paser. Para ter certeza de que não é estritamente competitivo em termos de comprimento, o problema é analisar uma linguagem simples, mas não trivial. Eu gostaria muito de ver respostas em outras sintaxes do compilador-compilador, porque não estou familiarizado com as opções.
dmckee

Respostas:

34

MATL , 5 4 bytes

tSP-

Imprime uma matriz não vazia de 1 s se a string pertencer a L e uma matriz vazia ou uma matriz com 0 s (ambos falsificados) caso contrário.

Obrigado a @LuisMendo por jogar fora um byte!

Experimente online!

Como funciona

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
fonte
6
Minha segunda (trabalhando) resposta MATL. :)
Dennis
2
Definição estranha de verdade e falsidade: 'aabb' dá -1 -1 1 1 é verdade. 'aaabb' dá -1 -1 0 1 1 e é falso
Etoplay 25/07
3
@Etoplay Uma matriz não vazia com todos os seus valores diferentes de zero é verdadeira. É a definição utilizada no Matlab e Octave
Luis Mendo
145

Python 3, 32 bytes

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

Saídas via código de saída : Erro para false, nenhum erro para True.

A cadeia é avaliada como código Python, substituindo parênteses (por ae )para b. Somente expressões do formulário a^n b^nse tornam expressões bem formadas de parênteses ((())), avaliando a tupla ().

Qualquer parêntese incompatível gera um erro, assim como vários grupos (()()), pois não há separador. A cadeia vazia também falha (seria bem-sucedida exec).

A conversão ( -> a, ) -> bé feita usando str.translate, que substitui os caracteres, tal como indicado por uma cadeia que serve como uma tabela de conversão. Dada a sequência de 100 comprimentos ") (" * 50, as tabelas mapeiam os primeiros 100 valores ASCII como

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

que leva ( -> a, ) -> b. No Python 2, as conversões para todos os 256 valores ASCII devem ser fornecidas, exigindo "ab"*128um byte a mais; obrigado a isaacg por apontar isso.

xnor
fonte
58
Ok, isso é inteligente.
TLW 21/07
O que *128faz?
Erik the Outgolfer
5
128pode ser substituído por 50(ou, 99nesse caso) para salvar um byte.
Isaacg
@ Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ: Eu acho que é um quantificador. Mas eu realmente não conheço Python e ainda não encontrei nenhuma documentação sobre isso.
Titus
4
@isaacg Obrigado, eu não estava ciente de que mudou para Python 3.
xnor
28

Retina , 12 bytes

Créditos para FryAmTheEggman que encontrou esta solução de forma independente.

+`a;?b
;
^;$

Imprime 1para entrada válida ou 0não.

Experimente online! (A primeira linha ativa um conjunto de testes separado por avanço de linha.)

Explicação

Grupos de balanceamento exigem sintaxe cara, então estou tentando reduzir uma entrada válida para um formulário simples.

Estágio 1

+`a;?b
;

O +instrui o Retina a repetir esse estágio em um loop até que a saída pare de mudar. Ele corresponde a abou a;be o substitui por ;. Vamos considerar alguns casos:

  • Se os as e bs na cadeia não são equilibradas, da mesma forma que (e )normalmente precisa ser, alguns aou bpermanecerá na cadeia, uma vez que ba, ou b;anão pode ser resolvido e um único aou bpor si só não pode ou. Para se livrar de todos os as e bs tem que haver uma correspondente bao direito de cada a.
  • Se o ae bnão são todos aninhados (por exemplo, se temos algo como ababou aabaabbb), então vamos acabar com múltiplos ;(e, potencialmente, alguns as e bs), porque a primeira iteração vai encontrar vários abs para inseri-los e mais iterações preservará o número de ;na sequência.

Portanto, se e somente se a entrada for do formato , acabaremos com um único na string.anbn;

Etapa 2:

^;$

Verifique se a sequência resultante contém apenas um ponto e vírgula. (Quando digo "marcar", na verdade, quero dizer ", conte o número de correspondências da regex especificada, mas como essa regex pode corresponder no máximo uma vez devido às âncoras, isso fornece um 0ou outro 1.)

Martin Ender
fonte
25

Haskell, 31 bytes

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

A compreensão da lista [c|c<-"ab",'a'<-s]faz uma corda de uma 'a'para cada 'a', em s, seguido por um 'b'para cada 'a'no s. Evita a contagem correspondendo a uma constante e produzindo uma saída para cada correspondência.

Essa sequência é verificada como igual à sequência original e a sequência original é verificada como não vazia.

xnor
fonte
Isso é adorável. Costumo esquecer como é útil Haskell ordenar os elementos de uma compreensão de lista de maneira consistente e muito específica.
Vectornaut 21/07
Muito melhor do que minha melhor tentativa ( f=g.span id.map(=='a');g(a,b)=or a&&b==(not<$>a)). Bem feito.
Jules
Uau, eu não sabia que alguém poderia corresponder a uma constante na compreensão de uma lista!
22416
16

Grime , 12 bytes

A=\aA?\b
e`A

Experimente online!

Explicação

A primeira linha define um não terminal A, que corresponde a uma letra a, possivelmente o não terminal A, e depois uma letra b. A segunda linha corresponde à entrada inteira ( e) contra o não-terminal A.

Versão não competitiva de 8 bytes

e`\a_?\b

Depois de escrever a primeira versão desta resposta, atualizei o Grime para considerar _como o nome da expressão de nível superior. Esta solução é equivalente à acima, mas evita repetir o rótulo A.

Zgarb
fonte
Por que você não fez isso em J?
Leaky Nun
@LeakyNun Eu só queria mostrar o Grime. : P
Zgarb
Você construiu esse idioma?
Leaky Nun
@LeakyNun Sim. O desenvolvimento é lento, mas contínuo.
Zgarb
11

Braquilog , 23 19 bytes

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

Experimente online!

Explicação

@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
Fatalizar
fonte
8
Parabéns por entrar no tryitonline.net!
Leaky Nun
10

05AB1E , 9 bytes

Código:

.M{J¹ÔQ0r

Explicação:

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

Os últimos dois bytes podem ser descartados se for garantido que a entrada não está vazia.

Usa a codificação CP-1252 . Experimente online! .

Adnan
fonte
O que acontece com a entrada vazia?
AdmBorkBork
2
Procure por zero na postagem; ele está lá :)
Lynn
@ Lynn As especificações não dizem apenas zero para um idioma válido? Não é sobre entrada.
Emigna
Verdadeiro. Pensei errado lá. Mas você ainda pode fazer .M{J¹ÔQ0rpelo seu.
Emigna
@ Emigna Obrigado, eu editei o post.
Adnan
9

Gelatina , 6 bytes

Ṣ=Ṛ¬Pȧ

Imprime a própria string se ela pertence a L ou está vazia e 0, caso contrário.

Experimente online! ou verifique todos os casos de teste .

Como funciona

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

Versão alternativa, 4 bytes (não concorrente)

ṢnṚȦ

Imprime 1 ou 0 . Experimente online! ou verifique todos os casos de teste .

Como funciona

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

J, 17 bytes

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

Isso funciona corretamente para fornecer falsey para a string vazia. Erro é falsey.

Versões antigas:

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

Prova e explicação

O verbo principal é uma bifurcação que consiste nestes três verbos:

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

Isso significa, "O menor de ( <.) o comprimento ( #) e o resultado do dente direito ( (-:'ab'#~-:@#))".

O dente direito é um trem de 4 trens , composto por:

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

Vamos krepresentar nossa entrada. Então, isso é equivalente a:

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

-:é o operador de partida, portanto, os principais -:testes de invariância sob o garfo monádico 'ab' #~ -:@#.

Como o dente esquerdo do garfo é um verbo, ele se torna uma função constante. Portanto, o garfo é equivalente a:

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

O dente direito do garfo reduz pela metade ( -:) o comprimento ( #) de k. Observe #:

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

Agora, isso é kapenas com entradas válidas, então terminamos aqui. #erros para strings de comprimento ímpar, que nunca satisfazem o idioma, então também estamos prontos.

Combinada com o menor do comprimento e isso, a cadeia vazia, que não faz parte da nossa linguagem, produz seu comprimento 0, e terminamos com tudo.

Conor O'Brien
fonte
Eu modifiquei para 2&#-:'ab'#~#que você evitasse o erro e apenas saísse 0usando 12 bytes.
milhas
@miles Fascinating! Eu nunca pensei nisso assim.
Conor O'Brien
Isso lida com a string vazia?
Zgarb 21/07
@Zgarb corrigiu isso!
Conor O'Brien
9

Bison / YACC 60 (ou 29) bytes

(Bem, a compilação para um programa YACC é composta por algumas etapas, portanto, você pode incluir algumas para isso. Veja abaixo os detalhes.)

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

A função deve ser bastante óbvia se você souber interpretá-la em termos de gramática formal. O analisador aceita um abou um aseguido por qualquer sequência aceitável seguida por a b.

Essa implementação depende de um compilador que aceita a semântica de K&R para perder alguns caracteres.

É mais elaborado do que gostaria com a necessidade de definir yylexe chamar getchar.

Ajuntar com

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

(a maioria das opções para o gcc é específica para o meu sistema e não deve contar na contagem de bytes; convém contar o -std=c89que adiciona 8 ao valor listado).

Correr com

$ echo "aabb" | ./equal

ou equivalente.

O valor de verdade é retornado ao sistema operacional e os erros também são relatados syntax errorna linha de comandos. Se eu puder contar apenas a parte do código que define a função de análise (que é negligenciar o segundo %%e tudo o que se segue), recebo uma contagem de 29 bytes.

dmckee
fonte
7

Perl 5.10, 35 17 bytes (com sinalizador -n )

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

Garante que a sequência inicie com as e depois retorne em bs. Corresponde apenas se os dois comprimentos forem iguais.

Agradeço a Martin Ender por reduzir pela metade a contagem de bytes e me ensinar um pouco sobre a recursão nas expressões regulares: D

Retorna a string inteira, se corresponder, e nada, se não.

Experimente aqui!

Paul Picard
fonte
O mais próximo que posso gerenciar, incluindo o caso de teste não vazio, é de 18 bytes: $_&&=y/a//==y/b//(requer -p), sem o vazio, você pode soltar o valor &&por 16! Tão perto ...
Dom Hastings
1
Então eu posso fazer outros 17 bytes: echo -n 'aaabbb'|perl -pe '$_+=y/a//==y/b//'mas não posso mudar outro byte ... Talvez precise desistir disso!
Dom Hastings
7

JavaScript, 54 55 44

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

Constrói uma regex simples com base no comprimento da string e a testa. Para uma string de comprimento 4 ( aabb), a regex se parece com:^a{2}b{2}$

Retorna um valor de verdade ou falsey.

11 bytes salvos graças a 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
fonte
O f=pode ser omitido.
Leaky Nun
A expressão de uma função é uma submissão válida ou deve ser realmente funcional?
Scimonster
Uma função é um envio válido.
Leaky Nun
@ TimmyD Costumava retornar true, mas agora retorna false.
Scimonster
1
s=>s.match(`^a{${s.length/2}}b+$`)?
l4m2
5

C, 57 53 bytes

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

Solução antiga de 57 bytes de comprimento:

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

Compilado com gcc v. 4.8.2 @Ubuntu

Obrigado ugoren pelas dicas!

Experimente no Ideone!

Jasmes
fonte
Como eu sou novo aqui e não posso comentar outras respostas ainda, só quero salientar que a solução 62b do @Josh fornece falso positivo em seqüências de caracteres como "aaabab".
Jasmes 22/07
Mudar (t+=2)para t++++para -1 byte.
27616 owacoder
@owacoder t++++não é um código C válido.
Jasmes
Salve alguns com t+=*s%2*2e:*s*!1[s]
ugoren 31/07
Resposta muito inteligente! Ele infelizmente falhar na entrada "ba": ideone.com/yxixG2
Josh
4

Retina , 22 bytes

Outra resposta mais curta no mesmo idioma acabou de chegar ...

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

Experimente online!

Esta é uma vitrine dos grupos de balanceamento na regex, explicada por Martin Ender .

Como minha explicação não chegaria nem perto da metade, vou apenas ligar para ela e não tentar explicar, pois isso seria prejudicial para a glória de sua explicação.

Freira Furada
fonte
4

Befunge-93, 67 bytes

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

Experimente aqui! Pode explicar como funciona depois. Também pode tentar jogar um pouco mais, apenas por diversão.


fonte
3

MATL , 9 bytes

vHI$e!d1=

Experimente online!

A matriz de saída é verdadeira se não estiver vazia e todas as suas entradas forem diferentes de zero. Caso contrário, é falso. Aqui estão alguns exemplos .

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
fonte
2
Essa é uma definição conveniente de verdade. (Eu sabia sobre a exigência diferente de zero, mas não sobre o não-vazia.)
Dennis
3

código de máquina x86, 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

Código de montagem:

    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;

Repete os abytes no começo e depois nos seguintes bytes 'b'. O primeiro loop aumenta um contador e o segundo diminui. Depois, faz um OR bit a bit entre as seguintes condições:

  1. Se o contador não for 0 no final, a sequência não corresponderá
  2. Se o byte que segue a sequência de bs não for 0, a sequência também não corresponderá

Então, ele deve "inverter" o valor da verdade eax- configure-o para 0 se não for 0 e vice-versa. Acontece que o código mais curto para fazer isso é o seguinte código de 5 bytes, que eu roubei da saída do meu compilador C ++ para 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
fonte
1
Eu acho que você pode melhorar sua negação. Tente: neg eaxdefinir o sinalizador de transporte como antes, cmcinverter o sinalizador de transporte e salcdefinir AL como FFh ou 0, dependendo de o sinalizador de transporte estar definido ou não. Economiza 2 bytes, apesar de ter um resultado de 8 bits em vez de 32 bits.
Jules
A mesma coisa usando ops cordas, com ESI apontando para a cadeia de entrada, e retornando o resultado na AL (usa SETcc, requer 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 Você deve postar isso em uma resposta - é suficientemente diferente da minha, e eu suspeito que seja significativamente menor!
anatolyg
3

Ruby, 24 bytes

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

(Essa é apenas a brilhante idéia de xnor na forma de Ruby. Minha outra resposta é uma solução que eu realmente criei.)

O programa pega a entrada, transforma ae bpara [e ]respectivamente, e a avalia.

A entrada válida formará uma matriz aninhada e nada acontece. Uma expressão desequilibrada fará com que o programa falhe. No Ruby, a entrada vazia é avaliada como nil, que trava porque nilnão definiu um *método.

daniero
fonte
3

Sed, 38 + 2 = 40 bytes

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

Uma saída de string não vazia é verdadeira

Autômatos de estados finitos não podem fazer isso, você diz? E os autômatos de estados finitos com loops . : P

Corra com re nsinalizadores.

Explicação

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
someonewithpc
fonte
Boa abordagem. Obrigado pela repartição.
Joeytwiddle
3

JavaScript, 44 42

O riscado 44 ainda é regular 44;

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

Funciona por forma recursiva tirando o exterior ae be recursivamente utilizando o valor interno seleccionado mas .+. Quando não há correspondência à ^a.+b$esquerda, o resultado final é se a sequência restante é o valor exato ab.

Casos de teste:

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

ANTLR, 31 bytes

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

Usa o mesmo conceito que a resposta YACC do @ dmckee , apenas um pouco mais.

Para testar, siga as etapas no tutorial de introdução do ANTLR . Em seguida, coloque o código acima em um arquivo chamado A.g4e execute estes comandos:

$ antlr A.g4
$ javac A*.java

Em seguida, teste dando entrada no STDIN para grun A r:

$ echo "aaabbb" | grun A r

Se a entrada for válida, nada será produzido; se for inválido, grundará um erro (ou token recognition error, extraneous input, mismatched inputou no viable alternative).

Exemplo de uso:

$ echo "aabb" | grun A r
$ echo "abbb" | grun A r
line 1:2 mismatched input 'b' expecting {<EOF>, '
'}
Cobre
fonte
Truque inteligente ao adicionar a nova linha como alternativa em uma única regra. Eu acho que também poderia salvar algumas dessas coisas no yacc. A grammerpalavra-chave é fedorenta para jogar golfe com o antlr. Meio como usar o fortran .
dmckee
3

C, 69 bytes

69 bytes:

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

Para quem não conhece:

  • strlen determina o comprimento da string
  • strcspn retorna o primeiro índice na string em que a outra string é encontrada
  • strchr retorna um ponteiro para a primeira ocorrência de um caractere
  • strrchr retorna um ponteiro para a última ocorrência de um caractere

Um grande obrigado a Titus!

Josh
fonte
1
salve um byte com em >97vez de==98
Titus
2
A solução de 61 bytes fornece falso positivo em seqüências de caracteres como "aaabab". Veja ideone.com/nmT8rm
Jasmes
Ah, você está certo, Jasmes, obrigado. Vou ter que repensar isso um pouco.
28716 Josh
Voltando à solução de 69 bytes, não tenho certeza se posso ficar mais curto usando essa abordagem.
28716 Josh
3

R, 64 61 55 bytes, 73 67 bytes (robusto) ou 46 bytes (se cadeias vazias forem permitidas)

  1. Mais uma vez, a resposta do xnor retrabalhou. Se está implícito pelas regras que a entrada será composto de uma série de as e bs, ele deve funcionar: retorna NULL se a expressão é válida, lança e erro ou nada contrário.

    if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
    
  2. Se a entrada não for robusta e puder conter algum lixo, por exemplo aa3bb, a seguinte versão deverá ser considerada (deve retornar TRUEpara casos de teste verdadeiros, não NULL):

    if(length(y<-scan(,'')))is.null(eval(parse(t=chartr("ab","{}",y))))
    
  3. Finalmente, se cadeias vazias forem permitidas, podemos ignorar a condição para entrada não vazia:

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

    Novamente, NULL se for bem-sucedido, qualquer outra coisa.

Andreï Kostyrka
fonte
Não sei R, qual é o seu resultado para entrada vazia? (deve ser Falsas)
Titus
Não existe realmente uma maneira mais curta de testar a entrada vazia?
Titus
Versão 1: apenas nada (entrada correta retorna somente NULL), versão 2: apenas nada (entrada correta retorna somente TRUE), versão 3 (assumindo cadeias vazias são OK, como estado): NULL. R é uma linguagem estatística orientada a objetos que tipifica tudo bem, sem nenhum aviso.
Andreï Kostyrka
Isso (resposta 1) pode ser aprimorado ainda mais para 55 bytes:if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
Giuseppe
3

Japonês , 11 bytes

©¬n eȦUg~Y

Experimente online!

Dá um trueou outro false, exceto o que """"que é falso em JS.

Descompactado e como funciona

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

Adotado da solução MATL de Dennis .

Bubbler
fonte
2

C (Ansi), 65 75 bytes

Golfe:

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

Explicação:

Define um valor j e incrementa j em cada be diminui j em qualquer outra coisa. Verificado se a letra anterior é menor ou igual à próxima letra, para evitar que o abab funcione

Editar% s

Adicionadas verificações para casos abab.

dj0wns
fonte
Isso não dará falsos positivos em strings como baou abab?
Zgarb
Ahh, sim, eu interpretei errado o post, pois não conseguia ver a foto, pois estava bloqueada para mim. Consertando-o!
dj0wns
2

Lote, 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

Retorna um ERRORLEVELde 0 em caso de sucesso, 1 em caso de falha. O lote não gosta de fazer a substituição de substring em cadeias vazias; portanto, precisamos verificar isso com antecedência; se um parâmetro vazio fosse legal, a linha 6 não seria necessária.

Neil
fonte
2

PowerShell v2 +, 61 52 bytes

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

Pega a entrada $ncomo uma string, cria $xcomo half the length. Constrói uma -andcomparação booleana entre $ne um -matchoperador de expressão regular contra a expressão regular de um número igual de a'se b'. Saídas booleanas $TRUEou $FALSE. O $n-andexiste para explicar ""= $FALSE.

Alternativo, 35 bytes

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

Isso usa o regex da resposta do Leaky , com base nos grupos de balanceamento do .NET, apenas encapsulados no -matchoperador PowerShell . Retorna a string para truthy, ou string vazia para falsey.

AdmBorkBork
fonte
Na versão alternativa você deve avaliar -matchcontra $args[0], caso contrário, -matchirá funcionar como um filtro
Mathias R. Jessen
@ MathiasR.Jessen No código de produção, sim, mas podemos jogar golfe [0]aqui porque recebemos apenas uma entrada e precisamos apenas de um valor truthy / falsey como saída. Como uma string vazia é falsey e uma string não vazia é verdadeira, podemos filtrar a matriz e recuperar a string de entrada ou nada, o que satisfaz os requisitos do desafio.
AdmBorkBork
2

Pitão - 13 bytes

&zqzS*/lz2"ab

Explicado:

  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
fonte
Você pode usar uma string como entrada e, em seguida, fazê-lo&qS*/lQ2"ab
Leaky Nun
@LeakyNun obrigado pela dica! Você pode explicar como / por que isso funciona? Esta é minha primeira vez usando Pyth
Cowabunghole
Por exemplo, +4será expandido para +4Q(preenchimento implícito de argumentos) #
Leaky Nun
2

Haskell, 39 bytes

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

Exemplo de uso: p "aabb"-> True.

scanl(\s _->'a':s++"b")"ab"xcrie uma lista de todos ["ab", "aabb", "aaabbb", ...]com um total de (length x)elementos. elemverifica se xestá nesta lista.

nimi
fonte
2

Python, 43 40 bytes

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

considerou a solução óbvia graças a Leaky Nun

outra ideia, 45 bytes:

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

-4 bytes usando len / 2 (eu recebo um erro quando chega a metade)

agora dá false para a string vazia

-3 bytes graças ao xnor

KarlKastor
fonte
Sim, lambdas não precisam ser nomeadas.
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
Sim, eu percebi isso ao postá-lo. lol, a solução óbvia é mais curta no Python 2:
KarlKastor 20/07/16
1
Você pode fazer em ''<vez de s anddescartar a caixa vazia.
Xnor