Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Resolvendo o Jogo Spin-out recursivamente

0 votos
30 visitas
perguntada Abr 17 em Programação Computacional por Felipe Yudi (46 pontos)  

A seguinte questão foi retirada do livro “Introduction to recursive programming - Manuel Rubio Sanchez” [IRP2018] – Exercício 9.8

"O seguinte problema é conhecido como o desafio Spin-out®. As figuras abaixo serão usadas para ilustrar o problema. Inicialmente, há n peças (7 no exemplo) que aparecem continuamente ao longo de uma haste e que estão dentro de um recipiente alongado com uma saída estreita no lado direito. As peças podem aparecer em duas orientações: verticalmente, apontando para cima como em (a), ou horizontalmente, apontando para esquerda como em (b). O objetivo é mudar a orientação das peças da configuração inicial em (a) “locked” para o padrão em (b) “unlocked”, onde é possível retirar a haste com as peças do recipiente. Note que uma peça na posição vertical impede a retirada da haste do recipiente, pois se choca contra a parede do mesmo. Apenas uma peça pode ser movida de cada vez: da posição vertical para horizontal e vice-versa. Além disso, podemos mudar a orientação das peças apenas no “ponto de rotação”, que é o círculo hachurado nas ilustrações.
Em (c), a quarta peça pode ser rotacionada para a posição horizontal. Adicionalmente, note que as paredes do recipiente impedem que movamos a haste para a direita, pois a peça a direita do ponto de rotação está na posição vertical. Note também que apesar de sempre ser possível mover a primeira peça (da direita para esquerda), só é possível mover qualquer outra se a peça a direita desta está na posição vertical, como em (c). Assim, em (d), não é possível rotacionar a quarta peça.

Implemente dois procedimentos mutualmente recursivos para indicar a sequência de peças que precisam ser rotacionadas para obter o padrão “unlocked”, indo da configuração (a) para a (b) para n peças. Finalmente, especifique uma função que determina o número de rotações necessárias para colocar na posição “unlocked” uma haste com n peças."

A imagem será apresentada aqui.

Compartilhe

1 Resposta

0 votos
respondida Abr 17 por Felipe Yudi (46 pontos)  
editado Abr 21 por Felipe Yudi

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.

...