El recuento de "a" sy "b" s debe ser igual. ¿Lo conseguiste en la computadora?

75

En el popular (y esencial) libro de ciencias de la computación, Introducción a los lenguajes formales y autómatas de Peter Linz, se menciona con frecuencia el siguiente lenguaje formal:

definición

principalmente porque este lenguaje no se puede procesar con autómatas de estado finito. Esta expresión significa "El lenguaje L consiste en todas las cadenas de 'a' seguidas de 'b', en las cuales el número de 'a' y 'b' son iguales y distintos de cero '.

Desafío

Escriba un programa / función de trabajo que obtenga una cadena, que contenga "a" sy "b" solo , como entrada y devuelva / salga un valor de verdad , indicando si esta cadena es válida el lenguaje formal L.

  • Su programa no puede usar ninguna herramienta de computación externa, incluida la red, programas externos, etc. Los shells son una excepción a esta regla; Bash, por ejemplo, puede usar utilidades de línea de comandos.

  • Su programa debe devolver / emitir el resultado de una manera "lógica", por ejemplo: devolver 10 en lugar de 0, "pitido", emitir a stdout, etc. Más información aquí.

  • Se aplican reglas estándar de golf de código.

Este es un . El código más corto en bytes gana. ¡Buena suerte!

Casos de prueba de verdad

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

Casos de prueba de falsa

""
"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"
Comunidad
fuente
24
¿Puede la entrada estar vacía? (Estás diciendo que no es parte del lenguaje, pero no si es una entrada que debemos considerar).
Martin Ender
1
¿Qué pasa si nuestro lenguaje no tiene veracidad o falsedad? ¿Sería empty string == truthyy non-empty string == falsysería aceptable?
DJMcMayhem
55
Buen desafío, pero creo que el título podría ser un poco menos ambiguo (es decir, una mención a^n b^no similar, en lugar de solo el número de as igual al número de bs)
Sp3000
1
@ Sp3000 Elegí este título porque parecía divertido. Puedo cambiarlo más tarde a algo más ...
1
Estoy un poco sorprendido de que en más de 50 respuestas soy el único que usa un generador paser. Sin duda, no es estrictamente competitivo en longitud, pero el problema planteado es analizar un lenguaje simple pero no trivial. Me gustaría mucho ver respuestas en otras sintaxis de compilador-compilador porque no estoy muy familiarizado con las opciones.
dmckee

Respuestas:

34

MATL , 5 4 bytes

tSP-

Imprime una matriz no vacía de 1 s si la cadena pertenece a L , y una matriz vacía o una matriz con 0 s (ambas falsas) de lo contrario.

¡Gracias a @LuisMendo por jugar golf en 1 byte!

Pruébalo en línea!

Cómo 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
fuente
66
Mi segunda respuesta (de trabajo) MATL. :)
Dennis
2
Definición extraña de verdad y falsedad: 'aabb' da -1 -1 1 1 es verdad. 'aaabb' da -1 -1 0 1 1 y es falso
Etoplay
3
@Etoplay Una matriz no vacía con todos sus valores distintos de cero es verdadera. Es la definición utilizada en Matlab y Octave
Luis Mendo
145

Python 3, 32 bytes

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

Salidas a través del código de salida : error para falso, no hay error para verdadero.

La cadena se evalúa como código Python, reemplazando parens (por ay )para b. Solo las expresiones de la forma se a^n b^nconvierten en expresiones bien formadas de paréntesis como ((())), evaluando a la tupla ().

Cualquier parens no coincidente da un error, como lo harán varios grupos (()()), ya que no hay separador. La cadena vacía también falla (tendría éxito en exec).

La conversión ( -> a, ) -> bse realiza utilizando str.translate, que reemplaza los caracteres como lo indica una cadena que sirve como una tabla de conversión. Dada la cadena de 100 longitudes ") (" * 50, las tablas asignan los primeros 100 valores ASCII como

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

que tiene ( -> a, ) -> b. En Python 2, se deben proporcionar conversiones para los 256 valores ASCII, que requieren "ab"*128un byte más; Gracias a Isaac por señalar esto.

