Your question is Optimal Path in Metabolic Graph. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
In a Genentech pathway analysis workflow, reactions form a directed metabolic pathway. Each reaction has a positive execution time and a nonnegative yield contribution. Given a maximum available time, find the feasible path from a starting metabolite to a target metabolite with the greatest total yield.
The pathway is guaranteed to be a directed acyclic graph. If multiple paths have the same maximum yield, choose the one with the smallest total time. If a tie remains, return the lexicographically smallest sequence of node IDs.
Implement find_optimal_path(graph, start, target, max_time). graph is a dictionary mapping a node ID to a list of reactions. Each reaction is represented as [next_node, reaction_time, yield_value]. Return a dictionary with keys path, time, and yield. If the target cannot be reached within max_time, return {"path": [], "time": -1, "yield": 0}.
def find_optimal_path(graph, start, target, max_time):