UnionFind clear solution for How to Find Friends by veky - python coding challenges

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

UnionFind solution in Clear category for How to Find Friends by veky

def check_connection(network, first, second):
    from collections import Counter
    component, rank = {}, Counter()
    def find(x):
        if component.setdefault(x, x) != x:
            component[x] = find(component[x])
        return component[x]
    for edge in network:
        xr, yr = map(find, edge.split("-"))
        if rank[xr] < rank[yr]:
            component[xr] = yr
        else:
            component[yr] = xr
            rank[xr] += rank[xr] == rank[yr]
    return find(first) == find(second)

June 4, 2014

Comments:

Talim42 on June 9, 2014, 10:48 a.m.
Setdefault() returns the key value available in the dictionary and if given key is not available then it will return provided default value. So setdefault(x, x) should be always equal to x, right?

veky on June 9, 2014, 11:15 a.m.
What your first sentence describes is dict.get. dict.setdefault also puts that default value in dict (and returns that copy) if key is missing. <blockquote> So setdefault(x, x) should be always equal to x, right? </blockquote> No. You're mixing keys and values. component.setdefault(x, x) is component[x], being set to x if not existing already.

reddog on July 21, 2014, 7:25 p.m.
Wild answer mate! A little confusing to a stark beginner, never the less I always learn about some new module or built in function from your answers. If you wouldn't mind glancing at mine, I'd love all the feedback available. Cheers

veky on July 22, 2014, 11:11 a.m.
<blockquote> I always learn about some new module or built in function from your answers. </blockquote> That's their purpose, mostly. It saddens me greatly when I see someone poorly and boringly reimplement some of Python's included batteries from scratch (or worse, from C idioms:). <blockquote> If you wouldn't mind glancing at mine, I'd love all the feedback available. </blockquote> It would help if you include the link. I'm not lazy as much as you think, but I get a lot of this kind of request, and since new interface disabled easy seeing of people's solutions from their comments, it's really much easier if I have the link, than waddling through the categories on the official solutions page, looking for your username.

reddog on July 22, 2014, 3:16 p.m.
Here's the link, thanks in advance: <a href="http://www.checkio.org/mission/find-friends/publications/reddog/python-3/first/">http://www.checkio.org/mission/find-friends/publications/reddog/python-3/first/</a> cheers

nickie on Oct. 5, 2014, 10:21 p.m.
Nice implementation of union/find. My only remark is that you could stop the "for edge in network" loop sooner, if it happens that "find(first) == find(second)".

veky on Oct. 6, 2014, 5:28 a.m.
Yes, I agree. But I usually don't think about going below (amortized) linear complexity. :-D This is Clear, not Speedy. ;-)

george.blackthorn on Aug. 10, 2016, 6:52 a.m.
Nice solution. It took me a while before I figure out that the rank Counter object is used to impose a (partial) ordering in the graph components. I think it would work also if you use just direct comparing of the nod values = names as strings (i.e. xr < yr instead of rank[xr] < rank[yr] and rank[xr] += rank[xr] == rank[yr] and rank object itself can be omitted at all). I tested it and it worked. Am I missing an issue with just the string comparison or some point or idea behind the Counter object used? I preferred set operations in my solution if you are insterested: <a href="https://checkio.org/mission/find-friends/publications/george.blackthorn/python-3/components/">https://checkio.org/mission/find-friends/publications/george.blackthorn/python-3/components/</a>

veky on Aug. 10, 2016, 8:10 a.m.
It would also "work" if you had no comparison at all (that is, if you always added left branch to the right). The point of ranks is to keep the tree balanced, so that finding is always fast (logarithmic in the number of elements). [If you want to know more details, go to <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure">https://en.wikipedia.org/wiki/Disjoint-set_data_structure</a> and Ctrl+F "union by rank".] Counter is just a cute way of defaulting to 0... defaultdict(int) would probably clarify that intent better. Your solution is ok, though of course it does no such balancing by rank. But your Python can be improved... for instance, builtin `any` can really help. ;-) Also, `while bool(rels)` is simply `while rels`. while bools its condition anyway.

george.blackthorn on Nov. 4, 2016, 9:42 a.m.
Thanks for the link. It is always interesting to compare an abstract (mathematical) concept with the possible computer implementations. It also made me to look at the Python C source setobject.c code to see how it handles the sets and set operations. Good to consider when complexity matters :-) Also thanks for the hints of improvement of my Python code. I am still getting used to the differences compared to other languages.

veky on Nov. 4, 2016, 10:06 a.m.
If you mean practical complexity, of course. sets are just atrophied dicts, which are just hash tables. But theoretical complexity (worstcase) of hashes is abysmal, of course. :-) Differences depend on which languages you're comparing it to. :-)

GitHub

0 %

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