💡 Problem Formulation: In a social network, friends can often become unhappy due to various reasons. For instance, if a favorite activity is closed or preferred mutual friends move away. Assume we have information about each friend’s preferences and connections. The goal is to count the number of unhappy friends using Python, given a list of friendship pairs and preferences. If friend A prefers to be with friend B over their current situation, and either A is not B’s friend or B prefers another friend C over A, then A is considered unhappy. The input could be a list where each element has a friend and their preference list, and the output would be an integer representing the total number of unhappy friends.
Method 1: Basic Iteration
An exhaustive search through the network defines basic iteration. This method involves checking each friend’s preferences against their current friendships and counting any mismatches as an unhappy friend. While not the most efficient, it’s straightforward and easy to implement even for beginners.
Here’s an example:
def count_unhappy_friends(friends, preferences):
unhappy_count = 0
for friend, pref in preferences.items():
if not pref or friend not in friends:
continue
current_best_friend = friends[friend]
if pref.index(current_best_friend) > 0:
unhappy_count += 1
return unhappy_count
friends_pairs = {'Alice': 'Bob', 'Charlie': 'Alice', 'Bob': 'Charlie'}
preferences = {'Alice': ['Charlie', 'Bob'], 'Bob': ['Alice'], 'Charlie': ['Bob', 'Alice']}
print(count_unhappy_friends(friends_pairs, preferences))
Output:
2
This code snippet defines a function count_unhappy_friends() that iterates over each friend and their preferred friends list. If their current paired friend is not their top choice, the code increments the unhappy count. In the example, Alice and Bob are each other’s not preferred choice, making both unhappy.
Method 2: Set Comparison
Set comparison leverages Python’s built-in data structures to quickly identify unhappy friends. By turning the preference lists and friendship pairs into sets, one can perform difference operations to find mismatches in expected versus actual friendships.
Here’s an example:
def count_unhappy_friends(friends, preferences):
unhappy_count = 0
for friend in friends:
unhappy_count += set(preferences[friend]) < set(friends[friend])
return unhappy_count
friends_pairs = {'Alice': ['Bob'], 'Charlie': ['Alice'], 'Bob': ['Charlie']}
preferences = {'Alice': ['Charlie', 'Bob'], 'Bob': ['Alice'], 'Charlie': ['Bob', 'Alice']}
print(count_unhappy_friends(friends_pairs, preferences))
Output:
2
In this snippet, the function count_unhappy_friends() uses set operations to determine if a friend’s preference list does not match their respective friend in the friends_pairs dict, thus adding to the unhappy count. This code also reveals Alice and Bob as unhappy for the same reasons as method 1.
Method 3: Graph Theory
Utilizing concepts from graph theory can also solve this problem by building a directed graph and traversing it to identify unhappy friends. It’s a more advanced technique that scales well with larger datasets.
Here’s an example:
def count_unhappy_friends(friends, preferences):
unhappy_count = 0
# Create a directed graph and traverse it
for friend in friends:
preferred_friend = preferences[friend][0] # Assume top of the list is most preferred
if preferred_friend != friends[friend]:
unhappy_count += 1
return unhappy_count
friends_pairs = {'Alice': 'Bob', 'Charlie': 'Alice', 'Bob': 'Charlie'}
preferences = {'Alice': ['Charlie', 'Bob'], 'Bob': ['Alice'], 'Charlie': ['Bob', 'Alice']}
print(count_unhappy_friends(friends_pairs, preferences))
Output:
2
This code utilizes graph theory principles by treating the friendship pairs as directed edges and preferences as desired edges. The function count_unhappy_friends() traverses the graph, comparing the actual friends with the top preference and tallying up any differences as unhappiness.
Method 4: Optimized Mapping
Mapping relationships into a format that’s fast to look up can lead to a more optimized and faster solution. It usually involves transforming the data structure into a hash map or dictionary for quicker comparison.
Here’s an example:
def count_unhappy_friends(friends, preferences):
unhappy_count = 0
preference_map = {f: set(prefs) for f, prefs in preferences.items()}
for friend, friend_of in friends.items():
if friend in preference_map and friend_of not in preference_map[friend]:
unhappy_count += 1
return unhappy_count
friends_pairs = {'Alice': 'Bob', 'Charlie': 'Alice', 'Bob': 'Charlie'}
preferences = {'Alice': ['Charlie', 'Bob'], 'Bob': ['Alice'], 'Charlie': ['Bob', 'Alice']}
print(count_unhappy_friends(friends_pairs, preferences))
Output:
2
This code creates a mapping of each friend to their set of preferred friends preference_map, allowing for fast lookups. The function count_unhappy_friends() iterates through the friend pairs and consults the map, incrementing the unhappy count if there’s a mismatch.
Bonus One-Liner Method 5: Functional Approach
The functional approach in Python, while sometimes less readable, can allow for a concise one-liner to solve the problem using functions like map() and filter().
Here’s an example:
friends_pairs = {'Alice': 'Bob', 'Charlie': 'Alice', 'Bob': 'Charlie'}
preferences = {'Alice': ['Charlie', 'Bob'], 'Bob': ['Alice'], 'Charlie': ['Bob', 'Alice']}
print(sum(1 for f, prefs in preferences.items() if friends_pairs.get(f) not in prefs))
Output:
2
The one-liner uses a generator expression to iterate through preferences.items(), checking if the friend pair is not within the preference list and sums up the results to find the count of unhappy friends.
Summary/Discussion
- Method 1: Basic Iteration. Easy to understand and implement. It is suitable for small datasets but might not scale well due to its O(n^2) complexity.
- Method 2: Set Comparison. Leverages Python’s efficient set operations. It’s more efficient than basic iteration and is also quite readable. However, large sets might consume more memory.
- Method 3: Graph Theory. Ideal for large and complex networks. It allows for sophisticated analyses and scaling with data size. It may, however, be overkill for simpler or smaller-scale problems.
- Method 4: Optimized Mapping. Provides fast access and comparison. It’s more optimized than the basic approach but requires additional memory for the map.
- Bonus Method 5: Functional Approach. Extremely concise. Offers a “Pythonic” way to solve the problem in a single line. It could be difficult for some to understand and debug if not familiar with functional programming paradigms.