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:
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 código de golf . 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"
fuente
empty string == truthy
ynon-empty string == falsy
sería aceptable?a^n b^n
o similar, en lugar de solo el número dea
s igual al número deb
s)Respuestas:
MATL ,
54 bytesImprime 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
fuente
Python 3, 32 bytes
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
(
pora
y)
parab
. Solo las expresiones de la forma sea^n b^n
convierten 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 enexec
).La conversión
( -> a
,) -> b
se realiza utilizandostr.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 comoque tiene
( -> a
,) -> b
. En Python 2, se deben proporcionar conversiones para los 256 valores ASCII, que requieren"ab"*128
un byte más; Gracias a Isaac por señalar esto.fuente
*128
?128
se puede reemplazar por50
(o99
para el caso) para guardar un byte.Retina , 12 bytes
Créditos a FryAmTheEggman que encontró esta solución de forma independiente.
Imprime
1
entradas válidas y de0
otro 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
El
+
le dice a Retina que repita esta etapa en un bucle hasta que la salida deje de cambiar. Coincide con oab
oa;b
y lo reemplaza con;
. Consideremos algunos casos:a
s y losb
s de la cadena no están equilibrados de la misma manera que(
y)
normalmente tienen que ser, algunosa
ob
permanecerá en la cadena, ya queba
, ob;a
no se puede resolver y una solaa
ob
por sí solo no puede ya sea. Para deshacerse de todos losa
sy losb
s tiene que haber uno correspondienteb
a la derecha de cada unoa
.a
y elb
no son todos anidado (por ejemplo, si tenemos algo parecidoabab
oaabaabbb
) a continuación, vamos a terminar con múltiples;
(y potencialmente algunosa
s yb
s) debido a que la primera iteración encontrará múltiplesab
s 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
0
o"1
).fuente
Haskell, 31 bytes
La lista de comprensión
[c|c<-"ab",'a'<-s]
hace que una cadena de uno'a'
para cada uno'a'
des
, seguido de uno'b'
de cada'a'
ens
. 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.
fuente
f=g.span id.map(=='a');g(a,b)=or a&&b==(not<$>a)
). Bien hecho.Grime , 12 bytes
Pruébalo en línea!
Explicación
La primera línea define un no terminal
A
, que coincide con una letraa
, posiblemente el no terminalA
, y luego una letrab
. La segunda línea hace coincidir toda la entrada (e
) con la no terminalA
.Versión no competitiva de 8 bytes
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 etiquetaA
.fuente
Brachylog ,
2319 bytesPruébalo en línea!
Explicación
fuente
05AB1E , 9 bytes
Código:
Explicación:
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! .
fuente
.M{J¹ÔQ0r
por el tuyo.Jalea , 6 bytes
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
Versión alternativa, 4 bytes (no competitiva)
Imprime 1 o 0 . Pruébalo en línea! o verificar todos los casos de prueba .
Cómo funciona
fuente
J, 17 bytes
Esto funciona correctamente para dar falsey para la cadena vacía. El error es falsey.
Versiones antiguas:
Prueba y explicación
El verbo principal es un tenedor que consta de estos tres verbos:
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:
Dejemos
k
representar nuestra entrada. Entonces, esto es equivalente a:-:
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:
El diente derecho de las mitades de la horquilla (
-:
) la longitud (#
) dek
. Observar#
:Ahora, esto es
k
solo 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.fuente
2&#-:'ab'#~#
que debería permitirle evitar el error y simplemente mostrarlo en su0
lugar mientras todavía usa 12 bytes.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).
La función debería ser bastante obvia si sabe interpretarla en términos de una gramática formal. El analizador acepta cualquiera
ab
oa
seguido de cualquier secuencia aceptable seguida de ab
.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
yylex
y llamargetchar
.Compilar con
(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=c89
que agrega 8 al valor enumerado).Corre con
o equivalente.
El valor de verdad se devuelve al sistema operativo y los errores también informan
syntax error
a 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.fuente
Perl 5.10,
3517 bytes (con el indicador -n )Asegura que la cadena comienza con
a
sy luego vuelve a aparecer enb
s. 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í!
fuente
$_&&=y/a//==y/b//
(requiere-p
), sin el vacío, ¡podría dejar el&&
16! Tan cerca ...echo -n 'aaabbb'|perl -pe '$_+=y/a//==y/b//'
pero no puedo cambiar otro byte ... ¡Puede que tenga que renunciar a esto!JavaScript,
545544Crea 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.
fuente
f=
puede ser omitido.s=>s.match(`^a{${s.length/2}}b+$`)
?C,
5753 bytesAntigua solución de 57 bytes de longitud:
Compilado con gcc v. 4.8.2 @Ubuntu
Gracias ugoren por consejos!
Pruébalo en Ideone!
fuente
(t+=2)
at++++
-1 byte.t++++
no es un código C válido.t+=*s%2*2
y:*s*!1[s]
Retina , 22 bytes
Otra respuesta más corta en el mismo idioma acaba de llegar ...
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.
fuente
Befunge-93, 67 bytes
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
MATL , 9 bytes
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 .
fuente
código de máquina x86,
2927 bytesHexdump:
Código de montaje:
Itera sobre los
a
bytes 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:b
s no es 0, la cadena tampoco coincideLuego, 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 ++ pararesult = (result == 0)
:fuente
neg eax
configurar la bandera de acarreo como antes,cmc
invertir la bandera de acarreo ysalc
configurar 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.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
Rubí, 24 bytes.
(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
a
yb
a[
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á porquenil
no ha definido un*
método.fuente
Sed, 38 + 2 = 40 bytes
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
r
yn
banderas.Explicación
fuente
JavaScript,
4442Tachado 44 sigue siendo regular 44; (
Funciona por recursivamente quitándose el exterior
a
yb
y 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 exactoab
.Casos de prueba:
fuente
ANTLR, 31 bytes
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 llamado
A.g4
y ejecute estos comandos:Luego pruebe dando entrada en STDIN para que le
grun A r
guste así:Si la entrada es válida, no se generará nada; si no es válido,
grun
se producirá un error (ya seatoken recognition error
,extraneous input
,mismatched input
, ono viable alternative
).Ejemplo de uso:
fuente
grammer
palabra clave es un apestoso para jugar al golf con antlr, sin embargo. Un poco como usar fortran .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 cadenastrcspn
devuelve el primer índice en la cadena donde se encuentra la otra cadenastrchr
devuelve un puntero a la primera aparición de un personajestrrchr
devuelve un puntero a la última aparición de un personaje¡Muchas gracias a Titus!
fuente
>97
lugar de==98
R,
646155 bytes,7367 bytes (robusto) o 46 bytes (si se permiten cadenas vacías)De nuevo, la respuesta de xnor se modificó . Si las reglas implican que la entrada consistirá en una cadena de
a
sysb
, debería funcionar: devuelve NULL si la expresión es válida, arroja un error o nada más.Si la entrada no es robusta y puede contener algo de basura, por ejemplo
aa3bb
, se debe considerar la siguiente versión (debe devolverseTRUE
para casos de prueba verdaderos, no NULL):Finalmente, si se permiten cadenas vacías, podemos ignorar la condición para la entrada no vacía:
Nuevamente, NULL si tiene éxito, cualquier otra cosa.
fuente
NULL
), versión 2, es suficiente nada (entrada correcta devuelve sóloTRUE
), 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.if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
Japt , 11 bytes
Pruébalo en línea!
Da cualquiera
true
ofalse
, excepto que""
da""
que es falso en JS.Desempaquetado y cómo funciona
Adoptado de la solución MATL de Dennis .
fuente
C (Ansi),
6575 bytesGolfizado:
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.
fuente
ba
oabab
?Lote, 133 bytes
Devuelve un valor
ERRORLEVEL
de 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.fuente
PowerShell v2 +,
6152 bytesToma la entrada
$n
como una cadena, crea$x
comohalf the length
. Construye una-and
comparación booleana entre$n
un-match
operador de expresiones regulares y la expresión regular de un número igual dea
'syb
' s. Salidas booleanas$TRUE
o$FALSE
. El$n-and
está ahí para dar cuenta de""
=$FALSE
.Alternativo, 35 bytes
Utiliza la expresión regular de la respuesta de Leaky , basada en grupos de equilibrio .NET, simplemente encapsulada en el
-match
operador de PowerShell . Devuelve la cadena para la verdad o cadena vacía para falsey.fuente
-match
en contra$args[0]
, de lo contrario-match
va a funcionar como un filtro[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.Pyth - 13 bytes
Explicado:
fuente
&qS*/lQ2"ab
+4
se expandirá a+4Q
(relleno implícito de argumentos)Haskell, 39 bytes
Ejemplo de uso:
p "aabb"
->True
.scanl(\s _->'a':s++"b")"ab"x
construya una lista de todos["ab", "aabb", "aaabbb", ...]
con un total de(length x)
elementos.elem
comprueba six
está en esta lista.fuente
Python,
4340 bytesconsideró la solución obvia gracias a Leaky Nun
otra idea, 45 bytes:
-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
fuente
lambda s:list(s)==sorted("ab"*len(s)//2)
(Python 3)lambda s:s=="a"*len(s)//2+"b"*len(s)//2
(Python 3)''<
lugar des and
descartar el caso vacío.