main.py

import json
from ortools.sat.python import cp_model


def solve_task_order(constraints_json):
    # Parse input
    prerequisites = []
    all_tasks = set()
    for req in constraints_json:
        # e.g., "Sleep requires dinner"
        before, _, after = req.partition(" requires ")
        before = before.strip()
        after = after.strip()
        prerequisites.append((before, after))
        all_tasks |= {before, after}
    task_list = sorted(all_tasks)
    task_to_idx = {task: i for i, task in enumerate(task_list)}
    n_tasks = len(task_list)

    # Model
    model = cp_model.CpModel()

    # Decision variables: order[t] = position in the sequence of task t
    order = [model.NewIntVar(0, n_tasks - 1, f"order_{task}") for task in task_list]
    # All tasks must have distinct positions
    model.AddAllDifferent(order)

    # We'll maximize the number of prerequisites that are satisfied
    constraints_satisfied = []
    for before, after in prerequisites:
        bidx = task_to_idx[before]
        aidx = task_to_idx[after]
        # Boolean variable: is_constraint_ok = (order[a] < order[b])
        ok = model.NewBoolVar(f"prereq_{before}_after_{after}")
        model.Add(order[aidx] < order[bidx]).OnlyEnforceIf(ok)
        model.Add(order[aidx] >= order[bidx]).OnlyEnforceIf(ok.Not())
        constraints_satisfied.append(ok)

    model.Maximize(sum(constraints_satisfied))

    # Solve
    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    result = []
    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        # Build final scheduled order
        # order[t] = position index, so invert the mapping
        idx_to_task = {solver.Value(o): task for o, task in zip(order, task_list)}
        result = [idx_to_task[i] for i in range(n_tasks)]
    return json.dumps(result)


# Example usage:
if __name__ == "__main__":
    input_json = [
        "pizza requires ordering",
        "sleep requires dinner",
        "sleep requires toothbrushing",
        "dinner requires prep",
        "dinner requires clean_dining_room",
        "prep requires shopping",
        "shopping requires money",
        "ordering requires money",
        "money requires work",
        "work requires waking_up",
        "clean_dining_room requires cleaning_time",
    ]
    output_json = solve_task_order(input_json)
    print(output_json)