Vermes em passeio

Vamos regressar ao módulo turtle para ilustrar um aspecto pouco referido nas aulas. É possível a tartaruga marcar os pontos por onde passou graças ao comando stamp(). Também se pode apagar as marcas com vários comandos, por exemplo, com clearstamps(). O leitor é convidado a consultar o manual da linguagem para os detalhes. O exemplo que se segue mostra como podemos simular um passeio (mais ou menos) aleatório de um verme.

import turtle
import random

def bug(length, step, life):
    # initialization
    turtle.penup()
    theta = 0
    dtheta = 1
    turtle.color(random.choice([‘red','blue','yellow','green','black']))
    # draw bug
    for j in range(length):
        turtle.forward(step)
        turtle.left(theta)
        theta += dtheta
        turtle.stamp()  
    # move
    for i in range(life):
        turtle.clearstamps(1)
        if abs(ycor()) > 400:
            turtle.left(30)
        if abs(xcor()) > 400:
            turtle.right(30)
        if theta > 10 or theta < -10:
            dtheta = -dtheta                
        turtle.forward(step)
        turtle.left(theta)
        theta += dtheta
        turtle.stamp()

if __name__ == '__main__':
    turtle.setworldcoordinates(-500, -500, 500, 500)
    bug(10, 15, 500)
    turtle.exitonclick()

O programa acima tem três parâmetros: o comprimento do verme (length), a amplitude de cada movimento (step), e o numero de movimentos (life), Tem também três partes distintas. Na primeira, inicializamos o sistema, definimos o valor da variação da orientação que nos permite simular um movimento ondulatório (dtheta), e escolhemos aleatoriamente uma cor. Na segunda, o primeiro ciclo for, desenhamos o verme inicial. Na terceira, pomos o verme e movimentar-se. Notar-se-á que fechamos a zona onde se pode movimentar, um quadrado 400X400. Com o método setworlcoordinates() limitamos o tamanho máximo do mundo. Execute o programa para ter uma ideia do que se passa. Procure alterar os vários parâmetros e ver as consequências. Altere o programa para que o passeio seja mais naturalmente aleatório. Nota: Este exemplo foi adaptado do livro de Mark J. Johnson "A concise introduction to programming ion Python".

Árvore Genealógica

No texto de apoio à disciplina é introduzido um conceito simplista de árvore genealógica. Estas árvores são representadas por um dicionário em que as chaves são nomes de pessoas (um progenitor) e os valores são listas de nomes de pessoas (os filhos). Esta representação permite, por exemplo, obter os filhos de alguém de modo trivial:

def filhos(dicio,progenitor):
    """ lista dos filhos."""
    return dicio.get(progenitor,[])

Também é fácil listar os netos de alguém. Por exemplo:

def netos(dicio,progenitor):
    """ Lista netos. Filhos dos filhos"""
    desc1 = filhos(dicio,progenitor)
    if desc1:
        net = []
        for elem in desc1:
            desc2 = filhos(dicio,elem)
            if desc2:
                net = net + desc2
        return net
    else:
        return []

Esta solução calcula primeiro os filhos e, caso existam, os filhos dos filhos. Não é difícil propor versões alternativas para esta questão. Por exemplo:

def netos_b(arv_genea,progenitor):
    net = []
    desc1 = filhos(arv_genea,progenitor)
    for prog in desc1:
        net.extend(filhos(arv_genea,prog))
    return net

Aqui simplificamos o código no interior do ciclo recorrendo ao método extend. Mas ainda podemos aproximarmo-nos mais da defino natural: netos são os filhos dos filhos:

def netos_b(dicio ,progenitor):
    """ Lista dos netos. Os filhos dos filhos"""
    return filhos_b(dicio,filhos_b(dicio,[progenitor]))

def filhos_b(dicio,lista_progenitores):
    lista_filhos = []
    for filho in lista_progenitores:
        lista_filhos.extend(dicio.get(filho,[]))
    return lista_filhos

Note-se que tivemos que alterar a função filhos para agora me dar a lista dos filhos de um conjunto de pessoas.
Agora o conceito básico de progenitor de alguém:

def progenitor(ag,nome):
    for p,fil in ag.items():
        if nome in fil:
            return p
    return None

Neste caso vamos procurar o nome na lista dos filhos de alguém que, a existir, será o progenitor. Passemos a outros exemplos. Irmãos são pessoas que têm um progenitor comum. Com está organizada a árvore genealógica cada pessoa tem um progenitor único, logo:

def irmaos(ag,nome1,nome2):
    """ Têm o mesmo progenitor?"""
    prog1 = progenitor(ag, nome1)
    prog2 = progenitor (ag,nome2)
    return prog1 == prog2

Socorrendo-nos de novo da ideia de progenitor podemos definir o conceito de avô/avó.

def avo(dic,nome):
    """ Quem é o avô/avó do nome."""
    prog = progenitor(dic,nome)
    if prog:
        return progenitor(dic,prog)
    return None

Deixamos ao leitor o cuidado de definir outras relações de parentesco. Por exemplo, tente o conceito de primos (os filhos de irmãos). Por outro lado, alguns dos conceitos acima são booleanos. Imagine que em vez de se saber se duas pessoas são primos se pretende saber quais os primos de alguém. Não lhe deve ser difícil chegar à solução.
Finalmente, pense numa implementação mais realista de uma árvore genealógica, em que cada pessoa tem associado os seus pais. E faça tudo de novo!!!

Listas por Compreensão (II)

Estamos habituados em matemática a definir um conjunto de duas formas distintas: por extensão, quando indicamos os seus elementos, ou por intenção, quando indicamos uma regra que nos permite identificar os elementos do conjunto. Em Python podemos descrever uma lista de elementos também destas duas formas. À segunda chamamos listas por compreensão. As listas por compreensão estão ligadas à resolução de problemas que obedecem a um certo padrão. Por exemplo, admitamos que queremos um programa que gere números inteiros, aleatoriamente, entre um certo intervalo. Uma solução simples seria:

import random

def gera_numeros(n,inf, sup):
     res = []
     for i in range(n):
          num = random.randint(inf,sup)
          res.append(num)
     return res

Este padrão em que temos um acumulador onde vão sendo guardados elementos através de um processo repetitivo, pode ser implementado também por recurso a listas por compreensão:

def gera_numeros_b(n,inf, sup):
     res = [ random.randint(inf,sup) for i in range(n)]
     return res

Como se percebe a sintaxe envolve, nesta versão básica, os indicadores de lista (“[“ e “]”), seguido de uma expressão que nos permite gerar os elementos da lista, seguido do processo repetitivo (ciclo for). Podemos aplicar este modelo em diferentes situações.

Elevar os números de aula lista ao quadrado:

def quadrados(lista):
     return [elem**2 for elem in lista]

Produto escalar de dois vectores:

def escalar_comp(x,y):
     """ Produto escalar de dois vectores."""
     return sum([x[i]*y[i] for i in range(len(x))])

A lista por compreensão gera os produtos e a função sum faz a soma.
Somas parciais (percorrer a lista e gerar uma nova list em que na posição i é colocada a soma dos números da primeira lista desde o início até (inclusive) i):

def somas_parciais(lista):
     """ somas de 1 a i."""
     return [sum(lista[:i+1]) for i in range(len(lista))]

Podemos dizer que, de um modo geral ,este padrão obedece ao modelo:

def my_map(func, lista):
     return [func(elem) for elem in lista]

O leitor poderá pensar que não é muito poderoso este modo de programar. Por exemplo, não podemos filtrar elementos a incluir na lista em função de um dado critério. Mas as listas por compreensão têm uma sintaxe mais completa. Admitamos que queremos construir uma lista a partir de outra, retendo apenas os seus elementos positivos:

def filtro_nega(lista):
     return [ elem for elem in lista if elem > 0]
  

Agora temos a expressão, seguida do ciclo for, seguida do if. Outros exemplos: Lista dos índices das ocorrências de um dado elemento:

def ocorre(elem, lista):
     """ localizaçoes das ocorrências de elem na lista."""
     return [ i for i in range(len(lista)) if lista[i] == elem]

Conta o número de ocorrências:

def conta(elem, lista):
     """Quantas ocorrências de elem na lista."""
     return sum([ 1 for e in lista if e == elem])

Parece melhor. Mas e problemas em que existem mais do que um ciclo? Por exemplo, quando pretendemos construir a lista de pares ordenados formados com elementos de outras duas listas fazemos:

def combina(a,b):
     """ pares ordenados com elementos de a e de b."""
     res = []
     for elem_a in a:
          for elem_b in b:
               res.append((elem_a,elem_b))
     return res

Mas também esta situação está contemplada:

def combina_b(a,b):
     return [(elem_a,elem_b) for elem_a in a for elem_b in b]

Como se vê a sintaxe é dada pela expressão, seguida do ciclo mais externo, seguida do ciclo mais interno. No ciclo interno podemos referir objetos do ciclo externo.

Um exemplo simples consiste em obter a lista dos elementos de uma lista de listas:

def aplana(lista_listas):
     """Aplanar uma lista de listaas."""
     return [elem for linha in lista_listas for elem in linha  ]

Podemos ainda complicar mais as coisas? Podemos! Numa lista por compreensão no lugar da expressão podemos ter … uma lista por compreensão!!! Vejamos como esse facto nos permite obter a transposta de uma matriz de modo simples:

def transposta_b(matriz):
     """transposta de uma matriz."""
     return [ [matriz[j][i] for j in range(len(matriz))] for i in range(len(matriz[0]))]

Agora a expressão é uma lista por compreensão e deve ser considerada como estando no interior do ciclo for que aparece a seguir! Podemos usar este código para escrever um programa que roda 90 graus no sentido dos ponteiros do relógio uma imagem a preto e branco representada por uma lista de listas de 1s e 0s.

def roda_90(imagem):
     """ Rodar 90 graus uma imagem."""
     img_trans = transposta_b(matriz)
     nova_imagem = [linha[::-1]  for linha in img_trans]
     return nova_imagem

Estaremos limitados a dois ciclos? Mais uma vez a resposta é negativa. Segue-se um exemplo, que mostra como se podem obter três inteiros que verificam a condição do Teorema de Pitágoras:

def pitagoras(n):
     return [(x,y,z) for x in range(1,n) for y in range(1,n) for z in range(1,n) if x**2 + y**2 == z**2]

Executando o programa verificamos a ocorrência de repetições. Mas podemos resolver facilmente esse problema:

def pitagoras_b(n):
     return [(x,y,z) for x in range(1,n) for y in range(x,n) for z in range(y,n) if x**2 + y**2 == z**2]

E se em vez da potência ser 2 fosse outro inteiro maior do que 2? Estamos perante o chamado último Teorema de Fermat. Mas não aconselho a tentar prová-lo deste modo…

def fermat(n,k):
     return [(x,y,z) for x in range(1,n) for y in range(x,n) for z in range(y,n) if x**k + y**k == z**k]

O leitor continua a pensar que tudo isto é muito limitado. Vamos então a um exemplo em que a expressão é um pouco mais complexa, pois inclui uma condicional. Neste caso podemos implementar uma função em que todos os elementos de uma lista de determinado valor são substituídos por outro elemento:

def my_replace(novo, velho,lista):
     return [novo if elem == velho else elem for elem in lista]

Pois é, estamos perante um novo tipo de expressão: objecto if condição else objecto. Vamos usar esta ideia para obter o negativo de uma imagem a preto e branco:

def negativo_img(imagem):
     return [[ 0 if elem == 1 else 1  for elem in linha] for linha in imagem]

Para terminar, vamos deixá-lo com um exemplo que nos permite calcular uma lista de números primos, recorrendo ao algoritmo conhecido por Sieve of Erathostenes.

def primos(n):
     up = int(math.sqrt(n))
     no_primes = [j for i in range(2,up+1) for j in range(i**2,n+1,i)]
     return [ x for x in range(2,n+1) if x not in no_primes]

Interessante, não concorda? Talvez. Chegados aqui coloca-se a questão de saber se é possível realizar com listas por compreensão coisas que não se podem fazer de outro modo. E resposta é um redondo não. Então porquê usar? Se olharmos para os exemplos anteriores é claro que há medida que queremos fazer coisas mais complexas a legibilidade do programa diminui. No entanto existe uma razão forte: o uso de listas por compreensão torna os programas muito mais rápidos! Então o nosso conselho final é: use as listas por compreensão sempre que o tempo de execução for crítico ou, não sendo crítico, sempre que a legibilidade do programa não seja comprometida.

Desenhar uma grelha: um exercício de programação

Nas aulas discutimos o problema de desenhar uma grelha rectangular com n células, cada uma um quadrado com um dado comprimento do lado. Uma das soluções que apareceu baseava-se na ideia de desenhar a grelha como nós humanos geralmente fazemos: desenhar separadamente as linhas verticais e as horizontais. Vejamos uma solução básica:

import turtle

def grelha_1(dim, lado):
    """ Solução básica."""
    # verticais
    turtle.setheading(90)
    for i in range(dim+1):
        # posiciona
        turtle.penup()
        turtle.goto(i * lado,0)
        turtle.pendown()
        # desenha
        turtle.forward(dim*lado)
    # horizontais
    turtle.setheading(0)
    for i in range(dim+1):
        # posiciona
        turtle.penup()
        turtle.goto(0,i*lado)
        turtle.pendown()
        # desenha
        turtle.forward(dim*lado)    
    turtle.hideturtle()

Como se pode ver as linhas são desenhadas em separado e cada tipo de linha (verticais ou horizontais) é desenhada no interior de um ciclo. A parte relevante em cada ciclo é o posicionamento da tartaruga para desenhar a linha. Fazemos isso através de um goto.
Uma primeira alteração possível é considerar a possibilidade de controlar a localização do canto inferior esquerdo. Vejamos como se pode fazer.

def grelha_2(dim, lado,pos_x,pos_y):
    """ Controlando a posição do canto inferior esquerdo."""
    # verticais
    turtle.setheading(90)
    for i in range(dim+1):
        # posiciona
        turtle.penup()
        turtle.goto(pos_x + i * lado,pos_y)
        turtle.pendown()
        # desenha
        turtle.forward(dim*lado)
    # horizontais
    turtle.setheading(0)
    for i in range(dim+1):
        # posiciona
        turtle.penup()
        turtle.goto(pos_x,pos_y+i*lado)
        turtle.pendown()
        # desenha
        turtle.forward(dim*lado)    
    turtle.hideturtle()

Como se notará a alteração é mínima, e traduz-se a colocar o valor das coordenadas do canto inferior esquerdo no sítio certo.
Suponhamos agora que nos pedem uma solução em que seja também possível controlar a orientação do quadrado. Esta questão já obriga a uma ginástica adicional, mas a questão central mantém-se a mesma: definir os pontos em que se iniciam as linhas. Eis uma solução, não muito elegante, mas que funciona…

def grelha_4(dim, lado,pos_x,pos_y,orient):
    """ Controlando a posição e a orientação. """
    # verticais
    for i in range(dim+1):
        # posiciona
        turtle.penup()
        turtle.goto(pos_x,pos_y)
        turtle.setheading(orient)
        turtle.forward(i*lado)
        turtle.setheading(90+orient)
        turtle.pendown()
        # desenha
        turtle.forward(dim*lado)
    # horizontais
    for i in range(dim+1):
        # posiciona
        turtle.penup()
        turtle.goto(pos_x,pos_y)
        turtle.setheading(90+orient)
        turtle.forward(i*lado)
        turtle.setheading(orient)
        turtle.pendown()
        # desenha
        turtle.forward(dim*lado)    
    turtle.hideturtle()

Outras alterações poderiam ser feitas, como seja mudar a espessura das linhas ou a sua cor. Mas o que não nos agrada é a legibilidade do código. Afinal o nosso ponto de partida foi considerar o desenho da grelha com base no conceito de linha, mas esse conceito está explicitamente ausente nas soluções acima. Vamos remediar a situação definindo uma função que nos permite desenhar uma linha, com uma dada posição inicial uma orientação e um dado comprimento. Não é difícil.

def linha(pos_x,pos_y, orient, tam):
    # posiciona
    turtle.penup()
    turtle.goto(pos_x,pos_y)
    turtle.setheading(orient)
    turtle.pendown()
    # desenha
    turtle.forward(tam)
    turtle.hideturtle()

Na posse desta nova construção (abstracção), podemos refazer as soluções acima apresentadas. Comecemos pela básica:

def grelha_5(dim, lado):
    """ Solução básica."""
    # horizontais
    for i in range(dim+1):
        linha(0,i*lado,0,dim*lado)
    # verticais
    for i in range(dim+1):
        linha(i*lado,0,90,dim*lado)
    turtle.hideturtle()

O leitor concordará que corresponde de modo mais claro à forma como enunciámos a solução. Passemos à posição.

def grelha_6(dim, lado,pos_x,pos_y):
    """ Solução com controlo da posição do canto inferior esquerdo."""
    # horizontais
    for i in range(dim+1):
        linha(pos_x,pos_y+i*lado,0,dim*lado)
    # verticais
    for i in range(dim+1):
        linha(pos_x+i*lado,pos_y,90,dim*lado)
    turtle.hideturtle()

Elementar, não acha? Finalmente a orientação. Aqui decidimos usar um pouco dos nossos conhecimentos de trignometria, para definir as novas posições de início das linhas.

Na posse deste conhecimento a solução vem, finalmente, como:

import math

def grelha_7(dim, lado,pos_x,pos_y,orient):
    """ Solução com controlo da posição do canto inferior esquerdo e a orientação."""
    deg_rad = math.pi/180
    # horizontais
    for i in range(dim+1):
        linha(pos_x+i*lado*math.cos((orient+90)* deg_rad),pos_y+ i*lado*math.sin((orient+90)* deg_rad),orient,dim*lado)
    # verticais
    for i in range(dim+1):
        linha(pos_x+i*lado*math.cos(orient * deg_rad),pos_y+ i*lado*math.sin(orient * deg_rad),90+orient,dim*lado)
    turtle.hideturtle()

Chegados a este ponto podemos achar que o trabalho está feito e, por isso, podemos passar a outro problema. Mas… e se alguém nos pedir a nossa solução para criar um tabuleiro de xadrez? Precisamos colorir as células, mas como fazer? A dificuldade reside no facto de termos olhado para a grelha não como uma grelha, isto é formada por células justapostas, mas como linhas que se cruzam. E precisamos partir de novo à aventura: criar a dita grelha formada por quadrados. Mas aprendemos algo com o caso anterior, a saber: usar abstração para criar primitivas é positivo.
Para começar precisamos de uma primitiva para desenhar um quadrado:

def quadrado(pos_x, pos_y, lado, orient):
    # posiciona
    turtle.penup()
    turtle.goto(pos_x,pos_y)
    turtle.setheading(orient)
    turtle.pendown()
    # desenha
    for i in range(4):
        turtle.forward(lado)
        turtle.lt(90)
    turtle.hideturtle()

E vamos percorrer de novo a nossa via sacra. Primeiro a versão básica:

def grelha_8(dim, lado):
    """ Solução básica."""
    # Por linhas
    for i in range(dim):
        # linha i
        for j in range(dim):
            quadrado(j*lado,i*lado,lado,0)    
    turtle.hideturtle()

Não muito diferente, certo? Só que agora temos uma perspectiva matricial, pelo que precisamos de um ciclo dentro de outro ciclo. Controlar a posição é trivial:

def grelha_9(dim, lado, pos_x, pos_y):
    """ Solução com controlo da posição do canto inferior esquerdo."""
    # Por linhas
    for i in range(dim):
        # linha i
        for j in range(dim):
            quadrado(pos_x+j*lado,pos_y+i*lado,lado,0)    
    turtle.hideturtle()

A quatro da orientação pede um pouco mais de atenção como na versão anterior, mas a lógica é semelhante: trata-se de definir os pontos iniciais para cada quadrado:

def grelha_10(dim, lado, pos_x, pos_y, orient):
    """ Solução com controlo da posição do canto inferior esquerdo e da orientação."""
    deg_rad = math.pi/180
    # Por linhas
    for i in range(dim):
        # linha i
        p_x = pos_x+i*lado*math.cos((orient+90)*deg_rad)
        p_y = pos_y+i*lado*math.sin((orient+90)*deg_rad)        
        for j in range(dim):
            quadrado(p_x,p_y,lado,orient)
            p_x = p_x+lado*math.cos(orient*deg_rad)
            p_y = p_y+lado * math.sin(orient*deg_rad)                   
    turtle.hideturtle()

Notar que nesta solução o ciclo interior apenas controla o número de vezes que desenhamos um quadrado numa linha.

. Agora sim podemos dar o trabalho por encerrado!!! Mas, espere aí, ouço-o dizer, a passagem para o ponto de vista das células quadradas não era para termos mais graus de liberdade, nomeadamente em relação à cor dos quadrados??? É verdade sim senhor. Então vamos a isso. A solução mais simples consistirá em poder desenhar quadrados coloridos…

def quadrado_cor(pos_x, pos_y, lado, orient,cor):
    # cor
    turtle.color(cor)
    # posiciona
    turtle.penup()
    turtle.goto(pos_x,pos_y)
    turtle.setheading(orient)
    turtle.pendown()
    # desenha
    turtle.begin_fill()
    for i in range(4):
        turtle.forward(lado)
        turtle.lt(90)
    turtle.end_fill()
    turtle.hideturtle()

E agora eis o nosso tabuleiro bi-color:

def grelha_11(dim, lado, pos_x, pos_y, orient):
    """ Solução com controlo da posição do canto inferior esquerdo e da orientação."""
    deg_rad = math.pi/180
    # Por linhas
    for i in range(dim):
        # linha i
        p_x = pos_x+i*lado*math.cos((orient+90)*deg_rad)
        p_y = pos_y+i*lado*math.sin((orient+90)*deg_rad)        
        for j in range(dim):
            if (i+j)%2 == 0:
                quadrado_cor(p_x,p_y,lado,orient,'black')
            else:
                quadrado_cor(p_x,p_y,lado,orient,'gray')
            p_x = p_x+lado*math.cos(orient*deg_rad)
            p_y = p_y+lado * math.sin(orient*deg_rad)                   
    turtle.hideturtle() 

Veja apenas como conseguimos o efeito das cores alternadas… Experimente o código e aprecie o resultado.

Se quiser outro tipo de tabuleiros coloridos é só adaptar. Agora é mesmo a sua vez de fazer alguma coisa. Eu vou descansar um pouco!

Teste #2 - Turma TP2

Pergunta 1
Diga o que são objectos mutáveis e exemplifique.
Resposta: São objectos que podem ter o seu valor alterado sem alterar a sua identidade. As listas são um exemplo.

b) Analise a listagem seguinte e diga, justificando, o que vai aparecer no lugar dos pontos de interrogação.

>>> x_2 = ([1,2,3],[4,5,6])
>>> x_2[0][1] = 'b'
>>> x_2
???             --> ([1,'b',3],[4,5,6])
>>> x_2[0] = (7,8,9)
???            --> Dá erro de atribuição. Não  se pode alterar, por atribuição,  o valor de um tuplo

Pergunta 2
Pretendia-se obter o valor aproximado da função geo(r) igual ao somatório com i a variar de 0 até infinito de 1/(r^i). Valorizava-se a consideração da precisão.
Versão sem precisão (soma de n termos):

def geo(r,n):
    res = 0
    for i in range(n):
        res += 1/pow(r,i)
    return res

Agora uma versão com a precisão a ser definida.

def geo_b(r,prec):
    erro = 1
    res = 0
    n = 0
    while erro > prec:
        aux = res
        res += 1/pow(r,n)
        erro = abs(aux - res)
        n += 1
    return res

Esta solução funciona com base na consideração da diferença de dois valores consecutivos. Para este tipo de séries infinitas isso não causa problema. Podemos mesmo usar outra solução:

def geo_c(r,prec):
    i = 1
    termo = res = 1
    while termo > prec:
        termo = 1/pow(r,i)
        res += termo
        i += 1
    return res

Pergunta 3
Pedia-se para transformar uma imagem a preto e branco, representada por uma lista de listas de uns (preto) e zeros (branco), na sua imagem no espelho, sem destruir a imagem original. Uma pequena reflexão diz-nos que é suficiente inverter a imagem, linha a linha.

def espelho(imagem):
    nova_imagem = []
    for linha in imagem:
        nova_linha = linha[:]
        nova_linha.reverse()
        nova_imagem.append(nova_linha)
    return nova_imagem

Teste #2 - Turma TP1

Pergunta 1

a) Diga o que entende por um objecto ser homogéneo. Indique um tipo de objectos que tem esta característica.
Resposta: quando as componentes do objecto têm quer ser todas do mesmo tipo. Exemplo: cadeias de caracteres.

b) Considere a seguinte listagem. Diga, justificando, o que vai aparecer no lugar dos pontos de interrogação.

