Clarificação

Este blogue é de apoio à cadeira de IPRP, como se clarifica no cabeçalho e na side-bar Bem Vindo. Por isso, e com naturalidade, é um blogue moderado por mim: todos os comentários têm que ser previamente aprovados antes de divulgados. Todos conhecemos o que se passa na blogosfera para saber que isso é um imperativo.

Fiz um post sobre o problema da fraude, no contexto de IPRP. Não quis fazer um exercício de moral, genérico, sobre o tema. Nem o vou fazer agora. Tudo o que tinha a conversar sobre o assunto, fi-lo em privado com quem entendi, e em privado ficará!

De tudo isto resulta que todos os comentários sobre o assunto não serão publicados. Os dois que aparecem no post referido, apenas o foram devido ao princípio da inércia: eu andava até essa data a aprovar tudo sem ler. E não penso que deva agora fazer censura sobre o que objectivamente deixei passar. Mas vai passar a ser diferente.

O problema da fraude não é para mim uma questão polémica. Quem quiser discorrer sobre o assunto, terá que procurar outros locais para o fazer.

Equívocos I

Sempre que corrigimos exames encontramos muitos erros, alguns muito básicos outros mais sofisticados. Fazer uma colectânea com os mais comuns, procurando explicar onde está o erro parece ser uma boa ideia. Tenho dúvidas se será muito pedagógico. Mas enquanto não me decido sobre esta metafísica questão indico aqui um ou outro. Estou aberto a que me enviem as vossas dúvidas sobre outras situações, que procurarei igualmente clarificar.

Coisas com listas

Um erro típico é tentar aceder a uma parte da lista que não existe, recebendo um erro do género IndexError: list assignment index out of range. Se uma lista tem, por exemplo, 5 objectos e perguntamos pelo objecto na posição 7 ... lá temos o erro. Mas pode ser mais subtil. Olhemos para o código:

x = []
for i in range(5):
    x[i] = i

O erro é exactamente o mesmo. Acontece que a lista x não tem nenhum valor quando tentamos lá colocar algo. Mesmo que seja na posição 0. É que esta não existe numa lista vazia!! No exemplo acima, uma maneira de resolver a questão seria usar listas por compreensão:

x = [ i for i in range(5)]

Assim fabricamos os elementos, e colocamos depois tudo numa lista.

Outra questão prende-se com o facto de as listas serem objectos mutáveis. Assim podemos substituir o seu valor sem alterar a sua identidade. Existem muitos métodos que se podem aplicar a listas. Alguns têm por objectivo alterar o objecto. Não têm que devolver nada. Mas em Python, quando não há um return explícito no código, é devolvido o objecto None. Exemplo de um erro comum, por não saberem o que isto significa.

x = []
for i in range(5):
    x= x.append(i)

print x

Executar o código acima resulta no erro AttributeError: 'NoneType' object has no attribute 'append'. Porquê? Precisamente porque na primeira passagem no interior do ciclo, x.append(i) coloca 0 na lista x, mas depois devolve None, valor esse que é associado ao mesmo objecto x pela instrução de atribuição (x = ...), desfazendo a anterior ligação ao objecto lista. Como resultado, na segunda passagem pelo ciclo temos um erro pois x está agora associado a um objecto do tipo None, que não possui nenhum método append.

Yin & Yang

Muitos são os que advogam que vivemos num mundo pleno de opostos: ciências e humanidades é um exemplo paradigmático. E, mesmo dentro de cada categoria, ainda nos oferecem outras oposições: ciência versus engenharia ou arte versus design. Em qualquer das situações alguns ainda pretendem destacar o nobre (e.g., ciência) e o menos nobre (e.g., design). Nada de mais ilusório. Tudo se interliga e alimenta mutuamente.




A programação é um campo onde se juntam os quatro aspectos referidos: ciência e arte, engenharia e design. O que os une: a criatividade! Um excelente programa é aquele que é eficaz e eficiente, mas também belo, elegante e funcional. Esses aspectos sobressaem tanto mais quanto mais complexo for o problema que são supostos resolver. Dominar a complexidade é pois a tarefa principal do programador consciente. Isso só se consegue com rigor e disciplina, mas também com treino, exploração e intuição.

