Acredito que o enunciado do livro não é o suficiente para entender a natureza do problema. Spin-out® é um jogo do tipo quebra-cabeça real lançado nos Estados Unidos nos anos 80. Para entender melhor como o jogo funciona, veja o vídeo neste link.
Antes de resolver o problema, começaremos definindo alguns termos:
- Uma peça é uma das n chaves do jogo.
- Uma peça pode assumir duas posições: horizontal ou vertical.
- A posição vertical será representada pelo número 1 e a horizontal pelo número 0.
- Um “turn” é uma troca de posição de uma peça.
- Um jogo é uma lista de peças.
- Um jogo começa quando todas as peças estão na posição 1 e termina quando todas as peças estão na posição 0.
- Cada chave tem uma identificação numérica (começando a contar a partir de 1) da esquerda para a direita, o inverso das ilustrações do enunciado.
Para a implementação em Python, consideraremos que um jogo é uma lista de inteiros que podem ser 1 ou 0. Cada inteiro representa uma peça em uma determinada posição. Assim, um jogo com n = 4 na posição inicial (todas as peças na vertical) é:
[1, 1, 1, 1]
O objetivo é chegar na posição final respeitando as regras descritas no enunciado, ou seja:
[0, 0, 0, 0]
Comece imaginando um jogo com 0 peças (n=0). Então claramente o jogo é resolvido com 0 turns, pois a haste pode ser retirada sem nenhuma troca de posição. Um jogo com 1 peça é resolvido com 1 turn. Basta mudar a posição da peça e retirar a haste. Já com 2 peças, temos que primeiro rotacionar a chave 2, rotacionar a chave 1 e retirar a haste. Portanto 2 turns são necessários.
Com três peças, o problema se complica um pouco, mas ainda é fácil verificar que a solução é:
1 Turn 1
2 Turn 3
3 Turn 1
4 Turn 2
5 Turn 1
Para 4 peças, temos que:
1 Turn 2
2 Turn 1
3 Turn 4
4 Turn 1
5 Turn 2
6 Turn 1
7 Turn 3
8 Turn 1
9 Turn 2
10 Turn 1
Já é possível notar que para resolver o problema com 4 peças, é necessário saber a solução para o problema com 3 peças e assim por diante. Começamos a suspeitar que se trata de um problema recursivo.
De fato, é possível mostrar que uma estratégia para resolver um problema de tamanho n é reduzi-lo a um problema de tamanho n-1. Para reduzir o problema, porém, é necessário resolver o problema n-2, pois isso nos permite rotacionar a enésima peça. Após isso, basta retornar as primeiras n-2 peças para suas posições verticais revertendo os passos na solução do problema de tamanho n-2.
Em resumo, a estratégia aqui utilizada será:
- Resolver o problema com n-2 peças.
- Rotacionar a enésima peça.
- Retornar as peças do problema n-2 para sua posição original.
- Resolver o problema com n-1 peças.
Para resolver o problema, vamos implementar três procedimentos e uma função. Um procedimento é como uma função, mas ele não retorna nenhum valor, apenas realiza operações, imprime resultados etc.
Antes de começar é importante ressaltar que um jogo será inicialmente uma variável global (posteriormente a tornaremos local) para facilitar a definição dos procedimentos.
Comece definindo um procedimento que pega um jogo e muda a enésima peça.
def turn(nth):
"""
Muda o valor da enesima peca.
"""
if lst[nth] == 0:
lst[nth] = 1
else:
lst[nth] = 0
Note que lst não é argumento do procedimento. Ela é uma variável global. É possível que seyu editor esteja reclamando (com razão) que lst ainda não foi definida. Ignore.
Em seguida vamos definir dois procedimentos. Um que coloca as chaves na posição 0 e outro que coloca as chaves na posição 1. Note, porém, que por se tratar de procedimentos recursivos mútuos, um chamará o outro.
def Open(n):
if n == 1:
turn(0)
elif n == 2:
turn(1)
turn(0)
else:
Open(n-2)
turn(n-1)
Close(n-2)
Open(n-1)
def Close(k):
if k == 1:
turn(0)
elif k == 2:
turn(0)
turn(1)
else:
Close(k-1)
Open(k-2)
turn(k-1)
Close(k-2)
Como em toda função recursiva, Open e Close possuem casos bases. Tais casos já foram discutidos anteriormente. No caso de Open, se o jogo tem uma peça basta rotacioná-la. Se tem duas, rotacione a segunda e depois a primeira. No caso de Close, as ações são as mesmas, mas na ordem oposta: se o jogo tem apenas uma peça, feche-a. Se tem duas, feche a primeira e depois a segunda.
O terceiro bloco dos procedimentos segue a estratégia descrita acima: resolva o problema para n-2, rotacione a enésima peça (note que no código chamamos o procedimento turn com n-1 como argumento - e não n- isso ocorre porque turn modifica uma lista e em Python, elas são indexadas a partir do zero). Retorne as peças do jogo n-2 para a posição original e resolva para n-1.
Os procedimentos acima ainda são desajeitados, pois dependem de variáveis globais e não mostram nem como e nem quantos passos são necessários para resolver um jogo. Para resolver isso, vamos inserir algumas funções print toda vez que o procedimento turn é chamado. Vamos também colocar esses procedimentos dentro de uma função (criando funções aninhadas) para que evitemos o uso de variáveis globais.
O programa final fica então:
def SpinOut(n):
"""
n: int
Resolve um jogo de Spin-out de
tamanho n.
Imprime os passos e imprime e
retorna o número de movimentos
necessários.
"""
a = []
def turn(nth):
"""
Muda o valor da enesima peca.
"""
if lst[nth] == 0:
lst[nth] = 1
else:
lst[nth] = 0
a.append(1)
def Open(n):
"""
n: int.
Abre uma chave.
"""
if n == 1:
turn(0)
print("turn 1 O")
elif n == 2:
turn(1)
print("turn 2 O")
turn(0)
print("turn 1 O")
else:
Open(n-2)
turn(n-1)
print("turn", n, "O")
Close(n-2)
Open(n-1)
def Close(k):
"""
k: int.
Fecha uma chave.
"""
if k == 1:
turn(0)
print("turn 1 C")
elif k == 2:
turn(0)
print("turn 1 C")
turn(1)
print("turn 2 C")
else:
Close(k-1)
Open(k-2)
turn(k-1)
print("turn", k, "C")
Close(k-2)
lst = []
for i in range(n):
lst.append(1)
Open(n)
print("Num. Passos:", len(a))
return len(a)
if __name__ == "__main__":
SpinOut(5)
SpinOut é a função que resolve o jogo. n é um inteiro que indica o tamanho do jogo. a é uma lista que recebe 1 toda vez que uma peça é virada. Ela guarda o número de jogadas necessárias para resolver o problema. As últimas linhas do código apenas geram uma lista de uns de comprimento n (ouseja, geram um jogo de comprimento n).
A saída para um jogo de tamanho 5 é:
turn 1 O
turn 3 O
turn 1 C
turn 2 O
turn 1 O
turn 5 O
turn 1 C
turn 2 C
turn 1 O
turn 3 C
turn 1 C
turn 2 O
turn 1 O
turn 4 O
turn 1 C
turn 2 C
turn 1 O
turn 3 O
turn 1 C
turn 2 O
turn 1 O
Num. Passos: 21
Para aqueles que se interessaram nos detalhes matemáticos do jogo consultar os papers abaixo:
LINDSAY BAUN AND SONIA CHAUHAN - PUZZLES ON GRAPHS: THE TOWERS OF HANOI, THE SPIN-OUT PUZZLE, AND THE COMBINATION PUZZLE
LEANNE MERRILL AND TONY VAN - A TALE OF TWO PUZZLES
Lamphere Robert et all. – Spinout Puzze and Recursion
Bônus:
Para uma solução mais rápida e eficiente consultar este vídeo a partir de 4 min.