>>> x_1 = [(1,2,3),(4,5,6)]
>>> x_1[0] = (7,8,9)
>>> x_1
??? --> [(7,8,9),(4,5,6)]
>>> x_1[0][1] = 'b'
??? --> Dá erro de atribuição. Não  se pode alterar, por atribuição,  o valor de um tuplo

Pergunta 2
Implemente um programa que calcula o valor aproximado da função zeta(s) igual ao somatório quando n varia de 1 a infinito de 1/(n^s). Valorizava-se uma solução que controlasse o erro máximo da solução.

Sem considerar a precisão, a solução baseia-se em somar um certo número de termos:

def zeta(s,k):
    res = 0
    for n in range(1,k+1):
        res += 1/pow(n,s)
    return res

Considerando agora a precisão:

def zeta(s,prec):
    erro = 1
    res = 0
    n = 1
    while erro > prec:
        aux = res
        res += 1/pow(n,s)
        erro = abs(aux - res)
        n += 1
    return res

Pergunta 3
Dadas duas imagens a preto e branco, representadas por uma lista de listas de uns (preto) e zeros (branco), construa uma nova imagem, sem destruir as anteriores, que é preta (um) numa dada posição apenas quando as duas imagens de entrada são ambas pretas nessa posição. A solução mais básica:

