Resolve a ReWOO Plan into Execution Waves

Problem Statement

ReWOO's whole trick is that the planner writes the entire plan up front, before a single tool has run, by referring to results it has not seen yet through variables like #E1. The worker then has to figure out what can run now, what must wait, and what can never run at all because the planner hallucinated a reference to a step it never wrote.

Background

A plan step looks like:

{"id": "E2", "tool": "LLM", "args": ["What is the population of #E1?"]}

Every occurrence of #E<n> inside any argument string is a dependency on step E<n>. A step is ready when all of its dependencies have completed in an earlier wave, so:

• Steps with no references at all form wave 0.
• Each subsequent wave holds every step whose references are now all satisfied.

Two things can make a step unrunnable, and the worker must report them rather than crash:

• an unresolved reference to an id that is not in the plan at all;
• a cycle (including a step that references itself), or a chain of steps hanging off an unresolved reference.

Either way that step is blocked: it never appears in a wave.

Your Task

Implement:

def resolve_plan(plan):

• plan: list of {"id": str, "tool": str, "args": list}. Ids have the form E followed by digits.

Return:

• waves: list of lists of ids. Ids within a wave are sorted by their numeric index (E2 before E10).
• unresolved: sorted list of strings "<step_id>:#<missing_id>", deduplicated.
• blocked: ids never scheduled, sorted by numeric index.

Input/Output Format

Returns the three-key dict. Note ids sort numerically, not lexicographically - a plain sorted() would put E10 before E2.

Sample

plan = [
    {"id": "E1", "tool": "Search", "args": ["capital of France"]},
    {"id": "E2", "tool": "Search", "args": ["landmarks in Paris"]},
    {"id": "E3", "tool": "LLM", "args": ["Summarise #E1 and #E2"]},
]
print(resolve_plan(plan)["waves"])
# [['E1', 'E2'], ['E3']]

E1 and E2 reference nothing, so ReWOO fires them in parallel; E3 waits for both.