Instruction Scheduler

Imagine you're building a robotic automation system. You have a series of instructions to execute, but some instructions depend on others completing first. This challenge asks you to build a Javascript scheduler that manages these dependencies and executes instructions in the correct order, ensuring no instruction runs before its prerequisites are met. This is a fundamental problem in task management and automation.

Problem Description

You need to create a Javascript class called InstructionScheduler. This class will take an array of instructions as input, where each instruction is an object with the following properties:

• id: A unique string identifier for the instruction.
• dependencies: An array of strings, representing the ids of instructions that must complete before this instruction can run. An empty array means the instruction has no dependencies.
• execute: A function that represents the action to be performed when the instruction is executed. This function should take no arguments and return a string indicating successful execution (e.g., "Instruction [id] executed").

The InstructionScheduler class should have a method called run() that executes all instructions in the correct order, respecting dependencies. The run() method should return an array of strings, where each string is the result of executing a single instruction, in the order they were executed. If a circular dependency is detected, the run() method should throw an error with the message "Circular dependency detected!".

Expected Behavior

• The scheduler should process instructions in a topological order, ensuring dependencies are met.
• Instructions with no dependencies should be executed first.
• If multiple instructions are ready to run (i.e., all dependencies are met), the scheduler can execute them in any order.
• The scheduler should handle circular dependencies gracefully by throwing an error.
• The scheduler should not execute an instruction before all its dependencies are completed.

Edge Cases to Consider

• Empty input array: Should return an empty array.
• Instructions with self-dependencies (e.g., dependencies: ['instruction1'] where id is 'instruction1'). This is a circular dependency.
• Circular dependencies involving multiple instructions.
• Instructions with dependencies that don't exist in the input array. (This is not required to be handled; assume all dependencies listed do exist.)

Examples

Example 1:

Input: [
  { id: 'A', dependencies: [], execute: () => "Instruction A executed" },
  { id: 'B', dependencies: ['A'], execute: () => "Instruction B executed" },
  { id: 'C', dependencies: ['B'], execute: () => "Instruction C executed" }
]
Output: [
  "Instruction A executed",
  "Instruction B executed",
  "Instruction C executed"
]
Explanation: Instruction A has no dependencies and is executed first. Then, Instruction B, which depends on A, is executed. Finally, Instruction C, which depends on B, is executed.

Example 2:

Input: [
  { id: 'X', dependencies: [], execute: () => "Instruction X executed" },
  { id: 'Y', dependencies: [], execute: () => "Instruction Y executed" },
  { id: 'Z', dependencies: ['X', 'Y'], execute: () => "Instruction Z executed" }
]
Output: [
  "Instruction X executed",
  "Instruction Y executed",
  "Instruction Z executed"
]
Explanation: Instructions X and Y have no dependencies and can be executed in any order. Then, Instruction Z, which depends on both X and Y, is executed.

Example 3: (Circular Dependency)

Input: [
  { id: 'P', dependencies: ['Q'], execute: () => "Instruction P executed" },
  { id: 'Q', dependencies: ['P'], execute: () => "Instruction Q executed" }
]
Output: Throws Error: "Circular dependency detected!"
Explanation: Instructions P and Q depend on each other, creating a circular dependency.

Constraints

• The number of instructions will be between 0 and 1000.
• Instruction IDs will be unique strings.
• The execute function will always return a string.
• The dependencies array will contain only strings (instruction IDs).
• Performance: The run() method should complete within a reasonable time (e.g., less than 1 second) for the given constraints.

Notes

• Consider using a graph data structure to represent the dependencies between instructions.
• Topological sorting is a common algorithm for ordering nodes in a directed acyclic graph, which is applicable here.
• Be mindful of potential circular dependencies and how to detect them. A simple way to detect circular dependencies is to keep track of the instructions currently being processed in a recursion stack. If you encounter an instruction already in the stack, you have a cycle.
• You can assume that the input instructions are valid (e.g., no invalid data types).