O exemplo que a seguir apresentamos é simples, servindo apenas para demonstrar algumas ideias básicas sobre como dominar a complexidade. O problema é o seguinte: quais os pares de números inteiros positivos, até um certo limite, que são primos entre si. Dos números dizem-se primos entre si se apenas admitirem como divisores comuns a unidade.

A estratégia será a seguinte:
a) gerar os pares de números até ao limite dado
b) para cada par: calcular os divisores de cada número, determinar a sua intersecção, e verificar se esta se reduz ao número 1.
c) acumular os resultados parciais

def primos_entre_si(limite):
    """Devole a lista dos pares de números que são primos entre so."""
    # Acumula resultado
    resultado = []
    # Gera pares a testar
    for i in range(limite):
        for j in range(limite):
            # testa
            if pes(i,j):
                resultado.append((i,j))
    # Devolve resultado
    return resultado

Este código traduz a nossa estratégia. É simples e claro. Mas mais do que isso: torna explícito algumas decisões. Por exemplo, que vamos acumular os resultados numa lista. Como princípio de projecto estas decisões devem ser tomadas o mais tarde possível. O ponto b) está concentrado numa chamada de função (pes). Mas nem tudo são rosas no código apresentado. Basta ter consciência de uma ineficiência: analisa pares de números idênticos, (n,n), ou repetidos, (n,m) e (m,n). Este problema pode ser tratado agora ou mais tarde, pois não interfere com o resto do programa. Este facto, poder deixar para mais tarde, é sempre um sinal de que o programa está a ser bem desenhado! Passemos então à a questão de saber se dois números são primos ente si (função pes). Aqui entra o conhecimento que temos sobre o domínio: dois números são primos entre si se o seu máximo divisor comum for 1.

 def pes(m,n):
    """Primos entre si?"""
    return mdc(m,n) == 1

E agora, para concluir, o programa que calcula o máximo divisor comum. Uma vez mais vem em nosso auxílio o conhecimento que temos sobre o Algoritmo de Euclides:

def mdc(m,n):
    """Algoritmo de Euclides para o máximo divisor comum."""
    if n == 0:
        return m
    else:
        return mdc(n, m % n)

É recursivo! Mas podemos facilmente propor uma solução iterativa, se não estamos confortáveis com a recursividade:

def mdc_iter(m,n):
    while n > 0:
        m, n = n, m % n
    return m

Podemos também ser tentados a usar:

def mdc_iter_b(m,n):
    while n:
        m, n = n, m % n
    return m

A diferença entre estas duas últimas soluções é ténue. Mas não gostamos da última. O código fica menos claro e mais dependente do modo como a linguagem Python interpreta a condição Falso.

Por falar da linguagem, e do conhecimento que se tem sobre a linguagem, podíamos usar como solução para o cálculo do máximo divisor comum:

def mdc_py(m,n):
    from fractions import gcd
    return gcd(m,n)

A partir da versão 2.6 apareceu o novo tipo Fraction. Como sabemos, a simplificação de fracções passa por saber o máximo divisor comum. Por isso o módulo usa esta operação.

Regressemos ao programa principal para corrigir as ineficiências. Sabemos o que fazer para evitar repetições:

def primos_entre_si_b(limite):
    """Devolve a lista dos pares de números que são primos entre so."""
    # Acumula resultado
    resultado = []
    # Gera pares a testar
    for i in range(1,limite):
        for j in range(i+1,limite):
            # testa
            if pes(i,j):
                resultado.append((i,j))
    # Devolve resultado
    return resultado

def pes(m,n):
    """Primos entre si?"""
    return mdc(m,n) == 1

Foi só mexer no comando range dos dois ciclos for!

Juntemos as peças do puzzle:

# Primos entre si

