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.

view sourceprint?

1.def mul_car(cadeia):

2.   cad = ''

3.   for i in range(1,len(cadeia)+1):

4.       elem = cadeia[i-1]

5.       if elem not in cad:

6.           cad += elem * i

7.   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.

view sourceprint?

1.def sobreposicao(img1, img2):

2.    nova_img = []

3.    for i in range(len(img1)):

4.        nova_linha = []

5.        for j in range(len(img1[0])):

6.            nova_linha.append(img1[i][j] or img2[i][j])

7.        nova_img.append(nova_linha)

8.    return nova_img

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

view sourceprint?

1.def sobreposicao2(img1,img2):

2.    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.

view sourceprint?

1.def anagramas1(cad1,cad2):

2.    """versão errada!"""

3.    if len(cad1) != len(cad2):

4.        return False

5.    for elem in cad1:

6.        if elem not in cad2):

7.            return False

8.    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:

view sourceprint?

1.def anagramas2(cad1,cad2):

2.    if len(cad1) != len(cad2):

3.        return False

4.    for elem in cad1:

5.        if cad1.count(elem) != cad2.count(elem):

6.            return False

7.    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:

view sourceprint?

1.def anagramas3(cad1,cad2):

2.    list_cad1 = list(cad1)

3.    list_cad2 = list(cad2)

4.    list_cad1.sort()

5.    list_cad2.sort

6.    return list_cad1 == list_cad2

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

view sourceprint?

1.from collections import Counter

2. 

3.def anagramas4(cad1, cad2):

4.    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:

view sourceprint?

1.def conta_elems(seq):

2.    conta = {}

3.    for elem in seq:

4.        counts[elem] = counts.get(elem, 0) + 1

5.    return conta

6. 

7.def anagramas4b(cad1, cad2):

8.    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:

view sourceprint?

1.def anagramas5(cad1, cad2):

2.    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á:

view sourceprint?

1.def interseccao(img1, img2):

2.    nova_img = []

3.    for i in range(len(img1)):

4.        nova_linha = []

5.        for j in range(len(img1[0])):

6.            nova_linha.append(img1[i][j] and img2[i][j])

7.        nova_img.append(nova_linha)

8.    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.