Problema 4.15

Estes problemas sobre árvores genealógicas baseiam-se numa organização simples em dicionário: a chave é um nome, o valor a lista dos descendentes. Neste problema, o nosso objectivo é determinar de duas pessoas são irmãs. Por definição, sê-lo-ão se tiverem o mesmo progenitor. Com a organização definida, encontrar o progenitor de uma pessoa corresponde a encontrar a chave associada a um elemento da lista correspondente ao valor. Não é o modo natural de procurar num dicionário e, por isso, é preciso alguma ginástica.

def progenitor(dic, nome):
  """ Devolve o progenitor do nome."""
  for chave, valor in dic.items():
      if nome in valor:
          return chave
  return None

A solução encontrada mostra como percorremos os itens do dicionário na procura da chave. Como necessitamos das duas componentes do par, a procura faz-se recorrendo a dic.items(). Obtemos assim um par (chave, valor). É por este último facto que podemos colocar dois nomes entre o for e o in! Deste modo, se em cada etapa do ciclo se aceder a um par, por exemplo, ('jorge', ['luis','ana','vasco']), chave fica associada ao primeiro elemento, neste exemplo a 'jorge', e o valor ao segundo, neste caso ['luis','ana','vasco']. Depois é só fazer o teste (linha 4) e devolver o resultado mal este seja encontrado (linha 5). Relembro que mal é encontrada uma instrução de return o programa termina devolvendo o valor associado.

Com este programa auxiliar, é agora trivial resolver a nossa questão inicial.

def irmaos(dic,nome1,nome2):
  """ Têm o mesmo progenitor?"""
  prog1 = progenitor(dic, nome1)
  prog2 = progenitor (dic,nome2)
  return prog1 == prog2

Este exemplo simples serve para ilustrar um princípio básico da programação: a abstracção. Posso começar pela definição e construir a minha solução abstracta que pressupõe, neste caso, que tenho o comando progenitor. Implemento depois o comando, caso ele não exista. Esta forma de programar, do topo para a base, por recurso a camadas de abstracção, recebeu o nome de Programação Descendente.