def primos_entre_si(limite):
    """Devole a lista dos pares de números que são primos entre so."""
    # Acumula resultado
    resultado = []
    # Gera pares a testar
    for i in range(1,limite):
        for j in range(i+1,limite):
            # testa
            if pes(i,j):
                resultado.append((i,j))
    # Devolve resultado
    return resultado

def pes(m,n):
    """Primos entre si?"""
    return mdc(m,n) == 1

def mdc(m,n):
    from fractions import gcd
    return gcd(m,n)
  
if __name__ == '__main__':
    print primos_entre_si(100)

E podemos terminar. Ou será que não? Vamos ver o que acontece se eu coloco os números que são primos entre si numa grelha quadrada. Para ficar mais bonito vou usar o módulo cImage. Mas não quero mexer no que fiz: o cálculo e a visualização devem estar bem separados. A estratégia, uma vez mais neste caso, é simples:

a) criar uma imagem vazia com a dimensão do número máximo (do limite)
b) colorir os pixeis nas posições que correspondem a pares de números primos entre si:

from cImage import *

def mostra_pes(limite,lista_pares):
    janela = ImageWin('Primos',limite,limite)
    imagem = EmptyImage(limite,limite)
    pixel_vermelho = Pixel(255,0,0)
    for cord_x,cord_y in lista_pares:
        imagem.setPixel(cord_x,cord_y,pixel_vermelho)
        imagem.setPixel(cord_y,cord_x,pixel_vermelho)
    imagem.draw(janela)
    janela.exitOnClick()

Ligamos as duas partes:

def main(limite):
    lista = primos_entre_si(limite)
    mostra_pes(limite,lista)

Notar como restaurámos a matriz completa, incluindo os pares (x,y) e (y,x)). E executamos!




Que bela textura obtida a partir da matemática... olhem bem para a imagem e descubram o padrão. Há uma ordem escondida!!

Vimos que era importante ter conhecimento sobre o domínio mas também sobre a linguagem. Além disso, com rigor e disciplina, avançando passo a passo, não procurando resolver todo o problema de uma só vez, construímos uma solução simples, clara, eficiente, reutilizável. Arte, Design, Ciência e Engenharia.





(*) As imagens são do excelente livro: The Plenitude: Creativity, Innovation, and Making Stuff, Rich Gold, MIT Press, 2007.

Anagramas

Em post anterior falámos de Will McGunan e dos problemas que colocam quando está a seleccionar candidatos para um emprego onde é preciso saber Python. A segunda questão que coloca é um pouco mais complexa. Temos uma palavra e uma lista de palavras guardadas num ficheiro, uma por linha. A ideia é construir todos os anagramas da palavra dada que são palavras da lista.

Por exemplo, roma é um anagrama de amor.


Vamos construir a solução por etapas.

def ana(s,file_in): 
 anas=anagrams(s)
 lst_ana=del_duplicates(anas)
 resultado=filtro(file_in,lst_ana)
 return resultado

Este é o nosso programa principal! Usa três programas auxiliares:

anagrams: para calcular a lista de anagramas de uma palavra

del_duplicates: que elimina eventuais duplicações

filtro: que selecciona quais os anagramas que são palavras válidas.

Analisemos os casos mais simples, começando pelo processo de filtragem:

def filtro(file_in,lst_ana):
 """One word in each line."""
 fin=open(file_in)
 lst_pal=[pal.strip() for pal in fin.read().split('\n')]
 lst_ana_final= [pal for pal in lst_pal if pal in lst_ana]
 fin.close()
 return lst_ana_final

Lemos o ficheiro todo de uma só vez, dividimos em palavras e retiramos eventuais espaços em branco (linha 4). Na linha 5, apenas consideramos as palavras que estão quer na lista dos anagramas quer na lista das palavras. É agora a vez de eliminar as duplicações:

def del_duplicates(lst):
 if len(lst) == 0:
  return lst
 elif lst.count(lst[0]) > 1:
  return del_duplicates(lst[1:])
 else:
  return [lst[0]] + del_duplicates(lst[1:])
  return [lst[0]] + del_duplicates(lst[1:])

