Get Dressed & Eat a PBJ Challenge

[Duthomhas]

The Standard Library comes with a lot of algorithms for processing lists of things, but one thing it does not have is any form of topological sort, which takes a graph as input and produces a list as output.

This weekend I will be flying to PA for a job interview. Before I go, I would like to make sure I get dressed properly. So I made a list of requirements to make sure nothing goes wrong:

    item   → prerequisite(s)
    ────────────────────────
    pants  → briefs, shirt
    shoes  → pants, socks
    tie    → shirt
    jacket → shirt, tie
    watch  → (none)

That is, I need to have my shirt on before I put on my tie.

But this is only somewhat helpful. What I'd really like is an actual list telling me what order to put clothes on.

A topological sort is designed precisely for this kind of thing.

However, there is a hiccup. A topological sort is specified as accepting a graph whose edges (u,v) indicate that u comes before v.

I need to transform my input from a requirements graph to a dependencies graph: one where every edge (u,v) represents things that can occur only after u has been accomplished.

The challenge
  1 • Write a program that accepts a requirements list.
  2 • Transform the requirements graph into a dependency graph.
  3 • Topologically sort it.
  4 • Print the ordered instructions.

A topological sort only gives you one possible order out of many. I would rather not be told to dress in a really odd order, such as:

    watch, shirt, socks, tie, jacket, briefs, pants, shoes

Also, as this is a CS interview, we should recognize that the ordering that comes out of a topological sort both depends on the input and reveals a lot about the underlying data structures and algorithms used. Since this is a security hole, we should fix it by producing a different but valid ordering every time the topological sort is used.

In fact, about three different orderings would be nice, because I could then choose which one I like best and use it.

Bonus
  5 • Produce a different valid ordering every time the topological sort is applied.

Example

List a item (any single word) and its prerequisite items, if any.
Repeat for each new line.
Press Enter twice to finish.
> pants briefs shirt
> shoes pants socks
> tie shirt
> jacket shirt tie
> watch
>
Three possible orderings:
  shirt, socks, tie, jacket, watch, briefs, pants, shoes
  watch, socks, briefs, shirt, pants, shoes, tie, jacket
  socks, briefs, shirt, watch, pants, tie, jacket, shoes

If that works nicely, I may use it to tell me how to make my PBJ lunch properly.

As this is a challenge, you may of course choose any underlying data structure you wish. I highly recommend an adjacency DAG using a couple of standard containers. You can read more about topological sorting at Wikipedia if you wish. https://en.wikipedia.org/wiki/Topological_sorting

I will be posting my solution about Wednesday next week. (And we’ll see if I get the job.)

Good luck!

[helios]

https://gist.github.com/Helios-vmg/2942d4fe9f312b87b3676252c1f3fd0b

The generation algorithm is kind of lame, but if I was to check if the orderings are actually different, then the program would definitely hang for some DAGs. As it is, it only has a chance of hanging.

[Duthomhas]

Generating random stuff (orderings in this case) and validating is a good and proper technique for a lot of things. For a small list it works fine. It is possible to be much more efficient about it though. ;^)

[helios]

Well, you're only likely to get duplicate orderings for small graphs with few possible orderings such as

0 1 2
2 5
1 3
3 4
4 5
5

or

0 1 2
1 3
2 3
3

[Duthomhas]

I am not talking about duplicate orderings. That will happen occasionally no matter what. And yes, the closer to 3 or fewer possible orderings the more likely a repeat will appear. (You guarantee a repeat at 2 or fewer possible orderings.)

Your generation algorithm starts by simply generating a random sequence, then sorting it to valid. Nice!

Anyway, next post is my solution, since you were the only one cool enough to try this this week. ;O)

[Duthomhas]

Here is my solution:

// Topological sorting challenge
// http://www.cplusplus.com/forum/lounge/228897/
//
// Uses Kahn's algorithm
// https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm

#include <chrono>
#include <ciso646>
#include <iterator>
#include <random>
#include <unordered_map>
#include <unordered_set>

