Problema 5.27

Como podemos gerar uma chave de encriptação? Eis a nossa primeira solução:

import random

def cria_chave():
    """Devolve uma chave para encriptar mensagens. Constrói uma permutação."""
    alfabeto = 'abcdefghijklmnopqrstuvwxyz '
    chave = ''
    while alfabeto:
        # escolhe próximo caracter
        indice = random.randint(0,len(alfabeto)-1)
        car = alfabeto[indice]
        # actualiza chave
        chave = chave + car
        # actualiza alfabeto
        alfabeto = alfabeto.replace(car,'')
    return chave

Consegue perceber a ideia? É fácil. Escolhemos ao acaso uma letra do alfabeto e adicionamos à nossa permutação. Retiramos de seguida a letra do alfabeto. Repetimos o processo até esgotarmos as letras. Notar que usamos um espaço em branco!

Outra forma de fazer, agora com um ciclo for.

def cria_chave_2():
    """Devolve uma chave para encriptar mensagens. Constrói uma permutação."""
    alfabeto = 'abcdefghijklmnopqrstuvwxyz '
    chave = ''
    for i in range(len(alfabeto)):
        indice= random.randint(0,26-i)
        chave = chave + alfabeto[indice]
        alfabeto = alfabeto[:indice] + alfabeto[indice + 1:]
    return chave

Analise as diferenças. Qual das duas versões é a sua preferida, e porquê?

Problema 5.22

Contar o número de caracteres, palavras e linhas num texto é um exercício interessante. Na sua aparente simplicidade coloca vários desafios, obrigando-nos a pensar nas diferentes situações que envolvem espaços em branco e mudanças de linha. Vamos mostrar várias soluções, algumas passam por simplificar o problema, um método que é de grande utilidade.

Vejamos uma primeira solução a que chamamos ingénua, pois parte da ideia de que o caracter ‘\n’ indica uma linha e um espaço em branco indica uma palavra.

def wc(texto):
    """Calcula o número de linhas, palavras e caracteres num texto. Não inclui
    espaços em branco. Versão ingénua!!!!"""
    num_caracteres = 0
    num_palavras = 0 
    num_linhas = 0
    for car in texto:
        if car == '\n':
            num_linhas = num_linhas + 1
        elif car == ' ':
            num_palavras = num_palavras + 1
        else:
            num_caracteres = num_caracteres + 1
    return (num_caracteres, num_palavras, num_linhas)

Agora uma versão mais sofisticada.

def wc_2(texto):
    """Calcula o número de linhas, palavras e caracteres num texto. 
    Não inclui espaços em branco"""
    num_caracteres = 0
    num_palavras = 0
    num_linhas = 0
    comp_texto = len(texto)
    posicao = 0
    while posicao < comp_texto:
        # analisa por casos
        while (posicao < comp_texto ) and (texto[posicao] == ' '):
            posicao = posicao + 1

        while (posicao < comp_texto ) and (texto[posicao] == '\n'):
            num_linhas = num_linhas + 1
            posicao = posicao + 1

        while (posicao < comp_texto) and (texto[posicao] != ' ') and (texto[posicao] != '\n'):
            enc_car = True
            num_caracteres = num_caracteres + 1
            posicao = posicao + 1

        if enc_car:
            num_palavras = num_palavras +1
            enc_car = False
    return (num_caracteres, num_palavras, num_linhas)        

Neste caso tratamos de modo mais claro várias linhas em branco ou vários espaços em branco consecutivos.

Mas será que precisamos de complicar assim tanto? Felizmente não! Basta saber um pouco mais sobre os métodos que se aplicam a cadeias de caracteres.... Então se pudermos usar split e splitlines:

def wc_3(texto):
    """Devolve o número de caracteres, palavras e linhas em texto. Inclui espaços em branco."""
    return (len(texto.replace('\n','')), len(texto.split()), len(texto.splitlines()))

def wc_4(texto):
    """Devolve o número de caracteres, palavras e linhas em texto. Não inclui espaços em branco."""
    texto_aux = texto.replace(' ','') # assim não inclui espaços em branco
    return (len(texto_aux.replace('\n','')), len(texto.split()), len(texto.splitlines()))

Nestas duas versões a segunda não conta os espaços em branco. Atente-se que tivemos que criar uma cópia do texto original, o que, com ficheiros grandes não é muito simpático.

Problema 5.19

