Programação com Python: 2009

quarta-feira, 30 de dezembro de 2009

Duplos... só no cinema!

Consideremos o problema de remover os elementos duplicados de uma sequência. Uma solução trivial será:

def remove_duplos_1(seq):
    """Retira elementos duplicados da sequência."""
    aux = []
    for i,elem in enumerate(seq):
        if elem not in seq[i+1:]:
            aux.append(elem)
    return aux

ou ainda:

def remove_duplos_2(seq):
    """Retira duplicados da sequência."""
    return [elem for i,elem in enumerate(seq) if elem not in seq[i+1:]]

Nestes dois casos a ideia é óbvia: pegar num elemento e ver se há mais à sua frente.

Tal como estão, estas soluções funcionam bem para listas. E se for outro tipo de sequências? Cadeias de caracteres, por exemplo:

def remove_duplos_3(seq):
    """Retira elementos duplicados da sequência."""
    aux = ''
    for i,elem in enumerate(seq):
        if elem not in seq[i+1:]:
            aux = aux + elem
    return aux

Mas se eu souber que existe um tipo de dados set, que implementa conjuntos em Python posso fazer melhor. Por exemplo, no caso das listas:

1.def remove_duplos_4(seq):

2. return list(set(seq))

Os conjuntos são colecções não ordenadas, mutáveis e heterogéneas de (referências para) objectos. Existem vários métodos associados com os objectos do tipo set, por exemplo union, intesection e difference. Para saber mais é só consultar o manual de Python.

Claro que agora é fácil encontrar uma solução que dê para diferentes tipos de objectos:

def remove_duplos_5(seq):
    aux = set(seq)
    if isinstance(seq,str):
        return ''.join(aux)
    elif isinstance(seq,list):
        return list(aux)
    elif isinstance(seq,tuple):
        return tuple(aux)
    else:
        print 'TypeError'
        return seq

E pronto. Acabaram-se os duplos!

O saber remove montanhas

Consideremos o problema simples de retirar todas as ocorrências de um item de uma sequência.

Podemos começar com uma solução simples:

def remove_1(item,seq):
    """Retira todas as ocorrências do item da sequência."""
    aux = []
    for elem in seq:
        if elem != item:
            aux.append(elem)
    return aux

Mas que só funciona para listas e tuplos. E, neste último caso, transforma o tuplo numa lista. Claro que se apenas tivermos que manipular listas ainda podemos optar pela solução que usa listas por compreensão:

def remove_2(item,seq):
    """Seq é uma lista."""
    return [elem for elem in seq if elem != item]

Então e se for um cadeia de caracteres? Podemos usar a função pré-definida replace:

def remove_3(item, seq):
    """se for uma cadeia de caracteres."""
    return seq.replace(item,'')

Mas podemos juntar tudo num único programa? Claro que sim! Só precisamos de fazer um teste ao tipo do objecto, e para isso usamos o comando isinstance.

def remove_4(item, seq):
    """Lista ou tuplo ou cadeia de caracteres."""
    if isinstance(seq,str):
        return seq.replace(item,'')
    elif isinstance(seq,list):
        return [elem for elem in seq if elem != item]
    elif isinstance(seq,tuple):
        return tuple([elem for elem in seq if elem != item])
    else:
        print 'TypeError'
        return seq

E pronto, já está!

terça-feira, 29 de dezembro de 2009

Errar é humano...

Um aluno de IPRP estava com dificuldades num problema que saiu no exame de 2006 e pediu-me ajuda. O problema era o seguinte:

Suponha que tem uma cadeia de caracteres com um dado comprimento e a pretende dividir em n partes iguais. Implemente em Python o respectivo programa não se esquecendo de prever o caso de o comprimento da cadeia não ser múltiplo de n.

Enviou-me a sua tentativa de solução que não funcionava:

def divide(f, p):
    aux=[]
    a=len(f)
    lpp=(len(f)-1)/p
    dif=0
    x=lpp
    faux=''
    n=0
    while(n < p):
        faux=f[dif:lpp+1]
        aux.append(faux)
        dif=(dif+lpp)+1
        lpp=(lpp+x)        
        n=n+1
    return aux

Qual é a lógica desta solução? Bem andar a partir a frase em pedaços todos do mesmo comprimento. Calcula-se esse comprimento na linha 4. Usam-se duas marcas (dif e lpp) para determinar os limites de cada pedaço, que vão sendo guardados em aux, a capa passagem pelo ciclo while. A ideia faz sentido.

Vamos ver alguns dos seus problemas. Começo pelo código inútil:

a = len(f), não está lá a fazer nada, nunca sendo usado.
faux = '' : esta inicialização não é preciso para nada

Agora os erros:

