Teste # 2 - Solução dos problemas (TP1 e TP2)

Turma TP1

P2

O problema 2 pedia para criar um programa que transformasse uma cadeia de caracteres numa outra na qual a primeira ocorrência de um dado caractere fosse replicada um numero de vezes na nova cadeia igual à posição onde ocorre na cheia original mais um. Era necessário manter a ordem relativa das ocorrências dos diferentes caracteres. Este exercício tinha uma solução simples baseada no padrão tantas vezes trabalhado de ciclo - acumulador.

 def mul_car(cadeia):
    cad = ''
    for i in range(1,len(cadeia)+1):
        elem = cadeia[i-1]
        if elem not in cad:
            cad += elem * i
    return cad

cad é o acumulador onde vamos acrescentando às soluções parciais as ocorrências do novo caractere. notar a existência da condicional que serve para filtrar os caracteres individuais já utilizados.

Quem conhece Python de um modo mais profundo podia propor uma versão alternativa baseada em listas por compreensão: def mul_car2(cadeia): return ''.join([cadeia[i] * (i+1) for i in range(len(cadeia)) if cadeia[i] not in cadeia[:i]]) Note-se o desaparecimento explicito do acumulador e o modo como se transforma a lista resultado numa cadeia de caracteres.

P3

A sobreposição de duas imagens a preto e branco, representadas como listas de listas de uns e zeros não representa problema de maior. A sobreposição significa que basta que numa dada posição (um dado pixel) esteja a 1 (preto) o resultado na nova imagem deve também ser 1. Percorrendo naturalmente a imagem com dois ciclos for e alternado um a um chegamos ao resultado desejado.

def sobreposicao(img1, img2):
    nova_img = []
    for i in range(len(img1)):
        nova_linha = []
        for j in range(len(img1[0])):
            nova_linha.append(img1[i][j] or img2[i][j])
        nova_img.append(nova_linha)
    return nova_img

Também aqui podemos recorrer a listas por compreensão para obter um programa mais curto:

def sobreposicao2(img1,img2):
    return [ [(img1[i][j] or img2[i][j]) for j in range(len(img1[0]))] for i in range(len(img1))]

Notar a existência de dois ciclos e como o ciclo mais interior aparece primeiro.

Turma TP2

P2

Anagrama é um conceito conhecido: palavras formadas por permutações das mesmas letras e em igual quantidade. O exemplo clássico em português é dado pelas palavras “roma” e “amor”. Uma solução ingénua para esta questão seria testar o igual comprimento das palavras e depois verificar se cada caractere de uma ocorre na outra.

def anagramas1(cad1,cad2):
    """versão errada!"""
    if len(cad1) != len(cad2):
        return False
    for elem in cad1:
        if elem not in cad2):
            return False
    return True

Para verificar que está errada basta testar com as palavras ‘aab’ e ‘bba’. Em vez de falso vai dar verdadeiro. O problema está no facto de o numero de ocorrência de cada caractere em cada uma das palavras ter que ser o mesmo. Daí que uma solução simples seja:

def anagramas2(cad1,cad2):
    if len(cad1) != len(cad2):
        return False
    for elem in cad1:
        if cad1.count(elem) != cad2.count(elem):
            return False
    return True

Claro que podemos pensar em alternativas. Por exemplo, transformar as cadeias em listas, ordená-las e verificar se resulta em duas listas … iguais:

def anagramas3(cad1,cad2):
    list_cad1 = list(cad1)
    list_cad2 = list(cad2)
    list_cad1.sort()
    list_cad2.sort
    return list_cad1 == list_cad2

Para os pitónicos puristas (peritos??) temos outra solução:

from collections import Counter

def anagramas4(cad1, cad2):
    return Counter(cad1) == Counter(cad2)

Counter é um typo que se pode definir como uma colecção não ordenada que implementada como um dicionário em que as chaves são os elementos e o valor o numero de ocorrências da chave. O conceito de dicionário será dado na próxima aula!

Quem não souber da existência de Counter pode implementar a sua solução:

def conta_elems(seq):
    conta = {}
    for elem in seq:
        counts[elem] = counts.get(elem, 0) + 1
    return conta

def anagramas4b(cad1, cad2):
    return conta_elems(cad1) == conta_elems(cad2)

Parece que já temos mulitas alternativas e que dificilmente arranjaremos outra substancialmente diferente. Ou será que não??? Olhemos o código abaixo:

def anagramas5(cad1, cad2):
    return [False,True][sum([ord(x) for x in cad1]) == sum([ord(x) for x in cad2])]

Experimente e … surpresa! Parece que funciona. Mas como? Como se pode ver usamos listas por compreensão para transformar cada lista na lista dos seus códigos numéricos. Esses códigos são somados e verificamos se são ou não iguais. O resultado por isso ou é True ou é False. Como disse nas aulas, True é representado por 1 e False por zero. Então o que temos no final é a forma [False,True][1] ou [False,True][0], isto é estamos a obter por indexação o elemento da lista [False,True] ou na posição zero (False) ou na posição um (True). Engenhoso, mas por ventura não muito claro e dependente do modo como estão implementados os booleanos.

P3

A intersecção de duas imagens é semelhante à sobreposição. A diferença agora é que devemos ter um apenas nas situações em que as duas imagens estejam, na mesma posição, iguais a um. Assim uma solução simples será:

def interseccao(img1, img2):
    nova_img = []
    for i in range(len(img1)):
        nova_linha = []
        for j in range(len(img1[0])):
            nova_linha.append(img1[i][j] and img2[i][j])
        nova_img.append(nova_linha)
    return nova_img

Também aqui podíamos recorrer a uma solução com listas por compreensão. Ao leitor o cuidado de o fazer.