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

Variações em torno de vogais

Nas aulas discutimos o problema de escrever um programa que leia um texto e indique para cada vogal a lista das suas ocorrências no texto. Trata-se de um problema em que, naturalmente, se opta por um dicionário para representar o resultado. Assim, para:

txt = 'ernesto ui ui cuidado com os alunos’

o resultado deve ser:

{'e': [0, 3], 'o': [6, 20, 23, 26, 33], 'u': [8, 11, 15, 31], 'i': [9, 12, 16], 'a': [18, 29]}

A solução evidente segue o padrão ciclo-acumulador. Aqui o acumulador é o dicionário que vai sendo actualizado à medida que percorremos o texto caractere a caractere.

def vogais_x(texto):
    dicio = dict()
    for i in range(len(texto)):
        if texto[i] == 'a':
            dicio['a'] = dicio.get('a',[]) + [i]
        elif texto[i] == 'e':
            dicio['e'] = dicio.get('e',[]) + [i]
        elif texto[i] == 'i':
            dicio['i'] = dicio.get('i',[]) + [i]
        elif texto[i] == 'o':
            dicio['o'] = dicio.get('o',[]) + [i]
        elif texto[i] == 'u':
            dicio['u'] = dicio.get('u',[]) + [i]  
        else:
            continue
    return dicio

Todos concordaremos que é uma solução feia. Todos aqueles ifs podem ser facilmente removidos. Por outro lado, sabemos que vamos precisar não apenas das posições mas também dos caracteres, pelo que nos interessa percorrer o texto obtendo estes dois elementos. Daí uma nova versão:

def vogais_y(texto):
    vogais ='aeiou'
    dicio = dict()
    for i,car in enumerate(texto):
        if texto[i] in vogais:
            dicio[car] = dicio.get(car,[]) + [i]
    return dicio 

Estas soluções constroem o dicionário de modo incremental. No entanto, nós sabemos quais são as chaves do dicionário, e sabemos ainda que nunca mudam. Daí , a possibilidade de criar inicialmente o dicionário com as posições todas iguais a listas vazias, recorrendo ao método fromkeys. Como consequência deixamos de necessitar do uso do método get.

def vogais(texto):
    vogais ='aeiou'
    dicio = dict.fromkeys(vogais, [])
    for i,car in enumerate(texto):
        if car in vogais:
            dicio[car] = dicio[car] + [i]
    return dicio  

O leitor atento dirá que ainda se pode ter uma solução mais elegante usando uma atribuição aumentada: +=.

def vogais_z(texto):
    vogais ='aeiou'
    dicio = dict.fromkeys(vogais, [])
    for i,car in enumerate(texto):
        if car in vogais:
            dicio[car] += [i] # <——— 
    return dicio 

No entanto, se correr este código verificará que não funciona. Ou melhor, corre mas apresenta o resultado errado:

{'a': [0, 3, 6, 8, 9, 11, 12, 15, 16, 18, 20, 23, 26, 29, 31, 33], 'e': [0, 3, 6, 8, 9, 11, 12, 15, 16, 18, 20, 23, 26, 29, 31, 33], 'i': [0, 3, 6, 8, 9, 11, 12, 15, 16, 18, 20, 23, 26, 29, 31, 33], 'o': [0, 3, 6, 8, 9, 11, 12, 15, 16, 18, 20, 23, 26, 29, 31, 33], 'u': [0, 3, 6, 8, 9, 11, 12, 15, 16, 18, 20, 23, 26, 29, 31, 33]} 

A explicação para o resultado (todas as vogais ocorrem nas mesmas posições, igual à união das posições de cada uma…) é simples: a construção do dicionário usando fromkeys faz com que os valores iniciais sejam o mesmo objecto (partilha de memória) e a instrução += não constrói objectos novos. Uma solução consiste em alterar a construção do dicionário inicial, usando dicionários por compreensão:

def vogais_e(texto):
    vogais ='aeiou'
    dicio = {vog:[] for vog in 'aeiou'}
    for i,car in enumerate(texto):
        if car in vogais:
            dicio[car] += [i]
    return dicio 

E pronto. Espero que tenha entendido. Ah, já agora, ainda outra solução….

def vogais_d(texto):
    vogais ='aeiou'
    dicio = {vog:[] for vog in 'aeiou'}
    for i,car in enumerate(texto):
        if car in vogais:
            dicio[car].append(i)
    return dicio