Pensar primeiro…

Programamos para resolver problemas, pelo que o centro da nossa atenção deve ser o problema. Por isso a primeira coisa que devemos fazer é pensar. Pensar para perceber o enunciado: qual é a entrada, qual é a saída. Pensar para definir uma estratégia: posso decompor o problema em sub-problemas mais simples? Já resolvi algum problema semelhante?

Este intróito vem a propósito da dificuldade que alguns encontraram em resolver o problema seguinte: Suponha que tem um dicionário que relaciona receitas com ingredientes. Faça um programa que retorne outro dicionário contendo os ingredientes usados no maior número de receitas, bem como as receitas em que cada um é usado. Por exemplo:

>>> receitas={’sonhos’:[’agua’,’farinha’,’manteiga’, ’ovos’,’acucar’],’rabanadas’:[’pao’,’leite’,’ovos ’,’manteiga’,’acucar’],’leite creme’:[’acucar’,’ farinha’,’ovos’,’leite’]} 
>>> ingredientes_mais_usados(receitas)
{’ovos’: [’sonhos’, ’rabanadas’, ’leite creme’], ’ 
acucar’: [’sonhos’, ’rabanadas’, ’leite creme’]} 

Se pensarmos um pouco verificamos que temos que passar de um dicionário em que as chaves são nomes de receitas e os valores são listas de produtos, para um dicionário em que as chaves são produtos e os valores listas de receitas onde esses produtos aparecem. Ou seja: temos que inverter o dicionário. Este é um problema que já resolvemos no passado:

def meu_inverte_dicio(dicio):
    novo_dicio = dict()
    for ch, val in dicio.items():
        for  ingrediente in val:
            novo_dicio[ingrediente] = novo_dicio.setdefault(ingrediente,[]) + [ch]
    return novo_dicio

Esta solução mostra a grande vantagem em usar o método setdefault!!

A partir do momento que temos o dicionário invertido temos que o percorrer à procura dos elementos cujo valor tem tamanho máximo. Já sabemos como resolver o problema semelhante de encontrar o elemento que é o “maior” de acordo com um dado critério, quando os elementos estão guardados numa lista. Neste caso, o problema é mais complexo por os elementos estarem num dicionário e por querermos não um mas todos os que têm dimensão máxima. Uma solução, possível passa por construir primeiro uma lista e só depois passar a lista a dicionário.

def meu_ingredientes_mais_usados(dicio):
    dicio_ingredientes = meu_inverte_dicio(dicio)
    lista_resultado = []
    tamanho = 0
    for ch, val in dicio_ingredientes.items():
        if len(val) > tamanho:
            lista_resultado = [(ch,val)]
            tamanho = len(val)
        elif len(val) == tamanho:
            lista_resultado.append((ch,val))
    dicio_resultado = dict(lista_resultado)
    return dicio_resultado

Mas nada impede que se construa o dicionário final directamente:

def meu_ingredientes_mais_usados_b(dicio):
    dicio_ingredientes = meu_inverte_dicio(dicio)
    dicio_resultado = dict()
    tamanho = 0
    for ch, val in dicio_ingredientes.items():
        if len(val) > tamanho:
            dicio_resultado.clear()
            dicio_resultado[ch] = val
            tamanho = len(val)
        elif len(val) == tamanho:
            dicio_resultado[ch] = val
        print(dicio_resultado)
    return dicio_resultado

Como se pode ver, cada vez que encontramos uma solução melhor, limpamos o dicionário (método clear) e actualizamos de seguida.