Problema 4.6

Este problema obriga a alguns cuidados. Mas também é um pretexto para percebermos como podemos construir um programa por aproximações sucessivas, não tentando resolver tudo de uma só vez.

De acordo com o algoritmo dado no enunciado uma solução possível para o nosso problema poderá ser:

view sourceprint?

01.def cria_chave(palavra_chave):

02.    """Gera uma chave a partir de uma palavra de passe."""

03.    alfabeto = 'abcdefghijklmnopqrstuvwxyz '

04.    # retira duplicações da palavra chave

05.    palavra_chave = retira_dup(palavra_chave)

06.    # divide em duas partes

07.    ultimo_car = palavra_chave[-1]

08.    indice = alfabeto.find(ultimo_car)

09.    antes = alfabeto[:indice]

10.    depois = alfabeto[indice+1:]

11.    # retira caracteres da palavra chave

12.    antes = retira_car(palavra_chave, antes)

13.    depois = retira_car(palavra_chave, depois)

14.    # junta tudo

15.    chave = palavra_chave + depois + antes

16.    return chave

Se olharmos para os comentários torna-se claro que o algoritmo foi correctamente implementado. Claro, que isto só é verdade se as duas funções auxiliares, retira_dup e retira_car, funcionarem bem. É disso que vamos agora tratar. Comecemos pelo problema de retirar os duplicados.

view sourceprint?

1.def retira_dup(cadeia):

2.    """Retira caracteres duplicados na cadeia."""

3.    nova_cadeia = ''

4.    for car in cadeia:

5.        if car not in nova_cadeia:

6.            nova_cadeia = nova_cadeia + car

7.    return nova_cadeia

Esta solução, constrói uma nova cadeia, percorrendo os elementos da cadeia antiga uma a um, e só introduzindo os caracteres caso não provoquem uma duplicação.

Uma alternativa é o programa seguinte.

view sourceprint?

1.def retira_dup_2(cadeia):

2.    """Retira caracteres duplicados na cadeia."""

3.    nova_cadeia = ''

4.    for ind, car in enumerate(cadeia):

5.        if car not in cadeia[ind+1:]:

6.            nova_cadeia = nova_cadeia + car

7.    return nova_cadeia

Aqui fazemos uso da função enumerate que nos permite percorrer a cadeia simultaneamente pela índices e pelo conteúdo. Veja-se como no teste dentro do if determinamos se um caractere é ou não repetido.

Agora a parte de retirar carateres de um texto.

view sourceprint?

1.def retira_car(caracteres, texto):

2.    """retira do texto os caracteres."""

3.    novo_texto = ''

4.    for car in texto:

5.        if car not in caracteres:

6.            novo_texto = novo_texto + car

7.    return novo_texto

Ainda e sempre a mesma ideia: percorrer o texto (ciclo), e sempre que o caractere em análise não pertencer aos caracteres proibidos ele é adicionado (acumulador). A contagem é implícita.

A lição que podemos tirar deste exemplo é a de que vale a pena usar mecanismos de abstracção (neste caso as duas funções auxiliares) para melhor dominar a complexidade da busca da solução para o nosso problema.