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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
// 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!
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.
Registered users can post here. Sign in or register to post.