Rings, links, bits and sets... creative solution for Break Rings by veky - python coding challenges

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

Rings, links, bits and sets... solution in Creative category for Break Rings by veky

break_rings = lambda rings: min(len(set.union(*bits)) for bits in __import__
    ("itertools").product(*([link - {w} for w in link] for link in rings)))

Dec. 31, 2014

Comments:

veky on Dec. 31, 2014, 8:25 p.m.
... how many were going to <a href="http://en.wikipedia.org/wiki/As_I_was_going_to_St_Ives#Lyrics">St. Ives</a>? :-D

fleo0917 on Jan. 6, 2015, 6:42 p.m.
Is there anyone who want to explain me how dose these two lines work?

veky on Jan. 6, 2015, 8:09 p.m.
Is it ok if I try? :-) The main point of the algorithm is that in every cluster ("link"), you surely need to break all but one ring. For example, if you have four rings clustered together, and they are not Borromean (as Bryukh explained:), then you need to break at least three of them. Now, for every link given, the algo generates the all possible link^ (link with one w from link removed), and itertools.product makes all possible combinations of all such possible link^s. Then len of set.union counts how many are broken alltogether in a single possibility. And min gives minimal number of broken rings over all possibilities. So, in short: break_rings gives the minimal number of total broken rings, considering that in every link, at most one must remain unbroken. Clearer?

Winandfx on Feb. 22, 2015, 10:24 p.m.
i've opened Wiki and it says that Borromean rings are a special case of a Brunnian link with 3 rings.

veky on Feb. 22, 2015, 10:51 p.m.
That's nice to know. :-) Thanks for terminology correction.

fleo0917 on Jan. 7, 2015, 12:09 a.m.
oh, I get it now. in every pair of rings, one of them surely must be destroyed. so pick one ring to break from each pairs. and find least destroyed combination. the word "cluster" you mentioned confused me a little. thank you veky

veky on Jan. 7, 2015, 9:42 a.m.
Sorry, that stems from first version of the task, where clusters didn't have to be pairs. They could have more than two rings in it, so you'd have to break three of four, for example, not just "one of these two". It seems the task was changed in the meantime. Of course, if clusters are restricted to having two elements, then the solution can be much simpler. How exactly, I leave to you as a homework. ;-)

fleo0917 on Jan. 7, 2015, 9:47 a.m.
I guess DiZ's solutions is the one. :)

veky on Jan. 7, 2015, 10:45 a.m.
Yeah, about that. :-)

nickie on Feb. 4, 2015, 10:14 a.m.
Brilliantly coded, with the general objection that I raised <a href="http://www.checkio.org/mission/break-rings/publications/DiZ/python-3/cycle/share/1d7fa66e435a5f45f355f6a7451bdd76/#comment-24468">elsewhere</a> (which I'm sure you'll dismiss as part of my already discussed obsession).

veky on Feb. 4, 2015, 11:57 a.m.
Yes. Difference between 2^n and 2^n^2 is academic. :-D

tommycarstensen on April 25, 2015, 2:02 p.m.
Why do I get this error, when I try to run your script? <pre class='brush: python'> ("itertools").product(*([link - {w} for w in link] for link in rings))) TypeError: type object argument after * must be a sequence, not generator </pre> I want to time it and all the other solutions. Hence I was trying to execute it.

GitHub

0 %

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