Pretendemos retirar as vogais que aparecem num dado texto. Esta solução mostra como por vezes a solução pode ser bastante simples:

def retira_vogais(cad):
    """ Retira as vogais numa cadeia, substituindo-as por espaços em branco."""
    vogais = 'aeiou'
    for ch in vogais:
        cad = cad.replace(ch,' ') 
    return cad

Como se pode ver usamos as vogais para conduzir o processo de eliminação. Isto evita ter que andar num longo percurso do texto, caracter a caracter, e fazer um não menos complexo processo de selecção com ifs. Acresce que esta solução é mais geral. Se quisermos um programa que elimine um subconjunto de caracteres basta alterar uma instrução e uns pequenos ajustes, ou, melhor ainda, passar esses caracteres para parâmetro (formal).

def retira_caracteres(cad, caracteres):
    """ Retira os caracteres  numa cadeia, substituindo-as por espaços em branco."""
    for ch in caracteres:
        cad = cad.replace(ch,' ') 
    return cad

Problema 5.16

Vamos simular o comportamento da nossa tartaruga como resposta a comandos, mas agora com o comprimento e o ângulos determinados aleatoriamente entre valores de referência definidos como constantes.

import turtle
import random

def adn_tartaruga_alea(tartaruga, adn):
    """ Simula o comportamento da tartaruga ditado pelo seu ADN."""
    tartaruga.down()
    for car in adn:
        lado = random.randint(20,100)
        angulo = random.randint(10,180)
        if car == 'f':
            tartaruga.fd(lado)
        elif car == 't':
            tartaruga.bk(lado)
        elif car == 'd':
            tartaruga.rt(angulo)
        else:
            tartaruga.lt(angulo)

Basta agora criar uma tartaruga, definir a sequência de comandos (no nosso casa escolhemos para representação cadeias de caracteres), e executar.

    tarta = turtle.Turtle()
    adn_tartaruga_alea(tarta,'ffefdtfftedf')
    turtle.exitonclick()

Problema 5.1

Foi-me pedido que indicasse aqui qual a solução para o problema 5.1. Recordando. Existe um país no qual todas as estradas são de sentido único. Para além disso existe apenas uma e uma só ligação directa entre todos os pares de cidades. Pretende-se mostrar que existe (pelo menos) uma cidade que pode ser alcançada por estrada a partir de qualquer outra cidade, de modo directo ou de modo indirecto. Neste último caso existe apenas uma cidade de permeio.

Vamos então à solução que nos impõe sermos capazes de alguma abstracção. Vamos escolher uma cidade que tem um número máximo de ligações directas para si. Como é bom de ver ela tem que existir. Na realidade pode mesmo existir mais do que uma. Mas escolhamos uma. Seja C o nome da cidade e m o número de ligações. Vejamos se existe alguma cidade, chamemos-lhe X, que não esteja ligada directamente a essa cidade. Se não existir então a prova está terminada. E se existir? Se existir ela tem que estar ligada a uma das cidades que se ligam à nossa cidade escolhida. E porquê? Bem porque se não X teria para si m+1 ligações directas: todas as que se ligam a C mais a ligação de C para X. Não se esqueça que tem que existir uma ligação entre todas as cidades! E isso não pode ser, pois por hipótese m é o número máximo de ligações directas! Com X é uma cidade qualquer não ligada directamente a C isto completa a nossa prova, pois fica ligada indirectamente a C e só com uma cidade pelo meio!

Q.E.D.

Problema 5.15

As tartarugas são como pequenos robots, obedecendo a comandos. Neste problema os comandos são muito simples: ‘f’ para avançar em frente, ‘t’ para recuar, ‘e’ para virar à esquerda e ‘d’ para virar á direita. Queremos visualizar o que a tartaruga faz quando recebe uma dada sequência de comandos. Quando analisamos o problema fica claro que os dados de entrada são a tartaruga (afinal podemos querer enviar comandos diferentes a tartarugas diferentes...), e a sequência de comandos. A saída neste caso é o que observamos em termos de comportamento da tartatuga. Como representação dos dados vamos usar um objecto do tipo turtle e uma cadeia de caracteres para a sequência de comandos. Um olhar mais atento leva-nos a concluir que também falta definir a dimensão dos movimentos e o ângulo de viragem. Vamos admitir que esses elementos são constantes.

Como se trata de realizar repetidas vezes a obediência a um comando, que varia ao longo do tempo, o nosso programa vai ter como parte principal um ciclo. Como o número de vezes que executamos é fixo, uma vez conhecida a sequência de comandos, será usado um ciclo for. Vejamos então o código:

