Bacon Number - codepath/compsci_guides GitHub Wiki

Unit 10 Session 2 Standard (Click for link to problem statements)

Unit 10 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Graph Traversal, BFS, Shortest Path

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What does the adjacency dictionary bacon_network represent?
    • A: It represents a network of actors, where each key is an actor and the corresponding value is a list of actors they have worked with.
  • Q: How do we compute the Bacon Number?
    • A: Kevin Bacon has a Bacon Number of 0, and the Bacon Number of another actor is the shortest path (in terms of connections) from them to Kevin Bacon.
  • Q: What should the function return if the celeb cannot be connected to Kevin Bacon?
    • A: The function should return -1 if no path exists.
HAPPY CASE
Input: 
```python
bacon_network = {
    ""Kevin Bacon"": [""Kyra Sedgewick"", ""Forest Whitaker"", ""Julia Roberts"", ""Tom Cruise""],
    ""Kyra Sedgewick"": [""Kevin Bacon""],
    ""Tom Cruise"": [""Kevin Bacon"", ""Kyra Sedgewick""],
    ""Forest Whitaker"": [""Kevin Bacon"", ""Denzel Washington""],
    ""Denzel Washington"": [""Forest Whitaker"", ""Julia Roberts""],
    ""Julia Roberts"": [""Denzel Washington"", ""Kevin Bacon"", ""George Clooney""],
    ""George Clooney"": [""Julia Roberts"", ""Vera Farmiga""],
    ""Vera Farmiga"": [""George Clooney"", ""Max Theriot""],
    ""Max Theriot"": [""Vera Farmiga"", ""Jennifer Lawrence""],
    ""Jennifer Lawrence"": [""Max Theriot""]
}
print(bacon_number(bacon_network, ""Jennifer Lawrence""))
```
Output:
```markdown
5
Explanation: The path is Jennifer Lawrence -> Max Theriot -> Vera Farmiga -> George Clooney -> Julia Roberts -> Kevin Bacon. Jennifer Lawrence has a Bacon Number of 5.
```

EDGE CASE
Input: 
```python
bacon_network = {
    ""Kevin Bacon"": [""Kyra Sedgewick"", ""Tom Cruise""],
    ""Kyra Sedgewick"": [""Kevin Bacon""],
    ""Tom Cruise"": [""Kevin Bacon""]
}
print(bacon_number(bacon_network, ""Tom Cruise""))
```
Output:
```markdown
1
Explanation: Tom Cruise has worked directly with Kevin Bacon, so his Bacon Number is 1.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Bacon Number problems, we want to consider the following approaches:

  • Breadth First Search (BFS): BFS is ideal for finding the shortest path in an unweighted graph, where the distance between two nodes is defined by the number of edges between them.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use BFS to explore all connections from Kevin Bacon. Start with Kevin Bacon (Bacon Number 0) and traverse the graph by exploring all co-stars. Each actor that is directly connected to Kevin Bacon gets a Bacon Number of 1, and each actor connected to those actors gets a Bacon Number of 2, and so on. If the target actor (celeb) is found during traversal, return their Bacon Number. If no path exists, return -1.

1) Initialize a queue with Kevin Bacon and a Bacon Number of 0.
2) Create a `visited` set to keep track of actors who have already been processed.
3) While the queue is not empty:
   a) Dequeue the current actor and their Bacon Number.
   b) If the current actor is the target `celeb`, return the Bacon Number.
   c) For each co-star of the current actor, if they have not been visited, add them to the queue with a Bacon Number of `bacon_num + 1`.
4) If the queue is exhausted and the `celeb` is not found, return `-1`.

⚠️ Common Mistakes

  • Forgetting to mark actors as visited, which could lead to cycles and infinite loops.
  • Incorrectly calculating the Bacon Number by not incrementing it correctly.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

def bacon_number(bacon_network, celeb):
    # BFS setup
    queue = deque([(""Kevin Bacon"", 0)])  # Start from Kevin Bacon with Bacon Number 0
    visited = set([""Kevin Bacon""])  # Keep track of visited actors
    
    while queue:
        current_actor, bacon_num = queue.popleft()
        
        # If we found the celebrity, return their Bacon Number
        if current_actor == celeb:
            return bacon_num
        
        # Explore all connections (co-stars) of the current actor
        for co_star in bacon_network.get(current_actor, []):
            if co_star not in visited:
                visited.add(co_star)
                queue.append((co_star, bacon_num + 1))
    
    # If no path to Kevin Bacon is found, return -1
    return -1

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input:
bacon_network = {
    ""Kevin Bacon"": [""Kyra Sedgewick"", ""Forest Whitaker"", ""Julia Roberts"", ""Tom Cruise""],
    ""Kyra Sedgewick"": [""Kevin Bacon""],
    ""Tom Cruise"": [""Kevin Bacon"", ""Kyra Sedgewick""],
    ""Forest Whitaker"": [""Kevin Bacon"", ""Denzel Washington""],
    ""Denzel Washington"": [""Forest Whitaker"", ""Julia Roberts""],
    ""Julia Roberts"": [""Denzel Washington"", ""Kevin Bacon"", ""George Clooney""],
    ""George Clooney"": [""Julia Roberts"", ""Vera Farmiga""],
    ""Vera Farmiga"": [""George Clooney"", ""Max Theriot""],
    ""Max Theriot"": [""Vera Farmiga"", ""Jennifer Lawrence""],
    ""Jennifer Lawrence"": [""Max Theriot""]
}

print(bacon_number(bacon_network, ""Jennifer Lawrence""))  # Expected output: 5
print(bacon_number(bacon_network, ""Tom Cruise""))  # Expected output: 1
  • Output:
5
1

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

  • Time Complexity: O(V + E), where V is the number of actors (vertices) and E is the number of connections (edges). Each actor is dequeued and processed once, and each connection (edge) is explored once.
  • Space Complexity: O(V) for the queue and visited set.