//--------------------------//
// Directed Adjacency Graph //
//--------------------------//

// Node  ←→ node name/value
// Edges ←→ set of Nodes
// Graph ←→ mapping of Node → Edges

// Consequences:
//  • every Node must be unique
//  • edges do not have associated weights
//  • cycles are possible

template <typename Node>
using Edges = std::unordered_set <Node>;

template <typename Node>
using Graph = std::unordered_map <Node, Edges <Node> >;

//-----------------------------------//
// Invert a Directed Adjacency Graph //
//-----------------------------------//

template <typename Node>
Graph <Node> invert( const Graph <Node> & G )
{
  Graph <Node> I;

  // For every (u,*) in G
  for (auto u : G)
  {
    // Make sure u is in I
    I[ u.first ];

    // Add every G(u,v) to I(v,u)
    for (auto v : u.second)
      I[ v ].insert( u.first );
  }

  return I;
}

//------------------//
// Kahn's Algorithm //
//------------------//

// Requirements Graph ←→ every edge (u,v) indicates u sorts after v

template <typename Node, typename OIterator>
bool toposort_requirements( Graph <Node> G, OIterator result )
{
  static std::ranlux24 rng( std::chrono::system_clock::now().time_since_epoch().count() );

  // S ← all u in G with no outgoing edges
  Edges <Node> S;
  for (auto p : G)
    if (p.second.empty())
      S.insert( p.first );

  while (!S.empty())
  {
    // Choose a RANDOM node from S
    Node u = *std::next( S.begin(), std::uniform_int_distribution <std::size_t> ( 0, S.size() - 1 )( rng ) );
    S.erase( u );

    *result++ = u;

    for (auto& v : G) if (v.second.count( u ))
    {
      v.second.erase( u );
      if (v.second.empty())
        S.insert( v.first );
    }
  }

  // Any remaining edges → not a DAG
  for (auto u : G)
    if (u.second.size())
      return false;

  return true;
}

// Dependencies Graph ←→ every edge (u,v) indicates u sorts before v
// (This is what is usually meant when describing a graph to be topologically sorted.)

template <typename Node, typename OIterator>
bool toposort_dependencies( const Graph <Node> & G, OIterator result )
{
  return toposort_requirements( invert( G ), result );
}

//-------------------------------------------------------------------------------------------------
// Main Program
//-------------------------------------------------------------------------------------------------
#include <cctype>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

Graph <std::string> ask_for_G()
{
  typedef std::string Node;
  Graph <Node> G;
  std::cout << "List a item (any single word) and its prerequisite items, if any.\n"
               "Repeat for each new line.\n"
               "Press Enter twice to finish.\n";
  std::string s;
  while ( (std::cout << "> ")
    and   getline( std::cin, s )
    and   s.size()               )
  {
    Node  u, v;
    Edges <Node> e;
    std::istringstream ss( s );
    ss >> u;
    while (ss >> v) e.insert( v );
    G[ u ] = e;
    for (auto n : e) G[ n ];
  }
  return G;
}

int main( int argc, char** argv )
{
  auto G = ask_for_G();
  auto I = invert( G );

  std::cout << "Three possible orderings:\n  ";
  for (int N = 0; N < 3; N++)
  {
    std::vector <std::string> xs;
    toposort_dependencies( I, std::back_inserter( xs ) );

    std::size_t n = 0;
    for (auto x : xs) std::cout << (n++ ? ", " : " ") << x;
    std::cout << "\n  ";
  }
}

Enjoy!

[Duthomhas]

Well, the promised update: I didn't get the job.

Apparently, doing fabulously with every part of an interview process means nothing if you don't have 'experience' for an entry-level position. LOL. I'm pretty much done talking to other people at all.

[helios]

Aw, man. That sucks. Was it a headhunter or at the company? Headhunters are the absolute worst in that regard (and in most other regards).

[Duthomhas]

Yeah, found by a headhunter. It is a really cool company, one I would really have enjoyed working for. But alas, no go.