xnor
fuente
58
Ok, eso es inteligente.
TLW
¿Qué hace el *128?
Erik the Outgolfer
55
128se puede reemplazar por 50(o 99para el caso) para guardar un byte.
isaacg
@ Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ: Creo que es un cuantificador. Pero realmente no conozco Python y todavía no he encontrado ninguna documentación al respecto.
Titus
44
@isaacg Gracias, no sabía que eso cambió para Python 3.
xnor
28

Retina , 12 bytes

Créditos a FryAmTheEggman que encontró esta solución de forma independiente.

+`a;?b
;
^;$

Imprime 1entradas válidas y de 0otro tipo.

Pruébalo en línea! (La primera línea habilita un conjunto de pruebas separado por salto de línea).

Explicación

Los grupos de equilibrio requieren una sintaxis costosa, por lo que en su lugar estoy tratando de reducir una entrada válida a un formulario simple.

Nivel 1

+`a;?b
;

El +le dice a Retina que repita esta etapa en un bucle hasta que la salida deje de cambiar. Coincide con o abo a;by lo reemplaza con ;. Consideremos algunos casos:

  • Si las as y los bs de la cadena no están equilibrados de la misma manera que (y )normalmente tienen que ser, algunos ao bpermanecerá en la cadena, ya que ba, o b;ano se puede resolver y una sola ao bpor sí solo no puede ya sea. Para deshacerse de todos los asy los bs tiene que haber uno correspondiente ba la derecha de cada uno a.
  • Si el ay el bno son todos anidado (por ejemplo, si tenemos algo parecido ababo aabaabbb) a continuación, vamos a terminar con múltiples ;(y potencialmente algunos as y bs) debido a que la primera iteración encontrará múltiples abs para insertarlos y otras iteraciones preservará El número de ;en la cadena.

Por lo tanto, si y solo si la entrada es de la forma , terminaremos con un solo en la cadena.anbn;

Etapa 2:

^;$

Compruebe si la cadena resultante no contiene más que un solo punto y coma. (Cuando digo "comprobar", en realidad quiero decir "cuente el número de coincidencias de la expresión regular dada, pero dado que esa expresión regular puede coincidir como máximo una vez debido a los anclajes, esto da 0o" 1).

Martin Ender
fuente
25

Haskell, 31 bytes

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

La lista de comprensión [c|c<-"ab",'a'<-s]hace que una cadena de uno 'a'para cada uno 'a'de s, seguido de uno 'b'de cada 'a'en s. Evita contar haciendo coincidir una constante y produciendo una salida para cada coincidencia.

Se verifica que esta cadena sea igual a la cadena original, y se verifica que la cadena original no está vacía.

xnor
fuente
Esto es adorable. A menudo olvido lo útil que es que Haskell ordene los elementos de una lista de comprensión de una manera consistente y muy específica.
Vectornaut
Mucho mejor que mi mejor intento ( f=g.span id.map(=='a');g(a,b)=or a&&b==(not<$>a)). Bien hecho.
Jules
¡Wow, no sabía que uno podría coincidir en una constante en una lista de comprensión!
rubik
16

Grime , 12 bytes

A=\aA?\b
e`A

Pruébalo en línea!

Explicación

La primera línea define un no terminal A, que coincide con una letra a, posiblemente el no terminal A, y luego una letra b. La segunda línea hace coincidir toda la entrada ( e) con la no terminal A.

Versión no competitiva de 8 bytes

e`\a_?\b

Después de escribir la primera versión de esta respuesta, actualicé Grime para considerarlo _como el nombre de la expresión de nivel superior. Esta solución es equivalente a la anterior, pero evita repetir la etiqueta A.

Zgarb
fuente
¿Por qué no lo hiciste en J?
Leaky Nun
@LeakyNun Solo quería presumir Grime. : P
Zgarb
¿Construiste este lenguaje?
Leaky Nun
@LeakyNun Sí. El desarrollo es lento, pero continuo.
Zgarb
11

Brachylog , 23 19 bytes

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

Pruébalo en línea!

Explicación

@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
fuente
8
¡Felicitaciones por entrar en tryitonline.net!
Leaky Nun
10

05AB1E , 9 bytes

Código:

