Python Execution Planner

Imagine you're building a task management system or a workflow engine. A crucial component of such systems is the ability to plan and execute a sequence of operations. This challenge focuses on creating a flexible execution planner that can handle a list of tasks, each with its own execution logic and potential dependencies. This is fundamental for building robust and automated processes.

Problem Description

Your task is to create a Python class named ExecutionPlanner that can:

Register Tasks: Allow users to register different types of tasks with specific execution logic.
Plan Execution: Given a list of task names, determine a valid execution order. A task can only be executed after all its dependencies have been met.
Execute Plan: Execute the tasks in the determined order.

Key Requirements:

Task Registration: The ExecutionPlanner should have a method to register tasks. Each registered task should be associated with a name (string) and a callable function (the execution logic).
Dependency Management: Tasks can have dependencies on other tasks. When registering a task, you should be able to specify a list of task names that must be completed before this task can run.
Planning (Topological Sort): The planner must be able to generate a valid execution order for a given set of tasks, considering their dependencies. This is essentially a topological sort problem.
Execution: The planner should have a method to execute a planned sequence of tasks. During execution, if a task's dependencies are not met (i.e., they haven't been executed yet), the planner should raise an appropriate error.
Error Handling:
- Handle cases where a requested task is not registered.
- Handle circular dependencies (e.g., Task A depends on Task B, and Task B depends on Task A).
- Handle cases where dependencies are not met during execution.

Expected Behavior:

The plan method should return a list of task names in an order that respects dependencies.
The execute method should call the registered functions for each task in the planned order.
If any issues are encountered (missing task, circular dependency, unmet dependency during execution), informative exceptions should be raised.

Edge Cases to Consider:

A task with no dependencies.
A task that is a dependency for multiple other tasks.
An empty list of tasks to plan.
Registering a task with a name that already exists.
Planning a sequence of tasks that includes unregistered tasks.

Examples

Example 1: Simple Sequential Tasks

planner = ExecutionPlanner()
planner.register_task("task_a", lambda: print("Executing Task A"))
planner.register_task("task_b", lambda: print("Executing Task B"))

plan = planner.plan(["task_b", "task_a"])
print(plan)
# Expected Output: ['task_a', 'task_b']

planner.execute(plan)
# Expected Output:
# Executing Task A
# Executing Task B

Explanation: task_a and task_b have no dependencies. The plan method is given a desired order, but it reorders them to ensure all dependencies are met (which is trivial here). The execute method then runs them sequentially.

Example 2: Tasks with Dependencies

planner = ExecutionPlanner()
planner.register_task("download_data", lambda: print("Downloading data..."))
planner.register_task("process_data", lambda: print("Processing data..."), dependencies=["download_data"])
planner.register_task("save_results", lambda: print("Saving results..."), dependencies=["process_data"])

plan = planner.plan(["save_results", "download_data"])
print(plan)
# Expected Output: ['download_data', 'process_data', 'save_results']

planner.execute(plan)
# Expected Output:
# Downloading data...
# Processing data...
# Saving results...

Explanation: process_data depends on download_data, and save_results depends on process_data. The plan method correctly identifies this order. execute runs them in the planned, dependency-respecting order.

Example 3: Circular Dependency

planner = ExecutionPlanner()
planner.register_task("task_x", lambda: print("Executing X"), dependencies=["task_y"])
planner.register_task("task_y", lambda: print("Executing Y"), dependencies=["task_x"])

try:
    planner.plan(["task_x", "task_y"])
except ValueError as e:
    print(e)
# Expected Output: Circular dependency detected involving task_x and task_y.

Explanation: task_x depends on task_y, and task_y depends on task_x. This creates a circular dependency, which the plan method should detect and report.

Example 4: Unmet Dependency During Execution

planner = ExecutionPlanner()
planner.register_task("prepare_config", lambda: print("Preparing configuration..."))
planner.register_task("run_service", lambda: print("Running service..."), dependencies=["prepare_config"])

# Intentionally skip preparing configuration in the execution list
try:
    planner.execute(["run_service"])
except RuntimeError as e:
    print(e)
# Expected Output: Dependency 'prepare_config' not met for task 'run_service'.

Explanation: run_service requires prepare_config. If prepare_config is not executed before run_service, a RuntimeError is raised.

Constraints

Task names must be unique strings.
Task dependencies must refer to other registered task names.
The number of tasks registered can be up to 1000.
The depth of dependency chains can be up to 50.
The plan method should have a time complexity of O(V+E), where V is the number of tasks and E is the number of dependencies, typical for topological sort algorithms.
The execute method should have a time complexity of O(N), where N is the number of tasks to be executed.

Notes

Consider using a graph-based approach to represent tasks and their dependencies.
For topological sorting, algorithms like Kahn's algorithm or a DFS-based approach are common.
Think about how to efficiently store task information (name, function, dependencies).
The plan method should be able to handle cases where the input list of tasks to plan is a subset of all registered tasks. It should still return a valid order for the requested tasks and any necessary prerequisites.
The execute method takes a planned list, which is assumed to be valid. The primary error it checks for is if the dependencies of a task within that plan are not yet met by preceding tasks in that specific plan execution.