Una serpiente elástica se ve así:
<||=|||:)~
Cada secuencia separada de barras verticales ( |
) en una serpiente elástica, conocida como una porción elástica , es extensible individualmente al doble de su ancho, y se dibuja con barras alternas ( /
, \
) una vez extendidas.
La serpiente particular de arriba tiene dos porciones elásticas, que le dan cuatro poses posibles:
<||=|||:)~
</\/\=|||:)~
<||=/\/\/\:)~
</\/\=/\/\/\:)~
La forma general de una serpiente elástica en su pose menos estirada se define por esta expresión regular :
<(\|+=)*\|+:\)~
Que puede expresarse en palabras como:
<
, seguido de cualquier número de secuencias de|
's unidas con=
signos, seguido de:)~
.
So <|:)~
y <||:)~
y <|=|:)~
y <|=|=||=|||||=||:)~
son serpientes elásticas, pero <=:)~
y <=|:)~
y <||=:)~
y <|==||:)~
no lo son.
Las serpientes elásticas también pueden mirar hacia la izquierda en lugar de hacia la derecha, por ejemplo ~(:|||=||>
. Las formas son las mismas, solo reflejadas.
Desafío
Escriba un programa que tome una cadena de una sola línea de dos serpientes elásticas una frente a la otra, con cierto número de espacios en el medio. Ambas serpientes estarán en su postura menos estirada (todas las barras verticales, sin barras). La cadena comenzará con la cola de la serpiente que mira hacia la derecha y terminará con la cola de la serpiente que mira hacia la izquierda (opcionalmente, puede suponer que también hay una nueva línea final).
Por ejemplo, aquí hay una posible entrada con cinco espacios entre las serpientes:
<|=||:)~.....~(:||||>
Estoy usando puntos ( .
) en lugar de caracteres espaciales reales para mayor claridad.
Cero espacios entre serpientes también es una entrada válida:
<|=||:)~~(:||||>
Decimos que las serpientes se besan cuando sus lenguas se tocan así.
Su programa necesita extender alguna combinación de las partes elásticas de ambas serpientes para que las serpientes tengan la menor cantidad de espacios posibles entre ellas (sin superponerse), es decir, para que las serpientes estén tan cerca de besarse como sea posible .
Ambas colas de las serpientes están fijas, pero sus cabezas y cuerpos pueden moverse, derecha para la serpiente que mira hacia la derecha, izquierda para la serpiente que mira hacia la izquierda, de acuerdo con las porciones elásticas que se han extendido.
La salida de su programa es la cadena de una sola línea (más la nueva línea final opcional) que muestra a las serpientes lo más cerca posible de besarse, con barras diagonales alternadas en lugar de barras verticales para las porciones elásticas que se han extendido.
Por ejemplo, la salida para <|=||:)~.....~(:||||>
(desde arriba) sería:
</\=||:)~~(:/\/\/\/\>
Esta es la única solución aquí porque con cualquier otra combinación de las porciones elásticas extendidas, las serpientes se superpondrían o estarían más lejos de besarse.
Si hay varias soluciones posibles, la salida puede ser cualquiera de ellas.
Por ejemplo, si la entrada fuera
<|=||:)~.....~(:|||=|>
la salida podría ser
<|=/\/\:)~~(:/\/\/\=|>
o
</\=||:)~~(:/\/\/\=/\>
Recuerda que no siempre será posible besar a las serpientes, pero aún así necesitas acercarlas lo más posible.
Por ejemplo, si la entrada fuera
<||=||||:)~...~(:||>
la salida podría ser
</\/\=||||:)~.~(:||>
o
<||=||||:)~.~(:/\/\>
Si las serpientes ya se están besando, la salida será la misma que la entrada. p.ej
<|=||:)~~(:||||>
En general, la salida será la misma que la entrada si la extensión de cualquier parte elástica haría que las serpientes se superpongan. p.ej
<|||=|||:)~..~(:||||=|||||=||||||>
Notas
- Toma la entrada de stdin o la línea de comando como de costumbre, o escribe una función que toma una cadena. Imprime o devuelve la salida.
- Puede usar puntos (
.
) en la entrada y salida en lugar de espacios () si lo prefiere.
- Solo es importante que las barras se alternen dentro de la secuencia de barras verticales que reemplazaron. Su orden en la serpiente en general o si un corte hacia adelante o hacia atrás es lo primero no importa.
- Las partes elásticas no pueden extenderse hasta la mitad: es exactamente el doble o ninguna extensión.
Puntuación
Este es el código de golf . La presentación más corta en bytes gana. Tiebreaker es la respuesta anterior.
fuente
>
no se convertiría<
tampoco, lo mismo para(
y)
), pero también dice "Es importante que las barras se alternen dentro de la secuencia de barras verticales que reemplazaron. serpiente en general o si una barra diagonal hacia adelante o hacia atrás es lo primero "Respuestas:
CJam,
87717068 bytesPruébelo en línea en el intérprete de CJam .
Cómo funciona
fuente
Retina ,
209107999792 bytesPara fines de conteo, cada línea va en un archivo separado, pero puede ejecutar el código desde un solo archivo con la
-s
bandera.Reúne las mejores características de .NET regex y Retina: grupos de equilibrio, búsquedas arbitrarias de longitud arbitraria y repetidas sustituciones de expresiones regulares.
Esencialmente, la expresión regular larga codifica una solución válida y el rastreador del motor de expresión regular encuentra uno de los mejores para mí.
Explicación
Primero, consideremos cómo podemos encontrar una solución válida (no necesariamente produciendo la salida correcta) con una expresión regular. Podemos usar los grupos de equilibrio de .NET para ayudarnos a contar las partes elásticas. Considere la siguiente expresión regular más simple:
Podemos diseccionar eso.
Esto coincide con la cadena completa, empujando una captura en la
1
pila de grupo para cada espacio en la entrada. Usaremos esa pila para asegurarnos de que las partes elásticas llenen exactamente el espacio capturado en esos grupos.El siguiente es un vistazo atrás. El problema es que las retrospectivas coinciden de derecha a izquierda en .NET (así es como debe leerlas). Esto nos da la oportunidad de atravesar la cadena por segunda vez, averiguar si hay un subconjunto de partes elásticas que sume al número de espacios coincidentes. Pasando por el lookbehind de derecha a izquierda:
Esto es solo para asegurarnos de que realmente estamos comenzando desde el final de la cadena (la cola de la serpiente).
Para cada parte elástica, esto solo coincide con la parte completa sin hacer nada (
\|+
), o coincide con la parte completa al extraer las capturas de la pila1
((?<-1>\|)*
). Tener esta alternancia asegura que solo podamos extender completamente una parte elástica o dejarla sin cambios, y no obtener cosas como|/\|
. Luego pasamos a la siguiente parte elástica con[^|]+
.Finalmente, nos aseguramos de que hemos atravesado toda la cadena (ambas serpientes), y esa pila
1
está completamente vacía. Es decir, hemos encontrado un subconjunto de partes elásticas que se suma exactamente al número de espacios que hemos capturado anteriormente.El rastreador retrocederá de un lado a otro a través de la cadena intentando todas las combinaciones de partes extendidas y sin cambios hasta que se resuelva el problema de la suma de subconjuntos. Si tal subconjunto no existe, la retrospectiva fallará. Esto hará que el rastreador regrese a la
\S+( )+.+
pieza e intente capturar un espacio menos con( )+
(que en su.+
lugar se cubrirá ). Debido a la avaricia de+
, por lo tanto, intentamos llenar tantos espacios como sea posible.Puede verificar la validez de este enfoque con esta sustitución ligeramente modificada:
Lo que le dará una cadena
=spaces=
con exactamente el número de espacios que se pueden llenar con las serpientes dadas.Tuve que agregar algunos trucos más para expandir realmente el
|
s correcto . Básicamente, quiero reemplazar todos los correos|
electrónicos que coinciden con la(?<-1>\|)+
rama. La idea es hacer coincidir un personaje individual, poner el solucionador en una búsqueda y establecer una bandera si la coincidencia está dentro de esa rama. Si esa bandera no se estableció, invalidamos la coincidencia al final para evitar el reemplazo de otros personajes.Para hacer esto, usamos un montón de miradas anidadas. Nuevamente, los lookbehinds de longitud variable de .NET coinciden de derecha a izquierda, por lo que si anidamos lookaheads y lookbehinds, podemos dejar que el motor regex atraviese la cadena varias veces. Por razones de golf, el solucionador se invierte en mi solución real (comenzando por el final, recogiendo los espacios de derecha a izquierda y luego resolviendo la suma del subconjunto de izquierda a derecha), pero de lo contrario la estructura del solucionador es exactamente la misma . Vamos a diseccionar la expresión regular completa:
Hacemos coincidir un solo carácter, luego capturamos el resto de la cadena y movemos el cursor al final de la cadena. Usaremos este grupo
1
más tarde para verificar en el solucionador si estamos en la posición del partido.Esto es como la primera parte del solucionador simple anterior, excepto que recogemos los espacios de derecha a izquierda. El retroceso del número de espacios funciona exactamente igual que antes, excepto que
5
ahora estamos usando group .Esto es lo mismo que antes, excepto que vamos de izquierda a derecha, y cada vez que hacemos coincidir una
|
en la rama en expansión, verificamos si es la que coincide con la derechaEsta es una búsqueda anticipada opcional. Intenta hacer coincidir el grupo
1
nuevamente (lo cual, aquí, solo es posible si estamos justo después del carácter que coincide), y si lo hacemos, capturamos una cadena vacía en el grupo4
, lo que indica que encontramos el carácter actual en uno de los bits expandidos. Si\1
no coincide,4
no capturará nada, y?
garantiza que la búsqueda anticipada que falla no afectará en absoluto al solucionador.Finalmente, después de que se haya resuelto todo, solo verificamos
\4
si se utilizó esta búsqueda anticipada. Si es así, queremos reemplazar el carácter actual con/\
.Queda una dificultad: eliminar la cantidad correcta de espacios. La forma más corta de hacer esto que he encontrado hasta ahora es insertar un espacio junto con el
/\
y luego eliminar un espacio entre las lenguas para cada uno de esos espacios marcadores en un paso separado:fuente
Rubí
191 187 186 170162Esta es una función que toma una cadena como parámetro y devuelve una cadena.
Pruebas en línea: http://ideone.com/uhdfXt
Aquí está la versión legible:
En la versión de golf, la función principal es el equivalente de la
KISS
función anterior, y laCOMBINATIONS
función ha sido en línea.fuente
<|=||:)~~(:||||>
, que la especificación menciona es una entrada válida.Python, 205 bytes
Tener una sola lambda se ve bien y todo, pero estoy casi seguro de que esta no es la mejor manera de hacerlo. Pero estoy publicando esto porque es todo lo que tengo hasta ahora que parece medio decente.
Esta es una fuerza bruta simple sobre todos los posibles reemplazos de
|
with/\
, filtrando las configuraciones inválidas. El único poco aseado que supongo es que en realidad no reemplaza ninguna|
con/\
directamente - en primer lugar reemplazamos|
conX
y coloca una.
de la media para cada reemplazo, tomar la cadena de longitud mínima sobre todas las cadenas válidas y vuelva a colocar losX
s con/\
.Intenté algunos otros enfoques, incluidos los recursivos, pero terminaron siendo bastante desordenados. También aprendí que
re.split
actualmente no se divide en cadenas vacías, lo cual fue desafortunado, porque una de mis ideas implicaba dividir en\b
límites de palabras.fuente
Mathematica, 381 bytes
Función pura tomando la cadena como argumento. Espera
.
más queentre las serpientes.
No pensé que sería tan malo ... Esto es lo que tenía antes de juntarlo y fijar todo.
Aquí hay un ejemplo de explicación:
fuente
a=StringReplace;b=StringSplit;c=StringLength;d=Total;
y luego sustituirlos según sea necesario en otro lugar dentro:a=StringReplace;b=StringSplit;c=StringLength;d=Total;a[MapAt[a[#,"|"->"/\\"]&,b[#<>"="<>#2,"="],#3]~StringRiffle~"=",")="->")~"<>If[#4>0,"."~StringRepeat~#4,""]<>"~"]&[#1,#3,Sequence@@Function[{l,s},{#,#2-d@Extract[l,#]}&[Flatten[l~Position~#~Take~#2&@@@Tally@#&@@Select[Subsets@l,d@#<=s&]~MaximalBy~d,1],s]][c/@StringCases[#1<>#3,"|"..],c@#2]]&@@#~b~"~"&
Prólogo (ECLiPSe), 438 bytes
Mis otras respuestas fueron resolver el problema incorrecto (perdón por el ruido). Aquí hay otro intento en Prolog que realmente respeta todas las reglas.
Pruebas
(formato: entrada, salida, nueva línea)
Explicaciones
El predicado principal es
s/2
, que toma la entrada como primer argumento y descalifica el resultado con el segundo argumento (ambas cadenas). La entrada es convertida a una lista de códigos de caracteres,E
.Luego,
s(E,Z,X,Y,L)
desestructura la lista en los siguientes elementos:Z
cantidad de espacios entre serpientesX
yY
, representación abstracta de los cuerpos izquierdo y derechoEl formato de un cuerpo es una lista de
n:N
os:N
expresiones, dondeN
es una longitud positiva;n
mediosnormal
ys
mediosstretched
.L
longitud total de la listaLo interesante
s/5
es que va en ambos sentidos , es decir, podemos construir una serpiente si se instancian otros argumentos:Q
que separa a las nuevas serpientes. La longitud total de la cadena calculada está limitada para que la búsqueda finalice.fuente
Python 2.7.3
427421400371 bytesCódigo no golf aquí -
Probar la solución de golf -
Seguramente esto se puede hacer mejor (no puedo entender cómo :)).
Avíseme si me he perdido algo obvio mientras jugaba al golf (es mi primer codegolf, puedo estar haciendo algo estúpido: P)
fuente
exit
porsys.exit()
(olvidadoexit
existió). Y tienes razón,__import__
se puede eliminar, eso se eliminó como 20 caracteres :)> 6
caracteres que valen el alias si lo usa dos veces,> 3
caracteres si lo usa tres veces. No estoy seguro de que elf=' '
alias valga la pena (cuento dos veces)05AB1E , 93 bytes
Demasiado tiempo ..>.>
Pruébelo en línea o verifique todos los casos de prueba o verifique todos los resultados posibles para todos los casos de prueba .
Explicación:
fuente