def intersecta(img_1, img_2):
    nova_img = []
    for i in range(len(img_1)):
        nova_linha = []
        for j in range(len(img_1[0])):
            if img_1[i][j] == 1 and img_2[i][j] == 1:
                nova_linha.append(1)
            else:
                nova_linha.append(0)
        nova_img.append(nova_linha)
    return nova_img

Uma alternativa que evita o teste dentro dos ciclos:

def intersecta(img_1, img_2):
    nova_img = []
    for i in range(len(img_1)):
        nova_linha = []
        for j in range(len(img_1[0])):
                nova_linha.append(img_1[i][j] * img_2[i][j])
        nova_img.append(nova_linha)
    return nova_img

Em vez do produto também se podia usar um AND lógico. Ainda outra alternativa seria construir uma imagem só com zeros e colocar a um sempre que o produto das outras for igual a um,, ou a soma for igual a 2. Fica para exercício.

Teste # 1 - Especial

Pergunta 2

Uma slot-machine tem três posições, podendo aparecer um de 5 objectos diferentes em cada posição. Pretendia-se uma programa que simulasse uma jogada indicando se se ganhou (todas as posições iguais) ou se se perdeu. Esta pergunta era muito simples, tanto mais que se dava a informação relativamente ao método choice do módulo random. Assim uma solução possível seria:

