How to break enough rings to free so as to get the maximum number of rings possible

checkio-break-rings.py

# -*- coding: UTF-8 -*-

# https://py.checkio.org/mission/break-rings/

# https://py.checkio.org/mission/break-rings/publications/schcriher/python-3/cute-problem/

# All of the rings are numbered and you are told which of the rings are connected. This
# information is given as a sequence of sets. Each set describes the connected rings.
# For example: {1, 2} means that the 1st and 2nd rings are connected. You should count
# how many rings we need to break to get the maximum of separate rings. Each of the
# rings are numbered in a range from 1 to N, where N is total quantity of rings.

from copy import deepcopy
from functools import reduce

def get(rings, connections=None):
    data = {}
    for r in rings:
        if len(r) == 2:
            for n in r:
                if n in data:
                    data[n] += 1
                else:
                    data[n] = 1
    if data:
        if connections is None:
            m = max(data.values())
        else:
            m = connections
        for n, c in data.items():
            if c == m:
                yield n

def get_neighbor(rings, n):
    for r in rings:
        if len(r) == 2 and n in r:
            a, b = r
            yield a if b == n else b

def get_conn(rings, n):
    c = 0
    for r in rings:
        if len(r) == 2 and n in r:
            c += 1
    return c

def remove(rings, n):
    for r in rings:
        if n in r:
            r.remove(n)

def remove_from_set(rings, to_break, already_break):
    num_break = 0
    not_break = set()

    for n in get(rings, 1):  # end of rings, not break
        if n not in to_break:
            not_break.add(n)
            for nn in get_neighbor(rings, n):
                if nn not in not_break:
                    to_break.add(nn)

    for n in to_break:
        c1 = n not in not_break
        c2 = n not in already_break
        c3 = get_conn(rings, n) > 1
        if c1 and c2 and c3:
            remove(rings, n)
            num_break += 1
            already_break.add(n)

    return num_break

def break_rings(original_rings):
    t = len(reduce(set.union, original_rings))
    b = []
    for max_conn_of_max in (4, t + 1):
        for conn_to_remove in ([3, 2], [3], [2]):

            rings = deepcopy(original_rings)
            already_break = set()
            num_break = 0

            while True:
                bb = 0
                for conn in conn_to_remove:
                    to_break = set()

                    for n in get(rings):
                        if get_conn(rings, n) > max_conn_of_max:
                            to_break.add(n)

                    conn_list = list(get(rings, conn))
                    if len(conn_list) > 3:
                        for n in conn_list:
                            to_break.add(n)

                    bb += remove_from_set(rings, to_break, already_break)

                if bb:
                    num_break += bb
                else:
                    break

            ways = [(num_break, deepcopy(rings), n) for n in get(rings)]
            if ways:
                nums_breaks = []
                while ways:
                    num_break, rings, n = ways.pop()

                    for r in rings:
                        if n in r:
                            r.remove(n)
                    num_break += 1
                    s = list(get(rings))
                    if s:
                        for n in s:
                            ways.append((num_break, deepcopy(rings), n))
                    else:
                        nums_breaks.append(num_break)
                num_break = min(nums_breaks)  # in ways the initial value is stored

            b.append(num_break)

    nb = min(b)
    if nb >= t:
        nb = t - 1
    return nb

if __name__ == '__main__':
    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"
    assert break_rings(({8, 7}, {1, 9}, {2, 7}, {3, 6}, {1, 7}, {5, 7}, {3, 4}, {9, 5},
        {9, 6}, {3, 5})) == 3, "extra test 1"
    assert 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})) == 5, "extra test 2"
    assert break_rings(({1, 3}, {3, 4}, {3, 5}, {4, 6}, {6, 7}, {8, 3}, {8, 1}, {2, 6},
        {8, 4}, {9, 5}, {4, 5}, {1, 7})) == 5, "extra test 3"
    assert break_rings(({3, 4}, {5, 6}, {2, 7}, {1, 5}, {2, 6}, {8, 4}, {1, 7}, {4, 5},
        {9, 5}, {2, 3}, {8, 2}, {2, 4}, {9, 6}, {5, 7}, {3, 6}, {1, 3})) == 5, "extra test 4"
    assert break_rings(({9, 7}, {9, 6}, {8, 5}, {8, 3}, {8, 9}, {5, 7}, {4, 5}, {8, 4},
        {1, 7}, {9, 4}, {1, 5}, {2, 5}, {4, 6}, {8, 2}, {1, 2}, {2, 4}, {8, 7}, 
        {8, 1})) == 5, "extra test 5"
    assert break_rings(({1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 2}, {1, 6}, {6, 7}, {7, 8},
        {8, 9}, {9, 6}, {1, 10}, {10, 11}, {11, 12}, {12, 13}, {13, 10},{1, 14},
        {14, 15}, {15, 16}, {16, 17}, {17, 14})) == 8, "extra test 6"
    assert break_rings(({1, 4}, {4, 7}, {9, 2}, {2, 6}, {5, 6}, {8, 1}, {3, 7}, {9, 3},
        {3,6}, {8,6}, {1,7}, {2,4}, {1,9}, {8,3}, {9,6})) == 5, "extra test 7"