lpp = (len(f) - 1) / p: não se deve retirar um ao comprimento, dado o modo como a divisão funciona.
faux[f[dif:lpp+1]: errado devido à soma de 1.
dif = dif + lpp +1: aqui talvez o erro maior! Em cada etapa dif deve avançar para o valor de lpp.

Posto tudo isto uma solução usando esta ideia seria (notem que uso x no lugar de lpp, por uma questão de clareza):

def divide_corrigido(f, p):
   aux=[]
   lpp=len(f)/p
   dif=0
   x = lpp
   n=0
   while(n < p):
       faux=f[dif:x]
       aux.append(faux)
       dif=x
       x = x + lpp
       n=n+1
   aux.append(f[dif:])
   return aux

Mas não estou satisfeito, pois podemos encontrar uma solução mais elegante, tendo por base o mesmo princípio: duas marcas que vão avançando a cada passagem pelo ciclo. Mas para tal podemos usar uma combinação de um ciclo for com a operação range:

def divide_ec(frase,n):
   """divide a frase em n pedaços iguais."""
   # número de caracteres em cada parte
   num_car = len(frase)/n
   # calcula e guarda em aux
   aux = []
   for i in range(0,len(frase),num_car):
       aux.append(frase[i:i+num_car])
   return aux

O trabalho de fazer avançar a marca correctamente é assegurado pelo modo de funcionar do range comn três argumentos. Concordarão que este programa é mais claro do que o proposto! E prevê o caso de a frase ter um comprimento que não é múltiplo de n!

Se gostarem de listas por compreensão podem ainda prescindir de aux.:

def divide_ec_2(frase,n):
   num_car = len(frase)/n
   return [frase[i:i+num_car] for i in range(0,len(frase),num_car)]

Mas voltemos ao enunciado, que nos fala em n partes iguais. Se corrermos o programa, verificamos que nos casos em que não é múltiplo existem n+1 partes! Como corrigir este aspecto? Uma solução será esticar a cadeia e passar a ter cadeias todas do mesmo tamanho, menos a última. Esta era, aliás, a interpretação correcta do enunciado...

def divide_ec_3(frase,n):
 """divide uma sequência frase em n partes.
 A última pode ser menor."""
 parte=(len(frase) + n - 1)/n
 aux = []
 for i in range(0,n):
  aux.append(frase[parte*i:parte*(i+1)])
 return aux

E até nos podemos dar ao luxo de ter uma solução recursiva!!

def divide_ec_4(frase,n):
 if n == 0:
  return []
 else: 
  return [frase[:len(frase)/n]] + divide_ec_4(frase[len(frase)/n:],n-1) 

E assim terminamos este exercício. aprendemos muito com os nossos erros ... e com os erros dos outros!!

quinta-feira, 24 de dezembro de 2009

Mini Teste # 3

Apresentamos de seguida um esboço da solução do Mini Teste #3.

Boas Festas!!

3.1

Parâmetros formais são os nomes dados aos argumentos das definições. Por exemplo, em:

1.def teste(x,y):

2. return x + y

x e y são os parâmetros formais. Durante a chamada (uso) de uma definição esses nomes recebem a identidade dos objectos associados aos parâmetros reais.

3.2

O módulo random foi importado de dois modos distintos. No primeiro caso, o acesso ao conteúdo do módulo, por exemplo para usar um dos seus métodos, obriga a usar o nome do módulo como prefixo, como se pode ver na linha 2. No segundo caso, é feita apenas uma imprtação selectiva, sendo apenas importados alguns elementos do módulo, no exemplo da linha 4 apenas se importa o método choice. Nesta situação usamos directamente o nome do método sem o prefixar com o nome do módulo. Nas linhas 7 a 11 a diferença entre os dois métodos aparece na forma de erro pois tentámos usar um método, randint, que não tinha sido importado directamente, sem o prefixar com o nome do módulo.

3.3

O programa cria uma matriz identidade, isto é uma matriz em que todos os elementos são zero, menos os elementos na diagonal principal que são um.

3.4

def posicoes(texto):
    vogais ='aeiouAEIOU'
    dic_pos = {}
    for i,letra in enumerate(texto):
        if letra in vogais:
            dic_pos[letra] = dic_pos.get(letra,[]) + [i]
    return dic_pos

3.5

def cota(fich):
    f_in = open(fich,'r')
    # ler cabeçalho
    linha = f_in.readline()
    dados = []
    # percorre ficheiro linha a linha
    linha = f_in.readline()
    while linha != '': # EOF?
        linha = linha[:-1].split(',')
        dados.append(float(linha[4]) - float(linha[1]))
        linha = f_in.readline()
    dados.sort()
    print 'Melhor: ', dados[-1]
    print 'Pior: ', dados[0]
    f_in.close()

domingo, 20 de dezembro de 2009

Problema 10.6

O ordenamento por selecção tem uma lógica muito simples: admitindo que uma parte do vector já está definitivamente ordenada concentra-mo-nos na outra parte. Escolhemos o maior elemento (ou o menor se for por ordem decrescente) da parte ainda desordenada e coloca-mo-lo na sua posição definitiva. este processo é repetido tantas vezes quantas a dimensão do vector menos um.

def selec_dir(seq):
 """Ordenamento por selecção directa"""
 copia=seq[:]
 for cont in range(len(seq)-1,0,-1):
  indice=copia.index(max(copia[:cont+1]))
  copia[cont],copia[indice]=copia[indice],copia[cont]
 return copia

Nesta implementação o ordenamento é por ordem crescente. Veja-me como usamos a operação de range!

Problema 10.5

Porque analisamos o vector em toda a sua dimensão se a partir de um certo índice não houve mais trocas? Não precisamos, pois não haver trocas significa: vector ordenado daí para a frente! O algoritmo apresetnado resolve essa questão.

def bubblesort_3(seq):
 """Ordenamento por bolhas.
 Apenas ordena o subvector esquerdo onde houve trocas!
 """
 copia = seq[:]
 indice= len(seq)-1
 while indice > 0:
  cont = indice - 1
  indice = 0
  for i in range(cont+1):
   if copia[i] > copia[i+1]:
    copia[i],copia[i+1] = copia[i+1],copia[i]
    indice=i
 return copia

Problema 10.4

Vamos melhorar o algoritmo de ordenamento por bolhas (bubble sort) evitandio que ele continue a efectuar comparações quando o vector já está ordenado. Como sabemos que o vector está ordenado? Simples: quando percorremos o vector sem haver trocas entre elementos!

def bubblesort_2(seq):
 """Ordenamento por bolhas.
 Pára mal fica ordenado = não há mais trocas!
 """
 copia = seq[:]
 cont= len(seq)-1
 troca = True
 while troca:
  cont = cont -1
  troca=False
  for i in range(cont+1):
   if copia[i] > copia[i+1]:
    copia[i],copia[i+1] = copia[i+1],copia[i]
    troca=True
 return copia

Então o que fizemos? Passamos a ter um ciclo condicional (while) controlado por uma variávewl booleana, que indica se houve ou não trocas na etapa anterior. Como temos que percorrer pelo menos uma vez o vector, inicializamos a variável booleana de controlo a True. No interior do ciclo começamos por assumir que não houve trocas. Percorremos o vector. Caso não haja nenhuma troca, ele mantém-se com o valor False e saímos do ciclo. Caso contrário, passa a verdadeira e retomamos o ciclo no seu início.

Problema 10.2

A dificuldade desta questão residia apenas na compreensão de que é possível passar uma função como argumento. Em Python, tudo são objectos e, por isso, as funções também são objectos, caracterizadas por identidade, valor e tipo. Por outro lado, o que se comunica a uma definição aquando da sua chamada ou é um objecto ou uma referência para um objecto. Na listagem abaixo ilustramos alguns destes aspectos.

>>> def maior(x,y):
... return  x > y
>>> maior(5,6)
False
>>> maior(6,5)
True
>>> type(maior)
<type 'function'="">
>>> id(maior)
13432752
>>> maior
<function maior at 0xccf7b0>
>>> menor = maior
>>> menor(6,5)
True
>>> 
</type>

Regressando ao nosso problema. O desafio é evitar duplicar o código, transmitindo na chamada a referência para a operação de comparação.

def insertion_both(seq, metodo):
 """ Como um jogador de cartas"""
 copia=seq[:] 
 for cont in range(1,len(seq)):
  elem=copia[cont]
  indice=cont - 1
  while (metodo(elem,copia[indice])) and (indice >= 0):
   copia[indice + 1] = copia[indice]
   indice = indice - 1
  copia[indice + 1] = elem
 return copia
 
def maior(x,y):
 return (x > y)
 
def menor(x,y):
 return (x < y)

E assim se resolve de forma simples e elegante, um problema aparentemente difícil! Deixo ao leitor o cuidado de perceber porque é que foi preciso criar as funções maior e menor que apenas fazem o que > e < fazem!

segunda-feira, 14 de dezembro de 2009

Problema 9.10

A questão dos agrupamentos vazios obriga a algum trabalho de alteração do código. Mas o que importa mais é definir a estratégia para lidar com esses agrupamentos. Uma solução simples seria deixar que existam.Mas não é isso que queremos! Então o que fazer? Bom, uma solução razoável será escolher o pior elemento de todo o conjunto de pontos. E qual é o pior? Começamos por calcular o pior dentro de cada agrupamento: o ponto mais distante ao respectivo centróide. De entre estes pontos vamos optar, uma vez mais, pelo mais distante. Esse elemento é retirado do seu agrupamento e é colocado no agrupamento vazio, passando a ser o seu centróide.

No código abaixo é fácil identificar as novas operações e a parte do código que foi alterada.

import math
import random
import cTurtle
import operator
 
def dist_euclidiana(p1,p2):
    return math.sqrt(sum([(p[1] - p[0])**2 for p in zip(p1,p2)]))
 
def centroide(pontos):
    """
    Calcula o centróide de um conjunto de pontos n-dimensionais.
    Entrada = uma lista de pontos.
    Assume a existência de pelo menos um ponto!!
    """
    cent = [sum(ponto)/len(ponto) for ponto in zip(*pontos)]
    return tuple(cent)
 
def cria_dicio_dados(ficheiro):
    """
    Lê as coordenadas dos pontos a partir de um ficheiro.
    Incorpora num dicionário.
    """
    f_in = open(ficheiro,'r')
    dicio_dados = dict()
     
    chave = 0
    linha = f_in.readline()
    while linha != '': # EOF?
        chave = chave + 1
        tuplo = tuple([int(valor) for valor in linha[:-1].split()])
        dicio_dados[chave] = tuplo
        linha = f_in.readline()
    return dicio_dados
 
# por localização
def cria_dicio_dados_terramoto(ficheiro):
    """
    Extrai os dados do ficheiro e constrói o dicionário.
    """
    f_in = open(ficheiro,'r')
    dicio_dados = dict()
     
    chave = 0
    linha = f_in.readline()
    while linha != '': # EOF?
        chave = chave + 1
        latitude = float(linha[:-1].split()[3])
        longitude = float(linha[:-1].split()[4])
        dicio_dados[chave] = (longitude,latitude)
        linha = f_in.readline()
    return dicio_dados
 
def cria_centroides(k,dicio_dados):
    """ 
    Devolve uma lista com k pontos distintos como centróides.
    Apenas com intensidade...
    """
    centroides = []
    conta_centroides = 0
    chaves_centroides = []
    while conta_centroides < k:
        chave_alea = random.randint(1,len(dicio_dados))
        if chave_alea not in chaves_centroides:
            centroides.append(dicio_dados[chave_alea])
            chaves_centroides.append(chave_alea)
            conta_centroides = conta_centroides + 1
    return centroides
 
#-- alterado por causa dos vazios
def cria_agrupamentos(k,centroides,dicio_dados,repete):
    """
    k = número de agrupamentos
    centroides = lista de centroides inicial
    dicio_dados = os dados organizados num dicionário {1:(...), 2: (...),...}
    repete = número de passagens
    Os dados podem ser n-dimensionais. Cada ponto é um tuplo.
    """
    for passo in range(repete):
        print "----- Passagem:\t {0}\t-----".format(passo)
        # cria contentor para os agrupamentos
        agrupamentos = []
        for conta in range(k):
            agrupamentos.append([])
             
        # Determina agrupamento para cada dado
        for chave in dicio_dados:
            distancias = []
            for indice_agrupamento in range(k):
                dist = dist_euclidiana(dicio_dados[chave],centroides[indice_agrupamento])
                distancias.append(dist)
            menor = min(distancias)
            indice = distancias.index(menor)
             
            agrupamentos[indice].append(chave)
 
        # Actualiza centróides
        for indice in range(k):
            agrupa = [dicio_dados[chave] for chave in agrupamentos[indice]]
            centroides[indice] = centroide(agrupa)
             
        # agrupamentos vazios: o elemento de um agrupamento não vazio de
        # maior distância é movido
        if agrupamento_vazio(agrupamentos):
            agrupamentos = consolida_agrupamentos(centroides,agrupamentos,dicio_dados)
         
        # mostra resultado
        mostra_agrupamentos(agrupamentos,dicio_dados)
         
    return agrupamentos
 
def mostra_agrupamentos(agrupamentos,dicio_dados):
    """
    Mostra os agrupamentos.
    """
    for indice,agrupamento in enumerate(agrupamentos):
        print "AGRUPAMENTO %d: " % (indice + 1)
        for chave in agrupamento:
            print dicio_dados[chave],
        print
 
def agrupamento_vazio(agrupa):
    """ Algum agrupamento vazio."""
    return any([len(elem) == 0 for elem in agrupa])
 
def indices_agrupa_vazios(agrupa):
    """ lista de índices dos agrupamentos vazios."""
    return [indice for indice in range(len(agrupa)) if len(agrupa[indice]) == 0]
 
def indice_max_dist(centroides, agrupamentos, dicio_dados):
    """ Determina o agrupamento e o índice do elemento mais distante do centroide
    considerando todos os agrupamentos.
    """
    max_dist = []
    for indice,agrupa in enumerate(agrupamentos):
        if len(agrupa) > 0:
            lista_dist = []
            for elemento in agrupa:
                lista_dist.append((elemento,dist_euclidiana(centroides[indice], dicio_dados[elemento])))
            lista_dist.sort(key=operator.itemgetter(1), reverse = True)
            maior = (indice,lista_dist[0][0])
            max_dist.append(maior)
    max_dist.sort(key=operator.itemgetter(1),reverse=True)
    return max_dist[0] # -- (indice agrupamento, indice elemento)
             
         
 
def consolida_agrupamentos(centroides, agrupamentos,dicio_dados):
    """ Devolve agrupamentos sem elementos vazios."""
    indice_vazios = indices_agrupa_vazios(agrupamentos)
 
    while indice_vazios:
 
        # qual o elemento à distância máxima do seu centróide?
        # qual o máximo dos máximos?
        maximo = indice_max_dist(centroides,agrupamentos,dicio_dados)
        # coloca o máximo dos máximos num agrupamento vazio
        agrupamentos[indice_vazios[0]].append(maximo[1])
        # retira do agrupamento origem
        agrupamentos[maximo[0]].remove(maximo[1])
        indice_vazios = indice_vazios[1:]
    return agrupamentos
     
 
def main(ficheiro,numero_grupos):
    """
    Faz a análise de agrupamentos segundo K-médias.
    """
    dicio_dados = cria_dicio_dados(ficheiro)
    centroides = cria_centroides(numero_grupos, dicio_dados)
    agrupamentos = cria_agrupamentos(numero_grupos,centroides, dicio_dados,3)

Problema 9.8

Este problema apenas acrescenta a necessidade de visualizar os dados. Para isso vamos usar o módulo cTurtle. O código é o seguinte:

def visualiza_terramotos(ficheiro, num_agrupa):
    dicio_dados = cria_dicio_dados_terramoto(ficheiro)
    centroides_terramoto = cria_centroides(num_agrupa,dicio_dados)
    agrupamentos = cria_agrupamentos(num_agrupa,centroides_terramoto,dicio_dados,10)
     
    # prepara o cenário ...
    tartaruga = cTurtle.Turtle()
    tartaruga.bgpic('/tempo/imagens/worldmap.gif')
    tartaruga.screensize(448,266)
    tartaruga.setWorldCoordinates(-180,-90, 180,90)
    tartaruga.hideturtle()
    tartaruga.up()
     
    # cores aleatorias
    tartaruga.colormode(255)
    lista_cores = []
    while len(lista_cores) < num_agrupa:
        r = random.randint(0,255)
        g = random.randint(0,255)
        b = random.randint(0,255)
        cor = (r,g,b)
        minimo = dist_euclid_lista(cor, lista_cores)
        if (cor not in lista_cores) and (minimo > 255):
            lista_cores.append(cor)
  
    # mostra os dados
    for indice_agrupa in range(num_agrupa):
        tartaruga.color(lista_cores[indice_agrupa])
        for chave in agrupamentos[indice_agrupa]:
            longitude = dicio_dados[chave][0]
            latitude = dicio_dados[chave][1]
            tartaruga.goto(longitude,latitude)
            tartaruga.dot()
    tartaruga.exitOnClick()

Começamos por obter os agrupamentos com os programas já desenvolvidos anteriormente (linhas 3 a 5 ). Criamos de seguida o objecto tartaruga (linha 8), colocamos em background a imagem (linha 9), e ajustamos o tamanho da janela ao tamanho real da imagem (linha 10). Redefinimos as coordenadas do mundo para ficarem iguais aos do problema (linha 11, latitude entre -90 e 90 e longitude entre -180 e 180), escondemos (linha 12) e levantamos a tartaruga (linha 13). Escolhemos aleatoriamente as cores dos pontos com que vamos marcar o mapa (linhas 15 a 25), mas garantido que são suficientemente distintas (linhas 23 a 25). Depois é só mostrar os pontos (linhas 27 a 34), e abandonar no final (linha 35)!
A figura abaixo mostra um exemplo resultado da execução do programa com os dados do tremor de terra e para 4 agrupamentos.

Problema 9.6

Para este problema só temos que definir qual é a informação relevante. Se queremos fazer o agrupamento por posição, temos que ir ao ficheiro de dados obter a latitude e a longitude da ocorrência do terramoto.
O ficheiro tem uma organização como se ilustra:

2.8 2006/10/19 02:02:10 62.391 -149.751 15.0 CENTRAL ALASKA

2.5 2006/10/19 00:31:15 20.119 -156.213 1.5 MAUI REGION, HAWAII

5.0 2006/10/18 21:15:51 4.823 -82.592 37.3 SOUTH OF PANAMA

2.6 2006/10/18 21:12:25 59.934 -147.904 30.0 GULF OF ALASKA

3.4 2006/10/18 20:59:21 36.540 -89.640 7.7 SOUTHEASTERN MISSOURI

2.7 2006/10/18 20:11:22 61.023 -151.418 60.0 SOUTHERN ALASKA

A latitude é o quarto elemento e a longitude o quinto (não se esqueça que as sequências em Python começam em zero). Daí o código:

def cria_dicio_dados_terramoto(ficheiro):
    """
    Extrai os dados do ficheiro e constrói o dicionário.
    """
    f_in = open(ficheiro,'r')
    dicio_dados = dict()
     
    chave = 0
    linha = f_in.readline()
    while linha != '': # EOF?
        chave = chave + 1
        latitude = float(linha[:-1].split()[3])
        longitude = float(linha[:-1].split()[4])
        dicio_dados[chave] = (longitude,latitude)
        linha = f_in.readline()
    f_in.close()
    return dicio_dados

É semelhante ao anterior dado para as notas, dispensado por isso mais comentários.

domingo, 13 de dezembro de 2009

k-Médias

O algoritmo k-médias é um algoritmo de agrupamento conceptual. De um modo simples, dado um conjunto de objectos, descritos por atributos, como os dividir em k grupos por forma que os objectos de um dado grupo são maximanente semelhantes entre si e minimamente semelhantes em relação aos objectos dos outros grupos.

Computacionalmente, o algoritmo K-Médias desdobra-se nos seguintes passos:

(1) Escolhe o número, K, de agrupamentos
(2) Escolhe, de modo aleatório, K pontos para servirem de centróides iniciais de cada um dos K agrupamentos
(3) Repetir os seguintes passos:

--> (3a) Afectar cada ponto ao agrupamento de cujo centróide se encontrar mais perto

-->(3b) Recalcular os centróides

(4) Mostrar os K agrupamentos

Posto isto, o código:

import math
import random
import cTurtle
 
def dist_euclidiana(p1,p2):
    """
    Distância euclidiana entre dois pontos. Os pontos são tuplos n-dimensionais.
    """
    soma =0
    for i in range(len(p1)):
        soma = soma + (p2[i] - p1[i])**2
    distancia = math.sqrt(soma)
    return distancia
     
def centroide(pontos):
    """
    Calcula o centróide de um conjunto de pontos n-dimensionais.
    Entrada = uma lista de pontos. Saida = tuplo
    Assume a existência de pelo menos um ponto!!
    """
    cent = [sum(ponto)/len(ponto) for ponto in zip(*pontos)]
    return tuple(cent)
 
def cria_dicio_dados(ficheiro):
    """
    Lê as coordenadas dos pontos a partir de um ficheiro.
    Incorpora num dicionário.
    """
    f_in = open(ficheiro,'r')
    dicio_dados = dict()
     
    chave = 0
    linha = f_in.readline()
    while linha != '': # EOF?
        chave = chave + 1
        tuplo = tuple([int(valor) for valor in linha[:-1].split()])
        dicio_dados[chave] = tuplo
        linha = f_in.readline()
    f_in.close()
    return dicio_dados
 
def cria_centroides(k,dicio_dados):
    """ 
    Devolve uma lista com k pontos distintos como centróides.
    """
    centroides = []
    chaves_centroides = []
    for i in range(k):
        chave_alea = random.randint(1,len(dicio_dados))
        while chave_alea  in chaves_centroides:
            chave_alea = random.randint(1,len(dicio_dados))
        centroides.append(dicio_dados[chave_alea])
        chaves_centroides.append(chave_alea)
    return centroides
 
def cria_agrupamentos(k,centroides,dicio_dados,repete):
    """
    k = número de agrupamentos
    centroides = lista de centroides inicial
    dicio_dados = os dados organizados num dicionário {1:(...), 2: (...),...}
    repete = número de passagens
    Os dados podem ser n-dimensionais. Cada ponto é um tuplo.
    """
    for passo in range(repete):
        print "----- Passagem:\t {0}\t-----".format(passo)
        # Cria contentor para os agrupamentos
        agrupamentos = []
        for conta in range(k):
            agrupamentos.append([])
             
        # Determina agrupamento para cada dado
        for chave in dicio_dados:
            distancias = []
            for indice_agrupamento in range(k):
                dist = dist_euclidiana(dicio_dados[chave],centroides[indice_agrupamento])
                distancias.append(dist)
            menor = min(distancias)
            indice = distancias.index(menor)
             
            agrupamentos[indice].append(chave)
 
        # Actualiza centróides
        for indice in range(k):
            agrupa = [dicio_dados[chave] for chave in agrupamentos[indice]]
            centroides[indice] = centroide(agrupa)
        # Mostra resultado
        mostra_agrupamentos(agrupamentos,dicio_dados)
         
    return agrupamentos
 
def mostra_agrupamentos(agrupamentos,dicio_dados):
    """
    Mostra os agrupamentos.
    """
    for indice,agrupamento in enumerate(agrupamentos):
        print "AGRUPAMENTO %d: " % (indice + 1)
        for chave in agrupamento:
            print dicio_dados[chave],
        print
 
def main(ficheiro,numero_grupos):
    """
    Faz a análise de agrupamentos segundo K-médias.
    """
    dicio_dados = cria_dicio_dados(ficheiro)
    centroides = cria_centroides(numero_grupos, dicio_dados)
    agrupamentos = cria_agrupamentos(numero_grupos,centroides, dicio_dados,3)
 
 
if __name__ =='__main__':
    main('/tempo/data/notasmt1.txt',5) # no seu caso o local do ficheiro pode ser diferente!!!

O leitor deve estar atento à representação dos objectos! Em particular:

(a) os agrupamentos são guardados numa lista, sendo que cada agrupamento é descrito pela lista das chaves dos objectos;

(b) os centróides são guardados numa lista e descritos pelos atributos dos objectos;

(c) os objectos estão guardados num dicionário, sendo a chaves inteiros e os valores os atributos do objecto.
(d) durante a computação é usada uma lista com as distâncias de um objecto a cada um dos centróides.

Problema 9.3

Este problema envolve a criação da lista de centróides a partir do número de agrupamentos pretendidos, e do dicionário de dados. Este dicionário está organizado de modo que cada chave é um inteiro e o valor o tuplo com as coordenadas do ponto. Os membros da lista devem ser escolhidos aleatoriamente e não pode haver repetições.
Uma solução simplista será:

import random
 
def cria_centroides(k,dicio_dados):
    “”” Devolve lista de k centroides escolhidos aleatoriamente.”””
   centroides = []
   chaves_centroides = []
   conta_centroides = 0
   while centroides < k:
      chave_alea = random.randint(1,len(dicio_dados))
      if chave_alea not in chaves_centroides:
         centroides.append(dicio_dados[chave_alea])
         chaves_centroides.append(chave_alea)
         conta_centroides = conta_centroides + 1
    return centroides

Existem variantes. Apresentamos uma, que se nos afigura mais elegante.

import random
 
def cria_centroides_b(k,dicio_dados):
    “”” Devolve lista de k centroides escolhidos aleatoriamente.”””
   centroides = []
   chaves_centroides = []
   for i in range(k):
      chave_alea = random.randint(1,len(dicio_dados))
      while chave_alea in chaves_centroides:
         chave_alea = random.randint(1,len(dicio_dados))
       centroides.append(dicio_dados[chave_alea])
       chaves_centroides.append(chave_alea)
    return centroides

Veja-se como o ciclo for trata do problema da contagem e como asseguramos a não repetição com um ciclo while no interior do ciclo for.

sábado, 12 de dezembro de 2009

Problema 9.2

Face à explicação dada para o problema 9.1, apresentamos sem mais uma solução para esta questão. Veja-se como resolvemos a questão de passar de uma lista para um conjunto de pontos: basta usar o operador * no parâmetro formal, e voltar a usar em zip. No primeiro caso empacotamos todos os pontos num tuplo; no segundo caso, desempacotamos esses mesmos pontos para poderem ser usados pelo zip!

def centroide_b(*pontos):
    """
    Calcula o centróide de um conjunto de pontos n-dimensionais.
    entrada = número variável de pontos.
    Assume a existência de pelo menos um ponto!!
    """
    cent = [sum(ponto)/len(ponto) for ponto in zip(*pontos)]
    return tuple(cent)

Problema 9.1

Em post anterior falei de listas por compreensão. Vejamos como elas nos ajudam a resolver esta questão. Recordo: trata-se de calcular o centróide de uma lista de pontos n-dimensionais.

def centroide_a(pontos):
    """
    Calcula o centróide de um conjunto de pontos n-dimensionais.
    Entrada = uma lista de pontos.
    Assume a existência de pelo menos um ponto!!
    """
    cent = [sum(ponto)/len(ponto) for ponto in zip(*pontos)]
    return tuple(cent)

Como fizemos? Precisamos somar por componente (coordenada) o valor, nessa componente, de cada ponto. Depois basta dividir pelo número de pontos. Que representação estamos a usar? Uma lista de tuplos. Por exemplo, para o caso a 3 dimensões podíamos ter algo como:

1.[(x1,y1,z1), (x2,y2,z2), (x3,y3,z3), (x4,y4,z4)]

Para a componente x, por exemplo, teríamos que fazer (x1 + x2 + x3 + x4)/4). Mas como passar da lista de pontos para uma lista em que temos as componentes de cada ponto juntas? Usamos a operação pré-definida zip. Com um detalhe: no argumento colocamos à cabeça o operador *, para que se possa operar correctamente. A diferença entre usar, ou não, * é ilustrada no exemplo seguinte:

