SRM 705, D2, 500-Pointer (AlphabetOrderDiv2)

James S. Plank

Wed Oct 6 14:40:49 EDT 2021

Problem Statement.
A main() with the examples compiled in. Use "-" to enter the vector of words on standard input.
A skeleton that compiles with main.cpp.
tests.sh
answers.txt
Problem Given in Topcoder: January, 2017
Competitors who opened the problem: 243
Competitors who submitted a solution: 139
Number of correct solutions: 73
Accuracy (percentage correct vs those who opened): 30.0%
Average Correct Time: 30 minutes, 47 seconds.

In case topcoder's servers are down

Here's a summary of the problem:

You are given a vector of lower-case words.
Your job is to determine whether there is an ordering of the letters where the following is true: For every pair of adjacent letters in every word, the letters do not appear out of order.
If you can't find a valid ordering of the letters, return "Impossible".
Otherwise, return "Possible"
Constraints are that the vector has ≤ 100 words, and each word has ≤ 100 characters.

Examples:

Example 0:
  {"single","round","match"}
  Returns: "Possible"
  One possible ordering of the letters is: "bfjkmapqrositchundglevwxyz".

Example 1:	
  {"topcoder","topcoder"}
  Returns: "Impossible"
  The word "topcoder" can never be a good word. The character 'o' cannot be both before 'p' and after 'p'.

Example 2:	
  {"algorithm", "contest"}
  Returns: "Impossible"

Example 3:	
  {"pink","floyd"}
  Returns: "Possible"

Example 4:	
  {"gimnasia","y","esgrima","la","plata"}
  Returns: "Impossible"

Example 5:	
  {"hello","hello"}
  Returns: "Possible"
  This is a good word for any ordering of the letters in which 'h', 'e', 'l', and 'o' appear in this order.

Example 6:	
  {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}
  Returns: "Possible"
  In this case the English alphabet is a valid ordering.

Example 7:	
  {"abc","bca"}
  Returns: "Impossible"
  'a' must come before 'c' (because of the first word) and after 'c' (because of the second word) and that is a contradiction.

Example 8:	
  {"aaaaa","eeeee","iiiii","ooooo","uuuuu"} 
  Returns: "Possible"
  Any order is valid in this case

Example 9:	
{"ab","bc","ca"}
Returns: "Impossible"

Testing yourself

I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt.

Hints - A first solution that is easier to program

This is a cycle detection problem. Treat each character as a node in a graph. There is an edge from node i to node j if the characters i and j are adjacent to each other in any of the words. Then:

if the graph has a cycle, it's impossible to find an ordering of the letters.
If the graph has no cycle, then you can find a valid ordering.

Now, before you go blasting away writing a DFS for cycle detection, think a little more. If you have this graph, how can you determine a legal ordering of the letters? The answer is Topological Sort. The precendence relationship on letters is the exact same as for a topological sort.

How does that help you? Well, if you create the graph, and do a topological sort on it, and it completes, then you have found a valid orer, and it's "Possible". If you do the topological sort and it can't complete, that's because the graph has a cycle. You can then return "Impossible".

I have commented code for this -- you can see it with colored comments here.

A second solution which is harder to program

You can also solve this with DFS, but in my opinion, it's trickier. It has to do with the starting nodes, directed edges and not wanting to replicate work. In the abstract, it's simple: Use DFS to perform cycle detection on each node. If you find a cycle, then it is "Impossible." If you don't, find a cycle on any node, then return "Possible."

If this were an undirected graph, then all you need is a visited array, which is a boolean. See the section entitled "Depth First Search To Perform Cycle Detection", from the DFS lecture notes from CS302 for a nice example.

In a directed graph, it's a little trickier. The reason is that in an undirected graph, if there is a path from A to B, then there is a path from B to A. That is not true in a directed graph.

What I do to handle the directed graph is make visited an integer, which can hold one of three values:

Zero means that the node has never been visited in the DFS.
One means that the node is currently being visited by the DFS to determine if it is in a cycle.
Two means that the node's DFS has completed, and it's not part of a cycle.

This allows you do perform the DFS for cycle detection efficiently. Let me give you an example with pictures. Suppose that the two words are "cat" and "cot". This will give you the following graph:

You'll note that this graph has no cycles. Were it undirected, it would have a cycle. Now, suppose you run through the letters in order to detect cycles. You start with 'a'. When you call DFS on it, you set visited to one, and you will then call DFS on 't':

This will set t's visited field to one, and since there are no outgoing edges, the DFS will complete instantly. There is no cycle with 't', so you set its visited field to two, and return to 'a':

Now, 'a' is done. You set its visited field to two, and the DFS returns that there is no cycle with 'a'. Here's the state of the graph:

Next, you call DFS on 'c'. This sets its visited field to one, and calls DFS on 'a'. Since 'a' has completed its DFS, you return instantly that there is no cycle with 'a'. Here's the state of the graph:

Next, you process the edges from 'c' to 'o', and call DFS on 'o'. This will set o's visited field to one, and it will call DFS on 't':

Since 't' has completed its DFS, you return instantly that there is no cycle with 't'. Now, 'o' can return that there is no cycle, as can 'c':

You will call DFS on 'o' and 't' next, but they are already done. Now, you're done and can return "Possible", because there are no cycles in the graph.

I have commented code for this too -- you can see it with colored comments here.