在Checkio上做測試女嘲，到了Node Disconnected Users這一個(gè)題杖玲±堆幔花了半天時(shí)間才勉強(qiáng)通過玄叠，先記錄在這里拓提。
題目
Gridland的市長利用網(wǎng)絡(luò)給市民發(fā)送緊急信息读恃，但是這個(gè)網(wǎng)絡(luò)總是存在問題，常常一個(gè)節(jié)點(diǎn)會(huì)發(fā)生故障代态，導(dǎo)致網(wǎng)路不通暢寺惫。這個(gè)時(shí)候就需要采用信鴿來傳遞信息。但是不同的節(jié)點(diǎn)對于網(wǎng)絡(luò)的影響是不一致的蹦疑，當(dāng)故障發(fā)生的時(shí)候西雀，市長需要根據(jù)發(fā)生故障的節(jié)點(diǎn)和發(fā)送信息的地點(diǎn)來判斷需要信鴿的數(shù)量。因此歉摧，你的任務(wù)是幫助市長算出發(fā)送故障時(shí)的信鴿需求量艇肴。如下圖所示，當(dāng)C節(jié)點(diǎn)發(fā)生故障的時(shí)候叁温，從A處的信息不能通過網(wǎng)絡(luò)傳到C和D點(diǎn)再悼，所以C和D點(diǎn)的用戶都需要接收信鴿。
采用如下的方式來表示這個(gè)網(wǎng)絡(luò)及故障情況：
- 網(wǎng)絡(luò)的連接情況表示為：
[['A','B'],['B','C'],['C','D']] - 每個(gè)地方的用戶數(shù)用一個(gè)字典來表示：
{'A':10,'B':20,'C':30,'D':40} - 發(fā)信息地點(diǎn)用字符表示：如
'A','B','C','D'之中選一個(gè) - 故障發(fā)生節(jié)點(diǎn)用列表表示：A點(diǎn)發(fā)生故障為
['A']膝但，AB同時(shí)發(fā)生故障為['A','B']
網(wǎng)絡(luò)圖
def disconnected_users(net, users, source, crushes):
node_name = list(users.keys()) #網(wǎng)絡(luò)節(jié)點(diǎn)名稱
node_name.remove(source) #去掉發(fā)信息的節(jié)點(diǎn)
#去掉故障節(jié)點(diǎn)
for node in crushes:
if node != source:
node_name.remove(node)
#故障后網(wǎng)絡(luò)中剩余的網(wǎng)絡(luò)鏈接數(shù)冲九，記錄在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[:] #這里如果讓后面的函數(shù)改變targ的值的話，會(huì)導(dǎo)致遍歷不到所有元素跟束。所以復(fù)制一個(gè)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')
如上的代碼基于的邏輯是：
- 將發(fā)生故障的節(jié)點(diǎn)和發(fā)信地點(diǎn)先去除莺奸，剩余的地點(diǎn)放在一個(gè)列表中，后面來判斷這個(gè)列表中的地點(diǎn)是否能通過網(wǎng)絡(luò)收到信冀宴，如果能夠憾筏，就在列表中去除
- 在正常網(wǎng)絡(luò)列表中，將發(fā)生故障的連接去除花鹅，能否通信需要靠連接狀況來判斷
- 寫一個(gè)遞歸函數(shù)來判斷某點(diǎn)網(wǎng)絡(luò)連接狀況氧腰，因?yàn)橹苯舆B接的可以馬上判斷出來，而二級/三級等不直接的連接，需要靠遞歸去判斷
- 去除掉連接成功的節(jié)點(diǎn)古拴，剩下的就是不能連接成功的節(jié)點(diǎn)
- 計(jì)算不能連接成功的節(jié)點(diǎn)的用戶數(shù)（需要加上之前去除掉的故障節(jié)點(diǎn)的用戶數(shù)）
如下貼一些其他人的代碼：
代碼一：
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, [])])
