Discussion on: When Recursion Comes to Rescue

[pentacular]

On reflection, I thought this might benefit from an alternative recursive implementation that uses a different partitioning strategy that avoids overconstraint, and does not rely on function calls to implement the recursive policy.

// Note: Assumes that there is a valid topological ordering.
const orderTasks = (tasks) => {
  const resolvedTasks = new Set();
  const orderedTasks = [];
  const unorderedTasks = [...tasks];

  const processFirstUnorderedTask = (task) => {
    for (const dependency of task.depends) {
      if (!resolvedTasks.has(dependency)) {
        // Schedule the task for backtracking.
        unorderedTasks.push(task);
        return;
      }
    }
    // Reduce the size of the problem.
    resolvedTasks.add(task.task);
    orderedTasks.push(task);
  }

  while (unorderedTasks.length > 0) {
    // Take the first unordered task.
    const task = unorderedTasks.shift();
    // Reduce the size of the problem, or schedule it for backtracking.
    processFirstUnorderedTask(task);
  }

  return orderedTasks;
}

const unorderedTasks = [
  {
    task: "buy groceries",
    depends: [ "go to the store" ]
  },
  {
    task: "make a sandwich",
    depends: [ "buy groceries" ]
  },
  {
    task: "go to the store",
    depends: []
  }
];

const orderedTasks = orderTasks(unorderedTasks);

console.log(JSON.stringify(orderedTasks, null, 2));

[Annie Liao]

Thanks so much for taking a stab at it. As someone who's still learning data structures and CS fundamentals, I really admire your backtracking technique here. It has truly expanded my knowledge of recursion.