Simple JavaScript Execution Planner

This challenge asks you to build a rudimentary execution planner in JavaScript. An execution planner, in the context of databases or task scheduling, determines the most efficient order to execute a series of operations. This is useful for optimizing performance by minimizing resource usage and execution time.

Problem Description

You are tasked with creating a JavaScript function called planExecution that takes an array of tasks as input and returns an optimized execution plan. Each task is represented as an object with the following properties:

• id: A unique identifier for the task (string).
• dependencies: An array of task IDs that must be completed before this task can start (array of strings).
• cost: A numerical value representing the cost of executing this task (number). Lower cost is better.

The planExecution function should return an array of task IDs representing the optimal execution order. "Optimal" in this case means the order that minimizes the total cost of execution, considering dependencies. If multiple orders have the same total cost, any valid order is acceptable.

Key Requirements:

• The execution plan must satisfy all dependencies. A task cannot be executed before all its dependencies are completed.
• The function should handle circular dependencies gracefully. If a circular dependency is detected, it should return an empty array.
• The function should prioritize tasks with lower costs when multiple valid execution orders exist.
• The function should not modify the original input array of tasks.

Expected Behavior:

The function should return an array of task IDs in the order they should be executed. The array should contain all tasks if a valid execution plan exists. If no valid plan exists (due to circular dependencies), the function should return an empty array.

Edge Cases to Consider:

• Empty input array: Should return an empty array.
• Tasks with no dependencies: Should be executed as early as possible.
• Tasks with multiple dependencies: Dependencies should be satisfied in the correct order.
• Circular dependencies: Should return an empty array.
• Tasks with the same cost: The order of these tasks doesn't matter for optimality.

Examples

Example 1:

Input: [
  { id: 'A', dependencies: [], cost: 10 },
  { id: 'B', dependencies: ['A'], cost: 5 },
  { id: 'C', dependencies: ['B'], cost: 8 }
]
Output: ['A', 'B', 'C']
Explanation: Task A has no dependencies and is executed first. Task B depends on A, so it's executed second. Task C depends on B, so it's executed last.

Example 2:

Input: [
  { id: 'A', dependencies: [], cost: 5 },
  { id: 'B', dependencies: [], cost: 10 },
  { id: 'C', dependencies: ['A', 'B'], cost: 3 }
]
Output: ['A', 'B', 'C']  (or ['B', 'A', 'C'] - order of A and B doesn't matter)
Explanation: Tasks A and B have no dependencies and can be executed in either order. Task C depends on both A and B, so it's executed last.

Example 3: (Circular Dependency)

Input: [
  { id: 'A', dependencies: ['B'], cost: 10 },
  { id: 'B', dependencies: ['A'], cost: 5 }
]
Output: []
Explanation: A depends on B, and B depends on A, creating a circular dependency.  No valid execution plan exists.

Constraints

• The number of tasks will be between 0 and 100.
• Task IDs will be unique strings.
• Dependencies will be arrays of valid task IDs.
• Costs will be non-negative numbers.
• The algorithm should complete within a reasonable time (e.g., less than 1 second) for the given constraints.

Notes

• Consider using a topological sort algorithm to determine the execution order.
• You can use a graph data structure to represent the dependencies between tasks.
• Be mindful of potential infinite loops when detecting circular dependencies. A simple visited set during the topological sort can help.
• The cost is only used to break ties when multiple valid execution orders exist. It does not influence the fundamental dependency satisfaction.
• Focus on correctness and clarity of code. Efficiency is important, but not at the expense of readability.