.M{J¹ÔQ0r

Explicación:

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

Los dos últimos bytes se pueden descartar si se garantiza que la entrada no está vacía.

Utiliza la codificación CP-1252 . Pruébalo en línea! .

Adnan
fuente
¿Qué pasa con la entrada vacía?
AdmBorkBork
2
Busque no cero en la publicación; está ahí :)
Lynn
@ Lynn ¿No dice la especificación que solo dice cero para un lenguaje válido? No se trata de entrada.
Emigna
Cierto. Pensé mal allí. Pero aún puedes hacerlo .M{J¹ÔQ0rpor el tuyo.
Emigna
@ Emmigna Gracias, he editado la publicación.
Adnan
9

Jalea , 6 bytes

Ṣ=Ṛ¬Pȧ

Imprime la cadena en sí si pertenece a L o está vacía, y 0 en caso contrario.

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo 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 == "".

Versión alternativa, 4 bytes (no competitiva)

ṢnṚȦ

Imprime 1 o 0 . Pruébalo en línea! o verificar todos los casos de prueba .

Cómo 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
fuente
9

J, 17 bytes

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

Esto funciona correctamente para dar falsey para la cadena vacía. El error es falsey.

Versiones antiguas:

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

Prueba y explicación

El verbo principal es un tenedor que consta de estos tres verbos:

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

Esto significa, "El menor de ( <.) la longitud ( #) y el resultado del diente correcto ( (-:'ab'#~-:@#))".

El diente derecho es un tren de 4 , que consiste en:

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

Dejemos krepresentar nuestra entrada. Entonces, esto es equivalente a:

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

-:es el operador del partido, por lo que las principales -:pruebas de invariancia bajo la bifurcación monádica 'ab' #~ -:@#.

Como el diente izquierdo del tenedor es un verbo, se convierte en una función constante. Entonces, la bifurcación es equivalente a:

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

El diente derecho de las mitades de la horquilla ( -:) la longitud ( #) de k. Observar #:

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

Ahora, esto es ksolo en entradas válidas, así que hemos terminado aquí. #errores para cadenas de longitud impar, que nunca satisfacen el lenguaje, por lo que también hemos terminado.

Combinado con el menor de la longitud y esto, la cadena vacía, que no es parte de nuestro lenguaje, produce su longitud 0, y hemos terminado con todo.

Conor O'Brien
fuente
Lo modifiqué en el 2&#-:'ab'#~#que debería permitirle evitar el error y simplemente mostrarlo en su 0lugar mientras todavía usa 12 bytes.
millas
@miles Fascinante! Nunca lo pensé así.
Conor O'Brien
¿Esto maneja la cadena vacía?
Zgarb
@Zgarb lo arregló!
Conor O'Brien
9

Bison / YACC 60 (o 29) bytes

(Bueno, la compilación de un programa YACC es un par de pasos, por lo que es posible que desee incluir algunos para eso. Consulte a continuación para obtener más detalles).

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

La función debería ser bastante obvia si sabe interpretarla en términos de una gramática formal. El analizador acepta cualquiera abo aseguido de cualquier secuencia aceptable seguida de a b.

Esta implementación se basa en un compilador que acepta la semántica de K&R para perder algunos caracteres.

Es más amplio de lo que me gustaría con la necesidad de definir yylexy llamar getchar.

Compilar con

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

(la mayoría de las opciones para gcc son específicas de mi sistema y no deberían contar para el recuento de bytes; es posible que desee contar, lo -std=c89que agrega 8 al valor enumerado).

Corre con

$ echo "aabb" | ./equal

o equivalente.

El valor de verdad se devuelve al sistema operativo y los errores también informan syntax errora la línea de comando. Si puedo contar solo la parte del código que define la función de análisis (es decir, descuidar el segundo %%y todo lo que sigue) obtengo un recuento de 29 bytes.

dmckee
fuente
7

Perl 5.10, 35 17 bytes (con el indicador -n )

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

Asegura que la cadena comienza con asy luego vuelve a aparecer en bs. Solo coincide si ambas longitudes son iguales.

Gracias a Martin Ender por reducir a la mitad el conteo de bytes y enseñarme un poco sobre la recursividad en expresiones regulares: D

Devuelve la cadena completa si coincide, y nada si no.

Pruébalo aquí!

Paul Picard
fuente
Lo más cercano que puedo manejar, incluido el caso de prueba no vacío, es de 18 bytes: $_&&=y/a//==y/b//(requiere -p), sin el vacío, ¡podría dejar el &&16! Tan cerca ...
Dom Hastings
1
Entonces puedo hacer otros 17 bytes: echo -n 'aaabbb'|perl -pe '$_+=y/a//==y/b//'pero no puedo cambiar otro byte ... ¡Puede que tenga que renunciar a esto!
Dom Hastings
7

JavaScript, 54 55 44

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

Crea una expresión regular simple basada en la longitud de la cadena y la prueba. Para una longitud de 4 cadenas ( aabb), la expresión regular se ve así:^a{2}b{2}$

Devuelve un valor verdadero o falso.

11 bytes guardados gracias 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
fuente
El f=puede ser omitido.
Leaky Nun
¿Es una expresión de función una presentación válida, o debe ser, ejem, funcional?
Scimonster
Una función es una presentación válida.
Leaky Nun
@TimmyD Solía ​​devolver verdadero, pero ahora devuelve falso.
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];}

