Se você não sabe o que é a Torre de Hanói , explicarei brevemente: Existem três barras e alguns discos, cada um com um tamanho diferente. No começo, todos os discos estão na primeira torre, em ordem ordenada: o maior está na parte inferior, o menor no topo. O objetivo é levar todos os discos para a terceira barra. Parece fácil? Aqui está o problema: você não pode colocar um disco em cima de um disco menor que o outro disco; você só pode segurar um disco em sua mão de cada vez para movê-lo para outra haste e só pode colocar o disco em hastes, e não em cima da mesa, seu bastardo sorrateiro.

solução de exemplo ascii:

  A      B      C
  |      |      |      
 _|_     |      |      
__|__    |      |


  A      B      C
  |      |      |      
  |      |      |      
__|__   _|_     |


  A      B      C
  |      |      |      
  |      |      |      
  |     _|_   __|__


  A      B      C
  |      |      |      
  |      |     _|_     
  |      |    __|__      

Desafio

Existem três hastes chamadas A, B e C. (Você também pode chamá-las respectivamente 1,2 e 3, se isso ajudar). No início, todos os n discos estão na haste A (1).

Seu desafio é verificar uma solução para a torre de Hanói. Você precisará garantir que:

1. No final, todos os n discos estão na haste C (3).
2. Para qualquer disco em um dado estado, não há disco menor abaixo dele.
3. Não há erros óbvios, como tentar tirar discos de uma barra vazia ou mover discos para barras inexistentes.

(a solução não precisa ser ótima.)

Entrada

Seu programa receberá duas entradas:

1. O número de discos n (um número inteiro)

2. Os movimentos realizados, que consistem em um conjunto de tuplas de: (torre para tirar o disco atualmente mais alto), (torre para levar esse disco) onde cada tupla se refere a um movimento. Você pode escolher como eles são representados. Por exemplo, algo como as seguintes maneiras de representar a solução para n = 2, que eu desenhei nas ascii acima. (Usarei o primeiro nos casos de teste, porque é fácil para os olhos):

   "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]

Saída

• Na verdade, se as condições que podem ser encontradas em "desafio" se mantiverem.

• Falsy, se não o fizerem.

Casos de teste:

Verdade:

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 é o código-golfe , a solução mais curta vence. Aplicam-se regras e brechas padrão. Sem pilhas incluídas.

Retina , 84 80 Bytes

^{-5 bytes graças a Martin Ender}

~
 ~$'
$
ABC
{`^(.)(.*)( ~+)\1
$3$2$1
}`^(\W+)(\w)(.*)(?<=\1~+|\w)\2
$3$1$2
^AB 

Experimente online! (mais 5 bytes para testes linha por linha)

O código simula um jogo completo.

• A entrada é fornecida como ACABCBACBABCAC~~~.
  ~~~significa três discos.
• Primeiras quatro linhas converter a entrada para o formato de jogo: ACABCBACBABCAC ~~~ ~~ ~ABC.
  No começo, a barra A possui todos os 3 discos e as barras B e C estão vazias.
• Em seguida, temos um loop de duas etapas:
  • Pegue a primeira letra da linha, que indica a próxima haste de origem. Encontre esta haste e coloque o último disco. Remova a letra e mova o disco para o ponto mais alto (pegue-o).
    Em fora exemplo, após a primeira etapa, o texto será algo como: ~CABCBACBABCAC ~~~ ~~ABC.
  • No segundo estágio, encontramos a haste alvo e movemos o disco para lá. Nós validar a haste está vazia, ou tem um maior disco no topo: ABCBACBABCAC ~~~ ~~AB ~C.
• Finalmente, confirmamos que as hastes A e B estão vazias - isso significa que todos os discos estão em C (há um espaço extra na última linha).

Retina , 167 165 157 150 123 bytes

Isso parece totalmente um desafio que deve ser resolvido com um único regex ... (apesar do cabeçalho dizer "Retina", este é apenas um regex .NET baunilha, que corresponde a entradas válidas).

^(?=\D*((?=(?<3>1+))1)+)((?=A(?<1-3>.+)|B(?<1-4>.+)|C(?<1-5>.+)).(?=A.*(?!\3)(\1)|B.*(?!\4)(\1)|C.*(?!\5)(\1)).)+(?!\3|\4)1

O formato de entrada é a lista de instruções do formulário AB, seguida por nunária usando o dígito 1. Não há separadores. A saída é 1válida e 0inválida.

Experimente online! (Os dois primeiros caracteres habilitam um conjunto de testes separado por avanço de linha.)

Solução alternativa, mesma contagem de bytes:

^(?=\D*((?=(?<3>1+))1)+)((?=A(?<1-3>.+)|B(?<1-4>.+)|C(?<1-5>.+)).(?=A.*(?!\3)(\1)|B.*(?!\4)(\1)|C.*(?!\5)(\1)).)+(?<-5>1)+$

Isso pode, eventualmente, ser encurtado usando 1, 11e 111em vez de A, Be C, mas eu vou ter que olhar para isso mais tarde. Também pode ser mais curto dividir o programa em várias etapas, mas qual é o desafio nisso? ;)

