Checkio笔记 - Node Disconnected Us

在Checkio上做测试，到了Node Disconnected Users这一个题。花了半天时间才勉强通过，先记录在这里。

题目

Gridland的市长利用网络给市民发送紧急信息，但是这个网络总是存在问题，常常一个节点会发生故障，导致网路不通畅。这个时候就需要采用信鸽来传递信息。但是不同的节点对于网络的影响是不一致的，当故障发生的时候，市长需要根据发生故障的节点和发送信息的地点来判断需要信鸽的数量。因此，你的任务是帮助市长算出发送故障时的信鸽需求量。如下图所示，当C节点发生故障的时候，从A处的信息不能通过网络传到C和D点，所以C和D点的用户都需要接收信鸽。
采用如下的方式来表示这个网络及故障情况：

• 网络的连接情况表示为：[['A','B'],['B','C'],['C','D']]
• 每个地方的用户数用一个字典来表示：{'A':10,'B':20,'C':30,'D':40}
• 发信息地点用字符表示：如'A','B','C','D'之中选一个
• 故障发生节点用列表表示：A点发生故障为['A']，AB同时发生故障为['A','B']

网络图

def disconnected_users(net, users, source, crushes):
    
    node_name = list(users.keys()) #网络节点名称
    node_name.remove(source) #去掉发信息的节点
    
    #去掉故障节点
    for node in crushes:
        if node != source:
            node_name.remove(node)
    
    #故障后网络中剩余的网络链接数，记录在net列表中
    for connect in net:
        for crush in crushes:
            if crush in connect:
                net.remove(connect)

    def connect_node(sours, remain, targ):
        org_targ = targ[:] #这里如果让后面的函数改变targ的值的话，会导致遍历不到所有元素。所以复制一个org_targ列表
        for node in org_targ:
            if [sours,node] in remain or [node,sours] in remain:
                targ.remove(node)
                connect_node(node, remain, targ)    
        return targ

    num = 0
    for node in connect_node(source, net, node_name):
        num += users[node]
    for node in crushes:
        num += users[node]
    return num

if __name__ == '__main__':
    #These "asserts" using only for self-checking and not necessary for auto-testing
    assert disconnected_users([
        ['A', 'B'],
        ['B', 'C'],
        ['C', 'D']
    ], {
        'A': 10,
        'B': 20,
        'C': 30,
        'D': 40
    },
        'A', ['C']) == 70, "First"

    assert disconnected_users([
        ['A', 'B'],
        ['B', 'D'],
        ['A', 'C'],
        ['C', 'D']
    ], {
        'A': 10,
        'B': 0,
        'C': 0,
        'D': 40
    },
        'A', ['B']) == 0, "Second"

    assert disconnected_users([
        ['A', 'B'],
        ['A', 'C'],
        ['A', 'D'],
        ['A', 'E'],
        ['A', 'F']
    ], {
        'A': 10,
        'B': 10,
        'C': 10,
        'D': 10,
        'E': 10,
        'F': 10
    },
        'C', ['A']) == 50, "Third"

    print('Done. Try to check now. There are a lot of other tests')

如上的代码基于的逻辑是：

• 将发生故障的节点和发信地点先去除，剩余的地点放在一个列表中，后面来判断这个列表中的地点是否能通过网络收到信，如果能够，就在列表中去除
• 在正常网络列表中，将发生故障的连接去除，能否通信需要靠连接状况来判断
• 写一个递归函数来判断某点网络连接状况，因为直接连接的可以马上判断出来，而二级/三级等不直接的连接，需要靠递归去判断
• 去除掉连接成功的节点，剩下的就是不能连接成功的节点
• 计算不能连接成功的节点的用户数（需要加上之前去除掉的故障节点的用户数）

如下贴一些其他人的代码：

代码一：

def disconnected_users(net, users, source, crushes):
    if source in crushes: return sum(users.values())
    temp = [source]
    goodnode = []
    while temp:
        node = temp.pop(0)
        goodnode.append(node)
        for i,j in net:
            if i == node and j not in crushes and j not in goodnode:
                temp.append(j)
            elif j == node and i not in crushes and i not in goodnode:
                temp.append(i)
    return sum(users.values()) - sum(users[node] for node in goodnode)

代码二

def disconnected_users(net, users, source, crushes):
    nodes = set()
    for link in net:
        nodes |= set(link)
    working_nodes = set(source) - set(crushes)
    while True:
        untested_links = []
        no_links = True
        for node1, node2 in net:
            if node1 in working_nodes:
                if node2 not in crushes:
                    working_nodes.add(node2)
                    no_links = False
            elif node2 in working_nodes:
                if node1 not in crushes:
                    working_nodes.add(node1)
                    no_links = False
            else:
                untested_links.append([node1, node2])
        if no_links:
            break
        net = untested_links
    nodes -= working_nodes
    unreceived_emails = 0
    for node in nodes:
        unreceived_emails += users[node]
    return unreceived_emails

代码三

def subnetworks(net, crushes):
    result = {x: {x} for x in sum(net, []) if x not in crushes}
    for a, b in net*len(net):
        if set(crushes) & {a, b}: continue
        result[a] |= result[b] | {a, b}
        result[b] |= result[a] | {a, b}
    return result

def disconnected_users(net, users, source, crushes):
    sum_all, subs = sum(users.values()), subnetworks(net, crushes)
    return sum_all - sum([users[x] for x in subs.get(source, [])])