import random

def slot_machine():
    valores = 'ABCDE'
    res_1 = random.choice(valores)
    res_2 = random.choice(valores)
    res_3 = random.choice(valores)
    if res_1 == res_2 and res_2 == res_3:
        return True
    return False

Notar que os valores possíveis são fixos e o número de posições também (igual a 3). Podemos generalizar para qualquer conjunto de objectos e qualquer número de posições. Vejamos como.

def slot_machine_b(valores,k):
    res = ''
    for i in range(k):
        res += random.choice(valores)
    return all_equal(res)

def all_equal(cadeia):
    conta = cadeia.count(cadeia[0])
    return conta == len(cadeia)

Como se observa passamos a usar um ciclo for com uma variável a fazer de acumulador. Uma variante para este caso:

def slot_machine_c(valores,k):
    ganhar = [''.join(k * [str(elem)]) for elem in valores]
    res = ''
    for i in range(k):
        res += random.choice(valores)
    return res in ganhar

Aqui usamos listas por compreensão para gerar todas as sequências de vitória, o que facilita o teste de tudo igual.

Pergunta 3

Pediam-se dois programas usando o módulo turtle. Um primeiro, que permitia desenhar uma lâmina, parametrizando a sua posição central, o tamanho dos dois braços e a orientação. O segundo, devia usar o primeiro para desenhar diferentes tipos de ventoinhas. Comecemos pelo primeiro.