Antigua solución de 57 bytes de longitud:

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

Compilado con gcc v. 4.8.2 @Ubuntu

Gracias ugoren por consejos!

Pruébalo en Ideone!

Jasmes
fuente
Como soy nuevo aquí y todavía no puedo comentar otras respuestas, solo quiero señalar que la solución 62b de @Josh da falsos positivos en cadenas como "aaabab".
Jasmes
Cambiar (t+=2)a t++++-1 byte.
owacoder
@owacoder t++++no es un código C válido.
Jasmes
Ahorre un poco con t+=*s%2*2y:*s*!1[s]
ugoren
Muy inteligente respuesta! Desafortunadamente falla en la entrada "ba": ideone.com/yxixG2
Josh
4

Retina , 22 bytes

Otra respuesta más corta en el mismo idioma acaba de llegar ...

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

Pruébalo en línea!

Este es un escaparate de los grupos de equilibrio en expresiones regulares, que se explica completamente por Martin Ender .

Como mi explicación no se acercaría a la mitad, la vincularé y no intentaré explicar, ya que eso sería perjudicial para la gloria de su explicación.

Monja permeable
fuente
4

Befunge-93, 67 bytes

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

Pruébalo aquí! Podría explicar cómo funciona más tarde. También podría intentar jugar al golf un poco más, solo por patadas.


fuente
3

MATL , 9 bytes

vHI$e!d1=

Pruébalo en línea!

La matriz de salida es verdadera si no está vacía y todas sus entradas son distintas de cero. De lo contrario, es falso. Aquí hay algunos ejemplos .

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
fuente
2
Esa es una definición conveniente de verdad. (Sabía sobre el requisito distinto de cero, pero no sobre el no vacío.)
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 montaje:

    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;

Itera sobre los abytes al principio, luego sobre los siguientes bytes 'b'. El primer bucle aumenta un contador y el segundo bucle lo disminuye. Luego, hace un bit a bit O entre las siguientes condiciones:

  1. Si el contador no es 0 al final, la cadena no coincide
  2. Si el byte que sigue la secuencia de bs no es 0, la cadena tampoco coincide

