Python is a cool language because it does not get between "you and the problem" - in that case, I think it took me a little longer to figure out how you got in that 45.83% than to figure out a way to solve it. p>
Well, it is necessary to represent each element of the list with the properties it has to the computer - in this case, each element has a list of other elements dependent on itself and a% of how much is solved. If the element has "children" this percentage of how much is solved is equal to that of the child list - otherwise, it is given by the value in its list.
This representation of the list is a minimal form of giving all the necessary information, but does not help to solve the problem - we need a class Node that has the two properties I mentioned: coefficient of how much is complete, and list of children - and from their given list we have created this tree - we may have the refinement of using the Python "decorator" property for the coefficient of how much is complete - this makes the reading of a coefficient of complete is 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 do not know the syntax that I used in the last line -of generator expression, it's worth checking the documentation: link - this code also takes advantage of the numerical value of "True" in Python to be "1", for historical reasons - otherwise it would require an "if")
Well, this is the class as described previously - but for her to describe the problem, you need to create a tree with nodes of this class from your input list - this can be done with one more function -
it is complicated, but notice from the comments that it is exactly what we would like to do if we were constructing this "paper" tree, 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
So, in order for the program to run with its sample data, when it is invoked as a "stand alone" we can add this part - (I use 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)
