Altas rotações

Um dos problemas do livro (problema 6.8) é pedido um programa que permita rodar de 90 graus uma matriz representada por uma lista de listas: uma lista com as linhas sendo que estas são também elas listas com os elementos na respectiva coluna. Um aluno de IPRP resolveu, e bem, ser mais ambicioso e implementar um programa que permita rodar 90, 128 ou 270 graus. Enviou-me o programa que reproduzo.

view sourceprint?

01.import copy

02.def rodar(matriz, grau):

03.     

04.    nova_matriz = copy.deepcopy(matriz)

05.    for i in range(len(matriz)):

06.        for j in range(len(matriz[i])):

07.            if grau == 90:

08.                nova_matriz[j][len(matriz)-(i+1)] = matriz[i][j]

09.            elif grau == 180:    

10.                nova_matriz[len(matriz)-(i+1)][len(matriz)-(j+1)] = matriz[i][j]

11.            elif grau == 270:  

12.                nova_matriz[len(matriz) - (j+1)][i] = matriz[i][j]

13.    return nova_matriz

14.     

15.if __name__ == '__main__':

16.        print(rodar([[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20],[21,22,23,24,25]], 90))

Trata-se de um programa muito bom, denotando ter entendido bem onde estava a dificuldade maior. E a solução para o problema não era fácil de encontrar... Teve o cuidado de fazer uma cópia profunda, pois estamos a lidar com listas de listas, e calculou correctamente a relação entre as posições antigas e as novas. Mas no email que me mandou estava um pouco incomodado pois o programa só funcionava bem no caso das matrizes serem quadradas. Vamos então ajudá-lo a resolver este pequeno detalhe...

A chave para a solução consiste em perceber que o número de linhas e de colunas original pode mudar com a rotação. Por essa razão não podemos fabricar a nova matriz a partir da matriz inicial. Devemos criá-la de raíz. Uma possibilidade é criar a matriz com a nova estrutura e colocando no seu interior zeros. Com a estrutura depende do valor da rotação vamos começar por considerar o caso de uma rotação de 90º, na qual as linhas passam a colunas. Assim uma matriz mXn passa a nXm.

view sourceprint?

1.    nova_matriz = []

2.    for i in range(len(matriz[0])):

3.        nova_linha = []

4.        for j in range(len(matriz)):

5.            nova_linha.append(0)

6.        nova_matriz.append(nova_linha) 

Claro que já interiorizou o conceito de listas por compreensão pode chegar a uma solução mais curta:

view sourceprint?

1.nova_matriz = [[0 for j in range(len(matriz))] for i in range(len(matriz[0]))]  

Estamos em condições de escrever um programa que faça rodar uma matriz de 90º.

view sourceprint?

1.def rodar_90(matriz):

2.    nova_matriz = [[0 for j in range(len(matriz))] for i in range(len(matriz[0]))]  # <<------ Aqui está o segredo :-)

3.    for linha in range(len(matriz)):

4.        for coluna in range(len(matriz[0])):

5.            nova_matriz[coluna][len(matriz) - 1 - linha] = matriz[linha][coluna]

6.    return nova_matriz

Mas ainda falta o resto, 180º e 270º. Vamos a isso. Como a nossa solução autonomizou as rotações, vamos ter um programa principal como este:

view sourceprint?

01.def rodar(matriz,grau):

02.    if grau == 90:

03.        return rodar_90(matriz)

04.    elif grau == 180:

05.        return rodar_180(matriz)

06.    elif grau == 270:

07.        return rodar_270(matriz)

08.    else:

09.        print('Oops, isso ainda não sei fazer...!')

10.        return -1

O resto da solução é trivial: rodar 180 é o mesmo que rodar duas vezes 90; rodar 270 é o mesmo que rodar três vezes 90 ou rodar uma vez 180 e outra 90. Certo?

view sourceprint?

1.def rodar_180(matriz):

2.    return rodar_90(rodar_90(matriz))

3. 

4.def rodar_270(matriz):

5.    return rodar_90(rodar_180(matriz))

Moral da história. Partimos de uma boa solução mas que resolve apenas um caso especial do problema (matrizes quadradas), e identificámos onde estava o problema; resolvemos para um caso (90) e usamos essa solução para o resto (180, 270); pelo caminho ainda deparámos com o problema causado pela mutabilidade e partilha de memória (modo como criámos a nova matriz); e ainda apresentámos uma solução baseada em listas por compreensão. Mas o essencial da mensagem é: perante um problema difícil, tente resolver uma versão mais simples, decomponha esse problema em sub-problemas e depois generalize a solução para chegar ao resultado pretendido.