Si no sabe qué es la Torre de Hanoi , lo explicaré brevemente: hay tres barras y algunos discos, cada uno de los cuales tiene un tamaño diferente. Al principio, todos los discos están en la primera torre, en orden: el más grande está en la parte inferior, el más pequeño en la parte superior. El objetivo es llevar todos los discos a la tercera barra. ¿Suena fácil? Aquí está el truco: no puede colocar un disco encima de un disco que sea más pequeño que el otro disco; solo puedes sostener un disco en tu mano a la vez para moverlos a otra barra y solo puedes colocar el disco en barras, no en la mesa, bastardo astuto.
Solución de ejemplo ASCII:
A B C
| | |
_|_ | |
__|__ | |
A B C
| | |
| | |
__|__ _|_ |
A B C
| | |
| | |
| _|_ __|__
A B C
| | |
| | _|_
| | __|__
Reto
Hay tres barras llamadas A, B y C. (También puede llamarlas 1,2 y 3 respectivamente si eso ayuda) Al principio, todos los n discos están en la barra A (1).
Su desafío es verificar una solución para la torre de hanoi. Deberá asegurarse de que:
- Al final, todos los n discos están en la barra C (3).
- Para cualquier disco dado en cualquier estado dado no hay un disco más pequeño debajo de él.
- No hay errores obvios como intentar sacar discos de una barra vacía o mover discos a barras no existentes.
(la solución no tiene que ser óptima).
Entrada
Su programa recibirá dos entradas:
- El número de discos n (un entero)
Los movimientos que se toman, que consistirán en un conjunto de tuplas de: (torre para tomar el disco más alto actualmente), (torre para llevar este disco) donde cada tupla se refiere a un movimiento. Puedes elegir cómo se representan. Por ejemplo, algo así como las siguientes formas de representar la solución para n = 2 que he dibujado en ascii arriba. (Usaré el primero en los casos de prueba, porque es fácil para la vista):
"A-> B; A-> C; B-> C"
[("A", "B"), ("A", "C"), ("B", "C")]
[(1,2), (1,3), (2,3)]
"ABACBC"
[1,2,1,3,2,3]
Salida
Verdad, si las condiciones que se pueden encontrar bajo "desafío" se mantienen.
Falsy, si no lo hacen.
Casos de prueba:
Cierto:
n=1, "A->C"
n=1, "A->B ; B->C"
n=2, "A->B ; A->C ; B->C"
n=2, "A->C ; C->B ; A->C ; B->C"
n=2, "A->C ; A->B ; C->B ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C ; B->C"
Falso:
3 ° sugerido por @MartinEnder, 7 ° por @Joffan
n=1, "A->B"
n=1, "C->A"
n=2, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=2, "A->B ; A->C ; C->B"
n=2, "A->C ; A->B ; C->B ; B->A"
n=2, "A->C ; A->C"
n=3, "A->B ; A->D; A->C ; D->C ; A->C"
n=3, "A->C ; A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->B ; B->C ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; C->B"
n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C"
n=4, "A->B ; A->B ; A->B ; A->C ; B->C ; B->C ; B->C"
Este es el código de golf , la solución más corta gana. Se aplican reglas estándar y lagunas. No incluye pilas.
A=1
,B=2
,C=3
, etc.)?A->A
?moving discs to nonexistant rods.
supuesto que sí, es unD
Respuestas:
Retina ,
8480 bytes-5 bytes gracias a Martin Ender
Pruébalo en línea! (más 5 bytes para pruebas línea por línea)
El código simula un juego completo.
ACABCBACBABCAC~~~
.~~~
significa tres discos.ACABCBACBABCAC ~~~ ~~ ~ABC
.Al principio, la barra A tiene los 3 discos, y las barras B y C están vacías.
En el ejemplo, tras el primer paso, el texto se verá así:
~CABCBACBABCAC ~~~ ~~ABC
.ABCBACBABCAC ~~~ ~~AB ~C
.fuente
Retina ,
167165157150123 bytesEsto parece totalmente un desafío que debería resolverse con una única expresión regular ... (a pesar de que el encabezado dice "Retina", esto es solo una expresión regular .NET de vainilla, que coincide con entradas válidas).
El formato de entrada es la lista de instrucciones del formulario
AB
, seguidon
en unario usando el dígito1
. No hay separadores La salida es1
válida y0
no válida.Pruébalo en línea! (Los primeros dos caracteres habilitan un conjunto de pruebas separado por salto de línea).
Solución alternativa, mismo recuento de bytes:
Esto posiblemente puede ser acortada mediante el uso
1
,11
y111
en lugar deA
,B
yC
pero voy a tener que mirar en eso más adelante. También podría ser más corto dividir el programa en varias etapas, pero ¿dónde está el desafío en eso? ;)Explicación
Esta solución hace un uso intensivo de los grupos de equilibrio de .NET. Para obtener una explicación completa, vea mi publicación sobre Desbordamiento de pila , pero lo esencial es que los grupos de captura en .NET son pilas, donde cada nueva captura empuja otra subcadena y donde también es posible volver a aparecer desde dicha pila. Esto le permite contar varias cantidades en una cadena. En este caso, nos permite implementar las tres barras directamente como tres grupos de captura diferentes donde cada disco está representado por una captura.
Para mover los discos entre las barras, utilizamos una peculiaridad extraña de la
(?<A-B>...)
sintaxis. Normalmente, esto muestra una captura de la pilaB
y empuja en la pilaA
la cadena entre esa captura emergente y el comienzo de este grupo. Tan(?<A>a).(?<B-A>c)
emparejado contraabc
dejaríaA
vacío yB
conb
(a diferencia dec
). Sin embargo, debido a los retrospectivos de longitud variable de .NET, es posible que se capturen(?<A>...)
y se(?<B-A>...)
superpongan. Por alguna razón, si ese es el caso, se empuja la intersección de los dos gruposB
. He detallado este comportamiento en la "sección avanzada" sobre grupos de equilibrio en esta respuesta .A la expresión regular. Varillas
A
,B
yC
corresponden a grupos3
,4
y5
en la expresión regular. Comencemos por inicializar la barraA
:Entonces, por ejemplo, si la entrada termina con
111
, entonces el grupo 3 / barraA
ahora tendrá la lista de capturas[111, 11, 1]
(la parte superior está a la derecha).El siguiente bit del código tiene la siguiente estructura:
Cada iteración de este ciclo procesa una instrucción. La primera alternancia extrae un disco de la barra dada (en un grupo temporal), la segunda alternancia pone ese disco en la otra barra dada. Veremos en un momento cómo funciona esto y cómo nos aseguramos de que el movimiento sea válido.
Primero, sacando un disco de la barra de origen:
Esto usa el extraño comportamiento de intersección grupal que describí anteriormente. Tenga en cuenta ese grupo
3
,4
y5
siempre tendrá subcadenas de1
s al final de la cadena cuya longitud corresponde al tamaño del disco. Ahora usamos(?<1-N>.+)
paraN
sacar el disco superior de la pila y empujar la intersección de esta subcadena con la coincidencia.+
en la pila1
. Como.+
siempre cubre necesariamente la captura completaN
, sabemos que esto simplemente mueve la captura.A continuación, colocamos este disco de la pila
1
en la pila correspondiente a la segunda barra:Tenga en cuenta que no tenemos que limpiar la pila
1
, simplemente podemos dejar el disco allí, ya que colocaremos uno nuevo encima antes de volver a usar la pila. Eso significa que podemos evitar la(?<A-B>...)
sintaxis y simplemente copiar la cadena con(\1)
. Para garantizar que el movimiento sea válido, usamos el lookahead negativo(?!\N)
. Esto garantiza que, desde la posición en la que queremos hacer coincidir el disco actual, es imposible hacer coincidir el disco que ya está en la pilaN
. Esto solo puede suceder si a)\N
nunca coincidirá porque la pila está completamente vacía o b)the disc on top of stack
Nis larger than the one we're trying to match with
\ 1`.Finalmente, todo lo que queda es asegurarse de que a) coincidamos con todas las instrucciones yb) varillas
A
y queB
estén vacías, de modo que todos los discos se hayan movidoC
.Simplemente verificamos que ni
\3
ni\4
pueden coincidir (que es el caso si ambos están vacíos, porque cualquier disco real podría coincidir) y que luego nos puede coincidir con una1
forma que no hemos omitido cualquier instrucción.fuente
Java "solo"
311 272 263 261 260 259256 bytesSalvado
39incontables bytes debido a @Frozn notando una característica de depuración mayores, así como algunos trucos de golf inteligente.Versión de golf
sin dudas con explicaciones y bonitas pilas impresas en cada paso
La versión sin golf tiene una función en la que imprimirá el aspecto de las pilas en cada paso, así que ...
fuente
System.out.println(Arrays.toString(s))
hacer?&&
por&
.Python 2,
186167158135127115110102 bytesToma entrada en STDIN en el siguiente formato:
Es decir, una tupla de Python del número de discos y una lista de tuplas de Python
(from_rod,to_rod)
. Como en Python, los paréntesis son opcionales. Las varillas están indexadas a cero.Por ejemplo, este caso de prueba:
se daría como:
Si la solución es válida, no genera nada y sale con un código de salida de 0. Si no es válida, lanza una excepción y sale con un código de salida de 1. Lanza un
IndexError
si se mueve a una barra no existente o intenta sacar un disco de un varilla que no tiene discos, aZeroDivisionError
si se coloca un disco encima de un disco más pequeño, oNameError
si quedan discos en la primera o segunda varillas al final.¡Ahorró 13 bytes gracias a @KarlKastor!
¡Guardado 8 bytes gracias a @xnor!
fuente
Python 2.7,
173158138130127123 bytes:Toma entrada a través del stdin en el formato
(<Number of Discs>,<Moves>)
donde<Moves>
se proporciona como una matriz que contiene tuplas correspondientes a cada movimiento, cada una de las cuales contiene un par de enteros separados por comas. Por ejemplo, el caso de prueba:dado en la publicación se daría como:
a mi programa Emite una
IndexError
si no se cumple la tercera condición, aNameError
si no se cumple la segunda condición yFalse
si no se cumple la primera condición. De lo contrario salidasTrue
.fuente
Y
no está definida en el código (creo que debe haber J) yU[J]+=[Y,[U[K].pop()]][U[J]<[1]or U[K]<U[J]]
es más corto por 3 personajes que elstmt1 if cond else stmt2
Y
variable de esa manera para elevarNameError
cuando no se cumple la segunda condición. Si tuviera que cambiarY
aJ
, entoncesNameError
no se plantearía. Por esta razón, tampoco puedo hacerloU[J]+=[Y,[U[K].pop()]][U[J]<[1]or U[K]<U[J]]
porque esto aumentaríaNameError
todo el tiempo , no solo cuando no se cumple la segunda condición.VBA,
234217213196 bytesEl formato de entrada para movimientos es una cadena con un número par de dígitos (012). La invocación está en la hoja de cálculo, = H ([número de discos], [mover cadena])
El conjunto A mantiene la posición de la barra de los diversos discos. Un movimiento es simplemente actualizar la primera aparición del número de barra "De" en el número de barra "A". Si primero encuentra un disco de varilla "A", o no tiene un disco de varilla "De", es un movimiento no válido. El "valor de barra" total de A se mantiene en L, que debe terminar en 2N. Los errores se acumulan como un recuento negativo en E.
Al igual que otras soluciones, "mover" un disco de una torre a la misma torre no está prohibido. Podría prohibirlo por otros 6 bytes.
Resultados
Resultado de la función en la primera columna (el último caso n = 3 es mi adición usando una barra adicional).
fuente
php, 141 bytes
La secuencia de comandos de la línea de comando toma la entrada como la altura y luego una serie de índices de matriz (0 indexados), por ejemplo, 1 0 2 o 2 0 1 0 2 1 2 para los casos de prueba más cortos de 1 o 2 alturas.
Echos 1 en casos verdaderos y nada en casos falsos.
Da 2 avisos y 1 advertencia, por lo que debe ejecutarse en un entorno que los silencie.
fuente
JavaScript (ES6), 108
Formato de entrada: función con 2 argumentos
Salida: devuelve 1 si está bien, 0 si no es válido, excepción si la varilla no existe
Menos golf y explicado
Nota de prueba : la primera fila de la función Prueba es necesaria para convertir el formato de entrada dado en la pregunta a la entrada esperada por mi función
fuente