break rings, autocheck not pass, console = pass
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