autotest
Extra
Test 1/1
Your result: 4
Right result: 3
break_rings(({8,7},{1,9},{2,7},{3,6},{1,7},{5,7},{3,4},{9,5},{9,6},{3,5},))
console out
>>> break_rings(({8,7},{1,9},{2,7},{3,6},{1,7},{5,7},{3,4},{9,5},{9,6},{3,5},))
[[8, 7], [9, 1], [2, 7], [3, 6], [1, 7], [5, 7], [3, 4], [9, 5], [9, 6], [3, 5]]
ring_count: {1: 2, 2: 1, 3: 3, 4: 1, 5: 3, 6: 2, 7: 4, 8: 1, 9: 3}
ring_count: {1: 2, 2: 1, 3: 3, 4: 1, 5: 3, 6: 2, 7: 4, 8: 1, 9: 3}
max: 7
ring_list: [[8], [9, 1], [2], [3, 6], [1], [5], [3, 4], [9, 5], [9, 6], [3, 5]]
ring_count: {1: 2, 2: 1, 3: 3, 4: 1, 5: 3, 6: 2, 8: 1, 9: 3}
ring_count: {1: 2, 2: 1, 3: 3, 4: 1, 5: 3, 6: 2, 8: 1, 9: 3}
max: 3
ring_list: [[8], [9, 1], [2], [1], [5], [9, 5], [9, 6]]
ring_count: {1: 2, 2: 1, 5: 2, 6: 1, 8: 1, 9: 3}
ring_count: {1: 2, 2: 1, 5: 2, 6: 1, 8: 1, 9: 3}
max: 9
ring_list: [[8], [2], [1], [5]]
ring_count: {8: 1, 1: 1, 2: 1, 5: 1}
<<< 3
code
def break_rings(rings):
rings_list = []
removed = 0
for ring in rings:
if len(ring) == 2: rings_list.append(list(ring))
print(rings_list)
len_ = len(rings)
while max(count_rings(rings_list,len_).values()) > 1:
count = count_rings(rings_list,len_)
max_ = max(count, key=count.get)
print('max: ',max_)
rings_list = update_rings(rings_list, max_)
removed += 1
for i in rings_list:
if len(i) > 1: removed += 1
return removed
def count_rings(rings, len_):
ring_count = {}
for i in range(1,len_+1):
for ring in rings:
if i in ring:
try:
ring_count[i] += 1
except KeyError:
ring_count.update({i: 1})
print('ring_count: ',ring_count)
return ring_count
def update_rings(rings, remove):
rings_list = []
for ring in rings:
if ring[0] == remove: continue
try:
ring.remove(remove)
rings_list.append(list(ring))
except ValueError:
rings_list.append(list(ring))
print('ring_list: ',rings_list)
return rings_list
if __name__ == '__main__':
# These "asserts" using only for self-checking and not necessary for auto-testing
assert break_rings(({1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {4, 6})) == 3, "example"
assert break_rings(({1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4})) == 3, "All to all"
assert break_rings(({5, 6}, {4, 5}, {3, 4}, {3, 2}, {2, 1}, {1, 6})) == 3, "Chain"
assert break_rings(({8, 9}, {1, 9}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {8, 7})) == 5, "Long chain"
From: http://www.checkio.org/mission/break-rings/solve/
HTTP_USER_AGENT:
Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/44.0.2403.157 Safari/537.36
Created at: 2015/09/05 15:54; Updated at: 2015/09/07 11:16