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