Suponga que un día está buscando en su gran caja de cables y adaptadores de computadora no utilizados (USB a USB mini, VGA a DVI, etc.). Hay cables enredados en todas partes que hacen un desastre, y te preguntas si podrías simplificar las cosas al unir todos los cables en un solo hilo y luego enrollarlos.
La pregunta es, ¿es posible conectar todos sus cables y adaptadores en una línea larga como esta? Obviamente, no siempre es posible, por ejemplo, si solo tuviera dos cables con enchufes completamente diferentes, no podrían conectarse entre sí. Pero si tuviera un tercer cable que pueda conectarse a ambos, entonces podría unir todos sus cables.
No le importa qué tipo de enchufes hay en los extremos del cordón de todos los cables. No necesitan conectarse entre sí para formar un bucle. Solo desea saber si es posible hacer el cordón de cable completo y, si es así, cómo hacerlo.
Reto
Escriba un programa o función que tome una cadena multilínea donde cada línea represente uno de los cables que posee. Un cable está formado por uno o más guiones ( -), con un enchufe en cada extremo. Un complemento siempre es uno de los 8 caracteres ()[]{}<>.
Estos son algunos cables válidos:
>->
(--[
}-{
<-----]
(---)
Pero estos no son:
-->
(--
)--
[{
---
Al conectar cables, solo se pueden conectar entre sí enchufes con exactamente el mismo tipo de soporte.
Estas son algunas conexiones de cable válidas:
...---((---...
...---))---...
...---]]---...
...---{{---...
...---<<---...
Y estos no son válidos:
...---()---...
...---)(---...
...---{]---...
...---{[---...
...---><---...
...--->)---...
Si todos los cables de la entrada se pueden reorganizar y unir en una sola hebra larga, entonces envíe esa hebra a stdout en una línea (con una nueva línea final opcional). Cuando hay varias soluciones, puede elegir cualquiera de ellas para la salida. Si no es posible hacer un solo capítulo, no envíe nada (o envíe una cadena vacía con una nueva línea final opcional).
Por ejemplo, si la entrada es
[-->
{---]
>----{
la salida podría ser
[-->>----{{---]
donde todos los cables están unidos.
Sin embargo, si la entrada fuera
[-->
{---]
los cables no se pueden conectar, por lo que no habría salida.
Tenga en cuenta que los cables se pueden voltear tanto como sea necesario para hacer las conexiones. por ejemplo, [-->y <--]son efectivamente el mismo cable porque pueden hacer el mismo tipo de conexiones. Algunas salidas pueden depender de voltear los cables de entrada.
Por ejemplo
(-[
}--]
podría tener salida
(-[[--{
donde se voltea el segundo cable, o
}--]]-)
donde se voltea el primer cable.
(Tenga en cuenta que, en general, invertir toda la salida es válido porque es lo mismo que invertir inicialmente cada cable individualmente).
Las longitudes de los cables en la salida, por supuesto, deben coincidir con las longitudes de los cables de entrada correspondientes. Pero los cables pueden reordenarse y girarse tanto como desee para hacer que el cable esté completamente trenzado. La entrada siempre contendrá al menos un cable.
El código más corto en bytes gana.
Casos de prueba
Casos con salida:
[-->
{---]
>----{
gives
[-->>----{{---]
or
[---}}----<<--]
(-[
}--]
gives
(-[[--{
or
}--]]-)
(-)
gives
(-)
[--{
gives
[--{
or
}--]
[-]
]-[
gives
[-]]-[
or
]-[[-]
[----->
)------------[
{--<
}---)
could give
[----->>--}}---))------------[
or
>--}}---))------------[[----->
or
}---))------------[[----->>--}
or
{--<<-----]]------------((---{
etc.
>-->
>->
>--->
could give
>-->>->>--->
or
>--->>-->>->
or
>->>-->>--->
or
<--<<---<<-<
etc.
(-]
]->
>-}
}-)
)-[
[-<
<-{
{-(
could give
(-]]->>-}}-))-[[-<<-{{-(
or
{-((-]]->>-}}-))-[[-<<-{
or
<-{{-((-]]->>-}}-))-[[->
etc.
Casos sin salida:
[-->
{---]
[-]
[-]
(-]
]->
}-)
>->
>-->
]---]
[-------------------]
]-------------------[
[-----------------]
[-----------------]
{--[
]--}
Respuestas:
Ilegible , 3924 bytes
Esta es la primera vez que implementé una estructura similar a la pila de llamadas en Unreadable.
(La primera versión de esto tenía más de 5300 bytes, solo para dar una idea de cuánto jugué al golf).
Explicación
Considere este ejemplo de entrada:
Durante la mayor parte de la ejecución, la cinta se presenta de la siguiente manera:
Las celdas 0 a 5 son ubicaciones para diversas variables.
La celda 6 en adelante contiene toda la información sobre el conjunto de cables en su caja:
Las celdas restantes después del "terminador cero" contienen la pila. Cada "stackframe" es una celda individual que apunta a la primera celda de un cable (la celda de "enchufe de inicio"). En el ejemplo anterior, cuando el programa decide que ha encontrado una solución, la pila contendrá 6 (en referencia al
>--{primer cable) y 21 (en referencia al{---]espejo del segundo cable).El programa se desarrolla en tres etapas principales:
La primera etapa (leer la entrada y generar la estructura de cables) solo usa las celdas n. ° 1 (que llamaré
p) y n. ° 2 (que llamaréch) y opera en un ciclo while de la siguiente manera:Mientras condición: incremente
pen 6, lea el siguiente carácter (comience a enchufar) en la celda*py verifique que no lo sea-1(EOF).Lee los caracteres siguientes
*(p+2)y cuéntalos*(p+1)hasta que encontremos algo que no sea-(guión). En ese punto,*(p+1)contendrá el número de guiones (longitud del cable) y*(p+2)el último carácter que no sea guión (el conector final). (También copiamos los caracteres de guión en la celda # 5 para que podamos acceder a este código ASCII más adelante en la etapa de salida).En un bucle while, encuentre el enchufe del espejo y guárdelo
*(p+3), luego incrementepen 2, hasta que*psea cero. El bucle se ve así en pseudocódigo:Este bucle siempre realizará dos iteraciones (el enchufe inicial y el enchufe final) y almacenará los resultados en la cuarta y sexta celda de este cable. Ahora, si prestó atención, se dará cuenta de que la sexta celda es, de hecho, la ubicación correcta para el enchufe final reflejado, pero el enchufe de inicio reflejado está en la celda etiquetada como "cable original que indica booleano". Esto está bien porque solo necesitamos que esta celda sea un valor distinto de cero.
Dado que
pacaba de incrementarse un total de 4, ahora apunta a la celda etiquetada como "se está usando el cable indicador booleano". Establecer*(p+3)en el valor de*(p-1). Esto coloca el enchufe de inicio reflejado en el lugar correcto.Lea (y descarte) un personaje más (que esperamos sea una nueva línea, pero el programa no verifica eso).
pinicialmente comienza en 0 pero se incrementa en 6 dentro de la condición while, por lo tanto, los datos del cable comienzan en la celda # 6.pse incrementa en 4 dentro del cuerpo del bucle y, por lo tanto, un total de 10 por cada cable, que es exactamente lo que necesitamos.Durante la segunda etapa, las células # 0-4 están ocupadas por variables que voy a llamar
a,p,q,m, ynotdone. (La celda 5 todavía recuerda el código ASCII del guión).Para prepararnos para la etapa 2, necesitamos
*pvolver a poner a 0 (la celda etiquetada como "terminador cero") para que pueda actuar como el terminador para la lista de cables; también establecemosq(que es nuestro puntero de pila) ap+1(es decir, la celda después del "terminador cero"; aquí es donde comienza la pila);*qa 1 (el primer elemento en la pila; por qué 1 se hará evidente más adelante); ynotdonepara 1. Todo esto se hace en una sola declaración:La segunda etapa también es un ciclo while. Su condición es simple
notdone. En cada iteración de ese ciclo while, cualquiera de las siguientes cuatro cosas podría suceder:*qa otro cable elegible (que marcamos rápidamente como "en uso" junto con su gemelo) y luego recurrir (es decir, crear un nuevo marco de pila).*qporque no existen más cables elegibles, por lo que debemos retroceder (eliminar un marco de pila y marcar el cable anterior y su gemelo como ya no "en uso").*qporque no existen más cables elegibles y no podemos retroceder porque hemos llegado al final de la pila. Esto significa que no hay solución.El cuerpo del bucle verifica cada una de estas cuatro condiciones en este orden. Aquí están los detalles:
Establezca
mypen 1 y en un ciclo while, incrementepen 5 (iterando así a través de los cables) y verifique si*(p+4)("en uso") está configurado. Si no es así, ajústeloma 0. Al final de ese ciclo,mnos dice si todos los cables están en uso. Si es así, ajústelonotdonea 0 para terminar el bucle principal. De lo contrario, continúe en el paso 2 a continuación.Ajústelo
pa*q(el cable en la parte superior de la pila) y en un bucle while similar al anterior, incrementepen 5 para recorrer los cables. Comenzar en*qasegura que solo consideramos aquellos que no hemos considerado antes; sin embargo, recuerde que el valor inicial para un nuevo stackframe es 1, por lo que el primer cable examinado es el de la celda 6, que de hecho es el primer cable.Para cada cable, debemos verificar
*(p+4)que no esté en uso y que sea*(q-1)cero (lo que significa que estamos en la parte inferior de la pila, por lo que no hay restricciones en el enchufe de inicio) o*p(el inicio del cable enchufe) es igual a*(*(q-1)+2)(el enchufe final del cable justo debajo de la pila). Comprobamos por la igualdad mediante el establecimientoade*(*(q-1)+2)ympara*p+1y luego disminuyendo tanto en un bucle while. El+1es porquemse disminuye dentro de la condición while, por lo que se disminuye una vez más quea. Siaes cero al final de esto, los dos enchufes son iguales.Por lo tanto, si
*(q-1)fue cero o la comparación de igualdad tuvo éxito, el cable es elegible. Configure*qparapreemplazar el cable en la parte superior de la pila con el nuevo; se establecemen lo mismo para indicar que encontramos un cable coincidente; y luego decrementop. Esa disminución es un pequeño truco para hacer que el ciclo while (iteración a través de los cables) termine antes; se incrementarápen 5 nuevamente, llevándolo así a la celda que contiene el indicador de "en uso" de este cable, y sabemos que es cero porque acabamos de verificar eso. Finalmente, después de la iteración del cable mientras iteramos, verificamos simno es cero. Si es así, encontramos un cable coincidente ypapuntamos a la bandera "en uso" para ese cable coincidente. Ajústelo a 1 para marcarlo como en uso. También establecer*(*(p-1) ? p+5 : p-5)a 1 para marcar su gemelo como en uso. Finalmente, incrementeqy establezca el nuevo*qen 1 para crear un nuevo marco de pila.Si, después de la iteración del cable mientras iteramos, encontramos
mque es cero, no hay más cables coincidentes, por lo que debemos retroceder. Disminuyaqpara bajar la pila y verifique si todavía está apuntando a un cable (un valor distinto de cero). Si es así, marque ese cable y su gemelo como ya no están en uso. (Almacenamos el valor de*qinppara acortar esta expresión en el código).Si, después de disminuir
q, encontramos que apunta a un valor cero, entonces ese es el "terminador cero", lo que significa que hemos superado la pila. Concluimos que no hay solución. Ponemosnotdonea 0 para terminar el ciclo principal.La tercera etapa es la etapa de salida. Hay dos cosas que pueden suceder:
Convenientemente, si no había solución,
pes cero porque lo configuramos al valor de*qantes de verificar que sea cero; y si no era una solución,pestá apuntando a la “terminador cero”, ya que sólo itera a través de los cables, de modo que ahora podemos utilizarppara iterar a través de la pila. Entonces, solo recorra la pila, generando para cada cable el conector de inicio (*(*p)), los guiones (decrementando*(*p+1)en un bucle while; y usando el código ASCII de guiones almacenado en la celda # 5) y el conector final (*(*p+2)). No importa que esto destruya la información del cable; ya no necesitamos eso.fuente
CJam, 67
Pruébalo en línea
Nota: el enlace está utilizando el último código del repositorio (enviado pero aún no publicado), ya que contiene una corrección de errores.
Explicación:
El programa simplemente intenta todas las permutaciones y todas las orientaciones de los cables.
fuente
(-] ]-> >-} }-) )-[ [-< <-{ {-(.JavaScript (ES6), 206
Función recursiva
Más legible
Prueba
fuente
Javascript, 800 bytes
Lejos de ser una solución optimizada, pero aquí hay un truco rápido en javascript (sin ecma5 sofisticado ni nada, porque no lo sé).
Ungolfed, aquí está ... Estoy seguro de que al menos 2 para los bucles son innecesarios aquí y que la comprobación de una entrada de un solo elemento en la parte superior y una coincidencia de un solo elemento en la parte inferior es desagradable ... pero parece funcionar y procesa las entradas de prueba.
fuente
s.charAt(x)===s[x]Python 3, 217 bytes
( Demo en Ideone )
fuente
(-] ]-> >-} }-) )-[ [-< <-{ {-(?Lua, 477 bytes
Acepta cables como argumentos de línea de comando
fuente
Python 3.5,
448432427424286311 bytes:( +25 ya que hubo un error en el que la salida puede ser más larga de lo que debería ser para algunas entradas )
¡Funciona perfectamente!
excepto para entradas con 7 o más valores. Lleva mucho tiempo para ellos, muy probablemente porque debe pasar por todas esas permutaciones de la entrada más la entrada invertida . Intentaré arreglar esto si y cuando pueda, pero por ahora, esto parece ser lo suficientemente bueno.¡Todo está bien ahora! Si sólo se pude utilizar de alguna manera quetry-exceptel bloque en la lista por comprensión, podría ser un poco más corto, y buscar mucho más agradable. Sin embargo, ahora trabaja para todos los casos de prueba, y lo mejor de todo, se utiliza no hay importaciones! :)Pruébalo en línea! (Ideone) (284 bytes aquí)
(Sugerencia: para probarlo, simplemente seleccione "bifurcación", y luego ingrese sus opciones, separadas por espacios , y seleccione "ejecutar")
Explicación
Básicamente, lo que está sucediendo es ...
Bcrea una lista, a partir de la entrada dividiéndola en el espacio en blanco en sus "cordones" componentes.Mes una cadena que creé que, cuando se evalúa, devuelve una lista basada en laBcual contiene todos los cables, pero esta vez al revés .Mesta última se concatena consigoBmisma para crear una listaf, con todas las orientaciones posibles de los "cables".dcrea otra lista, que se inicializará con el primer valor (valorf[0]) def.dse repiten, y el último carácter de cada valor se compara con el primer carácter de cada elementof, y cuando se encuentra una coincidencia, ese carácter aparece (o se elimina) y se devuelve de la listaf. Esto sucede hasta queIndexErrorse levanta a, o la longitud de la listadexcedeBy aNameErrorse levanta después de la llamada aE, ambos se manejan, y luegodel contenido de la lista se une en una cadena y se devuelve siempre que la longitud de la listadsea mayor igual o igual a la longitud de la listaB. De lo contrario, se devuelve una cadena vacía (''), ya quedno tiene la misma longitud queBsignifica que todos los "cables" en la listaBno se puede unir en un "cordón" largo.fuente
<!-- language: lang-python -->. ¿Qué cambia eso?