Cycle detection creative solution for Break Rings by DiZ - python coding challenges

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

Cycle detection solution in Creative category for Break Rings by DiZ

break_rings=lambda r:min(len(set(c))for c in __import__("itertools").product(*r))

Jan. 5, 2015

Comments:

veky on Jan. 7, 2015, 10:43 a.m.
Yup, that's the one. If elements of r are only pairs, it's simplest. Though it seems not the shortest. ;-) <pre class='brush: python'>break_rings=lambda r:min(map(len,map(set,__import__("itertools").product(*r)))) </pre>

DiZ on Jan. 7, 2015, 11:02 a.m.
There is still shorter ;) <pre class='brush: python'>from itertools import*;break_rings=lambda r:min(map(len,map(set,product(*r)))) </pre>

veky on Jan. 7, 2015, 11:55 a.m.
Ah yes, I often forget about `import*` (That is, I forget that CiO solutions are in global scope:).

nickie on Feb. 4, 2015, 10:06 a.m.
A brilliantly short solution (a bit obfuscated here, for obvious reasons). Horrible, from a graph theoretic perspective, but still brilliantly coded. An ordinary brute force solution would be exponential in the number of vertices (rings). This solution is exponential in the number of edges (links), which in general is quadratic to the number of vertices. Fortunately, the test cases do not contain graphs of 10 rings and 50 links.

altarfinch on Feb. 9, 2015, 1:44 p.m.
I still don't get it, could you explain your awesome code ?

DiZ on Feb. 9, 2015, 2:54 p.m.
While I can give you an explanation of this particular case (2-tuples), Veky wrote <a href="http://www.checkio.org/mission/break-rings/publications/veky/python-3/rings-links-bits-and-sets/#comment-22911">an excellent on general case</a>. I really recommend you to read it ;)

GitHub

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.