Problem Overview

You are designing a supply chain optimization system for a manufacturing company. A product requires multiple sequential production stages, and for each stage, there are several factory options to choose from. Each factory has a building cost and is located at a specific position along a railway line.

The goal is to select exactly one factory for each production stage to minimize the total cost, which includes both building costs and transportation costs between factories.

The problem is divided into four progressive parts:

• Basic Selection: Find the minimum cost when there is no transportation cost (all factories at the same location)

• With Transportation: Add transportation costs based on distance between consecutive factories

• N Stages: Generalize the solution to handle any number of production stages

• Skip One Stage: Find minimum cost when exactly one stage must be skipped

Important Notes

• There are multiple parts to this problem -- ask the interviewer how many parts there are to better manage your time

• Start with the simplest approach and extend it as parts get more complex

• Write your own test cases and ensure your code compiles and runs correctly

Input Format

You will receive a list of production stages, where each stage contains multiple factory options:

`

Each factory option: [building_cost, position]

stages = [ [[10, 0], [20, 5], [35, 2]], # Stage 0: 3 factory options [[35, 1], [50, 3], [25, 0]], # Stage 1: 3 factory options [[30, 4], [5, 2], [40, 0]] # Stage 2: 3 factory options ] `

Cost Formula

` total_cost = sum(building_costs) + sum(transportation_costs)

transportation cost between consecutive stages = abs(position_i - position_{i+1})

`

Implement a function find_minimum_cost(stages) that calculates the minimum total building cost when all factories are at the same position (transportation cost is zero).

` stages = [ [[10, 0], [20, 0], [35, 0]], # Stage 0 [[35, 0], [50, 0], [25, 0]], # Stage 1 [[30, 0], [5, 0], [40, 0]] # Stage 2 ]

find_minimum_cost(stages) # Returns 40

Stage 0: min(10, 20, 35) = 10

Stage 1: min(35, 50, 25) = 25

Stage 2: min(30, 5, 40) = 5

Total: 10 + 25 + 5 = 40

`

• Select exactly one factory from each stage

• Return the minimum total building cost

• Handle any number of factory options per stage

Extend your solution to include transportation costs. Factories are now located at different positions along a railway line, and moving products between consecutive stages incurs a cost equal to the absolute difference in positions.

` stages = [ [[100, 2], [50, 0], [30, 1]], # Stage 0 [[100, 1], [20, 2], [10, 5]], # Stage 1 [[10, 1], [12, 1], [5, 3]] # Stage 2 ]

find_minimum_cost(stages) # Returns 51

Optimal selection:

Stage 0: [30, 1] - cost: 30, position: 1

Stage 1: [10, 5] - cost: 10, position: 5

Stage 2: [5, 3] - cost: 5, position: 3

Building costs: 30 + 10 + 5 = 45

Transportation: abs(1-5) + abs(5-3) = 4 + 2 = 6

Total: 45 + 6 = 51

`

• Are positions always non-negative integers?

• Can multiple factories have the same position?

• Is there a maximum number of factory options per stage?

Generalize your solution to handle an arbitrary number of production stages. The input structure remains the same, but you can no longer hardcode the number of nested loops.

`

5 production stages

stages = [ [[10, 0], [20, 2]], [[15, 1], [25, 3], [35, 0]], [[30, 2], [40, 1]], [[5, 0], [15, 2]], [[20, 1], [10, 3], [25, 0]] ]

find_minimum_cost(stages) # Returns 77 `

• Handle any number of stages (N stages)

• Handle varying numbers of factory options per stage

• Maintain reasonable time complexity

Extend your solution to handle a new requirement: exactly one production stage must be skipped (not built). When a stage is skipped, the transportation cost is calculated between the factories on either side of the skipped stage.

` stages = [ [[10, 0], [20, 2]], # Stage 0 [[100, 5]], # Stage 1 - expensive, might skip [[15, 1], [25, 3]], # Stage 2 [[5, 2], [15, 0]] # Stage 3 ]

find_minimum_cost_skip_one(stages) # Returns 32

Optimal choice: skip Stage 1

Select: [10, 0] -> skip -> [15, 1] -> [5, 2]

Building costs: 10 + 15 + 5 = 30

Transportation: abs(0-1) + abs(1-2) = 1 + 1 = 2

Total: 32

`

• Can the first or last stage be skipped? (If yes, the product simply starts/ends at the next available stage)

• What if there are only 2 stages? (Skipping one leaves only 1 stage with no transportation cost)