
help me on task 4.4
Here is my code and it works file for the basic test, as well as first three of advanced.
but when it came to the following one
break_rings(({1,9},{1,2},{8,5},{4,6},{5,6},{8,1},{3,4},{2,6},{9,6},{8,4},{8,3},{5,7},{9,7},{2,3},{1,7},))
my answer is 6, but the correct one is 5.
When I check my result, and I don't know why it could be 5.so just wonder can any one help me? Thanks in advanced
my algrithm is as follows: 1. make a dict using ring number as key, and it connections as value. 2. found the ring with most link. 3. break it, and remove all connection from the input value.
repeat the same procedure until no connection exists.
code:
def sepringwithmostlink(rings, flaglist, av): # now we initialize the ring dict rltdict = {} cntlist = [0] * av for i in range(1, av+1): rltdict[i] = [] for item in rings: for element in item: # print(element, item) cntlist[element1] += 1 rltdict[element].append(list(item))
# get the ring with most link b_index = cnt_list.index(max(cnt_list)) # set the cnt list to 0 flag_list[b_index] = 1 # all links on this ring bt = rlt_dict[b_index+1] # remove all links from link for item in bt: # print(set(item)) print(item) if set(item) in rings: rings.remove(set(item)) elif tuple(item) in rings: rings.remove(tuple(item)) else: rings.remove(item) print('current connections are:', rings) print('now we want to breaker ring NO.: ',b_index) print('1 means the seperated ring: ',flag_list) # print(rlt_dict) print('Total number of links are', cnt_list) print('') return rings, flag_list
def breakrings(rings): av = max([max(a) for a in rings]) cntlist = [0] * av flaglist = [0] * av ringl = list(rings) while(len(ringl)): ringl, flaglist = sepringwithmostlink(ringl,flag_list,av)
return flag_list.count(1)
debug information for each step:
[9, 1] [1, 2] [8, 1] [1, 7] current connections are: [{8, 5}, {4, 6}, {5, 6}, {3, 4}, {2, 6}, {9, 6}, {8, 4}, {8, 3}, {5, 7}, {9, 7}, {2, 3}] now we want to breaker ring NO.: 0 1 means the seperated ring: [1, 0, 0, 0, 0, 0, 0, 0, 0]
Total number of links are [4, 3, 3, 3, 3, 4, 3, 4, 3]
[4, 6] [5, 6] [2, 6] [9, 6] current connections are: [{8, 5}, {3, 4}, {8, 4}, {8, 3}, {5, 7}, {9, 7}, {2, 3}] now we want to breaker ring NO.: 5 1 means the seperated ring: [1, 0, 0, 0, 0, 1, 0, 0, 0]
Total number of links are [0, 2, 3, 3, 3, 4, 2, 3, 2]
[3, 4] [8, 3] [2, 3] current connections are: [{8, 5}, {8, 4}, {5, 7}, {9, 7}] now we want to breaker ring NO.: 2 1 means the seperated ring: [1, 0, 1, 0, 0, 1, 0, 0, 0]
Total number of links are [0, 1, 3, 2, 2, 0, 2, 3, 1]
[8, 5] [5, 7] current connections are: [{8, 4}, {9, 7}] now we want to breaker ring NO.: 4 1 means the seperated ring: [1, 0, 1, 0, 1, 1, 0, 0, 0]
Total number of links are [0, 0, 0, 1, 2, 0, 2, 2, 1]
[8, 4] current connections are: [{9, 7}] now we want to breaker ring NO.: 3 1 means the seperated ring: [1, 0, 1, 1, 1, 1, 0, 0, 0]
Total number of links are [0, 0, 0, 1, 0, 0, 1, 1, 1]
[9, 7] current connections are: [] now we want to breaker ring NO.: 6 1 means the seperated ring: [1, 0, 1, 1, 1, 1, 1, 0, 0]
Total number of links are [0, 0, 0, 0, 0, 0, 1, 0, 1]
O so total seperated ring is 6