First clear solution for How to Find Friends by frantisek.jahoda - 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 frantisek.jahoda

def check_connection(network, first, second):
    friends = {first}
    while True:
        if second in friends:
            return True
        for edge in network:
            a, b = edge.split('-')
            if a in friends and b not in friends:
                friends.add(b)
                break
            if b in friends and a not in friends:
                friends.add(a)
                break
        else:
            return False

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."

April 4, 2016

Comments:

wervyn on April 15, 2016, 7:05 p.m.
<p>This processes the entire network on every iteration, which can lead to some nasty O(n^2) degenerate cases for performance</p>

frantisek.jahoda on April 15, 2016, 7:30 p.m.
<p>It's even bit worse. The complexity is O(mn) where n is number of vertices and m number of edges. The best complexity I know is O(m + n) so for densely connected graph it can be O(n^2). <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Breadth first search</a></p>

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.