Para referencia de lo que es la torre de Hanoi, busca en Google o mira en la página de Wikipedia .

Su código debería poder hacer 2 cosas, y son las siguientes:

• Acepte la entrada del usuario que especifica el número de discos en el punto de partida de la torre de Hanoi.
• Cree la salida de la manera que elija (siempre que sea lógico) para mostrar la solución al rompecabezas de la torre.

Un ejemplo de salida lógica sería el siguiente (usando un inicio de 4 discos):

L1L2C1L1R-2R-1L1L2C1C-1R-2C1L1L2C1

Lrepresenta la clavija izquierda, Crepresenta la clavija central y Rrepresenta la clavija derecha y los números son qué tan lejos mover el disco en esa clavija y en qué dirección. Los números positivos representan el número de clavijas que se mueven hacia la clavija más a la derecha (porque los discos comienzan en la clavija más a la izquierda).

Las reglas para la torre de Hanoi son simples:

• Solo se puede mover un disco a la vez.
• Cada movimiento consiste en tomar el disco superior de una de las clavijas y deslizarlo sobre otra clavija, encima de los otros discos que ya pueden estar presentes en esa clavija.
• No se puede colocar ningún disco encima de un disco más pequeño.

Los discos comienzan en la clavija más a la izquierda, la más grande en la parte inferior, la más pequeña en la parte superior, naturalmente.

Casco , 5 bytes

↑≠⁰İr

Pruébalo en línea!
Cada uno nen la salida representa mover el disco na la siguiente clavija disponible (envoltura cíclica).

Explicación

   İr   The ruler sequence [0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, ...]
↑       Take while...
 ≠⁰     ... not equal to the input.

Python, 76 caracteres

def S(n,a,b):
 if n:S(n-1,a,6-a-b);print n,a,b;S(n-1,6-a-b,b)
S(input(),1,3)

Por ejemplo, para N = 3 devuelve:

1 1 3  (move disk 1 from peg 1 to peg 3)
2 1 2  (move disk 2 from peg 1 to peg 2)
1 3 2  (move disk 1 from peg 3 to peg 2)
3 1 3  ...
1 2 1
2 2 3
1 1 3

Perl - 54 caracteres

for(2..1<<<>){$_--;$x=$_&-$_;say(($_-$x)%3,($_+$x)%3)}

Ejecute perl -M5.010e ingrese el número de discos en stdin.

Formato de salida:

Una línea por movimiento, el primer dígito es de clavija, el segundo dígito es de clavija (a partir de 0)

Ejemplo:

02 -- move from peg 0 to peg 2
01
21
02
10
12
02

GolfScript ( 31 25 24 caracteres)

])~{{~3%}%.{)3%}%2,@++}*

Gracias a Ilmari Karonen por señalar que mis trs / permutaciones originales podrían acortarse en 6 caracteres. Al descomponerlos como producto de dos permutaciones, logré salvar una más.

Tenga en cuenta que factorizar la 3%longitud aumenta en un carácter:

])~{{~}%.{)}%2,@++}*{3%}%

Algunas personas tienen formatos de salida realmente complicados. Esto genera la clavija movida desde (numerada 0, 1, 2) y la clavija movida a. La especificación no dice a qué clavija mover, por lo que se mueve a la clavija 1.

P.ej

$ golfscript hanoi.gs <<<"3"
01021201202101

Perl, 75 79 caracteres

Robando totalmente el formato de salida de Keith Randall:

sub h{my($n,$p,$q)=@_;h($n,$p^$q^h($n,$p,$p^$q),$q*say"@_")if$n--}h pop,1,3

Invocar con -M5.010para el say.

(Creo que esto puede mejorarse si puede encontrar una manera de utilizar el valor de retorno de la función en lugar de simplemente suprimirlo).

SML, 63

fun f(0,_,_)=[]|f(n,s,t)=f(n-1,s,6-s-t)@[n,s,t]@f(n-1,6-s-t,t);

función de llamada f(n,s,t)con:

• n cantidad de discos
• s punto de partida
• t punto objetivo

Bash (64 caracteres)

t(){ tr 2$1 $12 <<<$s;};for((i=$1;i--;))do s=`t 1`01`t 0`;done;t

Publicar este a pesar de ser más del doble de largo que el de GolfScript porque me gusta la reutilización de tpara servir echo $s.

Scala, 92 88 87 caracteres

def?(n:Int,a:Int,b:Int){if(n>0){?(n-1,a,a^b)
print(n,a,b);?(n-1,a^b,b)}};?(readInt,1,3)

Formato de salida

Di número de disco = 3 entonces,

(1,1,3)(2,1,2)(1,3,2)(3,1,3)(1,2,1)(2,2,3)(1,1,3) (disk number,from peg, to peg)
                                                   \---------------------------/       
                                                            Move 1              ... Move n

C, 98 92 87 caracteres

Implementa el algoritmo más trivial.
La salida está en la forma ab ab aben que cada par significa "mover el disco superior de la clavija a la clavija b".
EDITAR : Los movimientos ahora están codificados en hexadecimal - 0x12 significa moverse de la clavija 1 a la clavija 2. Guardado algunos caracteres.
EDITAR : lee el número de la entrada estándar, en lugar del parámetro. Más corto.
Ejemplo:
% echo 3 | ./hanoi
13 12 32 13 21 23 13

n;
h(d){n--&&h(d^d%16*16,printf("%02x ",d,h(d^d/16))),n++;}
main(){scanf("%d",&n);h(19);}

Jalea , 5 bytes

