Começar de novo

Começar de novo Cá estamos em mais um início de ano lectivo. Para os estreantes quero apenas dizer que neste blogue podem encontrar vários elementos que vos ajudarão na disciplina de IPRP e, assim o espero, a tornarem-se melhores programadores. Para todos os outros bom regresso.

Exame Recurso - P4

Temos uma base de dados, organizada com um dicionário, formada pelo identificador de cada docente (chave) e pelos seus dados profissionais e pessoais (valor). Estes dados estão também guardados num dicionário em que as chaves são os identificadores dos dados pessoais e académicos e os valores, os valores correspondentes. Era-nos pedido a verificação da consistência da base de dados. definida pela identidade das chaves dos dicionários associados a cada docente. Foram vários os erros feitos pelos alunos. Desde usarem à partida como argumento para além da base de dados a lista das chaves, até assumirem que as chaves de um dicionário estão ordenadas, passando por ignorar que os métodos para obter as chaves,os valores ou os items são iteradores.

Uma solução simples para o problema é o que apresentamos a seguir:

def bd_consistente(bd):
    lista_dados_docentes = list(bd.values())
    lista_chaves = []
    for elem in lista_dados_docentes:
        chaves = list(elem.keys())
        chaves.sort()
        lista_chaves.append(chaves)
    for i in range(len(lista_chaves)-1):
        if lista_chaves[i] != lista_chaves[i+1]:
            return False
    return True

if __name__ == '__main__':
    base_dados = {'ecosta':{'nome':'Ernesto','apelido':'Costa'},'lpato':{'nome':'Luís','apelido':'Pato', 'título':'Auxiliar'}, 'aneves':{'nome':'Artur','apelido':'Neves'}}
    print(bd_consistente(base_dados))

Come se pode ver, começamos por guardar em lista_dados_docentes a lista dos dicionários associados a cada docente. De seguida, construímos uma nova lista (lista_chaves) onde guardamos as chaves ordenadas de cada docente. Finalmente, no segundo ciclo, comparamos as chaves ordenadas, terminando mal exista uma caso de diferença.

Teste Final - Pergunta 4

Era pedido um programa em que se somam dois vectores esparsos representados através de dicionários. Um vector esparso é aquele em que a esmagadora maioria dos seus elementos é zero. Usando um dicionário apenas representamos explicitamente os casos diferentes de zero, poupando muito espaço e salvando tempo nas operações. Por exemplo, o vector x = (0,0,0,2,0,0,0,5,0,0) pode ser representado, com economia, pelo dicionário d ={3:2, 7:5, ‘len’:10}. Notar a referência ao comprimento, um parâmetro importante da representação.

Das respostas dadas no teste, quase todos(as) optaram por transformar os dois vectores representados por dicionários em listas, seguido da soma das duas listas, par finalmente depois construir o dicionário resultado. Se pensarmos um pouco, isto é tudo menos boa programação, porque precisamente destrói o que se ganha em usar uma representação baseada em dicionários: espaço e tempo! Mesmo assim, as soluções apresentadas têm muitas deficiências (por exemplo, recurso errado a isdigit() ou a type(x) == int, em vez de isinstance(x,int)). Eis uma solução possível para essa abordagem.

def soma_vec_esparso_b(vec_1, vec_2):
    comp = vec_1['len']
    # Converte dicionários em listas
    list_1 = [vec_1.get(i,0) for  i in range(comp) ]
    list_2 = [vec_2.get(i,0) for  i in range(comp)]
    # soma listas
    list = [list_1[i] + list_2[i] for i in range(comp)]
    # constrói dicionário
    dic = {i: list[i] for i in range(comp) if list[i] > 0}
    dic['len'] = comp
    return dic

Fazemos uso de listas e dicionários por compreensão, que nos permite um código curto.Claro que podem ser substituídas por ciclos normais.

Então qual seria a solução baseada em dicionários? Como vão ver, simples e curta.

def soma_vec_esparso(vec_1, vec_2):
    vec_3 = {}
    vec_3.update(vec_2)
    for ch1,val1 in vec_1.items():
        if ch1 != 'len': # isinstance(ch1,int)
            vec_3[ch1] = val1 + vec_3.get(ch1,0)
    return vec_3

A ideia é começar por copiar um dos dicionários para a solução usando o método update ( isso inclui a chave ‘len’), e depois verificar os elementos relevantes (isto é, diferentes de ‘len’) do outro vector efectuando a soma. Em comentário, mostramos que podemos fazer o teste para saber se é ‘len’ ou um número de um modo mais geral.

Teste #3 - TP2

