Simple Bruteforce clear solution for Break Rings by Pouf - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Simple Bruteforce solution in Clear category for Break Rings by Pouf

from itertools import *

def break_rings(rings):
    highest = max(chain.from_iterable(rings))
    for x in range(1, highest):
        for c in (combinations(range(1, highest+1), x)):
            if max([len(a-set(c)) for a in rings]) == 1:
                return x

March 18, 2015

Comments:

rojeeer on Nov. 19, 2015, 2:53 a.m.
Wow, enumerate algorithm, not efficient but very simple and clear! Thanks!

Pouf on Nov. 19, 2015, 9:31 a.m.
Thanks ! I couldn't get it to work any other way at the time.

rojeeer on Nov. 19, 2015, 2:36 p.m.
Yeah, It is NP-hard problem, analogous to vertex cover problem if you treat rings as graph. I tired two greedy algorithms: A1. The most connective ring (with higest degree) is the ring to be broken A2. The least connective ring (with lowest degree) is the ring to be protected However, In both algorithms, the maximum (or minimum) degree rings may exceeds one. For example, rings: 1--2--3--4--5, if we take algorithm A1, there are three ring {2,3,4} with maximum degree. We cannot break a random one, e.g., if we break 3, then we have to break two other rings, so the number of broken rings is 3. But actually the optimal solution is 2 (just break 2 and 4). An additional flavor we can use is to take neighbours of the maximum degree rings into consideration. In algorithm A1. we should break the one that the sum of its neighbours' degree is minimum. Take the above example, the neighbours of ring 3 is {2,4}, and sum of their degree is 2+2=4, while the sum of neighbours degree of ring 2 and ring 4 is 1+2=3, so we should break 2 or 4. I know these algorithm may be wrong, but when I implemented A2 and it passed all test cases. You can take a look at my first solution :-) My second solution is borrowed from you, hope you will not be unhappy! Forgive my poor english, hope you can understand and have a good day!

GitHub

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!