First clear solution for How to Find Friends by Sim0000 - python coding challenges

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

First solution in Clear category for How to Find Friends by Sim0000

def check_connection(network, first, second):
    setlist = []
    for connection in network:
        s = ab = set(connection.split('-'))
        # unify all set related to a, b
        for t in setlist[:]: # we need to use copy
            if t & ab:       # check t include a, b
                s |= t
                setlist.remove(t)
        setlist.append(s)    # only s include a, b
    return any(set([first, second]) <= s for s in setlist)



if __name__ == '__main__':
    #These "asserts" using only for self-checking and not necessary for auto-testing
    assert check_connection(
        ("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
         "scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
        "scout2", "scout3") == True, "Scout Brotherhood"
    assert check_connection(
        ("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
         "scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
        "super", "scout2") == True, "Super Scout"
    assert check_connection(
        ("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
         "scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
        "dr101", "sscout") == False, "I don't know any scouts."

June 4, 2014

Comments:

veky on June 4, 2014, 9:09 a.m.
Nice. BTW, there are set literals in Python: set([first, second]) -> {first, second}.

Sim0000 on June 4, 2014, 3:49 p.m.
Thank you.

FanHuang on Aug. 15, 2014, 6:26 a.m.
excuse me but what does the "|=" mean?

Sim0000 on Aug. 16, 2014, 9:22 a.m.
|= is set operation update. A = {1,2,3} and B = {3,4,5}, then result of A |= B is A = {1,2,3,4,5}. A |= B is same as A.update(B) or A = A | B or A = A.union(B). see <a href="https://docs.python.org/3.3/library/stdtypes.html#set">document</a>.

katamave on Feb. 14, 2021, 8:04 p.m.
Thanks for this. :)

nathan.l.cook on Oct. 2, 2014, 3:06 a.m.
Very clean! I like the use of t as a temporary, and cleaning it out after the union command.

Sim0000 on Nov. 18, 2014, 12:40 a.m.
Thank you :-)

unidwell on Nov. 17, 2014, 9:42 p.m.
Lovely m8 :-) Super idea to use the sets for complete sub-graphs (if something is completely connected there is no need to talk (i.e. store) about the connections, the set of nodes is enough) and complete sub-graphs are transitive envelopes that contain all possible routes between a in b in a symmetrical graph :-)

Sim0000 on Nov. 18, 2014, 12:41 a.m.
Thank you. Good explanation :-)

William.Forever on Dec. 9, 2014, 5:14 p.m.
Can not imagine such a way like that， I always thought set() is something for removing duplicate。

forrest1988 on Jan. 18, 2015, 3:01 p.m.
Short and clear, point from me.

Peter.White on April 7, 2015, 11:18 a.m.
Isn't ab redundant on lines 4 and 7? The way I see it: <pre class='brush: python'>s = ab # line 4 if t & s: # s == ab on line 7, hasn't changed </pre>

kryksyh on April 15, 2015, 4:52 p.m.
Good, same approach as mine, but implemented much better.

mlb00 on July 21, 2015, 11:46 p.m.
Could someone please explain line 11? Thanks!

dsethlewis on July 31, 2015, 6:38 a.m.
I can't, but I'd also love an explanation.

ivang on Aug. 22, 2015, 8:41 p.m.
It basically checks whether the set comprised of nodes "first" and "second" is a subset of any set in setlist. If it is, then there must be a relation between "first" and "second", otherwise there is none.

ivang on Aug. 22, 2015, 8:45 p.m.
It basically checks whether the set comprised of nodes (here "drones") "first" and "second" is a subset of any set in setlist. If it is, then there must be a relation between "first" and "second", otherwise there isn't.

harshagowdas on Sept. 10, 2015, 11:07 p.m.
brilliant!

Sedfer on Oct. 29, 2015, 7:43 p.m.
Nice and clear. I learned a lot from your solution, thanks!

mxmaslin on Feb. 21, 2016, 12:05 p.m.
nested loop. why?

Sim0000 on Feb. 21, 2016, 1:45 p.m.
Because transitive law. When we have known a-c, b-d and we become to know a-b, then we get a-b-c-d, where a-b represents a is related to b. Inner loop is used to scan [a-c, b-d]. I use Python set to represent relations. By the way, why do you thumb down my solution?

mxmaslin on Feb. 21, 2016, 5:37 p.m.
because it's over-complex. here's more clear and effective one: <a href="http://www.checkio.org/mission/find-friends/publications/mxmaslin/python-3/first/share/c0d89e60264b5de2fae092ff73616ca2/">http://www.checkio.org/mission/find-friends/publications/mxmaslin/python-3/first/share/c0d89e60264b5de2fae092ff73616ca2/</a>

Sim0000 on Feb. 22, 2016, 1:39 p.m.
Your code is very incomplete. See my comment of your code :-)

wangzhelee on Feb. 23, 2016, 3:42 p.m.
Could you tell me what is the difference between setlist[:] and setlist in that loop？

ljy95135 on April 18, 2016, 12:09 p.m.
if t & ab: # check t include a, b s |= t setlist.remove(t) wow,Learn it. It can omit one loop for me.

yun_zynb on July 7, 2016, 5:01 a.m.
why we need to use copy at 6th line? I tried both (use copy and not) at this question, and both are work. Could someone explain the difference?

Sim0000 on Aug. 10, 2016, 1:56 a.m.
In general, we should not remove list element in for loop. Read <a href="http://stackoverflow.com/questions/10665591/how-to-remove-list-elements-in-a-for-loop-in-python">here</a>.

Lukasz.Dolata on Aug. 9, 2016, 11:51 a.m.
Really clever solution

k.shogo on April 27, 2017, 11:10 p.m.
it's great

przemyslaw.daniel on Oct. 31, 2017, 4:48 p.m.
This is sad. Even the best solution doesn't answer the question 'How to find friends?'. I'll ask someone else then :-)

soloshowing on June 3, 2018, 12:37 p.m.
I cannot understand. Can you please explain it more clearly? Thanks

murtagy on Dec. 24, 2018, 8:09 p.m.
Well, he takes a connection splitting it in 2 elements. and adds it to set, So you have 2 elements in set for 1 connection. Later he takes next one and checks if any member of connection is in set already, if not he adds it as another set. So members who are connected are added to one set At the end, when you build all sets of people who have common friens, you just need to check if 2 are in the same set That's how i see it.

danersow on Jan. 30, 2020, 2:35 p.m.
I learned something new by this solution

igharok on Feb. 19, 2020, 2:17 p.m.
Thanks for set operators presentation!

majusmisiak on Aug. 31, 2021, 8:28 p.m.
Seems that in the worst case (no connections, all pairs separate) performance would be O(N^2). Using disjoint set, this could be done in (almost) O(N) -- <a href="https://py.checkio.org/mission/find-friends/publications/majusmisiak/python-3/clean-approach-using-disjoint-set/">https://py.checkio.org/mission/find-friends/publications/majusmisiak/python-3/clean-approach-using-disjoint-set/</a>

Sim0000 on Sept. 3, 2021, 9:55 p.m.
How about my another <a href="https://py.checkio.org/mission/find-friends/publications/Sim0000/python-3/dict-and-set/">solution</a>?

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.