Programação com Python: dezembro 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!

Programação com Python