2*Ṗọ2

Pruébalo en línea!

0mueva el disco más pequeño un espacio a la derecha (volviendo al inicio si es necesario)
1mueva el segundo disco más pequeño a la única otra columna legal
2mueva el tercer disco más pequeño a la única otra columna legal,
etc.

Algoritmo

Podemos ver la solución del problema de Towers of Hanoi de forma recursiva; para mover una pila de tamaño n de A a B , mover una pila de tamaño n -1 de A a C , entonces el disco de tamaño n de A a B , a continuación, mover una pila de tamaño n -1 desde B a C . Esto produce un patrón de la siguiente forma (en el formato de salida utilizado por este programa):

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2 …

Podemos observar que esta secuencia es A007814 en el OEIS. Otra posible definición de la secuencia es "el elemento k th (basado en 1) de la secuencia es el número de ceros al final del número k cuando está escrito en binario". Y eso es lo que calcula el programa aquí.

Explicación

Primero, calculamos el número de movimientos en la solución, 2 ⁿ -1. Resulta que es el más corto para calcular realmente un movimiento adicional y descartarlo más tarde, por lo que es 2*, es decir, 2 al poder de algo. (La única entrada que hemos tomado hasta ahora es el argumento de la línea de comando, por lo que se usa de forma predeterminada).

A continuación, usamos el código incorporado de Jelly para calcular el número de ceros al final de un número en la base b ; que de . Como estamos calculando en binario, es . Todo lo que necesitamos hacer es aplicar este valor incorporado a los números del 1 al 2 ⁿ -1 inclusive.ọbọ2

Hay dos formas sencillas para repetir una serie de números en la jalea, €y R, y mis anteriores intentos de este problema utilizan uno de estos. Sin embargo, en este caso, es posible ir un poco más corto: Ṗcuando se le da un número como entrada, le permitirá hacer una iteración que detiene un elemento brevemente (en general, Ṗes una función incorporada para procesar todos menos un elemento de algo). Eso es exactamente lo que queremos en este caso (porque 2*genera una demasiadas elments), por lo que el uso de enlace 2*y ọ2en la 2*Ṗọ2que nos da una solución de 5 bytes al problema.

Awk, 72 caracteres

function t(n,a,b){if(n){t(n-1,a,a^b);print n,a,b;t(n-1,a^b,b)}}t($0,1,3)

El formato de salida es el mismo que el de Keith Randall .

awk -f tower.awk <<< "3"    
1 1 1
2 1 1
1 1 1
3 1 3
1 1 1
2 1 3
1 1 3

Bash script, 100 96 caracteres

t(){ [[ $1<1 ]] && return
t $(($1-1)) $2 $(($2^$3))
echo $@
t $(($1-1)) $(($2^$3)) $3
}
t $1 1 3

El formato de salida es el mismo que el de Keith Randall .

1 1 3
2 1 2
1 3 2
3 1 3
1 2 1
2 2 3
1 1 3

Editar : Guardado 4 caracteres por el comentario de Peter .

J, 23 bytes

solución de números binarios

2&(+/@:~:/\)@#:@i.@^~&2

Esta solución utiliza el método de conteo binario descrito en este video .

Es decir, genero los dígitos binarios de 1hasta 2^n, luego tomo infijos de longitud 2 y comparo cada bit con el bit correspondiente del número anterior, y compruebo si son desiguales. El número de bits desiguales es la salida para ese movimiento.

Salida, por ejemplo, para 3 discos, donde el disco más pequeño está etiquetado como 1:

1 2 1 3 1 2 1

1 significa "mover la clavija más pequeña del disco a la derecha, volviendo a la primera clavija si es necesario"

n, para todos los demás n, significa "mover el disco na una clavija legal" (siempre habrá exactamente uno)

Pruébalo en línea!

solución recursiva

((],[,])$:@<:)`]@.(1=])

El mismo resultado que la solución anterior, pero la lógica aquí aclara la naturaleza recursiva del problema.

Visualizarlo como un árbol también enfatiza este punto:

              4
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      3               3      
     / \             / \    
    /   \           /   \
   /     \         /     \ 
  2       2       2       2  
 / \     / \     / \     / \
1   1   1   1   1   1   1   1

Pruébalo en línea!

APL (Dyalog Classic) , 19 bytes

3|(-⍪0 1⍪2∘-)⍣⎕,⍨⍪⍬

Pruébalo en línea!

la salida es una matriz de ints de 2 columnas en {0,1,2} - de clavija a clavija

K (ngn / k) , 23 bytes

{3!x{-x,(,0 2),1+x}/()}

Pruébalo en línea!

R , 73 bytes

Poniendo R en el mapa. Inspirado por [la respuesta de Keith Randall] [1] con entrada simplificada, imprima solo el final y comience a vincular para guardar 2 bytes. También clavijas indexadas 0.

f=function(n,s=0,e=2){if(n){f(n-1,s,3-s-e)
print(c(s,e))
f(n-1,3-s-e,e)}}

Pruébalo en línea!

JavaScript (ES6), 45b

h=(n,f,a,t)=>n?h(--n,f,t,a)+f+t+h(n,a,f,t):''

por ejemplo, llamar h(4, 'A', 'B', 'C')(mover 4 discos de la clavija A a la clavija C usando la clavija auxiliar B)

retornos 'ABACBCABCACBABACBCBACABCABACBC'(mover un disco de la clavija A a la clavija B, mover un disco de la clavija A a la clavija C, mover un disco de la clavija B a la clavija C, etc.)