def lamina(cent_x,cent_y,lado_1,lado_2,angulo, orient):
    # inicialização
    turtle.showturtle()
    turtle.penup()
    turtle.goto(cent_x, cent_y)
    turtle.setheading(orient)
    turtle.pendown()
    turtle.dot(10)
    # lamina superior
    turtle.forward(lado_2//2)
    turtle.lt(angulo)
    turtle.forward(lado_1)
    # recentra
    turtle.penup()
    turtle.goto(cent_x, cent_y)
    turtle.setheading(orient+180)
    turtle.pendown() 
    # lamina inferior
    turtle.forward(lado_2//2)
    turtle.lt(angulo)
    turtle.forward(lado_1)  
    # finaliza
    turtle.hideturtle()

Limita-se a ser … comprido. Mas não é difícil. Os comentários dispensam mais explicações. Procure tornar o código mais sintético, por exemplo, usando um mesmo programa para desenhar as duas partes da lâmina.

Resolvida esta questão, o segundo programa é trivial.

def ventoinha(num, dist, cent_x,cent_y,lado_1,lado_2,angulo, orient):
    # inicialização
    turtle.showturtle()
    turtle.penup()
    turtle.goto(cent_x, cent_y)
    turtle.pendown()
    turtle.dot(10) 
    # desenha num lâminas
    for i in range(num):
        lamina_c(cent_x,cent_y,lado_1,lado_2,angulo, orient)
        orient += dist

Imagens à roda

Todos nos habituámos a brincar com programas que manipulam imagens. Com frequência queremos um programa que roda uma imagem de 90 ou de 180 graus. Vamos ver como podemos resolver o primeiro caso. Depois o segundo é trivial.

Já discutimos como podemos representar uma imagem a preto e branco em Python: uma lista de listas. Para resolver este problema sabemos que temos que percorrer toda a imagem e para cada elemento da imagem saber qual será a sua nova posição. Mas no caso de uma rotação de 90 graus isso é fácil de resolver se olharmos globalmente para a matriz que representa a nossa imagem: a coluna i da matriz vai passar a ser a linha i da nova matriz… Daí a solução seguinte:

def roda_90(imagem):
    """Baseia-se na construção da transposta da imagem vista como uma matriz."""
    imagem_aux = list()
    # troca colunas por linhas = transpõe
    for coluna in range(len(imagem[0])):
        nova_linha = list()
        for linha in imagem:
            nova_linha.append(linha[coluna])
        imagem_aux.append(nova_linha)
    # inverte dentro das linhas
    for linha in range(len(imagem_aux)):
        imagem_aux[linha] = imagem_aux[linha][::-1]
    return imagem_aux

Esta solução numa ideia simples: percorrer por colunas e para cada coluna ir buscar os elementos das diferentes linhas. O modo como fazemos isto obriga-nos no final a inverter todas as linhas. Esta ultima parte não é simpática. Mas podemos mudar as coisas.

def roda_90_b(imagem):
    """Baseia-se na construção da transposta da imagem vista como uma matriz."""
    imagem_aux = list()
    # troca colunas e linhas = transpõe
    for coluna in range(len(imagem[0])):
        nova_linha = list()
        for linha in imagem:
            nova_linha = [linha[coluna]] + nova_linha
        imagem_aux += [nova_linha]
    return imagem_aux

Como se pode ver, em vez de usarmos append, que coloca sempre no final, usamos a operação de concatenação de listas (+), colocando o novo elemento sempre à cabeça, o que permite ter no final a nova linha já invertida.

Como temos vindo a explicar ao longo destes pequenos posts há sempre muitas alternativas. Algumas fazem uso de um conhecimento mais profundo de Python. É o caso da solução que apresentamos a seguir.

def roda_90_c(imagem):
    copia = copy.deepcopy(imagem)
    transposta = list(zip(*copia))
    final = [linha[::-1] for linha in transposta]
    return final

Neste exemplo, usamos um argumento na forma *copia. Isto significa que o objecto copia vai ser desmembrado nos seus elementos e é sobre esses elementos que vai ser aplicada a função zip. Deste modo obtemos a transposta. Depois é só inverter cada linha usando listas por compreensão. Refira-se finalmente que usámos uma cópia profunda da imagem inicial para não a destruir.

Cuidar da imagem...

Durante as aulas vimos como se podia representar uma imagem a preto e branco através de uma lista de listas de 0s e 1s. A questão concreta colocada na aula era a de produzir o negativo de uma imagem, sem destruir a imagem original. O exercício não era difícil. Temos que percorrer toda a imagem e efectuar a alteração dos 0s para 1s e os 1s para 0s. Como a estrutura é 2D vamos precisar de dois ciclos. Como não queremos a destruição da imagem original precisamos construir uma nova. Uma solução que respeite o enunciado é a seguinte:

def negativo(imagem):
    nova_imagem = []
    for linha in imagem:
        nova_linha = []
        for coluna in linha:
            if coluna == 0:
                nova_linha.append(1)
            else:
                nova_linha.append(0)
        nova_imagem.append(nova_linha)
    return nova_imagem

Como se pode ver a imagem é construída a partir de uma imagem vazia. Os dois ciclos são percorridos pelo conteúdo.

Podemos fazer de modo um pouco diferente. Criamos uma cópia da imagem inicial, e alteramos de acordo com o enunciado. Neste caso percorremos os ciclos for pela posição, pois estas são necessárias para a actualização da imagem. A cópia é feita usando o método deepcopy do módulo copy para assegurar que as duas imagens ficam totalmente separadas.

import copy

def negativo(imagem):
    copia = copy.deepcopy(imagem)
    for linha in range(len(imagem)):
        for coluna in range(len(imagem[0])):
            if copia[linha][coluna] == 0:
                copia[linha][coluna] = 1
            else:
                copia[linha][coluna] = 0
    return copia

Estas duas versões parecem esgotar as alternativas. Mas não é bem verdade isso. Podemos evitar o recurso ao teste no interior dos dois ciclos.

def negativo_b(imagem):
    copia = copy.deepcopy(imagem) 
    for linha in range(len(imagem)):
        for coluna in range(len(imagem[0])):
            copia[linha][coluna] = (copia[linha][coluna] + 1) %  2
    return copia

O que fizemos? Usemos o conhecimento de que o resto da divisão de um numero por dois ou é 0 ou é 1. No nosso caso somamos 1 ao conteúdo da matriz. Se for 0, fica 1. Se for 1 passa a 0! E pronto. Agora é que esgotámos as alternativas. Certo? Não, errado! Mais uma variante:

def negativo_c(imagem):
    copia = copy.deepcopy(imagem) 
    for linha in range(len(imagem)):
        for coluna in range(len(imagem[0])):
            copia[linha][coluna] ^= 1
    return copia

Esta solução é semelhante à anterior, são que usamos a operação binária ou exclusivo.