### Get Dressed & Eat a PBJ Challenge

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!
Last edited on
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.
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. ;^)
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
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)
Here is my solution:

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153`` ``````// 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 #include #include #include #include #include //--------------------------// // 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 using Edges = std::unordered_set ; template using Graph = std::unordered_map >; //-----------------------------------// // Invert a Directed Adjacency Graph // //-----------------------------------// template Graph invert( const Graph & G ) { Graph 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 bool toposort_requirements( Graph 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 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 ( 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 bool toposort_dependencies( const Graph & G, OIterator result ) { return toposort_requirements( invert( G ), result ); } //------------------------------------------------------------------------------------------------- // Main Program //------------------------------------------------------------------------------------------------- #include #include #include #include #include Graph ask_for_G() { typedef std::string Node; Graph 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 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 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!
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.
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).
Yeah, found by a headhunter. It is a really cool company, one I would really have enjoyed working for. But alas, no go.
Topic archived. No new replies allowed.