Compare 2 values in a general tree-CodePudding

I'm new to python, and the recursion here is hard for me to wrap my head around.

I have a general tree where each node has two values: a name and a score. I want to find the node with the highest score; however, sometimes the score is a tie, in which case out of all the tied winning scores I only want the one with the longest name.

In this example the first tree has two nodes with the highest score of 99.

The second tree only has one highest score.

class Node():
    def __init__(self):
        self.name = ""
        self.score = -1
        self.children = []
        self.parent = None
    def add_child(self, name, score=-1):
        child = Node()
        child.name = name
        child.parent = self
        child.score = score
        self.children.append(child)

def get_longest_string_of_highest_score(node):
    res = node
    children = []
    for x in node.children:
        children.append(get_longest_string_of_highest_score(x))
    biggest = res
    for x in children:
        if x.score > res.score: #is score bigger?
            if len(x.name) > len(res.name): #is string longer?
                biggest = x
    return biggest

#tree 1
root = Node()
root.add_child("ABC", 6)
root.add_child("ABCDEFG", 4)
root.add_child("ABCDE", 10)

root.children[0].add_child("ABCDEFGHIJK", 0)
root.children[1].add_child("ABCDE",99)

root.children[0].children[0].add_child("A",99)

#tree 2
root2 = Node()
root2.add_child("A", 99)
root2.add_child("ABCDEFG", 4)
root2.add_child("ABCDE", 10)

root2.children[0].add_child("ABCDEFGHIJK", 0)
root2.children[1].add_child("ABCDEFGHIJKLKMNOPQRST",98)

root2.children[0].children[0].add_child("A",0)

############################################
#
#   Get highest score with longest name
#
############################################

result1 = get_longest_string_of_highest_score(root)
result2 = get_longest_string_of_highest_score(root2)

#Expected output: "ABCDE", 99
print(result1.name)
print(result1.score)

print()

#expected output: "A", 99
print(result2.name)
print(result2.score)

I have tried many things and gotten other bad results. The results now are

ABCDE
10

ABCDE
10

I expect to see:

ABCDE
99

A
99

Tree1 should return "ABCDE" because even though "A" is also 99, "ABCDE" is a longer string.

How do I return the node with the longest name of all top scores?

Thanks in advance.

CodePudding user response：

The simplest approach is to just take the max of the longest score of all the child nodes and the node itself, using a tuple of the score and name length as the key:

def get_longest_string_of_highest_score(node):
    return max([node]   [
        get_longest_string_of_highest_score(n) for n in node.children
    ], key=lambda n: (n.score, len(n.name)))

results in your tests printing:

ABCDE
99

A
99

max does the work of iterating over the list and returning the biggest value, and using a tuple in the key function automatically gives you the tiebreaking behavior you're looking for -- the second element is only compared to break ties when the first element is equal.

CodePudding user response：

Maybe separate the function that finds a node's descendants from the search for the biggest node.

def get_descendants(node):
    '''Returns a list of all a node's decendants.
    '''
    if not node.children:
        return node.children
    children = [node for node in node.children]
    for child in children:
        children.extend(get_descendants(child))
    return children

# key function to use with max()
def key(node):
    return node.score,len(node.name)

>>> nodes = get_descendants(root)
>>> foo = max(nodes,key=key)
>>> print(foo.name,foo.score)
ABCDE 99
>>> nodes = get_descendants(root2)
>>> foo = max(nodes,key=key)       
>>> print(foo.name,foo.score)
A 99
>>>