import turtle

def adn_tartaruga(tartaruga, adn):
   """ Simula o comportamento da tartaruga ditado pelo seu ADN."""
   tartaruga.down()
   for car in adn:
       if car == 'f':
           tartaruga.fd(50)
       elif car == 't':
           tartaruga.bk(50)
       elif car == 'd':
           tartaruga.rt(45)
       else:
           tartaruga.lt(45)

Este código tem alguns pressupostos: os comandos são letras minúsculas, não há enganos nas letras, as constantes definidas directamente nos argumentos. Alterar o programa para estarmos mais precavidos não é difícil:

import turtle

def adn_tartaruga(tartaruga, adn):
    """ Simula o comportamento da tartaruga ditado pelo seu ADN."""
    adn.lower()
    TAM = 60
    ANG = 45
    comandos = 'fted'
    tartaruga.down()
    for car in adn:
        if car not in comandos:
            print 'Comando desconhecido...bye'
            break
        elif car == 'f':
            tartaruga.fd(TAM)
        elif car == 't':
            tartaruga.bk(TAM)
        elif car == 'd':
            tartaruga.rt(ANG)
        else:
            tartaruga.lt(ANG)  

Agora é só experimentar.

Problema 4.21

Este problema fala-nos de quadrados concêntricos cujas cores alternam entre o vermelho e o azul. É-nos dito também a posição e o valor do lado do quadrado mais pequeno e, ainda o modo como o quadrado aumenta.

É muita coisa para pensar ao mesmo tempo. Vamos então por partes. Vamos supor que é apenas um quadrado e que a cor é irrelevante. O leitor atento notará logo que assim formulado, trata-se na realidade do problema 4.20. E é! Vamos então resolver o dito.

def quadrado(tartaruga,x,y,lado):
    """Desenha um quadrado."""
    # prepara
    tartaruga.up()
    tartaruga.goto(x,y)
    tartaruga.hideturtle()
    tartaruga.down()
    # desenha
    for i in range(4):
     tartaruga.forward(lado)
     tartaruga.right(90)

Esta solução não tem nada de especial: o problema foi dividido em duas partes. Na primeira, colocamos a tartaruga no sítio apropriado. Na segunda, desenhamos o quadrado, através de uma repetição de desenho do lado e rotação de 90 graus. Pensemos agora num outro detalhe: a cor.

def quadrado_cor(tartaruga,x,y,lado,cor):
    """ Desenha um quadrado colorido."""
    tartaruga.color(cor)
    quadrado(tartaruga,x,y,lado)

Trivial, certo? A partir daqui, vamos querer desenhar quadrados coloridos concêntricos. Quantos serão será um parâmetro do problema. E terei um ciclo for. Algo assim:

def quad_concentricos(n,tartaruga,x,y,lado,cor,d):
    """Desenha n quadrados coloridos concêntricos."""
    for i in range(n):
 #desenha novo quadrado colorido

Mas como os faço concêntricos? A ideia é dada pela imagem seguinte:




Ou seja. Conhecidas as coordenadas do canto inferior esquerdo do último quadrado desenhado, a do próximo resulta de eu alterar essas coordenadas retirando um dado valor a x e aumentando desse mesmo valor y (notar o modo como estão orientados os eixos!). Se eu fizer isso, resulta claro que o novo lado vale a + 2 *d, se a dor o valor do lado inicial. Daqui resulta o código:

def quad_concentricos(n,tartaruga,x,y,lado,cor,d):
    """Desenha n quadrados concêntricos em cores alternadas."""
    for i in range(n):
 quadrado_cor(tartaruga,x-i*d, y+i*d, lado+i*2*d,cor)

Uso o valor de i para controlar o incremento. E como alterno as cores??? Se pensarmos bem, veremos que não é difícil. vou usar o valor de i: se for par, azul, se for ímpar, vermelho!!! E chego ao programa final.

def quad_concentricos(n,tartaruga,x,y,lado, cor_1, cor_2,d):
    """Desenha n quadrados concêntricos em cores alternadas."""
    for i in range(n):
 if i % 2 == 0:
  quadrado_cor(tartaruga,x-i*d, y+i*d, lado+i*2*d, cor_1)
 else:
  quadrado_cor(tartaruga,x-i*d, y+i*d, lado+i*2*d, cor_2)