Skip to content

Instantly share code, notes, and snippets.

@schcriher
Created November 23, 2017 20:18
Show Gist options
  • Save schcriher/e7416cbc29eb0e81288c3f98775fb7a8 to your computer and use it in GitHub Desktop.
Save schcriher/e7416cbc29eb0e81288c3f98775fb7a8 to your computer and use it in GitHub Desktop.
How to break enough rings to free so as to get the maximum number of rings possible
# -*- 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"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment