Calculate Fabric Waste - codepath/compsci_guides GitHub Wiki

Unit 4 Session 1 Advanced (Click for link to problem statements)

U-nderstand

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

• Q: What is the structure of the input?

  • A: The input consists of two lists: one list of tuples where each tuple contains a clothing item name (string) and its required fabric length (integer), and another list of integers representing the lengths of available fabric rolls.

• Q: What is the output?

  • A: The output is an integer representing the total amount of fabric waste after producing all the clothing items.

• Q: How should the fabric rolls be allocated to clothing items?

  • A: The fabric rolls should be used in such a way that each clothing item is made with a roll that is large enough, minimizing waste. The largest available roll should be used first.

• Q: What should happen if a clothing item cannot be made with the available fabric rolls?

  • A: The problem assumes that there are enough fabric rolls to produce all items, so this scenario does not need to be handled explicitly.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the fabric rolls in descending order and try to match each clothing item with the largest possible roll that meets or exceeds its required fabric length. Calculate the waste for each roll used.

1) Sort the `fabric_rolls` list in descending order.
2) Initialize a variable `total_waste` to 0.
3) For each `item, required_length` in `items`:
   a) Iterate over the `fabric_rolls` to find the first roll that is greater than or equal to `required_length`.
   b) Subtract the `required_length` from the chosen roll and add the difference to `total_waste`.
   c) Mark the chosen roll as used by setting it to 0 or removing it from the list.
4) Return the `total_waste`.

**⚠️ Common Mistakes**

- Forgetting to update the fabric roll after it has been used.
- Mismanaging the fabric rolls, leading to inefficient allocation and increased waste.

I-mplement

def calculate_fabric_waste(items, fabric_rolls):
    fabric_rolls.sort(reverse=True)
    total_waste = 0

    for item, required_length in items:
        for i in range(len(fabric_rolls)):
            if fabric_rolls[i] >= required_length:
                total_waste += fabric_rolls[i] - required_length
                fabric_rolls[i] = 0  # Use up the roll
                break

    return total_waste