Fix the safe step finder for a parallel pipeline
Your task
An agent sped up your data pipeline twice, and twice the faster version was wrong. The second time it ran a step in parallel that depended on the order of another. Now you decide which steps may run in parallel, and the agent may only optimize those.
An assistant wrote safe_parallel_steps(steps). It is in the editor. It has a bug. Find it and fix it.
Input and output:
steps: the pipeline's steps, each writtenname:reads:writes, wherereadsandwritesare comma separated keys of shared state. For exampleclean:raw:clean, oraudit::for a step that touches nothing shared.- Return the names of the steps that are safe to run in parallel, each name once, sorted as plain strings.
Rules the tests check:
- Split each step on
:. Ignore a step that does not have exactly 3 parts, or whose name is empty after trimming whitespace. An ignored step conflicts with nothing. - Trim whitespace from the name and from each key. Ignore empty keys.
- Compare each step with every other step in the list, one by one, including another step with the same name. A step is safe only when, for every other step, none of these holds:
- it reads a key the other step writes
- it writes a key the other step reads
- both steps write the same key
- Two steps that only read the same key do not conflict.
- A step never conflicts with itself. When two steps share a name, the name is in the result if either step is safe.
Examples
safe_parallel_steps(steps: list[str]) -> list[str]Example 1
Input
safe_parallel_steps(["load::raw", "clean:raw:clean", "audit::"])Output
["audit"]Example 2
Input
safe_parallel_steps(["a::x", "b::y", "c::z"])Output
["a", "b", "c"]Example 3
Input
safe_parallel_steps(["sum:rows:total", "sum:rows:total"])Output
[]