>>> ll = [(1,2,3), (4,5,6)]
>>> zip(ll)
[((1, 2, 3),), ((4, 5, 6),)]
>>> zip(*ll)
[(1, 4), (2, 5), (3, 6)]
>>> 

Repare-se que ao usar listas por compreensão, o nosso resultado é uma lista. Por isso na instrução return temos que forçar a passagem a tuplo.

Listas por Compreensão

Em Python existe uma construção que ajuda a tornar os programas mais curtos sem perda de legibilidade. Trata-se das listas por compreensão.

Suponhamos que temos uma lista de listas e que queremos formar uma nova lista, contendo o último elemento de cada uma das listas que fazem parte da lista inicial. Um modo de resolver seria:

def ultimos(arg):
    """ lista dos últimos..."""
    ult = []
    for lista in arg:
        ult.append(lista[-1])
    return ult

Percorremos a lista elemento a elemento. De cada um deles obtemos o seu último elemento e acrescentamos a um contentor (outra lista) que antes do ciclo criámos como lista vazia.

Usando agora listas por compreensão para resolver o mesmo problema:

def ultimos_comp(arg):
    """ Lista dos últimos."""
    return [ lista[-1] for lista in arg]

A sintaxe da formulação mais simples das listas por compreensão é a seguinte:

