Bellman–Ford-ish (short) clear solution for How to Find Friends by StefanPochmann - python coding challenges

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

Bellman–Ford-ish (short) solution in Clear category for How to Find Friends by StefanPochmann

def check_connection(network, first, second):
    team = {first}
    for _ in network:
        for edge in network:
            pair = set(edge.split('-'))
            if pair & team:
                team |= pair
    return second in team

April 16, 2015

Comments:

Mapotoufu on July 22, 2015, 7:02 p.m.
nice coding!! and Why do you use for _ in network? what does it mean?

StefanPochmann on July 25, 2015, 1:51 p.m.
It's a loop that runs as many times as there are edges in the network. If you're wondering about the "_", that's the usual name for something you're not going to use.

alexis12 on Aug. 30, 2015, 8:21 a.m.
Very nice solution! I would like to ask why do we need the outer loop to be executed len(network) times. Thank you!

StefanPochmann on Aug. 30, 2015, 1:16 p.m.
If I'm unlucky with the order of edges, each iteration might only add one person to the team. So I might need as many iterations as there are edges. Similar to <a href="https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm">Bellman-Ford</a>. I could of course stop as soon as nothing changes anymore, but that would require a bit more code.

DiZ on Sept. 3, 2015, 2:25 p.m.
Nice approach. I feared no one else used Bellman-Ford, you proved me wrong ;-)

shuai on Oct. 6, 2015, 3:56 p.m.
OMG. Could you explain this part a little bit? <pre class='brush: python'>if pair & team: team |= pair </pre>

alex-pobeditel-2004 on Oct. 7, 2015, 2 p.m.
'&' stands for intersection (pair & team is not an empty set?), '|=' is a set update operation - i.e. add to team everything 'new' from pair. Looks like this.

shuai on Oct. 7, 2015, 2:01 p.m.
thanks alex!

e-l on March 25, 2016, 7:44 p.m.
Awesome!

dana77 on April 19, 2016, 5:06 p.m.
I just love this solution!

chachafish on April 26, 2016, 7:11 p.m.
Neat solution. Great job!

Thenbacker on Oct. 23, 2016, 1:37 a.m.
Cool solution and educational too! I tend to forget about |= when it comes to set operations.

DeCooper on Sept. 30, 2017, 11:56 a.m.
This is a beauty!

clxnetom on May 5, 2019, 5:34 a.m.
This solution, if I'm not mistaken, creates the whole network. Wouldn't it be possible to insert <pre class='brush: python'>if second in pair: return True </pre> between lines 6 and 7 (when we know that at least one of the nodes in 'pair' is part of 'team') to exit the function as soon as we find the connection? There could be a substantial time save in big network but would there be any downsides (with regard to the task at hand)?

bsquare on Aug. 22, 2019, 8:24 p.m.
Nice solution!

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.