Ayuda a los monjes de Hanoi con sus torres
Existe una leyenda que cuenta que cerca de la ciudad de Hanoi, en Vietnam, hay un monasterio con una placa de bronce y tres varillas sobre ella.
Al crear el mundo, Dios ensartó 64 discos de diversos diámetros hechos de oro puro en la primera varilla. Colocó el disco más grande sobre la placa y puso cada disco más pequeño sobre uno más grande.
Había una profecía: en el momento en que los monjes del monasterio transfieran los 64 discos de la primera varilla a la tercera, llegará el fin del mundo y la dicha eterna llegará para los justos. Por eso, los monjes trabajan día y noche, trasladando discos. Pero el trabajo avanza muy lentamente porque los monjes tienen que seguir dos reglas simples:
- Los discos se pueden mover de una varilla a otra, de uno en uno.
- Los monjes no pueden colocar un disco más grande sobre uno más pequeño.
A los monjes les han dado un plazo de 600 mil millones de años para terminar su trabajo. Pero ya se han retrasado porque a veces se pierden en sus cálculos y durante mucho tiempo no pueden decidir qué disco mover ni adónde.
Ayuda a los monjes. Escribe una función que, al recibir el número de movimiento, muestre cómo realizarlo. La función debe devolver una tupla de tres números:
- Número del disco.
- Número de la varilla de la que se debe tomar el disco.
- Número de la varilla donde se debe colocar este disco.
Los discos están numerados del 1 (el disco más pequeño) al 64 (el disco más grande).
Ejemplos
hanoi(1) ➞ (1, 1, 2)
hanoi(2) ➞ (2, 1, 3)
hanoi(2**63) ➞ (64, 1, 3)
hanoi(15215285751613538304) ➞ (15, 2, 3)Notas
En una computadora promedio, Python tardaría unos 50 mil años en realizar todos los movimientos de discos. Por lo tanto, en lugar de recorrer todos los movimientos, es necesario encontrar un patrón de movimientos.
