http://www.reddit.com/r/dailyprogrammer/comments/1rnrs2/112813_challenge_137_intermediate_hard_banquet/

gistfile1.cpp

#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <limits>
#include <string>
#include <vector>
#include <queue>

using namespace std;

struct GraphNode {
  vector<GraphNode*> neighbors;
  string label;
  int level = 0;

  GraphNode(const string& l) : label(l) {}
};

void FindFoodItems(
    const string& food_glob,
    const vector<GraphNode*>& food_nodes,
    vector<GraphNode*>* results) {
  for (auto& food_node : food_nodes) {
    // The only cases supported are:
    //   (1) Exact match
    //   (2) '*' at the beginning
    //   (3) '*' at the end
    if (food_glob.find_first_of('*') == string::npos) {
      if (food_glob == food_node->label) {
        results->push_back(food_node);
        continue;
      }
    }
    if (food_glob.front() == '*') {
      const string matcher = food_glob.substr(1);
      if (food_node->label.substr(
            food_node->label.length() - matcher.length()) ==
          matcher) {
        results->push_back(food_node);
        continue;
      }
    }
    if (food_glob.back() == '*') {
      const string matcher = food_glob.substr(0, food_glob.length() - 1);
      if (food_node->label.substr(0, matcher.length()) == matcher) {
        results->push_back(food_node);
        continue;
      }
    }
  }
}

int main() {
  int num_food_items, num_food_relationships;
  cin >> num_food_items >> num_food_relationships;
  cout << "Will read in " << num_food_relationships << " relationships for " << num_food_items << " food items." << endl;
  vector<pair<string, string>> food_relationships;
  vector<GraphNode*> food_nodes;
  for (int i = 0; i < num_food_items; ++i) {
    string food_item;
    cin >> food_item;
    food_nodes.push_back(new GraphNode(food_item));
  }
  for (int i = 0; i < num_food_relationships; ++i) {
    string food_item_1, food_item_2;
    cin >> food_item_1 >> food_item_2;
    // We are going to use regex matching whereas the input is in 'glob' format,
    // so make a small adjustment.
    food_relationships.push_back(make_pair(food_item_1, food_item_2));
  }

  // Sanity check what we got.
  cout  << "Read in the following food items :- \n";
  for (const auto& food_item : food_nodes) {
    cout << food_item->label << endl;
  }
  cout << "Read in the following food relationships :- \n";
  for (const auto& food_relationship : food_relationships) {
    cout << food_relationship.first << " < " << food_relationship.second << endl;
  }

  // General approach:
  // 1. Create a graph which each node corresponding to a food item
  // 2. For every relationship, expand the regex to determine the nodes involved, and
  // then create a dependency link.
  // 3. Go through the dependency links and number the nodes
  //    - Increment the number of each of a node's dependencies
  //    - Repeat for each of the dependent nodes
  //    - Add the nodes into a numbered list.
  //    - Note: this will require adding and removing nodes from the list
  // 4. Once no more dependencies have to be processed, print out numbered list
  // 5. Go through graph and print out 'isolated' nodes
  //
  // Edge cases: Multiple origins, multiple nodes of the same number, isolated nodes

  // Step 2
  vector<GraphNode*> root_nodes = food_nodes;
  vector<GraphNode*> isolated_nodes = food_nodes;
  for (const auto& food_relationship : food_relationships) {
    vector<GraphNode*> dependents, dependees;
    // Each relationship can potentially be many->many
    // Note: the c++ regex implementation isn't available in my standard library
    // right now, so I'm going to support a limited range of globs:
    //   only those where the '*' is either right at the beginning or at the end
    FindFoodItems(food_relationship.first, food_nodes, &dependents);
    FindFoodItems(food_relationship.second, food_nodes, &dependees);

    // Now create dependency links
    for (auto& nodeA : dependents) {
      for (auto& nodeB : dependees) {
        nodeA->neighbors.push_back(nodeB);
      }
    }

    // Also as part of this process weed out non-root nodes for the next step, as well as isolated nodes.
    for (auto& node : dependees) {
      root_nodes.erase(
          remove(root_nodes.begin(), root_nodes.end(), node),
          root_nodes.end());
      isolated_nodes.erase(
          remove(isolated_nodes.begin(), isolated_nodes.end(), node),
          isolated_nodes.end());
    }
    for (auto& node : dependents) {
      isolated_nodes.erase(
          remove(isolated_nodes.begin(), isolated_nodes.end(), node),
          isolated_nodes.end());
    }
  }

  // Step 3
  // Process all the nodes in the current 'frontier' until there are non left.
  // The first frontier is the set of root nodes
  queue<GraphNode*> frontier;
  for (auto& node : root_nodes) {
    frontier.push(node);
  }
  while (!frontier.empty()) {
    GraphNode* current_node = frontier.front();
    for (auto& neighbor : current_node->neighbors) {
      neighbor->level = current_node->level + 1;
      frontier.push(neighbor);
    }
    frontier.pop();
  }

  // Step 4
  vector<vector<GraphNode*>> levels(food_nodes.size());
  for (const auto& node : food_nodes) {
    if (find(isolated_nodes.begin(), isolated_nodes.end(), node) ==
        isolated_nodes.end()) {
      levels[node->level].push_back(node);
    }
  }

  for (int i = 0; i < levels.size() && !levels[i].empty(); ++i) {
    cout << i + 1 << " : ";
    for (const auto& node : levels[i]) {
      cout << node->label << "  ";
    }
    cout << endl;
  }
  cout << endl;

  // Step 5
  // Finally, print out the nodes without dependees
  for (const auto& node : isolated_nodes) {
    cout << "Warning: " << node->label << " does not have any ordering." << endl;
  }

  for (auto& node : food_nodes) {                                                                          
    delete node;                                                                                           
  }                                                                                                        
}