Explicação

Esta solução faz uso pesado dos grupos de balanceamento do .NET. Para obter uma explicação completa, veja minha postagem no Stack Overflow , mas o essencial é que capturar grupos no .NET é pilhas, onde cada nova captura envia outra substring e também é possível sair dessa pilha novamente. Isso permite contar várias quantidades em uma sequência. Nesse caso, permite implementar as três hastes diretamente como três grupos de captura diferentes, onde cada disco é representado por uma captura.

Para mover os discos entre as barras, usamos uma peculiaridade estranha da (?<A-B>...)sintaxe. Normalmente, isso exibe uma captura da pilha Be empurra para a pilha Aa sequência entre a captura exibida e o início desse grupo. Assim, em (?<A>a).(?<B-A>c)comparação com abcdeixaria Avazio e Bcom b(em oposição a c). No entanto, devido às estruturas de comprimento variável do .NET, é possível capturar (?<A>...)e (?<B-A>...)sobrepor. Por qualquer motivo, se for esse o caso, a interseção dos dois grupos é pressionada B. Eu detalhei esse comportamento na "seção avançada" sobre grupos de equilíbrio nesta resposta .

Para a regex. Hastes A, Be Ccorrespondem a grupos 3, 4e 5pela expressão regular. Vamos começar inicializando o rod A:

^                 # Ensure that we start at the beginning of the input.
(?=               # Lookahead so that we don't actually move the cursor.
  \D*             # Skip all the instructions by matching non-digit characters.
  (               # For each 1 at the end of the input...
    (?=(?<3>1+))  # ...push the remainder of the string (including that 1)
                  # onto stack 3.
  1)+
)

Então, por exemplo, se a entrada terminar com 111, o grupo 3 / rod Aagora manterá a lista de capturas [111, 11, 1](a parte superior está à direita).

O próximo bit do código tem a seguinte estrutura:

(
  (?=A...|B...|C...).
  (?=A...|B...|C...).
)+

Cada iteração desse loop processa uma instrução. A primeira alternação puxa um disco da haste especificada (para um grupo temporário), a segunda alternação coloca o disco na outra haste especificada. Veremos em um momento como isso funciona e como garantimos que a mudança é válida.

Primeiro, retirando um disco da haste de origem:

(?=
  A(?<1-3>.+)
|
  B(?<1-4>.+)
|
  C(?<1-5>.+)
)

Isso usa o comportamento estranho de interseção de grupo que descrevi acima. Note-se que grupo 3, 4e 5terá sempre substrings de 1s no final da string cujo corresponde ao tamanho do disco comprimento. Agora usamos (?<1-N>.+)para retirar o disco superior da pilha Ne empurrar a interseção dessa substring com a correspondência .+para a pilha 1. Como .+sempre abrange necessariamente toda a captura capturada N, sabemos que isso simplesmente move a captura.

Em seguida, colocamos esse disco da pilha 1na pilha correspondente à segunda haste:

(?=
  A.*(?!\3)(\1)
|
  B.*(?!\4)(\1)
|
  C.*(?!\5)(\1)
)

Observe que não precisamos limpar a pilha 1, podemos apenas deixar o disco lá, pois colocaremos uma nova por cima antes de usar a pilha novamente. Isso significa que podemos evitar a (?<A-B>...)sintaxe e simplesmente copiar a string (\1). Para garantir que a mudança seja válida, usamos o lookahead negativo (?!\N). Isso garante que, a partir da posição em que queremos corresponder ao disco atual, é impossível corresponder ao disco que já está na pilha N. Isso só pode acontecer se a) \Nnunca corresponder porque a pilha está completamente vazia ou b) the disc on top of stackN is larger than the one we're trying to match with\ 1`.

Finalmente, tudo o que resta é garantir que a) correspondamos a todas as instruções eb) hastes Ae Bestejam vazias, para que todos os discos tenham sido movidos C.

(?!\3|\4)1

Nós simplesmente verificar que nem \3nem \4pode igualar (que é apenas o caso se ambos estão vazios, porque qualquer disco real seria combinar) e que pode, então, corresponder a um 1modo que não omiti quaisquer instruções.

"Apenas" Java 311 272 263 261 260 259 256 bytes

Salvou 39 inúmeros bytes devido ao @Frozn perceber um recurso de depuração mais antigo, além de alguns truques inteligentes de golfe.

Versão Golfed