Trata-se de uma solução recursiva: a função chama-se a ela própria. Não era necessário usar recursividade, podendo, caso queira pensar numa solução mais convencional.

Deixámos para o fim a questão de encontrar os anagramas. E aqui, mais uma vez, a solução é recursiva. No entanto, agora não é fácil encontrar uma solução que não faça usa de recursividade. Experimente por si!

def anagrams(s):
 # Return the list of anagrams for s
 if s == "":
  return [s]
 else:
  ans = []
  for w in anagrams(s[1:]):
   for pos in range(len(w)+1):
    ans.append(w[:pos]+s[0]+w[pos:])
  return ans

Porque, e como, funciona esta solução? A ideia é a seguinte: fabricamos (recursivamente) os anagramas com a palavra sem o seu primeiro caracter, para depois inserirmos esse caracter em todas as posições possíveis em cada um dos anagramas gerados. O processo termina se a palavra não tiver nenhum caracter.

E pronto. Só falta testar. Arranje um ficheiro com palavras e faça o exercício. Acho que, desta vez, era capaz de conseguir o lugar!!

Metarmofoses

Will McGugan é um conhecido programador de Python, especialista no desenvolvimento de jogos. Mas também trabalha na selecção de candidatos a emprego onde o conhecimento de Python é importante. No seu blogue dá conta de duas questões tipo que costuma colocar aos candidatos. A primeira é a seguinte. Suponha que precisa de desenvolver um programa que receba como parâmetro um número inteiro e devolva uma cadeia de caracteres que representa o número, mas onde foram colocadas vírgulas para marcar os milhares.

Por exemplo:

>>> milhares_com_virgulas(1234)
 '1,234'
>>> milhares_com_virgulas(123456789)
 '123,456,789'
>>> milhares_com_virgulas(12)
 '12'

Estes exemplo são elucidativos do que se pretende e também dos casos que têm que se ter em conta. Existem várias maneiras de resolver o problema. Pense um pouco antes de olhar para a solução e procure desenvolver a sua solução.

def milhares_com_virgulas(num):
    # muda representação
    cadeia = list(str(num))
    # calcula resultado
    resultado = ''
    while len(cadeia) > 3:
        aux = ',' + ''.join(cadeia[len(cadeia)-3:])
        resultado = aux + resultado
        cadeia = cadeia[:-3]
    resultado = ''.join(cadeia)+ resultado
    return resultado

A nossa solução faz uso de uma mudança de representação e dos comandos str, list e join para comutar entre números, listas e cadeias de caracteres. Socorre-se também de uma variável acumulador onde vamos construindo o resultado.

Notas Exame

Estão no WoC as notas finais após a realização do exame de época normal.

Os(as) Alunos(as):


Ângelo Pinto (LEI)
António Marques (LEI)
Daniel Frutuoso (LEI)
Mafalda Carvalho (LEGI)
Maria Goretti (LEGI)
Sílvia Rocha (LEGI)
Sofia Carvalho (LEGI)

devem contactar o docente, QUINTA-FEIRA, dia 14 de Janeiro, pelas 14h30.

Fraude

Estou a corrigir os exames, como sabem. E na fase em que estou, já deu para perceber muita coisa. Mas só quero referir uma: a fraude. Ou como se diz mais vulgarmente, copianço. E começo por relembrar o que vinha escrito no cabeçalho dos mini testes:

A fraude denota uma grave falta de ética e constitui um comportamento não admissível num estudante do ensino superior e futuro profissional licenciado. Qualquer tentativa de fraude leva a anulação da prova tanto do facilitador como do prevaricador.

O discurso é claro. Quem copiou e quem deixou copiar está reprovado na cadeira. Mesmo que isso só tenha envolvido uma parte ínfima da prova (ou dos trabalhos, ou do que seja que deviam ter feito sozinhos(as)).

Mas para que fique ainda mais claro, envio a url de um sítio com o enunciado da política com que me identifico.

http://robotics.eecs.berkeley.edu/~pister/etc/Cheating.htm

Leiam, e pensem bem, antes de se meterem por caminhos obscuros. Quem já se meteu ... lamento!