1.[ elemento for elemento in objecto]

Mas suponhamos, por exemplo, que no exemplo anterior apenas queremos os últimos elementos, caso sejam ímpares? Como fazer? Acrescenta-se um if!

def ultimos_comp_impares(arg):
    """ Lista dos últimos."""
    return [ lista[-1] for lista in arg if (lista[-1] % 2) == 1]

Admitamos que a nossa lista de listas representa uma imagem. Cada um dos seus elementos é um tuplo com três elementos entre 0 e 255. Como podemos obter a passagem da imagem para uma outra em que apenas mantemos o valor do canal vermelho e os outros dois ficam a 0? Usamos dois ciclos for!

def escala_cinzentos(imagem):
    """ Converte um imagem para a escala de cinzentos."""
    return [ [ (coluna[0],0,0 ) for coluna in linha]  for linha in imagem]

Notar que manter a estrutura da matriz, o ciclo mais à esquerda está envolto entre [ e ].

Como se pode ver é possível fazer muitas coisas com listas por compreensão. sempre que tiver uma oportunidade, use-as!

quinta-feira, 10 de dezembro de 2009

Matrizes, ciclos imbricados e impressões

Todos estamos habituados a lidar com informação cujo acesso se faz por indicação das suas coordenadas num espaço a n dimensões. Por exemplo, quando lidados com imagens, cada pixel é referenciado dessa forma, por duas coordenadas. Os matemáticos arranjaram um modo de organizar essa informação através de matrizes. Os cálculos complexos que temos que fazer com matrizes podem ser facilmente passados para o computador. Como aqui já referimos, a linguagem Python tem módulos que permitem lidar com matrizes (Scipy, por exemplo). Mas vamos supor que tal não existe. Um modo natural de representar uma matriz seria por recurso a uma lista de listas. Cada lista interior representa uma linha da matriz. Por exemplo:

1.matriz = [[1,2,3],[4,5,6],[7,8,9]]

Vamos ver como podemos visualizar os elementos de uma matriz quadrada qualquer. A questão essencial que temos que ter em conta é que, havendo duas dimensões, temos que criar dois ciclos, um dentro do outro,em que cada um deles responsável por percorrer de modo ordenado cada uma das dimensões. Vejamos o caso mais simples, ou seja, mostrar todos os elementos.

def mostra_por_linhas(matriz):
 “””Indexação pelo conteúdo.”””
 for linha in matriz:
  for coluna in linha:
   print “%3d” % coluna,
  print
 
 
def mostra_por_linhas(matriz):
 “””Indexação pela posição.”””
 for pos_linha in range(len(matriz)):
  for pos_coluna in range(len(matriz[0])):
   print “%3d” % matriz[pos_linha][pos_coluna],
  print

O que têm estes dois programas de diferente? O simples facto de, no primeiro, percorremos a matriz usando o seu conteúdo, enquanto que, no segundo, usamos as posições. E de comum, que pontos devem ser salientados??? Essencialmente o modo como fazemos a impressão: o comando print usa uma marca de formatação (%3d) e termina com uma vírgula. É este último facto que permite colocar os elementos de uma linha todos ao lado uns dos outros. O segundo print sem argumento serve apenas para mudar de linha.

Admitamos agora que queremos mostrar a matriz por colunas e não por linhas.

def mostra_por_colunas(matriz):
    """ AKO transposta. Indexação pelo conteúdo."""
    for pos_coluna in range(len(matriz[0])):
        for pos_linha in range(len(matriz)):
            print "%3d" % matriz[pos_linha][pos_coluna],
        print

Bastou trocar a ordem: o primeiro ciclo trata das colunas, enquanto o segundo ciclo (mais interior) as linhas!

E se forem as matrizes triangulares superior e inferior??

def mostra_tri_sup(matriz):
    """Matriz triangular superior.Indexação pela posição."""
    for pos_linha in range(len(matriz)):
        print ' '* 3 * pos_linha, # 3 por causa do %2d
        for pos_coluna in range(pos_linha,len(matriz[0])):
            print "%2d" % matriz[pos_linha][pos_coluna],
        print
 
def mostra_tri_inf(matriz):
    """Matriz triangular superior.Indexação pela posição."""
    for pos_linha in range(len(matriz)):
        for pos_coluna in range(0,pos_linha+1):
            print "%2d" % matriz[pos_linha][pos_coluna],
        print

Atente-se como tratamos de mostrar de modo conveniente. uma vez mais o comando print é essencial para esse objectivo. Terminamos com a matriz diagonal.

def mostra_diag_principal(matriz):
    """ Mostra diagonal principal."""
    for pos_linha in range(len(matriz)):
        print ' '* 3 * pos_linha,
        for pos_coluna in range(0,pos_linha+1):
            if pos_linha == pos_coluna:
                print "%2d" % matriz[pos_linha][pos_coluna]

Deixamos ao leitor a tarefa de testar estes programas. Fica também como exercício resolver o problema não de visualizar mas de criar.

segunda-feira, 7 de dezembro de 2009

Problema 8.13

Para animar o nosso programa uma possibilidade simples é usar o módulo cTurtle. Vamos definir o nosso boneco de acordo com as coordenadas dadas na figura.

O boneco estará separado em 6 partes: cabeça, tronco, braços e pernas. Isto coloca um limite de 6 tentativas falhadas. Claro que podemos alterar. Por exemplo, é preciso falhar 2 vezes seguidas para mais uma parte do corpo ficar pendurada. De qualquer maneira o que temos que introduzir no nosso código é uma chamada à operação de desenho cada vez que falhamos. Se é a nossa i tentativa falhada, então desenhamos a parte i do corpo. Eis o código.

import cTurtle
 
def desenha_enforcado(i):
    cTurtle.up()
    if(i==0):
        cTurtle.goto(60,-90)
        cTurtle.setheading(180)
        cTurtle.down()
        cTurtle.forward(130)
        cTurtle.right(90)
        cTurtle.forward(160)
        cTurtle.right(90)
        cTurtle.forward(70)
        cTurtle.right(90)
        cTurtle.forward(20)
        cTurtle.up()
        cTurtle.goto(-70,50)
        cTurtle.down()
        cTurtle.goto(-50,70)
    elif(i==1):
        cTurtle.goto(-20,30)
        cTurtle.down()
        cTurtle.circle(20)
    elif(i==2):
        cTurtle.goto(0,10)
        cTurtle.down()
        cTurtle.goto(0,-30)
    elif(i==3):
        cTurtle.goto(0,0)
        cTurtle.down()
        cTurtle.goto(-20,-10)
    elif(i==4):
        cTurtle.goto(0,0)
        cTurtle.down()
        cTurtle.goto(20,-10)
    elif(i==5):
        cTurtle.goto(0,-30)
        cTurtle.down()
        cTurtle.goto(-20,-70)
        cTurtle.goto(-30,-70)
    elif(i==6):
        cTurtle.goto(0,-30)
        cTurtle.down()
        cTurtle.goto(20,-70)
        cTurtle.goto(30,-70)
    cTurtle.hideturtle()

Problema 8.11

