Considere estas cinco criaturas marinas de arte ASCII:
- Pescado estándar:
><>
o<><
- Pez veloz:
>><>
o<><<
- Pescado robusto:
><>>
o<<><
- Pescado elástico:
><<<>
o<>>><
- Cangrejo:
,<..>,
Escriba un programa que acepte una cadena arbitraria de los caracteres <>,.
. Si hay una manera de interpretar la cadena completa como una serie de criaturas marinas que no se superponen, entonces la cadena debe reimprimirse con espacios individuales insertados entre las criaturas. Si esta interpretación es imposible, no se generará nada (el programa finaliza en silencio).
Por ejemplo, la cadena <><><>
se puede interpretar como dos peces estándar consecutivos. La salida correspondiente sería <>< ><>
.
Como otro ejemplo, la cadena ><>><>>
contiene "instancias" de ...
(los corchetes solo se agregan como indicadores)
- un par de peces estándar:
[><>][><>]>
- un pez veloz:
><[>><>]>
- un pez robusto de dos maneras:
[><>>]<>>
y><>[><>>]
sin embargo, solo el emparejamiento de un pez estándar y un pez resistente [><>][><>>]
abarca toda la longitud de la cadena sin caracteres de intercambio de peces (sin superposiciones). Por lo tanto, la salida correspondiente a ><>><>>
es ><> ><>>
.
Si hay varias formas de interpretar la cadena, puede imprimir cualquiera de ellas. (Y sólo imprimir una . De ellas) Por ejemplo, <><<<><
puede ser interpretado como un pez estándar y un pez robusto: [<><][<<><]
, o como un pez rápido y un pez estándar: [<><<][<><]
. Entonces, <>< <<><
o <><< <><
sería una salida válida.
Los cangrejos son solo por diversión. Como no comienzan o terminan con <
o >
, son mucho más fáciles de identificar (al menos visualmente). Por ejemplo, la cadena
,<..>,><<<>,<..>,><>,<..>,<>>><,<..>,><>>,<..>,<<><,<..>,<><,<..>,>><>
obviamente produciría la salida
,<..>, ><<<> ,<..>, ><> ,<..>, <>>>< ,<..>, ><>> ,<..>, <<>< ,<..>, <>< ,<..>, >><>
Aquí hay algunos ejemplos de cadenas (una por línea) que no producen salida:
<><>
,<..>,<..>,
>>><>
><<<<>
,
><><>
,<><>,
<<<><><<<>>><>><>><><><<>>><>><>>><>>><>><>><<><
La última cadena aquí se puede analizar si elimina el inicio <
:
<<>< ><<<> >><> ><> ><> <>< <>>>< >><> >><> >><> ><>> <<><
(Puede haber otras salidas posibles).
Detalles
- La cadena de entrada solo contendrá los caracteres
<>,.
. - La cadena de entrada tendrá al menos un carácter de longitud.
- Tome la entrada de cualquier manera común (línea de comando, stdin) y la salida a stdout.
- El código más corto en bytes gana. ( Práctico contador de bytes ) . Tiebreaker es una publicación anterior.
fuente
Respuestas:
Pyth,
644850 bytesCaso de prueba.
Versión que no tarda para siempre ( ) aquí , en 52 bytes.
O(9n/3)
Este es el enfoque de fuerza bruta, genera todas las secuencias y verifica si hay alguna suma en la entrada. Diagramas de peces comprimidos como caracteres, cuyas representaciones binarias son las
>
y<
. Todo está envuelto en un bloque try-catch para que no se produzca salida cuando no se encuentran resultados.Esta es una solución.
O(9n)
Algunos caracteres se eliminan arriba porque se usan caracteres de control. Se reproducen fielmente en el enlace de arriba.
salida xxd:
fuente
><>><>>
Toma 15 segundos en mi máquina.Máquina de Turing no determinista, 20 estados, 52 transiciones (882 bytes tal vez)
¿Cómo se convierte esto a bytes? He escrito los archivos (absolutamente sin golf) para ejecutar esta máquina con el Simulador de una máquina de Turing de Alex Vinokur 1 .
wc -c
genera lo siguiente (excluyendo el archivo de descripción y los archivos de entrada):De todos modos, me estaba preparando para mis A-Levels de informática, así que pensé que sería un buen ejercicio (no sé lo que estaba pensando). Así que aquí está la definición:
(la función de transición)
Disculpe la mala imagen, pero no podría molestarme en volver a dibujar esta cosa en una computadora. Si realmente desea descifrar las reglas de transición, le recomiendo que lea el archivo de reglas que he vinculado anteriormente.
He usado
X
s en lugar de espacios porque los espacios son difíciles de visualizar aquí y el simulador no acepta espacios en el alfabeto.El concepto es bastante simple: q1 a q4 se usan para atrapar peces orientados a la derecha, q11 a q14 se utilizan para atrapar peces orientados a la izquierda, q15 a q19 para cangrejos y la mancha de q5 a q10 es simplemente para insertar un espacio y mover todo siguientes personajes uno a la derecha.
Si la cadena es interpretable, acepta la cadena y la cinta contiene la cadena con espacios insertados. De lo contrario, rechaza la cadena (supongo que esto no cuenta como salida; vaciar la cinta sería bastante fácil, pero requeriría muchas reglas de transición y no creo que haga que la función de transición sea más bonita de ver).
1 Nota: es difícil de compilar. Tuve que editar el
src/tape.cpp
archivo y reemplazarLONG_MAX
con1<<30
y luego ir aldemo
directorio, editar el Makefile para reemplazarEXE_BASENAME
conturing.exe
y ejecutarmake
. Luego ve al directorio con los archivos que he escrito y ejecuto/path/to/turing/download/src/turing.exe meta
.fuente
pez (sí, ese pez), 437 bytes
Esto me parece una de esas tareas de programación donde exactamente un lenguaje es correcto.
La siguiente versión sigue siendo la respuesta más larga al desafío,
pero dado que esto se hizo principalmente para el juego de palabras (perdón, espero), el mejor golf se deja como un ejercicio para el lector.
fuente
printf 'H4sIADSjKlUCA4VPQW6DMBC89xUj5AOocSSOlV1/BHGgjgMrBUPN0kRRHl/jmEg99WBLszM7M7s4BqMw2hQotNHxNy+QkDYJZU7rTJqED/p4NIdCLdFmVOfVW6bJY04DeQGhVteBLg4cVqfYLQxBkD3jQ6HzJwTHa/BRRmf4ibEtBpRfriefXCxKZ4cJghtB7eNqIW2lnqMu9D9N3T7sGtOssDInJCk+982/MlmOHQ+I6rqKRv5UpRxCntN7XSk7eSYfK0f+eR3EmI23qilH3iFCrjIqdyNO8nzJvJH7alMu7jsnlHZafWw5VluD9r/0/c2vQ95+AYBxAwS2AQAA'|base64 --decode|gzip -d>a;fish a
> <>, 602 bytes
Una solución en Fish, probablemente muy golfable pero es mi primer programa> <>. Toma su entrada de la pila de entrada y se ejecuta en el intérprete en línea> <>.
Cómo funciona :
Un bucle lee toda la entrada y la apila, invierte y coloca un -1 en la parte inferior que marcará que el análisis se ha completado (todos los caracteres permanecen en la pila hasta que la cadena se considere analizable).
El análisis utiliza el hecho de que todos los caracteres son diferentes módulo 5, y todos los patrones son deterministas excepto <> << y> <>>. Los personajes analizados se colocan en la parte inferior de la pila.
Cuando se completa un patrón, si -1 está en la parte superior, se imprimen todos los caracteres; de lo contrario, se agrega un espacio y el programa se repite.
Si se encuentran <> << o> <>>, el registro se incrementa (0 al comienzo) y se coloca un 0 en la pila antes del último carácter (de modo que <> <o> <> permanezca después de la reversión) . Si después aparece un error durante el análisis, el registro disminuye, todos los caracteres después del 0 se vuelven a colocar en la parte superior (excepto los espacios gracias a una prueba% 8 = 0).
Si se detecta un error mientras el registro es 0, o dentro del cangrejo, el programa acaba inmediatamente.
fuente
Pitón 3, 156
La estrategia es generar listas de peces y comparar su concatenación con la cadena de entrada.
Esto lleva imposiblemente largo. Si realmente desea ver una salida, reemplace
for _ in s
confor _ in [0]*3
, donde 3 es el límite superior para el número de peces. Funciona para usars
porques
contiene como máximo un pez por carbón.Gracias a Sp3000 por la corrección de errores y un ahorro de caracteres en la entrada.
Viejo 165:
fuente
a and b or c
dio un valor incorrecto cuandob
podría ser Falsey. Volví aif/else
2 caracteres, pero podría haber una manera de hacer que el ternario funcione.*l,s=[],input()
Perl, 81 + 1 bytes
Prueba este código en línea.
Este código espera la entrada en la
$_
variable; ejecute esto con el-n
interruptor de Perl ( contado como +1 byte ) para aplicarlo a cada línea de entrada, por ejemplo, así:Este código utiliza el motor regexp de Perl (y específicamente su función de ejecución de código incrustada ) para realizar una búsqueda de retroceso eficiente. Los peces individuales encontrados se recopilan en la
@a
matriz, que se stringifica e imprime si la coincidencia es exitosa.Este código también utiliza el Perl 5.10+
say
función, por lo que se debe ejecutar con el-E
o-M5.010
interruptor (ouse 5.010;
) para permitir que tales características modernas. Por tradición, estos interruptores utilizados únicamente para habilitar una versión particular del idioma no se incluyen en el recuento de bytes.Alternativamente, aquí hay una versión de 87 bytes que no requiere modificadores especiales de línea de comandos. Lee una línea de stdin e imprime el resultado (si lo hay) en stdout, sin ningún avance de línea final:
PD. Si se permitiera imprimir un espacio extra al comienzo de la salida, podría guardar trivialmente dos bytes más con:
fuente
><(>|<<)>
Python 3,
196186 bytesRecurrencia simple
g
devuelve una lista de peces analizados oNone
si la cadena de entrada no se puede analizar.fuente
Python 2, 234 bytes
Primero probé una solución de expresión regular de Python, pero parece que no hay forma de extraer los grupos después de una coincidencia en múltiples patrones. La siguiente es una búsqueda recursiva que parece funcionar bien en los casos de prueba.
Un ejemplo de prueba:
Y la versión sin golf:
fuente
if
puede estar en una sola línea (como lo hizo en otro lugar). Además, en lugar deif p<len(t)
creo que puede hacerif t[p:]
para guardar unos pocos bytes.C # - 319 bytes
Esta solución es vergonzosamente simple, casi nada para Golf. Es un programa completo, toma la entrada como una línea de STDIN y envía el resultado a STDOUT.
Simplemente intenta hacer coincidir cada pez con la primera posición después de un espacio (o al comienzo de la secuencia), y hace coincidir cada tipo de pez con él. Si el pez encaja, llama recursivamente al solucionador después de insertar un espacio después del pez, o simplemente devuelve su entrada (con un \ n por razones de salida) si la cadena no coincidente es literalmente el pez (es decir, hemos encontrado una solución) .
No he hecho un gran intento de darle a la cuerda de pescado el tratamiento habitual de kolmogorov, porque no es tan largo y no puedo encontrar una forma barata de invertir una cuerda en C # (no creo que LINQ pagará), por lo que puede haber alguna oportunidad allí, pero dudo un poco.
fuente
Haskell (Parsec) - 262
fuente
Soy un poco un novato de Python, así que ignora la rareza: P
fuente
m
lugar demsg
, ens
lugar destart
, ...) y usar solo 1 espacio por incremento. Y luego agregue el recuento de caracteres de su programa (puede contarlos aquí ).Rubí, 177 bytes
No es el más corto sino el primero en rubí:
El intento aquí es extender recursivamente una expresión regular y compararla con la entrada.
Si se encuentra una coincidencia más larga, r () se repetirá, de lo contrario comprobará si la última coincidencia consume toda la cadena de entrada y solo luego la generará con espacios añadidos.
fuente
CJam,
111 9691 (o 62 bytes)Un enfoque codicioso iterativo para seguir descubriendo qué son posibles todas las combinaciones de peces a medida que itera. Realmente no golf en este momento.
El código contiene algunos caracteres no imprimibles, por lo tanto, utilice el siguiente enlace como referencia.
Actualizar codificado la cadena
Agregará explicación una vez que termine de jugar al golf
Pruébalo en línea aquí
62 bytes
Versión super lenta. Básicamente, esto crea todas las combinaciones y comprobaciones que son iguales a la entrada.
Esto también contiene caracteres no imprimibles, así que confíe en el siguiente enlace.
Pruébalo en línea aquí
fuente
Haskell,
148146bytesPruebas:
$ echo "> <>> <>>" | runhaskell fishes.hs
Explicación
Basado en mi respuesta anterior a una pregunta similar. El algoritmo se ejecuta en tiempo exponencial.
Esto se lee de derecha a izquierda.
Esto no imprimirá una cadena que termine con un espacio, aunque dichas cadenas también se generan, porque su contraparte sin espacio se genera primero.
fuente
JavaScript (ES6), 164
Recursivo, primer escaneo profundo.
Como un programa con E / S a través de una ventana emergente:
Como una función comprobable:
Conjunto de pruebas (ejecutar en la consola Firefox / FireBug)
Salida
Ungolfed solo la función k
fuente
Haskell,
148142esto usa las comprensiones de la lista para iterar sobre los peces, elegir los que coinciden con el inicio y continuar recursivamente.
fuente
Javascript (
122135 bytes)No es el más golfizado aquí, podría despojarse un poco.
Este está basado en expresiones regulares, y es un poco difícil de entender qué está pasando.
Este es un trazador de líneas.
Básicamente, verifico la sintaxis y luego divido la cadena en función de los caracteres y la unimos.
Lanza una excepción cuando le da una entrada no válida.
Si no puede lanzar excepciones (
126139 bytes):Ambos son de una sola línea.
Ambos funcionan de la misma manera.
Gracias @ edc65 por detectar el caso límite que no funcionaba bien.
Puede probarlo aquí (la salida se escribirá en el documento).
Se basa en la versión que arroja excepciones cuando introduce código no válido.
Mostrar fragmento de código
(Actualmente, hay un error en los fragmentos de pila,
He publicado en metaYa se le preguntó ayer. Para que funcione, lo reemplacé$
con\x24
, que tiene la misma salida. Puede leer sobre el error aquí: http://meta.codegolf.stackexchange.com/questions/5043/stack-snippets-messing-with-js )fuente
><>><>>
. Creo que esto no puede resolverse tan fácilmente con Regexp, necesitas algo de anticipación o retroceso o lo que sea ...Scala, 299 bytes
Casos de prueba
Salida
fuente
Java, 288 bytes
Formateado:
fuente
No iba por el tamaño, pero aquí hay una manera fácil de entender de Dart.
fuente
Python 3,
166164 bytesSolución recursiva. Tarde a la fiesta, pero pensé en publicarlo de todos modos ya que supera a Sp3000 por
2022 bytes sin tener que forzar la respuesta por fuerza bruta.fuente