|
1
|
|
|
from itertools import combinations |
|
2
|
|
|
|
|
3
|
|
|
|
|
4
|
|
|
def break_rings(rings): |
|
5
|
|
|
elements = set([j for i in rings for j in i]) |
|
6
|
|
|
for i in range(1, len(rings) - 1): |
|
7
|
|
|
for j in combinations(elements, i): |
|
8
|
|
|
if not [k for k in rings if not set(k).intersection(j)]: |
|
9
|
|
|
return len(j) |
|
10
|
|
|
|
|
11
|
|
|
|
|
12
|
|
|
if __name__ == "__main__": # pragma: no cover |
|
13
|
|
|
# These "asserts" using only for self-checking and not necessary for |
|
14
|
|
|
# auto-testing |
|
15
|
|
|
assert break_rings(({1, 2}, {2, 3}, {3, 4}, |
|
16
|
|
|
{4, 5}, {5, 6}, {4, 6})) == 3, "example" |
|
17
|
|
|
assert break_rings(({1, 2}, {1, 3}, {1, 4}, {2, 3}, |
|
18
|
|
|
{2, 4}, {3, 4})) == 3, "All to all" |
|
19
|
|
|
assert break_rings(({5, 6}, {4, 5}, {3, 4}, {3, 2}, |
|
20
|
|
|
{2, 1}, {1, 6})) == 3, "Chain" |
|
21
|
|
|
assert break_rings(({8, 9}, {1, 9}, {1, 2}, {2, 3}, {3, 4}, |
|
22
|
|
|
{4, 5}, {5, 6}, {6, 7}, {8, 7})) == 5, "Long chain" |
|
23
|
|
|
|
KenMercusLai /
checkio
