sexta-feira, 15 de dezembro de 2017

Teste # 2 - Especial

P2

Suponha que tem uma palavra e pretende criar uma outra de maneira que os caracteres da palavra inicial nas posições pares passam para as posições ímpares na nova palavra, e os caracteres das posições ímpares da palavra inicial passam para as posições pares da nova palavra. Por exemplo: \\
>>> palavra = 'a1b2c3d'
>>> print(troca(palavra))
1a2b3cd
Implemente o respectivo programa.

A solução adoptada começa por dividir a palavra nos seus elementos pares e nos ímpares. Depois, num ciclo, constrói-se a nova palavra. Finalmente, verifica-se o caso do tamanho ser ímpar o que o briga a acrescentar o último elemento na posição par, que não foi introduzido no ciclo.
def troca(pal):
    """Os caracteres nas posições pares passam para ímpares e os nas posições ímpares passam para as posiçõesp pares."""
    pares = pal[::2]
    impares = pal[1::2]
    nova_pal = ''
    for i in range(len(pal)//2):
        nova_pal += impares[i] + pares[i]
    if len(pal)%2 != 0:
        nova_pal += pares[-1]
    return nova_pal
P3

Suponha que tem uma imagens a preto e branco e que pretende limpar uma parte da imagem, ou seja, colocar os pixeis dessa parte todos a branco. A zona a limpar é dada por dois pontos, o canto superior esquerdo e o canto superior direito. Por exemplo:\\
>>> img = [[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]]
>>> sup = (1,2)
>>> inf = (3,4)
>>> print(limpar(img,sup,inf))
[[1, 1, 1, 1, 1], [1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [1, 1, 0, 0, 0]]
Implemente o respectivo programa.

A solução apresentada percorre todas a matriz de modo usual, por linhas e para cada linha por colunas, limitando as coordenadas ai interior do rectângulo definido pelo canto inferior esquerdo e santo superior direito, muda os piteis para zero (branco). Antes de proceder à alteração, verifica se a operação é possível.
def limpar(imagem, sup_esq,inf_dir):
    """ Limpa a imagem entre o canto superior esaquerdo e o canto superior direito."""
    # verifica se é possível
    num_linhas = len(imagem)
    num_colunas = len(imagem[0])
    possivel_linhas = (sup_esq[0] <= inf_dir[0] <= num_linhas )
    possivel_colunas = (sup_esq[1] <= inf_dir[1] <= num_colunas) 
    if possivel_linhas and possivel_colunas: 
        for linha in range(sup_esq[0], inf_dir[0]+1):
            for coluna in range(sup_esq[1],inf_dir[1]+1):
                imagem[linha][coluna] = 0
    return imagem

Teste 3 - TP2

P2

Suponha que tem uma árvore genealógica organizada usando um dicionário. A chave é um tuplo com dois elementos, em que cada elemento é um tuplo com o nome do progenitor e respectiva idade. O valor é uma lista com tuplos, em que cada tuplo tem o nome do descendente e respectiva idade. Um exemplo:
ag = {(('ernesto',64),('anabela',44)): [('daniela', 15)], (('vitor',72),('irm',68)): [('ines', 39)], (('carlos',68),('mena',65)): [('ricardo', 42), ('marcos', 37)],(('josé',85),('lurdes',82)): [('ernesto', 64), ('afonso',74),('vitor',72), ('carlos',68),('isabel',66)], (('joaobranco',70),('isabel',66)): [('anaisabel', 35),('joana',29)], (('jbp',77),('jbm',70)): [('joaobranco', 70), ('graça',68)]}
Escreva um programa que dada uma árvore genealógica e o nome de uma pessoa, devolva o nome do sobrinho(a) mais velho(a). Exemplo:
>>> sob_mais_velho(ag,'afonso')
ricardo
Os meus sobrinhos são os filhos dos meus irmãos. Daí fazer sentido ter definições auxiliares para determinar os filhos e os irmãos de uma pessoa.
def irmaos(ag, pessoa):
    for prog,filhos in ag.items():
        for filho in filhos:
            if pessoa == filho[0]:
                filhos.remove(filho)
                return filhos
            
def meus_filhos(ag, pessoa):
    for prog, filhos in ag.items():
        if (pessoa == prog[0][0]) or (pessoa == prog[1][0]):
            return filhos
    return None
Resolvida esta questão, o resto é fácil. Começamos por calcular os irmãos da pessoa. Caso existam, calculamos os filhos de cada um dos irmãos. Finalmente, determinamos qual deles é o mais velho.
def sob_mais_velho(ag,pessoa):
    irm = irmaos(ag,pessoa)
    if irm:
        filhos = []
        for irmao in irm:
            filhos.extend(meus_filhos(ag,irmao[0]))
        velho = filhos[0]
        for fil in filhos[1:]:
            if velho[1] < fil[1]:
                velho = fil
        return velho[0]
    return ()
P3

Suponha que tem dois ficheiros de texto com exactamente o mesmo número de linhas. Pretende-se que escreva um programa que dados esses dois ficheiros crie um terceiro cujo conteúdo resulta da junção das linhas dos dois primeiros, feita do seguinte modo. Se A e B forem os dois ficheiros de origem e C o ficheiro resultado, então C vai ter na primeira linha o conteúdo da primeira linha do ficheiro A seguido do conteúdo da primeira linha do ficheiro B, na segunda linha o conteúdo da segunda linha do ficheiro A seguido do conteúdo da segunda linha do ficheiro B, e assim sucessivamente.

Solução trivial. Lemos os dois ficheiros e guardamos o seu conteúdo como listas de linhas. De seguida criamos uma nova lista juntando as linhas de mesma ordem. Finalmente, criamos o novo ficheiro. Notar que temos que retirar o indicador de mudança de linha das linhas do primeiro ficheiro. Usamos o tab como separador.
def concatena_ficheiros(ficheiro_1,ficheiro_2, ficheiro_3):
    with open(ficheiro_1, 'r', encoding='utf-8') as fich_1:
        with open(ficheiro_2,'r',encoding='utf-8') as fich_2:
            with open(ficheiro_3, 'w',encoding='utf-8') as fich_3:
                dados_1 = fich_1.readlines()
                dados_2 = fich_2.readlines()
                dados_3 = []
                for i,linha in enumerate(dados_1):
                    dados_3 += [linha[:-1] +  '\t' + dados_2[i]]
                fich_3.writelines(dados_3)

Teste 3 - TP1

P2

Suponha que tem uma árvore genealógica organizada usando um dicionário. A chave é um tuplo com dois elementos, em que cada elemento é um tuplo com o nome do progenitor e respectiva idade. O valor é uma lista com tuplos, em que cada tuplo tem o nome do descendente e respectiva idade. Um exemplo:
ag = {(('ernesto',64),('anabela',44)): [('daniela', 15)], (('vitor',72),('irm',68)): [('ines', 39)], (('carlos',68),('mena',65)): [('ricardo', 42), ('marcos', 37)],(('josé',85),('lurdes',82)): [('ernesto', 64), ('afonso',74),('vitor',72), ('carlos',68),('isabel',66)], (('joaobranco',70),('isabel',66)): [('anaisabel', 35),('joana',29)], (('jbp',77),('jbm',70)): [('joaobranco', 70), ('graça',68)]}
Escreva um programa que dada uma árvore genealógica e o nome de uma pessoa, devolva o nome do mais velho dos avós. Exemplo:
>>> avo_mais_velho(ag,'anaisabel')
josé
Os avós de uma pessoa são os pais dos pais. Daí que a solução que vamos apresentar use uma definição auxiliar para determinar quem são os pais de alguém. Relativamente ao que tinha sido feito nas aulas apenas se teve que ter em linha de conta que agora cada pessoa tem associada a respectiva idade.

def pais_de(ag,pessoa):
    for ch,val in ag.items():
        for nome, idade in val:
            if nome == pessoa:
                return ch
    return ()
Usando esta função auxiliar, o resto é simples: determinamos quem são os pais da pessoa. se existirem, achamos os pais da cada um dos progenitores e chegamos aos quatro avós. De seguida obtemos o mais velho.
def avo_mais_velho(ag,pessoa):
    pais = pais_de(ag,pessoa)
    if pais:
        avos = []
        for progenit in pais:
            avos.extend(pais_de(ag,progenit[0]))
        # mais velho
        velho = avos[0]
        for av in avos[1:]:
            if velho[1] < av[1]:
                velho = av
        return velho[0]
    return None
P3

Suponha que tem dois ficheiros de texto com exactamente o mesmo número de linhas. Pretende-se que escreva um programa que dados esses dois ficheiros crie um terceiro cujo conteúdo resulta da fusão dos dois primeiros. A fusão é feita alternando as linhas dos dois ficheiros de origem. Assim, se A e B forem os dois ficheiros de origem e C o ficheiro resultado, então C vai ter na primeira linha a primeira linha do ficheiro A, na segunda linha a primeira linha do ficheiro B, na terceira linha a segunda linha do ficheiro A, na quarta linha a segunda linha do ficheiro B, e assim sucessivamente.

Problema muito simples. Lemos os ficheiros de entrada como listas de linhas (readlines). De seguida criamos uma nova lista em que os elementos das listas de entrada são colocadas na posição certa. Finalmente, escrevemos a lista de linhas no novo ficheiro. Como diz o enunciado, esta solução supõe o mesmo número del linhas nos dois ficheiros de entrada.
def junta_ficheiros_b(ficheiro_1,ficheiro_2, ficheiro_3):
    with open(ficheiro_1, 'r', encoding='utf-8') as fich_1:
        with open(ficheiro_2,'r',encoding='utf-8') as fich_2:
            with open(ficheiro_3, 'w',encoding='utf-8') as fich_3:
                dados_1 = fich_1.readlines()
                dados_2 = fich_2.readlines()
                dados_3 = []
                for i in range(len(dados_1)):
                    dados_3.extend([dados_1[i],dados_2[i]])
                fich_3.writelines(dados_3))

quinta-feira, 14 de dezembro de 2017

BINGO!

Se pensar primeiro é fundamental em programação, também sabemos que conhecer bem a linguagem em que vamos expressar a solução é igualmente importante. Numa das fichas recente de exercícios vinha a seguinte questão:

Os cartões para jogar BINGO têm 5 colunas, cada uma com 5 números. As colunas têm associado as letras B, para a primeira coluna, I para a segunda, N para a terceira, G para a quarta e O para a quinta. Nas primeira colunas os números podem ser entre 1 e 15, na segunda entre 16 e 30, na terceira entre 31 e 45, na quarta entre 46 e 60 e na quinta entre 61 e 75. Escreva um programa que permita gerar e guardar de modo apropriado um cartão de bingo. Escreva um segundo programa que permita visualizar um cartão de bingo. Vejamos a solução para a primeira questão:
import random

def bingo():
    nome = 'BINGO'
    cartao = dict()
    for i,letra in enumerate(nome):
        lista = list(range(i*15 +1, i*15 + 16))
        numeros = random.sample(lista,5)
        numeros.sort()
        cartao[letra] = numeros
    return cartao
O que tem de especial a solução? Desde logo usamos um dicionário para guardar a representação de um cartão. A chave é uma das letras de ‘BINGO’ e o valor são os 5 números. Usamos o método sample do módulo random para gerar os 5 números. Este método garante que os números serão todos diferentes. Finalmente usamos o método enumerate para poder ter uma forma simples de gerar os diferentes intervalos dos números.

A segunda questão era a da visualização do cartão. Aqui vai a solução:
def mostra_bingo(cartao):
    numeros_colunas = list(cartao.values())
    numeros_linhas = list(zip(*numeros_colunas))
    print('%2s\t%2s\t%2s\t%2s\t%2s\t'% tuple('BINGO'))
    print('_' * 35)
    for linha in numeros_linhas:
        print('%2s\t%s\t%s\t%s\t%s\t'% linha)

Qual era a dificuldade deste problema? O facto de termos de passar de listas de números associados a letras para uma visualização por colunas. Esta é uma situação onde a operação zip mostra todo o seu esplendor. O facto de fazermos:
numeros_linhas = list(zip(*numeros_colunas))
tem a seguinte explicação. Primeiro, zip é um iterador pelo que para obtermos todos os seus elementos de uma vez temos que usar list sobre o resultado de zip. Depois, o asterisco (*) resulta de zip se aplicar a uma sequência de argumentos e numeros_colunas ter apenas um. numeros_colunas é uma lista em que cada elemento é uma lista de 5 listas cada uma com 5 números. Com o asterisco passamos a ter as 5 listas como argumentos do zip.

 B  I  N  G  O 
__________________
 2 17 33 49 61 
 5 18 34 50 62 
 8 26 35 56 66 
11 27 37 57 72 
13 28 40 60 74

Pensar primeiro…

Programamos para resolver problemas, pelo que o centro da nossa atenção deve ser o problema. Por isso a primeira coisa que devemos fazer é pensar. Pensar para perceber o enunciado: qual é a entrada, qual é a saída. Pensar para definir uma estratégia: posso decompor o problema em sub-problemas mais simples? Já resolvi algum problema semelhante?

Este intróito vem a propósito da dificuldade que alguns encontraram em resolver o problema seguinte: Suponha que tem um dicionário que relaciona receitas com ingredientes. Faça um programa que retorne outro dicionário contendo os ingredientes usados no maior número de receitas, bem como as receitas em que cada um é usado. Por exemplo:

>>> receitas={’sonhos’:[’agua’,’farinha’,’manteiga’, ’ovos’,’acucar’],’rabanadas’:[’pao’,’leite’,’ovos ’,’manteiga’,’acucar’],’leite creme’:[’acucar’,’ farinha’,’ovos’,’leite’]} 
>>> ingredientes_mais_usados(receitas)
{’ovos’: [’sonhos’, ’rabanadas’, ’leite creme’], ’ 
acucar’: [’sonhos’, ’rabanadas’, ’leite creme’]} 
Se pensarmos um pouco verificamos que temos que passar de um dicionário em que as chaves são nomes de receitas e os valores são listas de produtos, para um dicionário em que as chaves são produtos e os valores listas de receitas onde esses produtos aparecem. Ou seja: temos que inverter o dicionário. Este é um problema que já resolvemos no passado:
def meu_inverte_dicio(dicio):
    novo_dicio = dict()
    for ch, val in dicio.items():
        for  ingrediente in val:
            novo_dicio[ingrediente] = novo_dicio.setdefault(ingrediente,[]) + [ch]
    return novo_dicio
Esta solução mostra a grande vantagem em usar o método setdefault!!

A partir do momento que temos o dicionário invertido temos que o percorrer à procura dos elementos cujo valor tem tamanho máximo. Já sabemos como resolver o problema semelhante de encontrar o elemento que é o “maior” de acordo com um dado critério, quando os elementos estão guardados numa lista. Neste caso, o problema é mais complexo por os elementos estarem num dicionário e por querermos não um mas todos os que têm dimensão máxima. Uma solução, possível passa por construir primeiro uma lista e só depois passar a lista a dicionário.

def meu_ingredientes_mais_usados(dicio):
    dicio_ingredientes = meu_inverte_dicio(dicio)
    lista_resultado = []
    tamanho = 0
    for ch, val in dicio_ingredientes.items():
        if len(val) > tamanho:
            lista_resultado = [(ch,val)]
            tamanho = len(val)
        elif len(val) == tamanho:
            lista_resultado.append((ch,val))
    dicio_resultado = dict(lista_resultado)
    return dicio_resultado
Mas nada impede que se construa o dicionário final directamente:
def meu_ingredientes_mais_usados_b(dicio):
    dicio_ingredientes = meu_inverte_dicio(dicio)
    dicio_resultado = dict()
    tamanho = 0
    for ch, val in dicio_ingredientes.items():
        if len(val) > tamanho:
            dicio_resultado.clear()
            dicio_resultado[ch] = val
            tamanho = len(val)
        elif len(val) == tamanho:
            dicio_resultado[ch] = val
        print(dicio_resultado)
    return dicio_resultado
Como se pode ver, cada vez que encontramos uma solução melhor, limpamos o dicionário (método clear) e actualizamos de seguida.

quarta-feira, 22 de novembro de 2017

Teste # 2 - TP2

P2

O problema: Duas palavra dizem-se deslocadas de n posições se se puder obter os caracteres de uma deslocando cada caracter da outra n posições no alfabeto. Por exemplo, HAL e IBM são palavras deslocadas com uma distância de 1. Escreva um programa que determina se duas palavras são deslocadas ou não de n.

A solução. Definimos o alfabeto e depois procuramos as posições no alfabeto dos caracteres presentes nas duas palavras. É preciso que todas as diferenças tenham o mesmo valor, igual a n.

def deslocadas(pal_1, pal_2,n):
    """ 
    pal_1 é pal_2 quand se deslocam todos os caracteres de n posições?
    Exemplo: IBM,HAL e n = 1.
    """
    alfabeto ='abcdefghijklmnopqrstuvwxyz'
    for i in range(len(pal_1)):
        indice_1 = alfabeto.find(pal_1[i])
        indice_2 = alfabeto.find(pal_2[i])
        if (indice_1 - indice_2) != n:
            return False
    return True
Notar que a ordem porque efectuamos a comparação dos índices é relevante. Se n for positivo a primeira palavra deve estar à esquerda da segunda, se for negativo é o contrário. Se quisermos não nos preocupar com a ordem e usar sempre valores positivos de n só temos que acrescentar:
def desloc(p_1,p_2,n):
    return (deslocadas(p_1, p_2,n) or deslocadas(p_2, p_1,n)
P3

O problema: Suponha que tem duas imagens a preto e branco e pretende saber se uma delas, a mais pequena,ocorre na imagem maior. Escreva um programa que resolve esta questão.

A solução. O problema desdobra-se em dois sub-problemas: saber se a operação é possível e, no caso afirmativo, calcular a ocorrência do canto superior esquerdo. Para simplificar a questão criámos um pequeno programa auxiliar que determina se duas imagens são iguais ou não.

def ocorre(img_1, img_2):
    # possivel
    n_linhas_1 = len(img_1)
    n_colunas_1 = len(img_1[0])
    n_linhas_2 = len(img_2)
    n_colunas_2 = len(img_2[0]) 
    possivel = (n_linhas_1 <= n_linhas_2) and (n_colunas_1 <= n_colunas_2)
    # verifica
    for l in range(n_linhas_2 - n_linhas_1 + 1):
        for c in range(n_colunas_2 - n_colunas_1 + 1):
            # verifica se imagem 1 ocorre a partir da posição (l,c)
            if igual(img_1,img_2,l,c):
                return (l,c)
    return (-1,-1)

def igual(img_1,img_2,l,c):
    for i in range(len(img_1)):
        for j in range(len(img_1[0])):
            if img_1[i][j] != img_2[l+i][c+j]:
                return False
    return True

Teste # 2 - TP1

P2

O problema: Um palavra diz-se embebida noutra palavra se os seus caracteres ocorrerem nesta pela mesma ordem, embora não necessariamente de modo consecutivo. Por exemplo, ADIA está embebida em ACADEMIA. Escreva um programa que dadas duas palavras, determina se uma delas está embebida na outra.

A solução. Não há grande mistério. Analisamos os caracteres da palavra mais pequena e verificamos se está presente na palavra maior. Para garantir o problema da ordem cada vez que fazemos a pesquisa limitarmos o campo de procura de modo que a posição inicial seja a posição imediatamente à frente da posição onde se encontrou o último caractere. notar que mal um caractere não esteja presente o programa termina com False.
def embebida(pal_1, pal_2):
    """ verifica se pal_1 está embebida em pal_2."""
    pos = 0
    for car in pal_1:
        indice = pal_2.find(car,pos)
        if indice == -1:
            return False
        pos = indice + 1
    return True
P3

O problema: Suponha que tem duas imagens a preto e branco e pretende que uma delas, a mais pequena, substitua uma parte da imagem maior. Escreva um programa que dadas as duas imagens e o ponto de inserção efectue a modificação.

A solução. A solução apresentada tem duas partes: uma em que se verifica se a operação é possível, e a segunda em que se processa a alteração. como se pode ver a estratégia consistiu em percorrer a imagem mais pequena e colocar os seus valores no sítio certo da imagem maior.

def altera_img(img_1, img_2,pos_l, pos_c):
    """ altera a imagem 2 com a imagem 1 a partir das posição (pos_l,pos_c)"""
    # é possível?
    n_linhas_1 = len(img_1)
    n_colunas_1 = len(img_1[0])
    n_linhas_2 = len(img_2)
    n_colunas_2 = len(img_2[0]) 
    possivel = ((pos_l + n_linhas_1) <= n_linhas_2) and ((pos_c + n_colunas_1) <= n_colunas_2)
    if possivel:
        # modifica
        for l in range(n_linhas_1):
            for c in range(n_colunas_1):
                img_2[pos_l + l][pos_c + c] = img_1[l][c]
    return img_2