Para referência sobre o que é a torre de Hanói, pesquise no Google ou consulte a página da Wikipedia .

Seu código deve ser capaz de fazer duas coisas e são as seguintes:

• Aceitar entrada do usuário que especifique o número de discos no ponto de partida da torre de Hanói
• Crie a saída da maneira que você escolher (desde que seja lógico) para mostrar a solução para o quebra-cabeça da torre.

Um exemplo de saída lógica seria o seguinte (usando uma inicialização de 4 discos):

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

Lrepresenta o pino esquerdo, Crepresenta o pino central e Rrepresenta o pino direito e os números estão a que distância mover o disco nesse pino e em que direção. Os números positivos representam o número de estacas que se movem na direção da estaca mais à direita (porque os discos começam na estaca mais à esquerda).

As regras para a torre de Hanói são simples:

• Somente um disco pode ser movido por vez.
• Cada movimento consiste em pegar o disco superior de um dos pinos e deslizá-lo para outro, em cima dos outros discos que já podem estar presentes nesse pinos.
• Nenhum disco pode ser colocado em cima de um disco menor.

Os discos começam no pino mais à esquerda, maior na parte inferior, menor na parte superior, naturalmente.

Casca , 5 bytes

↑≠⁰İr

Experimente online!
Cada um nna saída representa mover o disco npara o próximo peg disponível (encapsular ciclicamente).

Explicação

   İ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 exemplo, para N = 3, ele retorna:

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)}

Corra com perl -M5.010e digite o número de discos no stdin.

Formato de saída:

Uma linha por movimento, o primeiro dígito é do peg, o segundo dígito é o peg (a partir de 0)

Exemplo:

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

GolfScript ( 31 25 24 caracteres)

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

Agradeço a Ilmari Karonen por apontar que minhas trpermutações originais poderiam ser reduzidas em 6 caracteres. Decompondo-as como um produto de duas permutações, consegui salvar mais uma.

Observe que fatorando o 3%comprimento dos aumentos em um caractere:

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

Algumas pessoas têm formatos de saída realmente complicados. Isso gera o peg movido de (numerado 0, 1, 2) e o peg movido para. A especificação não diz para qual pino se mover, então se move para o pino 1.

Por exemplo

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

Perl, 75 79 caracteres

Roubando totalmente o formato de saída 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

Invoque com -M5.010para o say.

(Acho que isso pode ser melhorado se você encontrar uma maneira de usar o valor de retorno da função em vez de apenas suprimi-lo.)

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);

função de chamada f(n,s,t)com:

• n número de discos
• s ponto de partida
• ponto de objetivo

Bash (64 caracteres)

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

A publicação desta, apesar de ter mais que o dobro do tamanho da GolfScript, porque eu gosto da reutilização tpara servir como 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 saída

Diga o número do disco = 3 e, em seguida,

(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 o algoritmo mais trivial.
A saída está na forma em ab ab abque cada par significa "mover o disco superior do pino a para o pino b".
EDIT : Os movimentos agora são codificados em hexadecimal - 0x12 significa mover do pino 1 para o pino 2. Salve alguns caracteres.
EDIT : Lê o número de stdin, em vez de parâmetro. Mais curta.
Exemplo:
% 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);}

Gelatina , 5 bytes

2*Ṗọ2

Experimente online!

0mova o menor disco um espaço para a direita (retornando ao início, se necessário)
1mova o segundo menor disco para a única outra coluna legal
2mova o terceiro menor disco para a única outra coluna legal
etc.

Algoritmo

Podemos ver a solução do problema das Torres de Hanói recursivamente; a mover-se uma pilha de tamanho n a partir de um a B , mover-se de uma pilha de tamanho n -1 a partir de um de C , em seguida, o disco de tamanho n a partir de um a B , em seguida, mover uma pilha de tamanho n -1 de B para C . Isso produz um padrão do seguinte formato (no formato de saída usado por este programa):

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

Podemos observar que essa sequência é A007814 no OEIS. Outra definição possível da sequência é "o k ésimo elemento (com base em 1) da sequência é o número de zeros no final do número k quando ele é escrito em binário". E é isso que o programa aqui está calculando.

Explicação

Primeiro, calculamos o número de movimentos na solução, 2 ⁿ -1. Acontece ser o mais curto para realmente calcular um movimento extra e descartá-lo mais tarde, então isso é 2*, ou seja, 2 ao poder de algo. (A única entrada que levamos até agora é o argumento da linha de comando, que é usado por padrão.)

Em seguida, usamos o Jelly's embutido para calcular o número de zeros no final de um número na base b ; é isso . Como estamos calculando em binário, é . Tudo o que precisamos fazer é aplicar esse built-in aos números de 1 a 2 ⁿ -1, inclusive.ọbọ2

Existem duas maneiras simples de iterar em uma série de números no Jelly €e R, e minhas tentativas anteriores para solucionar esse problema usaram uma delas. Entretanto, nesse caso, é possível ficar um pouco mais curto: Ṗquando um número é fornecido como entrada, você pode fazer uma iteração que interrompe um elemento curto (em geral, Ṗé um componente interno usado para processar todos os elementos, exceto um). É exatamente isso que queremos neste caso (porque 2*gera muitos elementos), portanto, usá-lo para vincular 2*e ọ2nos 2*Ṗọ2fornece uma solução de 5 bytes para o 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)

O formato de saída é o mesmo 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

Script Bash, 100 96 caracteres

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

O formato de saída é o mesmo 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 : salvou 4 caracteres pelo comentário de peter .

J, 23 bytes

solução de números binários

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

Esta solução usa o método de contagem binária descrito neste vídeo .

Ou seja, eu giro os dígitos binários de 1até 2^n, depois pego infixes de comprimento 2 e comparo cada bit com o bit correspondente do número anterior e verifico se são desiguais. O número de bits desiguais é a saída para esse movimento.

Saída, por exemplo, para 3 discos, onde o menor disco é identificado como 1:

1 2 1 3 1 2 1

1 significa "mover o menor disco de um pino para a direita, retornando ao primeiro pino, se necessário"

n, para todos os outros n, significa "mover o disco npara uma estaca legal" (sempre haverá exatamente uma)

Experimente online!

solução recursiva

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

A mesma saída da solução acima, mas a lógica aqui torna a natureza recursiva do problema mais clara.

A visualização como uma árvore também enfatiza este ponto:

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

Experimente online!

APL (Dyalog Classic) , 19 bytes

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

Experimente online!

output é uma matriz de duas colunas de ints em {0,1,2} - do peg, ao peg

K (ngn / k) , 23 bytes

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

Experimente online!

R , 73 bytes

Colocando R no mapa. Inspirado na [resposta de Keith Randall] [1] com entrada simplificada, imprima apenas final e inicie o peg para economizar 2 bytes. Também pinos indexados a 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)}}

Experimente online!

JavaScript (ES6), 45b

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

por exemplo, chamada h(4, 'A', 'B', 'C')(mova 4 discos do pino A para o pino C usando o pino auxiliar B)

retornos 'ABACBCABCACBABACBCBACABCABACBC'(mova um disco do pino A para o pino B, mova um disco do pino A para o pino C, mova um disco do pino B para o pino C, etc.)