At AcmeCI, a pipeline consists of named gates with directed dependencies and additional OR-rules. You must compute the smallest set of gates (and an execution order) needed to reach a given milestone.
Implement plan_devsecops_gates(gates, deps, milestone, rules) -> list[str].
gates: list of unique gate names.deps: list of pairs [a, b] meaning gate a must run before gate b.rules: list of rules [[opt1, opt2, ...], before_gate] meaning at least one option must run before before_gate.The plan must:
milestone.before_gate is included (including milestone if it appears as a before_gate).[] if impossible.gates=[checkout,build,sast,sca,container_scan,deploy_prod], deps=[[checkout,build],[build,container_scan],[container_scan,deploy_prod]], rules=[[[sast,sca],deploy_prod],[[container_scan],deploy_prod]], milestone=deploy_prod → [checkout, build, sca, container_scan, deploy_prod] (pick sca to satisfy the OR-rule).
gates=[a,b,c,deploy], deps=[[a,deploy],[b,deploy],[c,deploy]], rules=[[[b,a],deploy]], milestone=deploy → [a, deploy] (only one option is needed; minimal picks a).
1 <= len(gates) <= 600 <= len(deps) <= 2000 <= len(rules) <= 121 <= len(options) <= 12 for each rule[] if no valid plan exists.