7.md

Day 7: The Sum of Its Parts - Part 1

The instructions specify a series of steps and requirements about which steps must be finished before others can begin (your puzzle input). Each step is designated by a single letter. For example, suppose you have the following instructions:

Step C must be finished before step A can begin.
Step C must be finished before step F can begin.
Step A must be finished before step B can begin.
Step A must be finished before step D can begin.
Step B must be finished before step E can begin.
Step D must be finished before step E can begin.
Step F must be finished before step E can begin.

Visually, these requirements look like this:

  -->A--->B--
 /    \      \
C      -->D----->E
 \           /
  ---->F-----

Your first goal is to determine the order in which the steps should be completed. If more than one step is ready, choose the step which is first alphabetically. In this example, the steps would be completed as follows:

• Only C is available, and so it is done first.
• Next, both A and F are available. A is first alphabetically, so it is done next.
• Then, even though F was available earlier, steps B and D are now also available, and B is the first alphabetically of the three.
• After that, only D and F are available. E is not available because only some of its prerequisites are complete. Therefore, D is completed next.
• F is the only choice, so it is done next.
• Finally, E is completed. So, in this example, the correct order is CABDFE.

In what order should the steps in your instructions be completed?

Solution

• Use a Priority Queue that returns nodes with the fewest dependencies first (i.e., if C -> A, it'll return C first because it has no dependencies, and then A, because A can't be done until C is done). If there are multiple nodes with X dependencies where X is the lowest # of dependencies, then it returns the node that is alphabetically first. E.g., if C -> A, B -> A, both B and C have 0 dependencies, but it'll return B first because it's first alphabetically.

  export const getOrderedToplogicalSortQueue = (graph: Graph<string>) => {
      const queue = new PriorityQueue<IQueueState>(({node, mustBeAfter}) =>
          -1 * (mustBeAfter.size * 100 + node.charCodeAt(0)));
      graph.vertices.forEach(v =>
              queue.enqueue({node: v, mustBeAfter: graph.edges.get(v) ?? new Set()}));
      return queue;
  };

• After that, just enqueue the first node N with fewest nodes and alphabetically first (there must be at least 1 node with 0 dependencies), remove N from all other nodes in the queue, and heapify() the queue so it's re-ordered.

  export const toplogicalSort = ({graph}: ISimulation) => {
      const queue = getOrderedToplogicalSortQueue(graph);
      const result: string[] = [];
  
      while (!queue.isEmpty()) {
          const { node } = queue.dequeue()!;
          result.push(node);
          queue.values.forEach(v => v.mustBeAfter.delete(node));
          queue.heapify();
      }
      return result.join('');
  };