I'm working on this function to find a possible friendship between two people. The friendship system works in a transitive way, that is, if A is a friend of B and B is a friend of C, then A is a friend of C. The dictionary stores the initial relationships (like a graph) and the function parameters are the dictionary and the names of the two people you want to identify if they are friends or not.
def findfriendship(people, X, Y):
if Y in people[X] or X in people[Y]:
return True
if len(people[X]) != 0:
for friend in people[X]:
return findfriendship(people, friend, Y)
if len(people[Y]) != 0:
for friend in people[Y]:
return findfriendship(people, X, friend)
return False
This is my code and I was successful in identifying a possible friendship between two people as long as one of them have a list of friends not empty, like this:
friendships = {'Jordan': ['Shaq'], 'Lebron': [], 'Kobe': [], 'Shaq': ['KD'], 'KD': []}
print(findfriendship(friendships, 'KD', 'Jordan')) -> return True
But I can't solve the problem where both have no direct friends, like this:
friendships = {'Jordan': ['Shaq'], 'Lebron': [], 'Kobe': ['KD', 'Lebron'], 'Shaq': ['KD'], 'KD': []}
print(findfriendship(friendships, 'Lebron', 'KD')) -> return False
it returns False, but Kobe is a friend of them both, so they should be friends.
Can you guys help me trying to solve this problem or do you know a similar question so I can understand this type of concept? Thanks for your attention.
Checking if two people are friends would be easy if we could get the full list of friends for either person. Let's write a helper for that:
friendships = {
'Jordan': ['Shaq'], 'Lebron': [],
'Kobe': ['KD', 'Lebron'], 'Shaq': ['KD'], 'KD': [],
"foo": ["bar", "baz"], "bar": [], "baz":[],
}
def buildFriendSet (x, people=None, fSet=None):
people = people or friendships; # default value
fSet = fSet or set([x] + people[x]); # Friend Set
changeDetected = False;
for kPerson, vPersonList in people.items():
personList = [kPerson] + vPersonList;
if fSet.issuperset(personList):
pass;
elif fSet.intersection(personList):
fSet = fSet.union(personList);
changeDetected = True;
if not changeDetected:
return fSet;
return buildFriendSet(x, people, fSet);
print(buildFriendSet('KD'));
# Output: {'Shaq', 'Kobe', 'KD', 'Lebron', 'Jordan'}
print(buildFriendSet('foo'))
# Output: {'baz', 'bar', 'foo'}
Once we can compute the set of friends for any person, checking if two people are friends is easy:
def checkFriends (x, y, people=None):
people = people or friendships; # default value
return (x in people[y] or y in people[x] or
x in buildFriendSet(y, people)
);
print(checkFriends('KD', 'Jordan')); # -> True
print(checkFriends('Lebron', 'KD')); # -> True
print(checkFriends('KD', 'foo')); # -> False
Logic behind buildFriendSet():
We iterate over people and check if the friend-set fSet changes. If no change is detected, then we return fSet unchanged. Else, we keep looking for more friends.
For a given group of close friends, such as any personList above, if everyone in the group is already in fSet, there's no need to change fSet. This corresponds to the .issuperset(.) check.
Otherwise, if at least one person from personList is already in fSet, then by association, everyone else must be in it too! We use .intersection(.) and .union() to check and achieve this, respectively.
Is everyone their own friend?
The above implementation assumes that everyone is their own friend. If such behavior isn't desired, using a simple if-guard and/or fSet.remove(.) should suffice.