A tudo o que já foi feito anteriormente junta-se agora a introdução do conceito de nível. O nível de um jogador (iniciado, normal e perito, vai determinar a complexidade da palavra a adivinhar e o número de tentativas a que tem direito. No nosso caso, escolhemos o seguinte:

(1) iniciado: palavras até 4 caracteres, tentativas igual à soma de 6 com o comprimento da palavra;
(2) normal: palavras até 8 caracteres, tentativas igual à soma de 6 com o número de caracteres diferentes na palavra;
(3) perito: palavra com mais do que 8 caracteres, tentativas igual à soma de 6 com 0.8 * número de letras diferentes.

Posto isto apresentemos as definições que tratam da escolha da palavra (do ficheiro onde estão as palavra do nível escolhido), e do número de tentativas permitido.

def escolhe_nivel():    
    """ Escolhe o nível. Implicações para as palavras e o número de tentativas."""
    print
    print "Níveis possíveis: Iniciado, Normal, Perito."
    nivel = raw_input('Que nível [I/N/P]? ')
    if nivel == 'I':
        return '/tempo/data/pal_iniciado.txt', 'I'
    elif nivel == 'N':
        return '/tempo/data/pal_normal.txt', 'N'
    else:
        return '/tempo/data/pal_perito.txt', 'P'
     
def define_tentativas(dicio_pal, nivel):
    diferentes = len(dicio_pal)
    comprimento = sum([ len(indices) for indices in dicio_pal.values()]) 
    if nivel == 'I':
        return 6 + comprimento
    elif nivel == 'N':
        return 6 + diferentes
    else:
        return int(6 + 0.8 * diferentes)

No programa que joga precisamos introduzir a parte em que se define o nome do ficheiro onde vamos buscar a palavra, e o número de tentativas. O resto é mais do mesmo. O leitor deve consultar as soluções aos problemas anteriores.

def hang811():
    while True:        
        # Definição do nível
        ficheiro,nivel= escolhe_nivel()
        # --- palavra secreta
        palavras = open(ficheiro).read().split()
        secreta = list(random.choice(palavras))
        dicio = seq_to_dict(secreta)
        # --- parâmetros
        tentativas = define_tentativas(dicio,nivel)
        acertou = False
        estado = cria_estado(list('_'* len(secreta)), [],tentativas)
        # resto igual
        .......

Problema 8.10

É-nos pedido uma alteração ao programa de base (problema 8.7), por forma a ser possível ter informação estatística. Vamos discutir o princípio, e não vamos estar preocupados com definir informação detalhada do jogador e seu desempenho. Assim ,o que vamos querer sobretudo é que a informação sobreviva, mesmo depois de o jogador ter terminado de jogar. Isso significa ter a informação armazenada externamente, logo significa usar ficheiros. No entanto, pode ser conveniente internamente ao programa usar outra organização. Como vamos ter vários jogadores, cada um deles com informação estatística associada, o uso de dicionários surge como a forma mais natural de guardar a informação. Para tudo isto ser possível teremos que definir duas operações de interface: uma que converte do ficheiro para o dicionário e, uma segunda, que faz o inverso (nota para o programador savvy: também pode usar o módulo pickle e, neste caso não é preciso preocupar-se com as conversões!). São essas definições que apresentamos de seguida.

def fich_to_dict(ficheiro):
    """Transforma os dados de um ficheiro para um dicionário."""
    linhas = ficheiro.readlines()
    dicio = {}
    for linha in linhas:
        nome,jogos,vitorias = linha.split()
        dicio.update({nome:[int(jogos),int(vitorias)]})
    return dicio
 
def dict_to_fich(dicio, ficheiro):
    """Transforma os dados de um dicionário para um ficheiro."""
    f_out= open(ficheiro,'w')
    for chave,valor in dicio.items():
        linha = chave + '\t\t' + str(dicio[chave][0]) + '\t' + str(dicio[chave][1]) + '\n'
        f_out.write(linha)
    f_out.close()
    return dicio    

Por outro lado, a parte inicial do programa também deve ser alterada, de modo a identificar o jogador e saber como actualizar os dados no final de cada jogo. Vejamos como.

def hang810a(fich_dados):
    # Mensagem inicial
    print 'Bem Vindo ao Jogo do Enforcado!!!'
    print 'Vamos jogar!'
    # recupera informação estatística
    f_in = open(fich_dados,'r')
    dicio_jogadores = fich_to_dict(f_in)
    f_in.close()
    # identificação do jogador
    nome = raw_input('O seu nome por favor: ')
    if nome in dicio_jogadores:
        print 'Olá de novo!'
        print 'O seu desempenho actual é:'
        print 'Jogos efectuados: %d \nVitórias: %d' % (dicio_jogadores[nome][0], dicio_jogadores[nome][1])
    else:
        print 'Bem Vindo pela primeira vez!'
        dicio_jogadores[nome]=[0,0]
         
    # jogar
    jogar = True
    while jogar:
        hang810(nome,dicio_jogadores)
        jogar = continuar(jogar,dicio_jogadores, fich_dados)
         
             
def continuar(jogar,dicio_jogadores,fich_dados):
    # Jogar mais??
    mais = raw_input('mais? [S/N]: ')
    while mais not in ['S','N', 's','n','sim','não']:
        mais = raw_input('A resposta tem que ser [S/N]. A sua  resposta: ')
    if mais in ['N','n','não']:
        # Actualiza estatística
        dict_to_fich(dicio_jogadores,fich_dados)
        print 'Adeus, até à vista...'
        jogar = False
    return jogar     

Como se pode ver o programa depois de fazer a inicialização necessária, chama o programa que efectivamente joga. Aqui tivemos que fazer as alterações que envolvem a actualização da parte estatística no final de cada jogo. Por outro lado, mantivemos a parte do programa que permite jogar mais do que uma vez.

def hang810(nome,dicio_jogadores):
 
    # --- palavra secreta
    palavras = open('/tempo/data/palavras.txt','r').read().split()
    secreta = list(random.choice(palavras))
    dicio = seq_to_dict(secreta)
 
    # --- parâmetros
    tentativas = len(secreta)
    acertou = False
    estado = cria_estado(list('_'* len(secreta)), [],tentativas)
 
    # Começa o jogo
    for tentativa in range(tentativas):
        # Estado actual
        mostra_estado(estado)
        # joga
        letra = adivinha(estado)
        # analisa resposta
        if letra in dicio: 
            # --- Acertou na letra!
            indices = dicio[letra]
            pal_utilizador = get_palavra(estado)
            for ind in indices:
                pal_utilizador[ind] = letra
            estado= set_palavra(estado,pal_utilizador)
            # --- Acertou na palavra??
            if fim(secreta,pal_utilizador):
                acertou = True
                mensagem_sim(secreta)
                break
        # Actualiza estado
        estado = actualiza_estado(estado, estado['palavra'],letra, get_tentativas(estado) - 1)
    # actualiza estatística
    dicio_jogadores[nome][0] = dicio_jogadores[nome][0] + 1
    if acertou:
        dicio_jogadores[nome][1] = dicio_jogadores[nome][1] + 1
    # mensagem final
    mensagem_fim(acertou,secreta)

Falta apenas incluir as definições auxiliares introduzidas nas versões anteriores.

domingo, 6 de dezembro de 2009

Objectos com Classe!!

Temos estado a discutir como a definição de uma estrutura de dados adequada pode ser benéfica para a qualidade da programação. A estrutura de dados tem duas componentes: o objecto propriamente dito, devidamente representado, e um conjunto de operações sobre o objecto, operações que dependem da representação escolhida. Dizemos que as operações escondem o objecto do exterior, ou, dito de outro modo, o objecto fica encapsulado pelas operações. Normalmente o programador deve-se preocupar em definir estrutura de dados que sejam eficientes computacionalmente, passando, se for esse o caso, a só ter que se preocupar com as funcionalidades oferecidas pela estrutura. O leitor mais atento já ligou este aspecto ao que se passa com os tipos de dados das linguagens de programação: nós operamos com números inteiros, por exemplo, sem cuidar de saber como é que estes inteiros estão organizados. Apenas nos interessam as funcionalidades. Alguém teve o trabalho de definir esses tipos para nós. Mas será que nós podemos definir novos tipos de dados com as mesmas características de abstracção? Já vimos que sim! Mas podemos fazer, diferente, para melhor? Uma vez mais a resposta é sim, e liga-se ao conceito de objecto tal como é usado em programação orientada aos objectos: o objecto é um todo englobando as duas componentes acima referidas.

Neste paradigma de programação o conceito de classe é central. De um modo simples, uma classe é um modelo abstracto de objectos. Traduz as características comuns a todos os objectos da classe.Na vida comum nós falamos da classe dos mamíferos, sendo o meu cão ‘Bobi’ e eu objectos dessa classe. Dizemos que os objectos são instâncias da classe. Repetindo: os objectos formam um todo com as suas características (estado) definidas por meio de atributos (por exemplo, palavra, letras usadas, tentativas) e as operações (por exemplo, add_letra_pal) determinando o seu comportamento.

Em Python todos os tipos de dados são implementados como classes. Vamos tentar fazer o mesmo com o conceito de estado apresentado no problema 8.9.

# classe Estado
class Estado(object):
     
    # Construtor
    def __init__(self,palavra =[],usadas=[],tentativas=0):
        """ Cria estado 'vazio'."""
        self.palavra = list(palavra)
        self.usadas = list(usadas)
        self.tentativas = tentativas
     
    # Acessores
    def get_estado(self):
        # Devolve estado
        return (self.palavra, self.usadas, self.tentativas)
 
    def get_pal(self):
        return  self.palavra
 
    def get_letras(self):
        return self.usadas
 
    def get_tentativas(self):
        return  self.tentativas
 
    # Modificadores
    def set_estado(self, palavra,letras,tentativas):
        # Altera estado
        self.palavra = list(palavra)
        self.usadas = list(letras)
        self.tentativas = tentativas
 
 
    def set_palavra(self,pal):
        self.palavra = list(pal)
 
 
    def set_usadas(self,letras):
        self.usadas = list(letras)
 
 
    def set_tentativas(self,tenta):
        if tenta >= 0:
            self.tentativas = tenta
        else:
            print 'O valor não pode ser negativo. Foi indicado %d.' % tenta   
 
 
    def add_letra_palavra(self, letra,l_pos):
        """ Junta a letra em todas as posições não ocupadas indicadas em l_pos."""
        for ind in l_pos:
            if self.palavra[ind] == '_':
                self.palavra[ind] = letra
            else:
                print 'Posição %d já ocupada. Estado inalterado!' % ind
 
 
    def add_letra_usadas(self, letra):
        """ Junta a letra às letras usadas."""
        if not letra in self.usadas:
            self.usadas.append(letra)
        else:
            print '%s já existente. Estado inalterado!' % letra
 
    def add_tentativas(self,tenta):
        """ Modifica o valor das tentivas em tenta."""
        novo_valor = self.tentativas + tenta
        if novo_valor >= 0:
            self.tentativas = novo_valor
        else:
            print 'O valor não pode ser negativo. o Resultado foi %d.' % novo_valor    
 
 
    # Auxiliares
    def __str__(self):
        palavra = ' '.join(self.palavra)
        usadas =  ', '.join(self.usadas)
        tentativas = self.tentativas
        return 'Palavra: %s\nUsadas: %s\nTentativas: %d' % (palavra,usadas,tentativas)
 
if __name__ == '__main__':
    estado = Estado()
    estado.set_palavra('__n_n_')
    estado.add_letra_usadas('b')
    estado.set_tentativas(7)
    print estado
    estado.add_letra_usadas('b')
    estado.set_tentativas(-4)
    estado.add_letra_palavra('a',[1,2,3,5])
    estado.add_letra_usadas('a')
    print estado

Carregue o código e execute-o. Sem entrar em muitos detalhes, o que podemos dizer por comparação ao que fizemos anteriormente?

(1) Aparece uma nova construção denominada classe;

(2) As definições anteriormente apresetnadas estão agora no interior da classe;

(3) O construtor tem agora o nome __init__ (trata-se de um método especial que permite ao utilizador fugir ao construtor por defeito);

(4) Já não temos um dicionários mas sim atributos do objecto definidos no interior do método __init__;

(5) O nome da estrutura (estado) é substituído pelo nome genérico self;

(6) Os modificadores alteram os atributos e não devolvem por return;

(7) A chamada dos métodos da classe usa a notação por ponto (dot notation);

(8) Na chamada dos métodos não se usa o parâmetro self

Muito mais poderia ser dito, mas ficamos por aqui. O leitor interessado pode alterar o código do enforcado para usar a nova classe.

Estruturas de Dados e Abstracção

Regressemos à ideia de estado avançada no problema do Enforcado. Dissemos que o estado era o que andava a ser comunicado entre o programa e o utilizador. Dissemos também que a implementação seria feita com um dicionário. Existem algumas questões interessantes que se colocam. Uma primeira, prende-se com de saber como definir uma camada de abstracção entre a estrutura de dados estado e o resto do mundo. Uma segunda, é a de saber como reagir a uma modificação na implementação do estado, por exemplo, passando de dicionário para lista.

Para responder a estas questões vamos começar por definir uma estrutura de dados, a que chamaremos estado, e que, como referimos será implementada como um dicionário.

# estado como dicionário
# {'palavra':..., 'usadas':..., 'tentativas':...}
# palavra e usadas são listas de caracteres. tentativas é um inteiro não negativo
 
# Construtor
def cria_estado():
    """ Cria estado 'vazio'."""
    estado= dict(palavra=[],usadas=[],tentativas=0)
    return estado
     
# Acessores
def get_estado(estado):
    # Devolve estado
    pal = ' '.join(estado['palavra'])
    letras = ', '.join(estado['usadas'])
    tenta = estado['tentativas']
    return (pal, letra,tenta)
 
def get_pal(estado):
    return  ' '.join(estado['palavra'])
 
def get_letras(estado):
    return  ' '.join(estado['usadas'])
 
def get_tentativas(estado):
    return  estado['tentativas']
 
# Modificadores
def set_estado(estado, palavra,letras,tentativas):
    # Altera estado
    estado['palavra'] = list(palavra)
    estado['usadas'] = list(letras)
    estado['tentativas'] = tentativas
    return estado
 
def set_pal(estado,pal):
    estado['palavra'] = list(pal)
    return estado
 
def set_letras(estado,letras):
    estado['usadas'] = list(letras)
    return estado
 
def set_tentativas(estado,tenta):
    if tenta >= 0:
        estado['tentativas'] = tenta
    else:
        print 'O valor não pode ser negativo. Foi indicado %d.' % tenta   
    return estado
 
def add_letra_pal(estado, letra,l_pos):
    """ Junta a letra em todas as posições não ocupadas indicadas em l_pos."""
    for ind in l_pos:
        if estado['palavra'][ind] == '_':
            estado['palavra'][ind] = letra
        else:
            print 'Posição %d já ocupada. Estado inalterado!' % ind
    return estado
 
def add_letra_letras(estado, letra):
    """ Junta a letra às letras usadas."""
    if not letra in estado['usadas']:
        estado['usadas'].append(letra)
    else:
        print '%s já existente. Estado inalterado!' % letra
    return estado
 
def add_tentativas(estado,tenta):
    """ Modifica o valor das tentivas em tenta."""
    novo_valor = estado['tentativas'] + tenta
    if novo_valor >= 0:
        estado['tentativas'] = novo_valor
    else:
        print 'O valor não pode ser negativo. o Resultado foi %d.' % novo_valor    
    return estado
 
# Auxiliares
def mostra_estado(estado):
    # Mostra palavra
    print 'Palavra Actual: ',' '.join(estado['palavra'])
    print
    # Mostra letras usadas
    print 'Letras já usadas: ',', '.join(estado['usadas'])
    print
    # Mostra tentativas restantes
    print 'Ainda tem as tentativas: ', estado['tentativas']
    print

Acabamos de mostrar como uma estrutura de dados se define através de grupos de operações. Um (ou mais) construtor, acessores (para o todo ou a parte dos elementos da estrutura), modificadores (do todo ou da parte da estrutura) e, ainda operações auxiliares. Algumas dessas operações são simétricas: uma consulta (get), a outra altera (set ou add). Com base nelas o nosso código para o enforcado pode ser reescrito.

def hang89():
    # inicialização
    # --- palavra secreta
    palavras = open('/tempo/data/palavras.txt').read().split()
    secreta = list(random.choice(palavras))
    dicio = seq_to_dict(secreta)
    # --- parâmetros
    TAMANHO = len(secreta)
    LIMITE = limite(TAMANHO)
    estado = cria_estado()
    estado = set_estado(estado,'_'* TAMANHO,'',LIMITE)
    acertou = False
    # Entra no jogo
    for tentativa in range(LIMITE):
        # estado actual
        mostra_estado(estado)
        # joga
        letra = adivinha(estado['usadas'])
        # analisa resposta
        if letra in dicio: 
            # --- Acertou na letra!
            indices = dicio[letra]
            estado = add_letra_pal(estado,letra,indices)
            # --- Acertou na palavra??
            if fim(secreta,estado['palavra']):
                acertou = True
                mensagem_sim(secreta)
                break
        # actualiza estado
        esatdo = add_letra_letras(estado,letra)
        estado = add_tentativas(estado, -1)
    # mensagem final
    mensagem_fim(acertou,secreta)

A pergunta natural que se coloca é a de saber o que ganhámos com estas alterações. A resposta liga-se às duas questões iniciais. Imaginemos que decidimos altera a representação de um dicionário para uma lista. Como proceder? Nesta abordagem basta alterar as operações sobre a estrutura de dados estado. Não precisamos alterar nada no código do programa principal! Programar por camadas de abstracção tem elevados ganhos de produtividade.

Problema 8.9

No jogo do Enforcado existe um conceito importante que é o conceito de estado, conceito esse que traduz a situação do jogo num dado momento. Jogar significa provocar uma mudança de estado. Um outro aspecto neste jogo é o da comunicação entre o programa e o utilizador. Para que essa comunicação seja efectiva deve ser implementado um bom interface entre ambos. É o que vamos mostrar usando precisamente a noção de estado. Isso vai-nos levar a alterar o programa hang87(), mostrando que a nossa análise inicial não foi a melhor. Concentrar tudo no estado vai ser benéfico, permitindo mais tarde alterar o programa de modo mais fácil, caso a especificação seja alterada.

Para já decidimos incluir no estado a palavra que o utilizador está a construir, as letras já tentadas e o número de tentativas de que ainda dispõe. Não é difícil aceitar que a melhor estrutura para guardar esta informação será um dicionário. As operações sobre o estado serão as operações de consulta e de alteração de componentes. Apresentamos a nova versão de hang87.

def hang89():
    # inicialização
    # --- palavra secreta
    palavras = open('/tempo/data/palavras.txt').read().split()
    secreta = list(random.choice(palavras))
    dicio = seq_to_dict(secreta)
    # --- parâmetros
    TAMANHO = len(secreta)
    LIMITE = limite(TAMANHO)
 
    estado = {'palavra':list('_'* TAMANHO),'usadas':[],'tentativas':LIMITE}
    acertou = False
    # Entra no jogo
    for tentativa in range(LIMITE):
        # estado actual
        mostra_estado(estado)
        # joga
        letra = adivinha(estado['usadas'])
        # analisa resposta
        if letra in dicio: 
            # --- Acertou na letra!
            indices = dicio[letra]
            for ind in indices:
                estado['palavra'][ind] = letra
            # --- Acertou na palavra??
            if fim(secreta,estado['palavra']):
                acertou = True
                mensagem_sim(secreta)
                break
        # actualiza estado
        estado['usadas'] = estado['usadas'] + [letra]
        estado['tentativas'] = estado['tentativas'] - 1
    # mensagem final
    mensagem_fim(acertou,secreta)

Problema 8.8

Num post anterior apresentámos a solução para o problema 8.7. Chamámos a função principal hang87. Com base nisso vamos mostrar a solução para este problema.

def hang88():
    print 'Vamos jogar!'
    jogar = True
    while jogar:
        hang87()
        mais= raw_input('Jogar mais? [S/N]: ')
        if mais == 'N':
            print 'Adeus, até à vista...'
            jogar = False

Como se pode ver não alterámos o nosso programa principal. Apenas definimos um programa envolvente (os ingleses chamam-lhe wrapper). Claro que esta solução é muito simplista, e pressupõe que tudo o que não for N significa que se quer continuar a jogar. Mas podemos melhorar a solução.

def hang88b():
    print 'Vamos jogar!'
    jogar = True
    while jogar:
        jogar = continuar(jogar)
             
def continuar(jogar):
    mais = raw_input('mais? [S/N]: ')
    while mais not in ['S','N', 's','n','sim','não']:
        mais = raw_input('A resposta tem que ser [S/N]. A sua  resposta: ')
    if mais in ['N','n','não']:
            print 'Adeus, até à vista...'
            jogar = False
    return jogar

Deixamos ao leitor a tarefa de fazer à sua maneira. A moral desta solução era apenas a de que não foi preciso alterar o nosso programa principal.

Ao longo da vida de um programador a tarefa mais comum é ter que manter um programa, seja devido a erros seja devido a alterações na especificação. Quanto melhor tiver sido construído o nosso programa, mais fácil serão estas tarefas!

sábado, 28 de novembro de 2009

Problema 8.7

Vamos apresentar uma solução básica para esta questão ... básica. O leitor é chamado a estudar o resultado e tentar entender como, e porque, funciona. Ter feito os problemas 8.1 a 8.7 ajuda! O mais importante a reter é que usamos diferentes representações internas (o que é manipulado no interior pelo programa) e externas (o que é visualizado no écran). Refira-se ainda que a palavra secreta é guardada na forma de um dicionário, onde as chaves são os caracteres e os valores os índices na cadeia onde esses caracteres ocorrem. É usada para alterar de modo expedito o estado da palavra que o utilizador vai construindo.

import random
 
def hang87():
    # inicialização
    # --- palavra secreta
    palavras = open('/tempo/data/palavras.txt').read().split()
    secreta = list(random.choice(palavras))
    dicio = seq_to_dict(secreta)
    # --- parâmetros
    TAMANHO = len(secreta)
    LIMITE = limite(TAMANHO)
 
    pal_utilizador = list('_'* TAMANHO)
    acertou = False
    letras_usadas = []
     
    # Entra no jogo
    for tentativa in range(LIMITE):
        # estado actual
        mostra_palavra(pal_utilizador)
        # joga
        letra = adivinha(letras_usadas)
        # analisa resposta
        if letra in dicio: 
            # --- Acertou na letra!
            indices = dicio[letra]
            for ind in indices:
                pal_utilizador[ind] = letra
            # --- Acertou na palavra??
            if fim(secreta,pal_utilizador):
                acertou = True
                mensagem_sim(secreta)
                break
        # actualiza estado
        letras_usadas.append(letra)
    # mensagem final
    mensagem_fim(acertou,secreta)
     
         
 
# Auxiliares
 
def adivinha(letras_usadas):
    """Tenta mais uma letra."""
    letra = raw_input('Escolha uma letra: ')
    # verifica letra - ciclo
    while letra in letras_usadas:
        print
        print '*** Letra já usada. Escolha outra sff!***'
        print
        letra = raw_input('Escolha uma letra: ')
    return letra
     
def limite(tam_palavra):
    """ para mais tarde se poder generalizar..."""
    return tam_palavra
 
def mensagem_sim(secreta):
    print
    print 'Uau! Acertou!'
    mostra_palavra(secreta)
    print
     
def mensagem_fim(acertou,secreta):
    if not acertou:
        print 'Oops! Esgotaram-se as suas hipóteses...'
        print 'A palavra secreta era: '
        mostra_palavra(secreta)
        print 'See you!'
 
def mostra_palavra(palavra):
    """ mostra uma plavra formada por caracteres guardados numa lista."""
    pal = ' '.join(palavra)
    print 'Palavra:'
    print pal
    print
 
def fim(secreta, utilizador):
    return secreta == utilizador
 
 
# --- Importante        
def seq_to_dict(palavra):
    """
    Transforma uma palavra num dicionário de chave os caracteres e 
    valores a lista dos índices.
    """
    dicio = {}
    for indice,letra in enumerate(palavra):
        dicio[letra] = dicio.get(letra,[])+[indice]
    return dicio
 
if __name__ == '__main__':
    hang87()

Problema 7.10

Comparando com o problema 7.8 pouco há a dizer. Tudo se resume à gestão dos pixeis que devem ter o mesmo valor nas posições simétricas relativamente ao eixo dos xs.

import cImage
 
def espelho_v_s(imagem_fich):
    """Faz o espelho vertical de uma imagem.
    Usa a parte superior."""
    imagem = cImage.FileImage(imagem_fich)
    largura = imagem.getWidth()
    altura = imagem.getHeight()
 
    nova_imagem = cImage.EmptyImage(largura,altura)
    for coluna in range(largura):
        for linha in range(altura/2):
            pixel = imagem.getPixel(coluna, linha)
            nova_imagem.setPixel(coluna,linha,pixel)
            nova_imagem.setPixel(coluna,altura - linha - 1,pixel)
    return nova_imagem
     
     
def main710(nome_fich):
    # Prepara
    imagem = cImage.FileImage(nome_fich)
    largura = imagem.getWidth()
    altura = imagem.getHeight()
    # Converte
    nova_imagem = espelho_v_s(nome_fich)
    # Cria janela
    janela = cImage.ImageWin('Espelho Vertical Superior',2*largura ,altura )
    # Mostra
    imagem.draw(janela)
    nova_imagem.setPosition(largura,0)
    nova_imagem.draw(janela)
    # Termina
    janela.exitOnClick() 
     
if __name__ == '__main__':
    main710('/tempo/imagens/duck3.jpg')

A respectiva imagem:

Problema 7.8

Estes problemas com imagens são todos muito parecidos. No caso da obtenção da versão a preto e branco, o mais relevante é sabermos que a imagem se obtém por comparação com um limiar. Esse limiar vai ser comparado com o valor na escala de cinzentos do pixel. Valores inferiores ficam preto (0,0,0), valores maiores ou iguais ficam brancos (255,255,255). Quanto ao mais é mais do mesmo: dois ciclos imbricados, criação da janela, transformação da imagem, posicionamento das imagens, desenho na tela e terminar.

import cImage
 
# 7.8 
def preto_branco(imagem_fich, limiar):
    """ Transforma para imagem a preto e branco."""
 
    imagem = cImage.FileImage(imagem_fich)
    largura = imagem.getWidth()
    altura = imagem.getHeight()
    
    nova_imagem=cImage.EmptyImage(largura,altura)
     
    for coluna in range(largura):
        for linha in range(altura):
            pixel = imagem.getPixel(coluna,linha)
            pixel_aux = pixel_cinzento(pixel)
            if pixel_aux.getRed() < limiar :
                novo_pixel = cImage.Pixel(0,0,0)
            else:
                novo_pixel = cImage.Pixel(255,255,255)
            nova_imagem.setPixel(coluna,linha,novo_pixel)
 
    return nova_imagem
     
def pixel_cinzento(pixel):
    """ Converte um pixel para escala de cinzentos."""
    vermelho = pixel.getRed()
    verde = pixel.getGreen()
    azul = pixel.getBlue()
     
    int_media = (vermelho + verde + azul) / 3
    novo_pixel = cImage.Pixel(int_media,int_media, int_media)
    return novo_pixel
 
def main78(nome_fich,limiar):
    # Prepara
    imagem = cImage.FileImage(nome_fich)
    largura = imagem.getWidth()
    altura = imagem.getHeight()
    # Converte
    nova_imagem = preto_branco(nome_fich,limiar)
    # Cria janela
    janela = cImage.ImageWin('Preto e Branco',2*largura ,altura )
    # Mostra
    imagem.draw(janela)
    nova_imagem.setPosition(largura,0)
    nova_imagem.draw(janela)
    # Termina
    janela.exitOnClick() 
 
if __name__ == '__main__':
    main78('/tempo/imagens/duck3.jpg', 128)

Executando o código para a imagem e limiar dados, obtemos a imagem seguinte.

terça-feira, 24 de novembro de 2009

Problema 7.3

Vamos beneficiar dos ensinamentos do exemplo 7.2. Já sabemos quais são os famosos três passos:

(1) Definir uma janela onde possam ser colocados os objectos;
(2) Gerar as imagens
(3) Posicionar as imagens e mostrar na janela

Reflectindo sobre o problema, não é difícil chegar à conclusão de que vamos andar a colocar quadriláteros de diferentes dimensões na nossa tela. Notar que as linhas são na realidade quadriláteros de pequena espessura. Podemos por isso modularizar o nosso programa desenvolvendo sub-programas que podem ser reutilizados!

Dito isto, uma solução possível é a seguinte:

def quadrilatero(lado_1,lado_2,cor):
    """
    Cria uma figura rectangular, colorida.
    """
    imagem = cImage.EmptyImage(lado_1,lado_2)
    pixel = cImage.Pixel(cor[0],cor[1],cor[2])
    for coluna in range(lado_1):  
        for linha in range(lado_2):
            imagem.setPixel(coluna,linha,pixel)       
    return imagem
 
def cria_e_mostra(lado_1,lado_2, cor, pos,janela):
    imagem = quadrilatero(lado_1,lado_2,cor)
    imagem.setPosition(pos[0],pos[1])
    imagem.draw(janela)
 
def main():
    janela = cImage.ImageWin('Mondrian',600,600)
    # cria imagem, posiciona e mostra
    cria_e_mostra(400,400,(255,0,0),(200,0),janela)
    cria_e_mostra(200,200,(0,0,255),(0,400),janela)
    cria_e_mostra(50,100,(255,255,0),(550,500),janela)
    cria_e_mostra(10,600,(0,0,0),(190,0),janela)
    cria_e_mostra(190,20,(0,0,0),(0,150),janela)
    cria_e_mostra(600,10,(0,0,0),(0,390),janela)
    cria_e_mostra(5,200,(0,0,0),(545,400),janela)
    cria_e_mostra(50,10,(0,0,0),(550,500),janela)
    # finito!
    janela.exitOnClick()

No programa main temos os três passos bem identificados. A definição quadrilatero permite criar todas as formas necessárias. Compare com quadrado do problema 7.2. Finalmente, cria_e_mostra trata de criar as diferentes imagens, posicioná-las e mostrar na janela. Com os valores da figura o boneco é o apresentado na figura.

Problema 7.2

O enunciado do problema diz o seguinte:

Pretende colorir o chão da sua cozinha com quadrados coloridos. As cores devem ser colocadas de acordo com um padrão. A figura abaixo mostra um exemplo possível. A escolha das duas cores é sua!

Vamos reflectir. Olhando para a figura acima vemos que existe um padrão: os quadrados são colocados de modo alternado. Por outro lado, como é dito no enunciado, as formas são quadradas. Finalmente, embora na imagem a cozinha tenha uma dimensão 4 x 3, nó queremos uma solução geral, ou seja, para cozinhas de dimensão n x m. Do ponto de vista informático o que precisamos fazer? De acordo com o princípio geral deste tipo de aplicações vamos ter que responder a três sub-problemas:

(1) Definir uma janela onde possam ser colocados os azulejos;
(2) Gerar os quadrados de duas cores
(3) Posicionar os quadrados e mostrar na janela

A primeira questão, obriga-nos a saber a dimensão dos quadrados e as dimensões n x m da cozinha. Claro que as duas cores também são importantes. Mas disso trataremos de seguida. Daí o nosso programa principal poder ser definido do seguinte modo:

def main1(nx,ny,lado,cores):
    janela = cImage.ImageWin('Ladrilhos',nx * lado, ny*lado)
    # -- resto do programa  a definir aqui 
    janela.exitOnclick()

A segunda questão, remete para a geração de quadrados coloridos. Trata-se de uma questão geral, pelo que a solução para o problema de gerar quadrados de duas cores diferentes pode ser resolvido por um único programa:

def quadrado(lado,cor):
    """
    Cria um quadrado colorido de lado.
    """
    imagem = cImage.EmptyImage(lado,lado)
    pixel = cImage.Pixel(cor[0],cor[1],cor[2])
    for linha in range(lado):  
        for coluna in range(lado):
            imagem.setPixel(coluna,linha,pixel)       
    return imagem

Como se pode ver, começamos por criar uma imagem vazia, com as dimensões apropriadas. Depois definimos um pixel com a cor apropriada. A indicação da cor é dada por um tuplo com os valores (r,g,b). Finalmente, colocamos o pixel em cada ponto da imagem.

Falta agora a parte mais difícil, a questão três: posicionar os quadrados e mostrar a imagem. Pensemos um pouco e olhemos para a figura, que ilustra o caso de quadrados 2 x 2, para serem colocados numa cozinha 4 x 3:

Os círculos alaranjados indicam os pontos onde cada quadrado deve começar a ser desenhado. Correspondem aos índices de uma matriz 4 x 3. (0,0), (1,0), (2,0) ....É aí que devemos colocar as imagens. Mas, é claro, que neste caso estes pontos estão afastados entre si do valor do lado. Assim, na realidade, em termos da imagem, esses pontos são (0,0), (lado,0), (2*lado, 0), ..... Assim o problema reduz-se a colocar 4 x 3 = 12 imagens nas posições referidas. Isso faz-se com dois ciclos for, um dentro do outro que são gerados os índices da matriz, calculando-se em função deles o posicionamento na imagem. Para simplificar admitamos, por agora, que os quadrados são todos da mesma cor:

def cozinha_mono(nx,ny,lado, cor, janela):
    """ Desenha os azulejos todos da mesma cor."""
    for coluna in range(nx):
        for linha in range(ny):
            imagem = quadrado(lado, cor)
            imagem.setPosition(coluna * lado,linha * lado)
            imagem.draw(janela)

Se executarmos o programa apenas vemos desenhar uma cozinha com o chão todo da mesma cor. Não é muito impressionante! Então com alternar entre duas cores?? Um modo possível é notar que a soma das posições (x,y) do canto superior esquerdo das imagens são, alternadamente, pares e ímpares. E sabermos como determinar se um número é par. Logo:

def cozinha_poli(nx,ny,lado, cores, janela):
    """ Desenha os azulejos com duas cores alternadas."""
    for coluna in range(nx):
        for linha in range(ny):
            if (coluna + linha)%2 == 0:
                # par
                imagem = quadrado(lado, cores[0])
            else:
                # ímpar
                imagem = quadrado(lado, cores[1])
                 
            imagem.setPosition(coluna * lado,linha * lado)
            imagem.draw(janela)

Juntando agora todas as peças temos o programa completo:

import cImage
 
def cozinha_mono(nx,ny,lado, cor, janela):
    """ Desenha os azulejos todos da mesma cor."""
    for coluna in range(nx):
        for linha in range(ny):
            imagem = quadrado(lado, cor)
            imagem.setPosition(coluna * lado,linha * lado)
            imagem.draw(janela)
 
def cozinha_poli(nx,ny,lado, cores, janela):
    """ Desenha os azulejos com duas cores alternadas."""
    for coluna in range(nx):
        for linha in range(ny):
            if (coluna + linha)%2 == 0:
                # par
                imagem = quadrado(lado, cores[0])
            else:
                # ímpar
                imagem = quadrado(lado, cores[1])
                 
            imagem.setPosition(coluna * lado,linha * lado)
            imagem.draw(janela)
                 
def quadrado(lado,cor):
    """
    Cria um quadrado colorido de lado.
    """
    imagem = cImage.EmptyImage(lado,lado)
    pixel = cImage.Pixel(cor[0],cor[1],cor[2])
    for linha in range(lado):  
        for coluna in range(lado):
            imagem.setPixel(coluna,linha,pixel)       
    return imagem
 
def main1(nx,ny,lado,cores):
    janela = cImage.ImageWin('Ladrilhos',nx * lado, ny*lado)
    cozinha_poli(nx,ny,lado,cores, janela) 
    janela.exitOnClick()
     
if __name__=='__main__':
    main1(4,3,50,[(255,0,0),(0,0,255)])

Se quisermos variar nas cores e ter alguma surpresa basta fazer uma pequena mudança no programa principal:

def main2(nx,ny,lado):
    janela = cImage.ImageWin('Ladrilhos',nx * lado, ny*lado)
    # escolhe cores aleatoriamente
    cores= []
    for i in range(2):
        r = random.randint(0,255)
        g= random.randint(0,255)
        b = random.randint(0,255)
        while (r,g,b) in cores:
            r = random.randint(0,255)
            g= random.randint(0,255)
            b = random.randint(0,255)
        cores.append((r,g,b))
             
    cozinha_poli(nx,ny,lado,cores, janela) 
    janela.exitOnClick()

Os mais puristas poderão criar um programa à parte para produzir uma lista de cores diferentes de tamanho variável:

def gera_cores(n):
    “”” Gera uma lista de n cores.”””
    cores= []
    for i in range(n):
        r = random.randint(0,255)
        g= random.randint(0,255)
        b = random.randint(0,255)
        while (r,g,b) in cores:
            r = random.randint(0,255)
            g= random.randint(0,255)
            b = random.randint(0,255)
        cores.append((r,g,b))

segunda-feira, 23 de novembro de 2009

Imagens

Na aula teórica estudámos o módulo cImage, que permite algumas manipulações simples de imagens. Explorámos mais tarde nas aulas TP as capacidades do módulo em resolver alguns dos problemas normais que queremos resolver com imagens. Este pequeno exemplo pretende apenas chamar a atenção para os três aspectos (fases) envolvidos na manipulação de imagens:

(1): criação de uma janela

(2): obtenção/criação de imagens

(3): colocação das imagens na janela e sua visualização

Vejamos então o exemplo.

import cImage
 
def mostra_imagem(imagem,pos,janela):
    """ 
    Mostra imagem numa dada posição da janela.
    """
    imagem.setPosition(pos[0],pos[1])
    imagem.draw(janela)
 
def cria_imagem(largura,altura, r,g,b):
    “””
    Cria imagem a partir de nada...
    “””
    imagem = cImage.EmptyImage(largura,altura)
    pixel = cImage.Pixel(r,g,b)
    for coluna in range(largura):
        for linha in range(altura):
            imagem.setPixel(coluna,linha,pixel)
    return imagem
 
def main(largura,altura):
    “”” As três fases.”””
    # Cria janela
    janela = cImage.ImageWin('Toto',largura,altura)
    # Cria imagem
    imagem = cria_imagem(largura/3,altura/2,255,0,0)
    # Coloca imagem na janela e mostra
    mostra_imagem(imagem,(50,100),janela)
    janela.exitOnClick()
 
if __name__=='__main__':
    main(600,400)

Analisemos o programa. Comecemos pela definição main. Ela faz o papel do nosso programa principal. Estão claramente identificadas as três fases acima referidas. Para definir a janela temos que lhe dar um nome (‘Toto’ neste caso) e as suas dimensões (largura e altura). De seguida, a definição cria_imagem é responsável por criar uma imagem simples, em que todos os pixeis são da mesma cor (r,g,b). Note-se como se cria um pixel (linha 15). Não basta indicar um tuplo com os valores das intensidades nos três canais de cor! Outro aspecto importante é o facto de estarmos a lidar com imagens 2D. Isso significa que cada pixel vai ser identificado pelas suas coordenadas em largura e em altura. Como se fosse uma matriz. Assim, navegar por uma imagem, seja para criar, analisar ou modificar, obriga, regra geral, a dois ciclos for, um dentro do outro (linhas 16-18). Ver a imagem obriga a duas coisas: definir a posição onde a imagem vai ser colocada, através da identificação explícita do seu canto superior esquerdo (linha 7 ) e, a seguir mandar desenhar (linha 8 ).
Executando este programa o resultado é a imagem que se pode ver abaixo.

quinta-feira, 19 de novembro de 2009

Mini Teste # 2

Pergunta 2.1

Diga o que entende por aliasing. Pode usar um exemplo como auxiliar da sua justificação.
Resposta

Falamos de aliasing quando nomes distintos ficam associados (pela identidade) ao mesmo objecto.
Exemplo:

>>> a = 5
>>> b = 5
  
>>> a = [1,2,3]
>>> b= a

Pergunta 2.2

Explique de modo claro, sintético e rigoroso o que aconteceu na sessão seguinte:

>>> def prod(x,y):
...  return x * y
... 
>>> a = 5
>>> print prod(a,3)
15
>>> a
5
>>> x
Traceback (most recent call last):
  File "<string>", line 1, in <fragment>
NameError: name 'x' is not defined
>>> 
</fragment></string>

Resposta

Nas linhas 1 e 2 definimos uma função de nome prod. Na linha 4, associamos o nome a ao objecto inteiro 5. Na linha 5, usamos a definição prod, sendo o resultado devolvido impresso por força da instrução print. Quando usamos a definição prod os parâmetros formais x e y vão ficar associados aos parâmetros reais a e 3, como se se tivesse feito no inicio de prod x=a e y = 3. A linha 6 mostra o resultado de executar o comando da linha 5.Na linha 7 perguntamos pelo objecto associado a a , e a resposta é dada na linha 8. Tentamos fazer o mesmo na linha 9 para x, mas dá erro pois x é um parâmetro formal da definição prod e, como tal, só existe no interior da definição.

Pergunta 2.3

Admitindo que n é um número inteiro positivo, explique o que faz o programa da listagem abaixo. A sua resposta não pode ser baseada em generalidades. Em concreto, queremos saber para cada valor de n qual o valor devolvido pela instrução return.

def misterio(n):
    res = [0]
    for i in range(1,n+1):
        res.append(res[-1] + i)
    return res[-1]

Resposta

Calcula o somatorio de 1 a n. O processo é iterativo, calculando-se primeiro os diferente somatórios de 1 a i. No final ao devolver o elemento na última posição (res[-1]), este é o valor da soma de todos os elementos.

Pergunta 2.4

Numa das fichas abordámos as árvores genealógicas e referimos que podiam ser organizadas através de um dicionário. As chaves são nomes, e os valores são listas de nomes dos descendentes directos (isto é, filhos(as)). Desenvolva um programa que, dados um dicionário, cujo conteúdo é uma árvore genealógica, e dois nomes, determina se esses dois nomes são primos(as) em primeiro grau. Relembramos que duas pessoas são primas entre si, se são filhos(as) de dois(duas) irmãos(ãs).

Exemplificando:

>>>    dic = {'ernesto':['carlos', 'jorge','ana'], 'carlos':['ricardo', 'joana'],
'joana': [], 'jorge':['carla', 'francisca'], 'ana':[], 'ricardo':['sara']}
>>>  <------- A sua definicão aqui
>>>  print primos(dic,'ricardo','francisca')
True
>>>

Resposta

def primos(dicio,nome1,nome2):
    """
    Primos são os filhos de dois irmãos...
    """
    prog1 = progenitor(dicio,nome1)
    prog2 = progenitor(dicio,nome2)
    return (prog1 != prog2) and irmaos(dicio,prog1,prog2)
 
def irmaos(dic,nome1,nome2):
    """ Têm o mesmo progenitor?"""
    prog1 = progenitor(dic, nome1)
    prog2 = progenitor (dic,nome2)
    return prog1 == prog2
 
def progenitor(dic, nome):
    """ Devolve o progenitor do nome."""
    for chave, valor in dic.items():
        if nome in valor:
            return chave
    return []

Pergunta 2.5

Suponha que está perdido no meio de uma cidade e não tem GPS para se orientar. Pergunta a um transeunte como pode chegar ao seu destino. Como a cidade é geométrica a resposta é fácil. Recebemos uma sequência de indicações do tipo vira à esquerda (E), depois avança (A), depois roda à direita (D), depois avança (A), depois avança de novo (A), depois recua (R), etc.. Usando o módulo cTurtle desenvolva um programa, que quando executado, simule com a tartaruga os seus movimentos quando esta executa os comandos recebidos.
A imagem mostra o que acontece quando manda correr o programa geral main_tarta(). Por conveniência de visualização marcámos o inicio e o fim do percurso com pontos, verde e vermelho, respectivamente. O seu programa chama-se, no código abaixo, navega.

def main_tarta():
    tartaruga = cTurtle.Turtle()
    tartaruga.setheading(0)
    comandos = 'ADAEAERDAAEARA'
    navega(comandos, tartaruga)
    tartaruga.exitOnClick()