Pergunta 2
Temos uma árvore genealógica representada por um dicionário, sendo que as chaves são nomes de pessoas e os valores são os pais dessas pessoas. Trata-se pois de uma representação diferente (inversa) da discutida em post anterior. Pedem-nos um programa em que dado o dicionário e o nome de uma pessoa nos seja devolvido a lista dos avós dessa pessoa. É-nos sugerido que pensemos que os avós são os pais dos pais…
Com esta observação uma abordagem lógica seria começar por determinar os pais de uma pessoa. Como a representação liga uma pessoa (chave) aos seus pais (valor) podemos obter essa informação de modo directo.

def pais(ag,nome):
    return ag.get(nome,[])

Resolvido esta questão vamos então usar a definição de avós: pais dos pais.

def avos(ag,nome):
    p = pais(ag,nome)
    return pais(ag,p[0]) + pais(ag,p[1])

A estratégia é linear: determinamos os fpais e, depois, para cada um dos pais, os seus pais. Notar que o get tem um valor por defeito que é uma lista vazia.
Pergunta 3
Partimos de um ficheiro em que cada linha era composta por “nome apelido nota1 nota2 nota3\n” . Queremos criar um novo ficheiro em que cada linha é semelhante à do ficheiro de origem. A diferença é que foi acrescentada informação: a média das três notas e a referência “Aprovado” ou “Reprovado” em função da média ser igual ou superior a 47.5, para aprovação e menor para reprovação. A ideia da solução é simples, pois trata-se de criar um novo ficheiro. Percorremos o ficheiro linha a linha e transformamos cada linha antes de a introduzir no ficheiro de saída. Daí a solução:

def define_notas(fich_1,fich_2):
    with open(fich_1,'r',encoding='utf-8') as f_ent:
        with open(fich_2,'w',encoding='utf-8') as f_saida:
            for linha in f_ent:
                # define média
                nome,apelido,n_1,n_2,n_3 = linha.strip().split()
                media = (float(n_1) + float(n_2) + float(n_3))/3
                if media >= 47.5:
                    classific = 'Aprovado'
                else:
                    classific = 'Reprovado'
                # escreve nova linha
                nova_linha = nome + ' ' + apelido + ' ' + n_1 + ' ' + n_2 + ' ' + n_3 + ' ' + str('%4.2f' % media) + ' ' + classific + '\n'
                f_saida.write(nova_linha)

Teste #3 - TP1

Pergunta 2
Temos uma árvore genealógica representada por um dicionário, sendo que as chaves são nomes de pessoas e os valores são os pais dessas pessoas. Trata-se pois de uma representação diferente (inversa) da discutida em post anterior. Pedem-nos um programa em que dado o dicionário e o nome de uma pessoa nos seja devolvido a lista dos netos dessa pessoa. É-nos sugerido que pensemos que os netos são os filhos dos filhos…
Com esta observação uma abordagem lógica seria começar por determinar os filhos de uma pessoa. Como a representação liga uma pessoa (chave) aos seus pais (valor) temos que percorrer o dicionário recorrendo às chaves e ao conteúdo.

def filhos(ag,nome):
    fil = []
    for ch,val in ag.items():
        if nome in val:
            fil.append(ch)
    return fil

Resolvido esta questão vamos então usar a definição de netos: os filhos dos filhos.

def netos(ag,nome):
    f  = filhos(ag,nome)
    net = []
    for filho in f:
        net.extend(filhos(ag,filho))
    return net

A estratégia é linear: determinamos os filhos e, depois, para cada um dos filhos, os seus filhos. Como o que é devolvido pela função filhos é uma lista temos que recorrer ao uso de extend.
Pergunta 3
Partimos de um ficheiro em que cada linha era composta por “nome apelido nota1 nota2 nota3\n” . Queremos criar um novo ficheiro em que cada linha é semelhante à do ficheiro de origem. A diferença é que foi retirada a nota mais baixa. Com esta formulação o problema torna-se mais simples e a estratégia é básica: percorrer o ficheiro origem por linha (ciclo for), transformar a linha e guardá-la no novo ficheiro. Daí a solução:

def define_notas(fich_1,fich_2):
    with open(fich_1,'r',encoding='utf-8') as f_ent:
        with open(fich_2,'w',encoding='utf-8') as f_saida:
            for linha in f_ent:
                # transforma linha 
                #  —- retira pior nota
                nome,apelido,*notas = linha.strip().split()
                notas = list(notas)
                notas.remove(min(notas))
                #  —- escreve nova linha
                nova_linha = nome + ' ' + apelido + ' ' + ' '.join(notas) + '\n'
                f_saida.write(nova_linha)

O lado menos usual nesta solução está no recurso a *notas quando estamos a extrair as componentes da linha. Quem não estivesse familiarizado com essa notação poderia sempre fazer:

 nome,apelido,n1,n2,n3 = linha.strip().split()
            notas = [n1,n2,n3]

Das aulas

