Crafting Survival Gear - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 45 mins
  • 🛠️ Topics: Topological Sorting, Graph Representation

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?
  • What happens if a component is not in gear or supplies?
    • If a component is not in gear or supplies, it cannot be crafted.
  • Can you craft gear in any order?
    • No, the crafting order is determined by the dependencies between components.
HAPPY CASE
Input: 
gear = [""weapon""]
components = [""metal"", ""wood""](/codepath/compsci_guides/wiki/""metal"",-""wood"")
supplies = [""metal"", ""wood"", ""rope""]
Output: [""weapon""]
Explanation: You can craft ""weapon"" because you already have the required components ""metal"" and ""wood.""

EDGE CASE
Input: 
gear = [""weapon"", ""trap""]
components = [""metal"", ""wood""], [""weapon"", ""wire""](/codepath/compsci_guides/wiki/""metal"",-""wood""],-[""weapon"",-""wire"")
supplies = [""metal"", ""wood"", ""wire""]
Output: [""weapon"", ""trap""]
Explanation: First, you craft ""weapon"" because the components ""metal"" and ""wood"" are in your supplies. Then you can craft ""trap"" using ""weapon"" and ""wire.""

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 Topological Sort problems, we want to consider the following approaches:

  • Graph Representation: Treat the gear and components as a directed acyclic graph (DAG), where edges point from components to the gear that depends on them.
  • Kahn’s Algorithm (BFS Topological Sort): Use a queue to process gear in a topological order, ensuring that each gear is crafted after its dependencies are satisfied.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Build a directed acyclic graph (DAG) where the vertices represent gear and the edges represent dependencies between components. Perform topological sorting using BFS to determine the order in which gear can be crafted.

1) Initialize a set `supplies_set` containing all initial supplies.
2) Create a graph (adjacency list) to track which gear depends on others.
3) Use an in-degree array to keep track of how many components are needed to craft each gear.
4) For each gear:
    a) If all its components are in `supplies`, mark it as craftable.
    b) For gear with dependencies, add it to the graph and update the in-degree array.
5) Use a queue to process gear with no dependencies (in-degree == 0).
6) For each gear in the queue, mark it as craftable and update the in-degrees of dependent gear.
7) Return the list of all craftable gear.

⚠️ Common Mistakes

  • Forgetting to process the gear dependencies in topological order can lead to incorrect results.
  • Not handling cases where some components are not available in supplies.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

# Main function to find all craftable gear
def craftable_gear(gear, components, supplies):
    # Set of supplies you already have
    supplies_set = set(supplies)
    
    # In-degree for each gear (how many components must be crafted before we can craft this gear)
    in_degree = {g: 0 for g in gear}
    
    # Adjacency list mapping each gear to the gear that depends on it
    adj_list = {g: [] for g in gear}
    
    # Build the graph
    for i, g in enumerate(gear):
        for component in components[i]:
            if component in supplies_set:
                continue  # If the component is in the initial supplies, skip it
            # If the component is another gear, set up a dependency
            if component in adj_list:  # Ensure the component is a gear we need to track
                in_degree[g] += 1
                adj_list[component].append(g)  # Gear `g` depends on this component
    
    # Queue to process gear that can be crafted immediately
    queue = deque()
    
    # Add all gear with no dependencies (in-degree == 0) to the queue
    for g in gear:
        if in_degree[g] == 0:
            queue.append(g)
    
    # List to store the result (the gear we can craft)
    result = []
    
    while queue:
        current_gear = queue.popleft()
        result.append(current_gear)
        # Treat this gear as now available in our supplies
        supplies_set.add(current_gear)
        
        # Process all gear that depends on this gear
        for dependent_gear in adj_list[current_gear]:
            in_degree[dependent_gear] -= 1  # Reduce in-degree since one of its dependencies is crafted
            if in_degree[dependent_gear] == 0:
                queue.append(dependent_gear)  # Add to queue if all dependencies are satisfied
    
    return result

5: R-eview

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

Example 1:

  • Input: gear = [""weapon""], components = ""metal"", ""wood"", supplies = [""metal"", ""wood"", ""rope""]
  • Expected Output: [""weapon""]
  • Watchlist:
    • Ensure that gear dependencies are correctly represented in the graph.
    • Verify that BFS correctly processes gear in topological order.

6: E-valuate

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

Assume g is the number of gear and n is the total number of components.

  • Time Complexity: O(g + n) because we process each gear and its components once.
  • Space Complexity: O(g + n) due to the adjacency list, in-degree array, and queue.