Python is a cool language because it doesn’t usually come between "you and the problem" - in this case, I think it took me longer to understand how you came to this 45.83% than to think of a way to solve the issue.
Well, it is necessary to represent to the computer each element of the list with the properties it has - in this case, each element has a list of other dependent elements and a % of how much is solved. If the element has "children" this percentage of how much is solved is equal to the list of children - otherwise, it is given by the value in your list.
This representation of the list is a minimal way of giving all the necessary information, but it doesn’t help to solve the problem - we need a Node class that has the two properties I mentioned: coefficients of how complete it is, and list of children - and from your given list we created this tree - we can have the refinement of using Python’s "Property" developer for the coefficient of how much is complete - this makes the reading of a coefficient of completeness actually the call of a function that calculates the value in real time.
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)
(If you’re not familiar with the syntax I used in the last line of Generator Expression, it’s worth checking out the documentation: https://www.python.org/dev/peps/pep-0289 - that code also takes advantage of the numerical value of the "True" in Python to be "1" for historical reasons - if it were not so, it would be necessary one more "if")
Good -this is the class as described above - only for it to describe the problem it is necessary to create a tree with nodes of this class from its entry list - this can be done with another function -
it’s complicated, but note from the comments that it’s exactly how we would have to proceed if we were inserting this tree "on paper", drawing each node as we process it from the input list:
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
And, so that the program runs with its sample data, when it is invoked as "stand alone", we can add this part - (using Python’s own string formatting to display the value of the completeness coefficient as a percentage):
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)
What it means to be "solved"?
– Juan Lopes
@Juanlopes solved is when is
True
– Paulo
No fraction of denominator 11 (the number of nodes in the tree) rounds to 45.83%. Could you explain the result, please?
– Juan Lopes
@Juanlopes I think the explanation is very clear. The level 3 branch is 50% resolved (a
True
and anotherFalse
), it belongs to a branch of level 2, so this branch has a value of 50%. These four level 2 branches have a total of (0% + 100% + 50% + 0%) which divided by 4 is 37.5%. Then there is at level 1 a branch of 100% another of 37.5% and another of 0%, which divides by three of 45.83%.– Paulo
It had not been clear. The interpretation I had initially given was "what percentage of us is solved?" , not "what percentage of subtrees is solved recursively?". But now I get it. I just think it should be in the body of the question.
– Juan Lopes
It is interesting to note that, judging by the semantics, each node of the tree would be better represented by a tuple than by a list.
– Pablo Almeida