Luego, tiene que "invertir" el valor de verdad en eax- configúrelo en 0 si no fuera 0, y viceversa. Resulta que el código más corto para hacerlo es el siguiente código de 5 bytes, que robé de la salida de mi compilador de 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
fuente
1
Creo que puedes mejorar tu negación. Intente: neg eaxconfigurar la bandera de acarreo como antes, cmcinvertir la bandera de acarreo y salcconfigurar AL a FFh o 0 dependiendo de si la bandera de acarreo está configurada o no. Guarda 2 bytes, aunque termina con un resultado de 8 bits en lugar de 32 bits.
Julio
Lo mismo usando operaciones de cadena, con ESI apuntando a la cadena de entrada y devolviendo el resultado en AL (usa SETcc, requiere 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 Deberías publicar eso en una respuesta: es lo suficientemente diferente de la mía, ¡y sospecho que es significativamente más corto!
anatolyg
3

Rubí, 24 bytes.

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

(Esta es solo la brillante idea de xnor en forma de Ruby. Mi otra respuesta es una solución que realmente se me ocurrió).

El programa toma la entrada, transforma ay ba [y ], respectivamente, y lo evalúa.

La entrada válida formará una matriz anidada y no sucede nada. Una expresión desequilibrada hará que el programa se bloquee. En Ruby, la entrada vacía se evalúa como nil, lo que se bloqueará porque nilno ha definido un *método.

daniero
fuente
3

Sed, 38 + 2 = 40 bytes

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

Una salida de cadena no vacía es verdadera

Los autómatas de estado finito no pueden hacer esto, ¿dices? ¿Qué pasa con los autómatas de estado finito con bucles ? :PAGS

Corre con ry nbanderas.

Explicación

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
alguien con pc
fuente
Buen enfoque. Gracias por el desglose.
joeytwiddle
3

JavaScript, 44 42

Tachado 44 sigue siendo regular 44; (

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

Funciona por recursivamente quitándose el exterior ay by de forma recursiva mediante el valor interno seleccionado pero .+. Cuando no hay coincidencia a la ^a.+b$izquierda, el resultado final es si la cadena restante es el valor exacto ab.

Casos de prueba:

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

ANTLR, 31 bytes

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

Utiliza el mismo concepto que @ dmckee's respuesta YACC de , solo que un poco más golfizado.

Para realizar la prueba, siga los pasos del tutorial de introducción de ANTLR . Luego, coloque el código anterior en un archivo llamadoA.g4 y ejecute estos comandos:

$ antlr A.g4
$ javac A*.java

Luego pruebe dando entrada en STDIN para que le grun A rguste así:

$ echo "aaabbb" | grun A r

Si la entrada es válida, no se generará nada; si no es válido, grunse producirá un error (ya sea token recognition error, extraneous input,mismatched input , o no viable alternative).

Ejemplo de uso:

$ echo "aabb" | grun A r
$ echo "abbb" | grun A r
line 1:2 mismatched input 'b' expecting {<EOF>, '
'}
Cobre
fuente
Truco inteligente que agrega la nueva línea como alternativa en una sola regla. Creo que también podría ahorrar algunos en Yacc. La grammerpalabra clave es un apestoso para jugar al golf con antlr, sin embargo. Un poco como usar 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 aquellos que no están familiarizados:

  • strlen determina la longitud de la cadena
  • strcspn devuelve el primer índice en la cadena donde se encuentra la otra cadena
  • strchr devuelve un puntero a la primera aparición de un personaje
  • strrchr devuelve un puntero a la última aparición de un personaje

¡Muchas gracias a Titus!

Josh
fuente
1
guardar un byte con en >97lugar de==98
Titus
2
La solución de 61 bytes da falso positivo en cadenas como "aaabab". Ver ideone.com/nmT8rm
Jasmes
Ah, tienes razón Jasmes, gracias. Tendré que repensar esto un poco.
Josh
Volviendo a la solución de 69 bytes, no estoy seguro si puedo acortarme más con este enfoque.
Josh
3

R, 64 61 55 bytes, 73 67 bytes (robusto) o 46 bytes (si se permiten cadenas vacías)

  1. De nuevo, la respuesta de xnor se modificó . Si las reglas implican que la entrada consistirá en una cadena de asys b, debería funcionar: devuelve NULL si la expresión es válida, arroja un error o nada más.

    if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
    
  2. Si la entrada no es robusta y puede contener algo de basura, por ejemplo aa3bb, se debe considerar la siguiente versión (debe devolverse TRUEpara casos de prueba verdaderos, no NULL):

    if(length(y<-scan(,'')))is.null(eval(parse(t=chartr("ab","{}",y))))
    
  3. Finalmente, si se permiten cadenas vacías, podemos ignorar la condición para la entrada no vacía:

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

    Nuevamente, NULL si tiene éxito, cualquier otra cosa.

Andreï Kostyrka
fuente
No sé R, ¿cuál es su resultado para la entrada vacía? (debería ser falso)
Tito
¿Realmente no hay una forma más corta de probar la entrada vacía?
Titus
Versión 1: apenas nada (entrada correcta devuelve sólo NULL), versión 2, es suficiente nada (entrada correcta devuelve sólo TRUE), versión 3 (suponiendo cadenas vacías están bien, como estado): NULL. R es un lenguaje estadístico orientado a objetos que encasilla todo de manera correcta, sin ninguna advertencia.
Andreï Kostyrka
Esto (respuesta 1) se puede mejorar aún más a 55 bytes:if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
Giuseppe
3

Japt , 11 bytes

©¬n eȦUg~Y

Pruébalo en línea!

Da cualquiera trueo false, excepto que ""da"" que es falso en JS.

Desempaquetado y cómo 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

Adoptado de la solución MATL de Dennis .

Bubbler
fuente
2

C (Ansi), 65 75 bytes

Golfizado:

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

Explicación:

Establece un valor j e incrementa j en cada b y disminuye j en cualquier otra cosa. Se verificó si la letra anterior es menor o igual que la siguiente letra, así que evite que abab funcione

Ediciones

Se agregaron controles para casos de abab.

dj0wns
fuente
¿Esto no dará falsos positivos en cadenas como bao abab?
Zgarb
Ah, sí, leí mal la publicación ya que no podía ver la imagen ya que está bloqueada para mí. ¡Arreglando lo!
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

Devuelve un valor ERRORLEVELde 0 en caso de éxito, 1 en caso de error. A Batch no le gusta reemplazar las subcadenas en cadenas vacías, por lo que debemos verificarlo por adelantado; Si un parámetro vacío fuera legal, la línea 6 no sería necesaria.

Neil
fuente
2

PowerShell v2 +, 61 52 bytes

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

Toma la entrada $ncomo una cadena, crea $xcomo half the length. Construye una -andcomparación booleana entre $nun -matchoperador de expresiones regulares y la expresión regular de un número igual de a'sy b' s. Salidas booleanas $TRUEo $FALSE. El $n-andestá ahí para dar cuenta de ""= $FALSE.

Alternativo, 35 bytes

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

Utiliza la expresión regular de la respuesta de Leaky , basada en grupos de equilibrio .NET, simplemente encapsulada en el -matchoperador de PowerShell . Devuelve la cadena para la verdad o cadena vacía para falsey.

AdmBorkBork
fuente
En la versión alternativa se debe evaluar -matchen contra $args[0], de lo contrario -matchva a funcionar como un filtro
Mathias R. Jessen
@ MathiasR.Jessen En el código de producción, sí, pero podemos jugar golf [0]aquí porque solo se nos da una entrada y solo necesitamos un valor verdadero / falso como salida. Como una cadena vacía es falsey y una cadena no vacía es verdadera, podemos filtrar contra la matriz y recuperar la cadena de entrada o nada, lo que satisface los requisitos de desafío.
AdmBorkBork
2

Pyth - 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
fuente
Puede usar una cadena como entrada y luego hacerla&qS*/lQ2"ab
Leaky Nun
@LeakyNun gracias por el consejo! ¿Puedes explicar cómo / por qué funciona eso? Esta es mi primera vez usando Pyth
Cowabunghole
Por ejemplo, +4se expandirá a +4Q(relleno implícito de argumentos)
Leaky Nun
2

Haskell, 39 bytes

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

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

scanl(\s _->'a':s++"b")"ab"xconstruya una lista de todos ["ab", "aabb", "aaabbb", ...]con un total de (length x)elementos. elemcomprueba si xestá en esta lista.

nimi
fuente
2

Python, 43 40 bytes

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

consideró la solución obvia gracias a Leaky Nun

otra idea, 45 bytes:

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

-4 bytes usando len / 2 (obtengo un error cuando llega la mitad)

ahora da falso para la cadena vacía

-3 bytes gracias a xnor

KarlKastor
fuente
Sí, las lambdas no tienen que ser nombradas.
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
Sí, me di cuenta de eso mientras lo publicaba. jajaja, la solución obvia es más corta en Python 2:
KarlKastor
1
Puede hacerlo en ''<lugar de s anddescartar el caso vacío.
xnor