int i(int n,int[]m){int j=0,k=0,i=n;Stack<Integer>t,s[]=new Stack[3];for(;j<3;)s[j++]=new Stack();for(;i-->0;)s[0].push(i);for(;k<m.length;k+=2)if((t=s[m[k+1]]).size()>0&&s[m[k]].peek()>t.peek())return 0;else t.push(s[m[k]].pop());return s[2].size()<n?0:1;}

destituído de explicações e pilhas bem impressas a cada passo

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package codegolf;

/**
 *
 * @author rohan
 */
import java.util.Arrays;
import java.util.Stack;
public class CodeGolf {
    //golfed version
    int i(int n,int[]m){int j=0,k=0,i=n;Stack<Integer>[] s=new Stack[3];for(;j<3;j++)s[j]=new Stack();for(;i-->0;)s[0].push(i);for(;k<m.length;System.out.println(Arrays.toString(s)),k+=2)if(!s[m[k+1]].isEmpty()&&s[m[k]].peek()>s[m[k+1]].peek())return 0;else s[m[k+1]].push(s[m[k]].pop());return s[2].size()==n?1:0;}
    /** Ungolfed
        * 0 as falsy 1 as truthy
        * @param n the number of disks
        * @param m represents the zero indexed stacks in the form of [from,to,from,to]
        * @return 0 or 1 if the puzzle got solved, bad moves result in an exception
        */
    int h(int n, int[] m) {
        //declarations
        int j = 0, k = 0, i = n;
        //create the poles
        Stack<Integer>[] s = new Stack[3];
        for (; j < 3; j++) {
            s[j] = new Stack();
        }
        //set up the first tower using the "downto operator
        for (; i-- > 0;) {
            s[0].push(i);
        }
    //go through and perform all the moves
        for (; k < m.length; System.out.println(Arrays.toString(s)), k += 2) {
            if (!s[m[k + 1]].isEmpty() && s[m[k]].peek() > s[m[k + 1]].peek()) {
                return 0;//bad move
            } else {
                s[m[k + 1]].push(s[m[k]].pop());
            }
        }
        return s[2].size() == n ? 1 : 0;// check if all the disks are done
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
    //test case
        System.out.println( new CodeGolf().h(3,new int[]{0,2,0,1,2,1,0,2,1,0,1,2,0,2})==1?"Good!":"Bad!");
    }

}

A versão ungolfed possui um recurso no qual será impressa a aparência das pilhas a cada etapa ...

[[2, 1], [], [0]]
[[2], [1], [0]]
[[2], [1, 0], []]
[[], [1, 0], [2]]
[[0], [1], [2]]
[[0], [], [2, 1]]
[[], [], [2, 1, 0]]
Good!

Python 2, 186 167 158 135 127 115 110 102 bytes

n,m=input()
x=[range(n),[],[]]
for a,b in m:p=x[a].pop();e=x[b];e and 1/(p>e[-1]);e+=p,
if x[0]+x[1]:_

Recebe entrada em STDIN no seguinte formato:

(1,[(0,1),(1,2)])

Ou seja, uma tupla em Python do número de discos e uma lista em Python de tuplas (from_rod,to_rod). Como no Python, os parênteses ao redor são opcionais. As hastes são indexadas a zero.

Por exemplo, este caso de teste:

n=2; "A->B ; A->C ; B->C"

seria dado como:

(2,[(0,1),(0,2),(1,2)])

Se a solução for válida, não produzirá nada e sairá com um código de saída 0. Se for inválido, lança uma exceção e sai com um código de saída 1. Lança um IndexErrorse estiver se movendo para uma haste inexistente ou tentando retirar um disco de um disco. haste que não possui discos, a ZeroDivisionErrorse um disco for colocado em cima de um disco menor ou a NameErrorse ainda houver discos na primeira ou na segunda haste no final.

Guardou 13 bytes graças a @KarlKastor!

Economizou 8 bytes graças a @xnor!

Python 2.7, 173 158 138 130 130 127 123 bytes:

r=range;a,b=input();U=[r(a,0,-1),[],[]]
for K,J in b:U[J]+=[U[K].pop()]if U[J]<[1]or U[K]<U[J]else Y
print U[-1]==r(a,0,-1)

Recebe a entrada através do stdin no formato em (<Number of Discs>,<Moves>)que <Moves>é fornecida como uma matriz contendo tuplas correspondentes a cada movimento, cada uma contendo um par de números inteiros separados por vírgula. Por exemplo, o caso de teste:

n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C" 

dado no post seria dado como:

(3,[(0,2),(0,1),(2,1),(0,2),(1,0),(1,2),(0,2)]) 

ao meu programa. Produz um IndexErrorse a 3ª condição não for atendida, a NameErrorse a 2ª condição não for atendida e Falsese a 1ª condição não for atendida. Caso contrário, as saídas True.

