Python é uma linguagem legal por que não costuma ficar entre "você e o problema" - nesse caso, acho que levei mais tempo para entender como você chegou nesse 45.83% do que para pensar numa forma de resolver a questão.
Bom, é necessário representar para o computador cada elemento da lista com as propriedades que ele tem - no caso, cada elemento tem uma lista de outros elementos dependentes de si e uma % de quanto está resolvido. Se o elemento tem "filhos" essa porcentagem de quanto está resolvido é igual a da lista de filhos - senão, é dada pelo valor na sua lista.
Essa representação da lista é uma forma mínima de dar toda a informação necessária, mas não ajuda a resolver o problema - precisamos sim de uma classe Nó que tem as duas propriedades que eu citei: coeficente de quanto está completo, e lista de filhos - e a partir da sua lista dada criamos essa árvore - podemos ter o requinte de usar o decorator "property" do Python para o coeficiente de quanto está completo - isso faz com que a leitura de um coeficiente de completo seja na verdade a chamada de uma função que calcula o valor em tempo real.
class Node(object):
def __init__(self, completeness=0):
self._completeness = float(completeness)
self.children = []
def add_child(self, child):
self.children.append(child)
@property
def completeness(self):
if self._completeness or not self.children:
return self._completeness
return sum(child.completeness for child in self.children) / len(self.children)
(Se não conhecer a sintaxe que usei na última linha -de generator expression, vale a pena conferir a documentação: https://www.python.org/dev/peps/pep-0289 - esse código também tira proveito do valor numérico do "True" em Python ser "1", por razões históricas - se não fosse isso, seria necessário mais um "if")
Bom -essa é a classe como foi descrita anteriormente - só que para ela descrever o problema é necessário criar uma árvore com nós desta classe a partir da sua lista de entrada - isso pode ser feito com mais uma função -
ela é complicadinha, mas perceba pelos comentários que é exatamente comoteriamos que proceder se estivessemos cosntruindo essa árvore "em papel", desenhando cada nó a medida que o processacemos a partir da lista de entrada:
def build_tree(source):
# transforma a lista num iterador:
# isso permite que tomemos o primeiro elemento com a função "next"
# e guardemos os demais elementos para serem consumidos pelo "for" abaixo.
source = iter(source)
# consome o primeiro nó na lista, criando a raiz da árvore)
level, completeness = next(source)
root = Node(completeness)
# lista temporária que permite subir para os nós superiores
# quando cada ramo for preenchido:
tree_stack = [(level, root)]
for level, completeness in source:
new_node = Node(completeness)
# se estamos de volta num nó pelo menos um nível acima do anterior - remover
# elementos da lista temporária - o nó que ficar por último
# nessa lista será o último nó inserido com nível acima do
# atual (portanto, o pai do atual)
while tree_stack[-1][0] > level:
tree_stack.pop()
previous_level = tree_stack[-1][0]
if level == previous_level:
# o mesmo nível do último nó inserido -
# inserir o novo nó como irmão do último
tree_stack[-2][1].add_child(new_node)
# remover o irmão do nó atual da lista temporária -
# de forma que o penultimo elemento seja o sempre o
# pai de outros nós no nível atual
tree_stack.pop()
elif level > previous_level:
#colocar o novo nó como filho do último nó criado
tree_stack[-1][1].add_child(new_node)
tree_stack.append((level, new_node))
return root
E, de forma que o programa rode com seus dados de exemplo, quando for invocado como "stand alone" podemos adicionar esta parte - (uso a própria formatação de strings do Python para exibir o valor do coeficiente de completude como porcentagem):
if __name__ == "__main__":
data = [
[0, False],
[1, True],
[1, False],
[2, False],
[2, True],
[2, False],
[3, False],
[3, True],
[2, False],
[1, False],
[2, False]
]
tree = build_tree(data)
print ("A porcentagem de completude da árvore é {:.02%}".format(tree.completeness)
True
True
e outroFalse
), ela pertence a um ramo do nível 2, logo esse ramo tem valor de 50%. Esses quatro ramos de nível 2 tem um total de (0% + 100% + 50%+ 0%) que dividido por 4 é igual a 37,5%. Então existe no nível 1 um ramo de 100% outro de 37,5% e outro de 0%, que divido por três da 45,83%.