Na aula de hoje falei numa organização das nossas músicas recorrendo a um dicionário. O dicionário é formado por pares (autor, lista dos álbuns do autor). Por sua vez, cada album da lista é representado por um dicionário com três pares. O primeiro é o par (nome, nome da música), o segundo o par (tipo, tipo da música), e o terceiro o par (emprestado, sim/não). Um exemplo de dicionário (muito pequeno …).

musicas = {'pink floyd': [{'nome':'dark side', ‘tipo':'pop','emprestado':False},{'nome':'wall','tipo':'pop','emprestado':True}],
 'doors': [{'nome':'LA woman’,'tipo':'rock','emprestado':True},{'nome':'live','tipo':'rock','emprestado':False}],
'jethro tull':[{'nome':'thick as a brick','tipo': ‘rock','emprestado':False}]}

Esta organização não pretende ser realista, mas apenas uma ajuda a compreender as operações sobre dicionários. Coloquei três questões para esta representação: (1) adicionar um album à base de dados de músicas; (2) Marcar um album como emprestado; (3) listar todas as músicas de um dado tipo. Vamos resolver por etapas.

No primeiro caso uma solução trivial será:

def acrescentar(dicio_musicas,autor,album):
    dicio_musicas[autor] = dicio_musicas.get(autor,[]) + [album]

Como se pode ver uma simples instrução resolve o assunto. Notar que os dicionários são objectos mutáveis nos valores pelo que as alterações efectuadas são permanentes e não é obrigatório usar o return para devolver a nova versão do dicionário. Refira-se ainda neste caso apenas o método get ou o setdefault eram apropriados, garantindo que não há interrupção por erro caso o autor ainda não exista no dicionário.
Para o segundo caso apresentamos duas soluções:

def emprestar(dicio_musicas,autor,album):
    albuns = dicio_musicas.get(autor,[])
    if albuns:
        for musica in albuns:
            if musica == album:
                musica['emprestado'] = True
                break

 
def emprestar_b(dicio_musicas,autor,nome_musica):
    albuns = dicio_musicas.get(autor,[])
    if albuns:
        for musica in albuns:
            if musica['nome'] == nome_musica:
                musica['emprestado'] = True
                break 

Nos dois casos verificamos se o autor existe e, depois, se o album existe. Passados estes dois testes fazemos a alteração. A primeira solução pressupõe que todo o album é fornecido como entrada, enquanto que no segundo caso apenas o nome do album é fornecido. Notar uma vez mais o não recurso a return.
Finalmente, para o terceiro problema:

def musicas_tipo(dicio_musicas, tipo):
    res = []
    for albuns_autor in dicio_musicas.values():
        # analisa musicas de um autor
        for album in albuns_autor:
            if album['tipo'] == tipo:
                res.append(album['nome'])
    return res

Agora, executarmos um ciclo, por autor, em que os álbuns dos autores são analisados à vez.

Dicionários

Suponha escreveu um livro e tem dois índices: um, com os capítulos e as páginas de início e de fim do capítulo. Outro, o índice remissivo, com as palavras e as páginas onde ocorrem. Pretendemos estabelecer uma nova associação em que as palavras têm associadas os capítulos onde aparecem. Vejamos como podemos resolver esta questão. Comecemos por pensar na organização dos índices: como dicionários.

    indice = {'c1':[1,34], 'c2': [35,42], 'c3':[43,52],'c4':[53,60]}
    remissivo = {‘p1':[2,54],'p2':[36,37,50],'p3':[40]}

Agora a solução. Sabemos que queremos passar das palavras aos capítulos. Então uma ideia simples é a de percorrer os dicionários das palavras e, por cada palavra e por cada página em que ocorre, procurar qual o capítulo.

def cap_pal(indice, remissivo):
# inicializa novo dicionário
    sol = dict()
    # percorre indice remissivo por palavra
    for palavra, pgs in remissivo.items():
        # percorre por pagina
        #  para cada pagina onde ocorre a palavra determina o capitaulo
        # actualiza o dicionário e passa à palavra seguinte
    return sol

Tornemos este esboço mais concreto.

def cap_pal(indice, remissivo):
    sol = dict()
    # percorre por palavra
    for palavra, pgs in remissivo.items():
        # percorre por pagina
        cap = []
        for pagina in pgs:
            c = capitulo(indice,pagina)
            if c not in cap:
                cap.append(c)
        sol[palavra] = cap
    return sol

Esta solução tem o cuidado de não acrescentar mais do que uma vez o capítulo, ou seja, se a palavra ocorrer mais do que uma vez no capítulo tal só é indicado uma vez. Mas falta-nos escrever o código que determina em que capítulo está uma dada página.

def capitulo(dicio,pg):
    for ch, val in dicio.items():
        if val[0] <= pg <= val[1]:
            return ch

    return None

Percorremos o dicionário extraindo as páginas de início e de fim para cada capítulo e tentamos saber em que intervalo está a nossa página, para definir o capítulo. E pronto. Podemos passar ao exercício seguinte…