VBA, 234 217 213 196 bytes

Function H(N,S)
ReDim A(N)
While P<Len(S)
P=P+2:F=1*Mid(S,P-1,1):T=1*Mid(S,P,1)
E=E+(T>2):L=L+T-F
For i=1 To N
If A(i)=F Then A(i)=T:Exit For
E=E+(A(i)=T)+(i=N)
Next
Wend
H=L+9*E=2*N
End Function

O formato de entrada para movimentos é uma sequência com um número par de dígitos (012). A chamada está na planilha, = H ([número de discos], [mover seqüência])

A matriz A mantém a posição da haste dos vários discos. Um movimento é simplesmente atualizar a primeira ocorrência do número da haste "De" para o número da haste "Para". Se você encontrar um disco de haste "Para" primeiro ou nenhum disco de haste "De", é um movimento inválido. O "valor total da haste" de A é mantido em L, que precisa terminar em 2N. Os erros são acumulados como uma contagem negativa em E.

Em comum com outras soluções, "mover" um disco de uma torre para a mesma torre não é proibido. Eu poderia proibi-lo por mais 6 bytes.

Resultados

Resultado da função na primeira coluna (o último caso de n = 3 é minha adição usando uma haste extra).

TRUE    1   02
TRUE    1   0112
TRUE    2   010212
TRUE    2   02210212
TRUE    2   020121101202
TRUE    3   02012102101202
TRUE    4   010212012021010212102012010212

FALSE   1   01
FALSE   1   20
FALSE   2   02012102101202
FALSE   2   010221
FALSE   2   02012110
FALSE   2   0202
FALSE   3   0202012102101202
FALSE   3   0201210112101202
FALSE   3   02012102101221
FALSE   3   0103023212
FALSE   4   0102120120210102121020120102
FALSE   4   01010102121212

php, 141 bytes

<?php $a=$argv;for($t=[$f=range($a[++$i],1),[],[]];($r=array_pop($t[$a[++$i]]))&&$r<(end($t[$a[++$i]])?:$r+1);)$t[$a[$i]][]=$r;echo$t[2]==$f;

O script da linha de comando recebe a entrada como altura e, em seguida, uma série de índices de matriz (0 indexados), por exemplo, 1 0 2 ou 2 0 1 0 2 1 2 para os casos de teste mais curtos de 1 ou 2 alturas.
Ecos 1 em casos verdadeiros e nada em casos falsos.
Dá 2 avisos e 1 aviso, portanto, precisa ser executado em um ambiente que os silencie.

JavaScript (ES6), 108

n=>s=>!s.some(([x,y])=>s[y][s[y].push(v=s[x].pop())-2]<v|!v,s=[[...Array(s=n)].map(_=>s--),[],[]])&s[2][n-1]

Formato de entrada: função com 2 argumentos

• arg 1, numérico, número de toques
• arg 2, array de strings, cada string 2 caracteres '0', '1', '2'

Saída: retorno 1 se ok, 0 se inválido, exceção se haste não existente

Menos jogado e explicado

n=>a=>(
  // rods status, rod 0 full with an array n..1, rod 1 & 2 empty arrays
  s = [ [...Array(t=n)].map(_=>t--), [], [] ],
  // for each step in solution, evaluate function and stop if returns true
  err = a.some( ([x,y]) => {
    v = s[x].pop(); // pull disc from source rod
    // exception is s[x] is not defined
    if (!v) return 1; // error source rod is empty
    l = s[y].push(v); // push disc on dest rod, get number of discs in l
    // exception is s[y] is not defined
    if(s[y][l-2] < v) return 1; // error if undelying disc is smaller
  }),
  err ? 0 // return 0 if invalid move
  : s[2][n-1]; // il all moves valid, ok if the rod 2 has all the discs
)

Nota do teste : a primeira linha da função Teste é necessária para converter o formato de entrada fornecido na pergunta para a entrada esperada pela minha função

F=
n=>s=>!s.some(([x,y])=>s[y][s[y].push(v=s[x].pop())-2]<v|!v,s=[[...Array(s=n)].map(_=>s--),[],[]])&s[2][n-1]

Out=x=>O.textContent+=x+'\n'

Test=s=>s.split`\n`.map(r=>[+(r=r.match(/\d+|.->./g)).shift(),r.map(x=>(parseInt(x[0],36)-10)+''+(parseInt(x[3],36)-10))])
.forEach(([n,s],i)=>{
  var r
  try {
    r = F(+n)(s);
  } 
  catch (e) {
    r = 'Error invalid rod';
  }
  Out(++i+' n:'+n+' '+s+' -> '+r)
})

Out('OK')
Test(`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"`)

Out('\nFail')
Test( `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"`)

<pre id=O></pre>