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.

Um problema, várias soluções

Sempre que estamos diante de um problema novo a melhor maneira de o resolver é tentar identificar um modelo de solução por analogia com problemas antigos já resolvidos. Para além disso, quando os problemas têm uma certa complexidade, pois necessitamos fazer muitas coisas e sujeitos a diferentes restrições, nada melhor do que dividir o problema em sub-problemas mais simples e/ou tentar resolver primeiro uma versão mais simples que depois completamos. Isto são princípios que temos vindo a explorar ao longo das aulas. Também é um facto que conhecendo melhor a linguagem de programação podemos encontrar variantes para a nossa solução inicial, eventualmente mais eficientes. Vamos ver este último aspecto com exemplos simples das aulas.

Contar quantos elementos de uma lista são menores do que um elemento de referência.

A solução trivial passa por percorrer (recorrendo a um ciclo) a lista e ir contando sempre que aparecer um elemento menor (uso de um acumulador. Mas mesmo esta situação pode ser feita de diferentes maneiras: percorrer a lista por índice ou percorrer por conteúdo:

def conta_menores1(num,lista_num):
    acum = 0
    for i in range(len(lista_num)):
        if lista_num[i] < num:
            acum += 1
    return acum


def conta_menores2(num,lista_num):
    acum = 0
    for i in lista_num:
        if i < num:
            acum += 1
    return acum

A segunda versão é a preferível do ponto de vista da eficiência, sendo que, na nossa opinião, é mais clara. Quem conhecer o conceito de listas por compreensão pode sugerir outra solução:

def conta_menores3(num, lista_num):
    return sum([ 1 for i in lista_num if i < num])

Será que podemos arranjar ainda outra solução. Na aula um aluno sugeriu uma alternativa muito interessante:

def conta_menores4(num, lista_num):
    lista_num.sort()
    return lista_num.index(num)

Nesta solução ordenamos a lista e depois calculamos a posição do número da lista que vai ser igual ao número de elementos menores. Mas esta solução tem um problema: só funciona se o número de referência estiver na lista. Consegue perceber porquê?? Tratemos agora de uma variante deste problema.

Listagem dos menores

Podemos ter soluções semelhantes às anteriores. O que muda é a natureza do acumulador (agora terá que ser um contentor, tuplo ou lista.

def lista_menores1(num,lista_num):
    acum = []
    for i in range(len(lista_num)):
        if lista_num[i] < num:
            acum += [lista_num[i]]
    return acum


def lista_menores2(num,lista_num):
    acum = []
    for i in lista_num:
        if i < num:
            acum += [i]
    return acum

Aqui podemos variar a forma de juntar o elemento à lista, recorrendo ao método append em substituição da operação de concatenação:

def lista_menores3(num,lista_num):
    acum = []
    for i in range(len(lista_num)):
        if lista_num[i] < num:
            acum.append(lista_num[i])
    return acum

def lista_menores4(num,lista_num):
    acum = []
    for i in lista_num:
        if i < num:
            acum.append(i)
    return acum

E uma vez mais a solução com listas por compreensão (a nossa preferida):

def lista_menores5(num, lista_num):
    return [i for i in lista_num if i < num]

Será que a sugestão do nosso aluno também se aplica aqui (no pressuposto de que o elemento está na lista)? Claro:

def lista_menores4(num,lista_num):
    lista_num.sort()
    return lista_num[:lista_num.index(num)]

Soma cumulativa

Agora a questão é a de dada uma lista construir uma nova lista em que na posição i vamos ter a soma dos elementos da lista original entre as posições inicial e i (inclusivé). A solução mais simples baseia-se no recurso ao padrão ciclo-acumulador que contem no interior do ciclo outro padrão ciclo-acumulador. Este último é usado para o cálculo da soma cumulativa.

def soma_cumulativa(lista):
    acum = []
    for i in range(len(lista)):
        # soma de 0 a i
        soma = 0
        for j in range(i+1):
            soma += lista[j]
        # junta soma ao acumulador
        acum.append(soma)
    return acum 

Conhecendo a existência da função sum podemos simplificar a nossa primeira solução:

def soma_cumulativa2(lista):
    acum = []
    for i in range(len(lista)):
        # soma de 0 a i
        soma = sum(lista[:i+1])
        # junta soma ao acumulador
        acum.append(soma)
    return acum 

E, também aqui, o recurso a listas por compreensão da origem a um programa mais curto:

def soma_cumulativa3(lista):
    return [sum(lista[:i+1]) for i in range(len(lista))]

Será que podemos fazer melhor? Podemos. Uma pequena reflexão sobre o problema mostra que existe uma relação simples entre duas somas cumulativas consecutivas: basta somar à soma anterior (de 0 a i) o valor do elemento na posição (i+1):

def soma_cumulativa4(lista):
    acum = [lista[0]]
    for i in lista[1:]:
        acum.append(acum[-1]+i)
    return acum 

E pronto. Esperamos que tenham ficado com uma ideia de que em programação mesmo os problemas mais simples podem ter várias alternativas.

Vamos ao Casino?

Nas aulas abordámos o método de Monte Carlo e vimos como nos pode auxiliar a calcular o valor aproximado de pi. Eis o código:

def monte_carlo_pi(num_dardos):
    """
    Calcula o valor de pi pelo método de Monte Carlo.
    """
    # define e inicializa acumulador
    conta_dardos_in = 0
    for i in range(num_dardos):
        # gera posição dardo i
        x= random.random()
        y= random.random()
        # dentro ou fora?
        d = (x**2 + y**2)**0.5
        if d <= 1:
            conta_dardos_in = conta_dardos_in + 1
    res_pi = 4 * (conta_dardos_in/num_dardos)
    return res_pi

A ideia consiste em ter um quarto de círculo de raio um (cuja área é igual a pi/4) inscrito num quadrado de lado um. Simulamos de seguida o lançamento de dardos cuja posição de impacto é escolhida com base numa distribuição uniforme (todos os pontos são equi-prováveis). A percentagem de dardos que cai dentro do círculo, multiplicado por 4 dá-nos o valor pretendido.

Este método pode ser aplicado nas mais diversas situações e problemas. Por exemplo, determinar a probabilidade de um dardo lançado aleatoriamente cair dentro de uma certa zona. Procurámos resolver esta questão no caso das áreas 1 e 3 da figura abaixo.

A ideia para a solução não é diferente da anterior: contar a percentagem dos dardos que caem dentro de uma das áreas pretendidas:

def monte_carlo_reg_2(num_dardos):
    """
    Calcula o valor de uma área  pelo método de Monte Carlo.
    """
    # define e inicializa acumulador 
    conta_dardos_in = 0
    for i in range(num_dardos):
        # gera posição dardo i
        x= random.uniform(0,2)
        y= random.uniform(0,2)
        # dentro ou fora
        zona_1 = (x <= 1 and y >=1)
        zona_3 = (x >= 1 and y <= 1) or (x>= 1 and y <= x)
        if zona_1 or zona_3:
            conta_dardos_in = conta_dardos_in + 1
    res = conta_dardos_in/num_dardos
    return res

Com estes dois exemplos o leitor está preparado para dar o salto para uma generalização da abordagem. Imaginemos que queremos calcular um dado integral:

Sabemos que o valor do integral é dado pela área debaixo de f(x), para x entre a e b. Então conhecido f(x) podemos encontrar uma figura geométrica de área conhecida e que envolva f(x). Feito isto só temos que calcular a percentagem de dados que ficam debaixo da curva e multiplicar pela área. E o programa que o faz é o seguinte:

def monte_carlo_int(funcao, min_x, max_x, min_y, max_y, num_dardos):
    """
    Calcula o valor de um integral  pelo método de Monte Carlo.
    """
    # define e inicializa acumulador 
    conta_dardos_in = 0
    for i in range(num_dardos):
        # gera posição dardo i
        x= random.uniform(min_x,max_x)
        y= random.uniform(min_y,max_y)
        # dentro ou fora
        zona_limite = funcao(x) 
        if y < zona_limite:
            conta_dardos_in = conta_dardos_in + 1
    area = (max_x - min_x) * (max_y -min_y)
    res = area * (conta_dardos_in/num_dardos ) 
    return res

Podemos testar o programa para um caso concreto, o da função y = e^x. A imagem mostra o seu comportamento entre x= 0 e x = 1, e ainda alguns dardos que foram “lançados”:

Como chamamos o programa? Fácil. Definimos a função, os respectivos valores máximos e mínimos para x e y e o número de dardos:

def my_exp(x):
    return pow(math.e, x)

minx = 0
maxx = 1
miny = 0 
maxy = math.e

print(monte_carlo_int(my_exp, minx,maxx,miny,maxy,1000000))

Exercícios Complementares e Programação

Durante a semana passada andámos a resolver exercícios complementares envolvendo cadeias de caracteres e tuplos. Esses exercícios permitiram consolidar o conhecimento sobre os objectos de cada um destes tipos e respectivas operações (na realidade, uma parte delas). Vamos apresentar soluções para esses exercícios aproveitando a ocasião para, nalguns casos mais complexos, ilustrar formas de dominar a complexidade.

Comecemos pelos dois primeiros (retirar duplicados de uma cadeia de caracteres, efectuar a diferença entre duas cadeias de caracteres) e pelo exercício do produto escalar.

def retira_dup(cadeia):
    nova_cad = ''
    for i in range(len(cadeia)):
        if cadeia[i] not in cadeia[i+1:]:
            nova_cad += cadeia[i]       
    return nova_cad

def dif_cad(cad1,cad2):
    cad3 = ''
    for car in cad2:
        if car not in cad1:
            cad3 += car
    return cad3

def prod_esc(vec1,vec2):
    soma = 0
    for i in range(len(vec1)):
        soma += vec1[i] * vec2[i]
    return soma

Estes três casos são instâncias de um padrão de programação simples, designado por ciclo-acumulador. O acumulador pode ser de um dado tipo (cadeia de caracteres, inteiros) e vamos acrescentando ao acumulador mais um elemento, eventualmente condicionado a um teste (dois primeiros exemplos.

Mesmo com estes exemplos triviais podemos propor implementações alternativas:

def retira(cadeia):
    nova_cad = ''
    for car in cadeia:
        if car not in nova_cad:
            nova_cad += ca
    return nova_cad

def prod_esc(v1,v2):
    comp = min(len(v1), len(v2))
    soma = 0
    for i in range(comp):
        soma +=  v1[i] * v2[i]
    return soma



def prod_esc_2(vec1,vec2):
    comp = min(len(vec1),len(vec2))
    aux = tuple()
    for i in range(comp):
        aux += (vec1[i] * vec2[i],)
    return sum(aux)

No primeiro caso, a travessia da cadeia é feita de modo diferente (por conteúdo). No segundo caso, o programa passa a funcionar correctamente mesmo quando os vectores têm dimensões diferentes. No terceiro exemplo, usamos um tuplo para ir armazenando os produtos internos que no final são somados.

Há muitos exemplos desta forma. Por exemplo, criar uma lista só com o elementos não nulos de outra lista:

def so_posit(vec):
    vec_posit = ()
    for val in vec:
        if val > 0:
            vec_posit += (val,)
    return vec_posit

Um outro exercício pede-nos para retirar espaços entre palavras num texto guardado como uma (eventualmente longa) cadeia de caracteres. Este problema, aparentemente simples tem algumas dificuldades escondidas. Uma ideia simples consiste em detectar um espaço em branco e enquanto existirem espaços em brancos não fazer nada, até ao momento que volta a aparecer um espaço em branco. Esta solução pode ser implementada recorrendo a um ciclo diferente do ciclo for a que estamos habituados. Trata-se do ciclo while, que é executado enquanto uma dada condição for verificada. Vejamos então o código:

def retira_espacos_1(cadeia):
    nova_cadeia = ''
    dim = len(cadeia)
    i = 0
    while i < dim:
        nova_cadeia += cadeia[i]
        if cadeia[i] == ' ':
            while i < dim and cadeia[i] == ' ':
                i += 1
        else:
            i += 1      
    return nova_cadeia

Não se pense que não se pode aplicar uma solução com ciclos for. Vamos mostrar uma solução possível que faz aparecer um elemento que em inglês se designa por flag. Trata-se de um booleano que nos permite separar duas situações (caracteres brancos ou não). Na solução apresentada mais em baixo também generalizámos para o conceito de separador incluir um caractere de tabulação (\t).

def retira_espacos_2(cadeia):
    sep = ' \t'
    nova_cadeia = ''
    branco = False
    for car in cadeia:
        if car in sep and not branco:
            branco = True
            nova_cadeia += ' '
        elif car not in sep:
            nova_cadeia += car
            branco = False
    return nova_cadeia

O problema de obter a transposta de uma matriz pode ser resolvido facilmente no pressuposto de que a matriz está representada como um tuplo de tuplos sendo que cada elemento representa uma linha da matriz. A ideia é percorrer a matriz de modo não natural , por colunas, transformando cada coluna numa … linha!

def transpose(matrix):
    res = ()
    for j in range(len(matrix[0])):
        # por cada coluna
        line = ()
        for i in range(len(matrix)):
            # constrói nova linha
            line += (matrix[i][j],)
        # junta linha
        res  += (line,)
    return res

Sabendo como obter a transposta de uma matriz põe ajudar-nos a resolver o problema do quadrado mágico: verificar se todas as linhas, colunas e diagonais têm somas iguais ao valor do número mágico. Numa primeira abordagem a solução pode ser:

def magico(matriz):
    # verifica linhas
    # verifica colunas
    # verifica diagonais
    pass

Vamos tentar resolver cada sub-problema de modo isolado. começamos pelo mais fácil: as linhas.

def magico(matriz):
    tam = len(matriz)
    numero = sum(matriz[0])
    # verifica linhas
    for i in matriz:
        soma = sum(i)
        if soma != numero:
            return False, None

    # verifica colunas
    # verifica diagonais

No caso das colunas a questão é mais difícil pois não existe modo de percorrer de forma elementar as colunas. A menos que transformemos o problema de modo a que fique idêntico ao anterior, transformando as colunas em linhas. Mas isso é o que conseguimos com a operação transposta!!!

def magico(matriz):
    tam = len(matriz)
    numero = sum(matriz[0])
    # verifica linhas
    for i in matriz:
        soma = sum(i)
        if soma != numero:
            return False, None

    # verifica colunas
    for i in transpose(matriz):
        soma = sum(i)
        if numero != soma:
            return False, None

    # verifica diagonais

Fica o problema das diagonais. São duas: a principal e a secundária. Os elementos da primeira têm os índices todos iguais. Quanto à segunda, os índices somam a dimensão da matriz mais um. Isto é assim porque o segundo índice varia de 1 a n o primeiro varia de n a 1! Daí a solução final:

def magico(matriz):
    tam = len(matriz)
    numero = sum(matriz[0])
    # verifica linhas
    for i in matriz:
        soma = sum(i)
        if soma != numero:
            return False, None

    # verifica colunas
    for i in transpose(matriz):
        soma = sum(i)
        if numero != soma:
            return False, None

    # verifica diagonais
    soma = 0
    for i in range(tam):
        soma = soma + matriz[i][i]
    if numero != soma:
        return False, None
    soma = 0
    for i in range(tam):
        soma = soma + matriz[tam-i-1][i]
    if numero != soma:
        return False, None

Este exercício mostra, ainda que seja de modo primitivo, a ideia de dividir um problema em sub-problemas, teoricamente mais simples. Vejamos a mesma ideia num último exemplo que envolve um programa que conta o número de caracteres, palavras e linhas existentes num texto.

def wc_1(texto):
    if texto:
        # conta caracteres
        num_car = conta_car(texto)
        # conta palavras
        num_pal = conta_pal(texto)
        # conta linhas
        num_lin = conta_linhas(texto)
        return num_car, num_pal, num_lin
    else:
        return 0,0,0

Num texto não vazio, contamos separadamente cada condição. Faltam as funções que resolvem cada um dos casos:

def conta_car(texto):
    return len(texto)

def conta_linhas(texto):
    return texto.count(‘\n’) + 1


def conta_pal(texto):
    sep_pal = '\n\t '
    pal = False
    num_pal = 0
    for car in texto:
        if (car not in sep_pal) and not pal:
            num_pal += 1
            pal = True
        elif car in sep_pal and pal:
            pal = False
    return num_pal

Também aqui as duas primeiras situações são triviais e apenas a contagem de palavras levanta algumas dificuldades que resolvemos recorrendo à técnica da flag já acima referida. É evidente que esta solução não é muito eficiente pois o texto é percorrido mais do que uma vez. Mas se entendeu a solução que apresentámos não teria dificuldade em mudar para aquela que a seguir apresentamos e que já não sofre da ineficiência referida:

def wc_2(texto):
    blank = ' \n\t'
    if len(texto) == 0:
        return 0,0,0
    cars = 0
    palavras = 1
    linhas = 1

    
    for i in range(len(texto)-1):
        cars+= 1
        if texto[i] in blank and texto[i+1] not in blank:
            palavras += 1
            
        if texto[i] == '\n':
            linhas += 1
            
    return cars, palavras, linhas