你想得到木勺吗? 我可不想! 在某些比赛中, 木勺是个玩笑奖，它授予给在比赛中的最后一名. 这并不是网球运动的官方做法，但这并没有阻止球迷授予虚拟勺子。

职业巡回赛中的网球赛事以淘汰赛进行，每个人每轮都与另一个人比赛。 每轮结束后，其余一半的球员都被淘汰出局。

所以，如果我们想要奖励别人勺子，我们需要更好地定义谁是最后一名.

如果 . . .

• 在第一轮 (R1), A 输给 B
• 在第二轮 (R2), B 输给 C
• 在第三轮 (R3), C 输给 D
• . . .
• 在四分之一决赛中 (QF), W 输给 X
• 在半决赛中 (SF), X 输给 Y
• 在决赛中 (F), Y 输给 Z

然后玩家A有资格获得木勺.

有些比赛中，很可能没有人获得木勺（Bye不能得木勺，它代表轮空）,否则一定有那么一个人会拿到木勺。 写一个程度，读取一个外部文件，文件的内容包含锦标赛的每场比赛结果。文件名将作为程序的参数。 如果有玩家拿到木勺，你的程序应该输出导致这种结果的比赛场次。(R1 R2 R3 ... QF SF F)

文件包含一套有效的比赛结果. 若 A. Aardvark 在某场比赛中击败了 C. Capybara, 那么文件里就会有这么一行 A. Aardvark d. C. Capybara. 比赛会按照顺序给出.

比赛的结果包含几个玩家！ A. Aardvark, B. Badger, C. Capybara, D. Dolphin, E. Echidna, F. Flamingo 和 G. Goat！

文件内容如下：

A. Aardvark d. C. Capybara
C. Capybara d. B. Badger
C. Capybara d. F. Flamingo
A. Aardvark d. G. Goat
F. Flamingo d. Bye
E. Echidna d. D. Dolphin
A. Aardvark d. E. Echidna

注意这一行 F. Flamingo d. Bye.  这会告诉我们 F. Flamingo 首轮轮空,自动进入下一轮. 注意 Bye 不会得到木勺!

动物大联盟锦标赛 2018
=============================

QF      SF       F

A-------+
        A--------+
G-------+        |
                 A------+
E-------+        |      |
        E--------+      |
D-------+               |
                        A
C-------+               |
        C--------+      |
B-------+        |      |
                 C------+
F-------+        |
        F--------+
(Bye)---+

A. Aardvark 获得冠军,但谁获得了木勺呢?

样例

样例 1

> cat gat_2018.txt
A. Aardvark d. C. Capybara
C. Capybara d. B. Badger
C. Capybara d. F. Flamingo
A. Aardvark d. G. Goat
F. Flamingo d. Bye
E. Echidna d. D. Dolphin
A. Aardvark d. E. Echidna

> python wooden_spoon.py gat_2018.txt
No one wins the wooden spoon.

样例 2

> cat gat_2017.txt
C. Capybara d. A. Aardvark
C. Capybara d. B. Badger
C. Capybara d. F. Flamingo
A. Aardvark d. G. Goat
F. Flamingo d. Bye
E. Echidna d. D. Dolphin
A. Aardvark d. E. Echidna

> python wooden_spoon.py gat_2017.txt
D. Dolphin wins the wooden spoon!

QF: E. Echidna d. D. Dolphin
SF: A. Aardvark d. E. Echidna
F: C. Capybara d. A. Aardvark

样例 3

> python wooden_spoon.py invisible.txt
Could not read file

样例 4

> python wooden_spoon.py
No file specified

[代码]

import sys

class TreeNode:
    def __init__(self, name, parent=None):
        self.name = name
        self.parent = parent
        self.children = []
        self.depth=0

    def defeat(self, node):
        "add a child"
        self.children.append(node)
        node.parent = self # 这一句很必要

    def updateDepth(self):
        count=0
        cnode = self
        while cnode.parent:
            cnode = cnode.parent
            count += 1
        self.depth = count
        return self.depth

def createTree( cc ):
    root=None  # 树根，即最后的赢家, 初始化为None
    nodes = {} # 字典保存所有的参赛者, name:treeNode
    for line in cc: # 读取文件，形成树结构, 赢家为父节点，输家为孩子节点
        a,b = None,None
        aa = [ w.strip() for w in line.split('d.')]
        aname = aa[0]
        if aname in nodes:
            a = nodes[aname]
        else:
            a = TreeNode(aname)
            nodes[aname] = a
        bname = aa[-1]
        if bname in nodes:
            b = nodes[bname]
        else:
            b = TreeNode(bname, a)
            nodes[bname] = b
        a.defeat(b)
       
    for name, player in nodes.items(): # 寻找树根节点，也就是最后的冠军
        if player.parent is None:
            root = player
        else:
            player.updateDepth() # 更新节点深度
    return root,nodes
   

def whoGetSpoon( node, res ):
    # 递归函数
    # 遍历树的所有节点, 将树叶保存到 res 参数字典里, {深度:赛手名字}
    # 最深的树叶节点就是拿木勺的人名(当然Bye除外)
    if len(node.children)==0:
        res[node.depth] = node.name
        return None
    else:
        for c in node.children:
            whoGetSpoon(c, res)

def qfsff( loser ):
    # 顺藤摸瓜，找出四分之一决赛，半决赛，决赛的参与者
    res = [loser] # 拿spoon的失败者
    n = loser
    while n.parent: # 从失败者一路找到冠军, 全部输入列表并返回
        n = n.parent
        res.append(n)
    return res

def main():
    content = None
    if len(sys.argv)<2:
        print("No file specified")
    else:
        try:
            f = open(sys.argv[1])
        except:
            print("Could not read file")
            return None
       
        try:
            content = f.readlines()
        except:
            print("Could not read file")
        finally:
            f.close()
           
    if content:
        root,players = createTree(content)
        whos = {}
        whoGetSpoon( root, whos)
        # print(whos)
        name = whos[max(whos)] # 找到最大深度所对应的名字
        if name=='Bye':
            print("No one wins the wooden spoon.")
        else:
            print("{} wins the wooden spoon! ".format(name))
            ps = qfsff( players[name] )
            if len(ps)>=4:
                print("QF: {} d. {}".format(ps[-3].name, ps[-4].name))
                print("SF: {} d. {}".format(ps[-2].name, ps[-3].name))
                print("F: {} d. {}".format( ps[-1].name, ps[-2].name))
            elif len(ps)==3:
                print("SF: {} d. {}".format(ps[-2].name, ps[-3].name))
                print("F: {} d. {}".format( ps[-1].name, ps[-2].name))
            elif len(ps)==2:
                print("F: {} d. {}".format( ps[-1].name, ps[-2].name))
            else:
                print("No one wins the wooden spoon.")


if __name__ == "__main__":
    main()