A. First Edition

This is the problem from topCoder practice room and I tried for two versions.

B.The problem

***Note:  Please keep programs under 7000 characters in length.  Thank you


Class Name: Prerequisites
Mathod Name: orderClasses
Parameters: String[]
Returns: String[]

You are a student at a college with the most unbelievably complex prerequisite
structure ever. To help you schedule your classes, you decided to put together
a program that returns the order in which the classes should be taken.  

Implement a class Prerequisites which contains a method orderClasses.  The
method takes a String[] that contains the classes you must take and returns a
String[] of classes in the order the classes should be taken so that all
prerequisites are met.

String[] elements will be of the form (and TopCoder will ensure this):
"CLASS: PRE1 PRE2 ..." where PRE1 and PRE2 are prerequisites of CLASS.  CLASS,
PRE1, PRE2, ... consist of a department name (3 or 4 capital letters, A-Z
inclusive) followed by a class number (an integer between 100 and 999,
inclusive).  The department name should be immediately followed by the class
number with no additional characters, numbers or spaces (i.e. MATH217).  It is
not necessary for a class to have prerequisites.  In such a case, the colon is
the last character in the String.  

You can only take one class at a time, therefore, use the following rules to
determine which class to take :
1) Any prerequisite class(es) listed for a class must be taken before the class
can be taken.
2) If multiple classes can be taken at the same time, you take the one with the
lowest number first, regardless of department.
3) If multiple classes with the same number can be taken at the same time, you
take the department name which comes first in alphabetical order.  
4) If the inputted course schedule has errors, return a String[] of length 0.
There is an error if it is impossible to return the classes in an order such
that all prerequisites are met, or if a prerequisite is a course that does not
have its own entry in the inputted String[].

Examples of valid input Strings are:
"CSE111: CSE110 MATH101"
"CSE110:"

Examples of invalid input Strings are:
"CS117:" (department name must consist of 3 - 4 capital letters, inclusive)
"cs117:" (department name must consist of 3 - 4 capital letters, inclusive)
"CS9E11:" (department name must be letters only)
"CSE110: " (no trailing spaces allowed)
"CSE110: CSE101 " (no trailing spaces allowed)
"MATH211: MAM2222" (class number to large)
"MATH211: MAM22" (class number to small)
"ENGIN517: MATH211" (department name to large)

Here is the method signature (be sure your method is public):
String[] orderClasses(String[] classSchedule);

TopCoder will make sure classSchedule contains between 1 and 20 Strings,
inclusive, all of the form above.  The Strings will have between 1 and 50
characters, inclusive.  TopCoder will check that the syntax of the Strings are
correct: The Strings will contain a valid class name, followed by a colon,
possibly followed by a series of unique prerequisite classes separated by
single spaces.  Also, TopCoder will ensure that each class has at most one
entry in the String[]. 

Examples:
If classSchedule={
"CSE121: CSE110",
"CSE110:",
"MATH122:",
}
The method should return: {"CSE110","CSE121","MATH122"}

If classSchedule={
"ENGL111: ENGL110",
"ENGL110: ENGL111"
}
The method should return: {}

If classSchedule=[
"ENGL111: ENGL110"
}
The method should return: {}

If classSchedule={
"CSE258: CSE244 CSE243 INTR100"
"CSE221: CSE254 INTR100"
"CSE254: CSE111 MATH210 INTR100"
"CSE244: CSE243 MATH210 INTR100"
"MATH210: INTR100"
"CSE101: INTR100"
"CSE111: INTR100"
"ECE201: CSE111 INTR100"
"ECE111: INTR100"
"CSE243: CSE254"
"INTR100:"
}
The method should return:
{"INTR100","CSE101","CSE111","ECE111","ECE201","MATH210","CSE254","CSE221","CSE2
43","CSE244","CSE258"}

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

At beginning I spent a lot of time in dreaming to implement a "clean" once for all sorting by using "dynamically" function

struct for a set such that whenever an element is removed the sequence will be automatically sorted by the predicate of

that "functor". However, this is a kind of illusion because "sorting" only happens when "inserting" an element happens in

STL set. You cannot force the "entire" set to sort again which is ridiculous unless you use another empty set to "reinsert"

all elements into it, but that is not what I considered as "clean".

So, at the beginning I was stuck to "set" and didn't realize that it was a "heap". Why? The set will give a "static" order

when all elements are in. However, the real order will NOT be exposed unless you "remove" the highest priority one which is

exactly the idea of "priority queue"!

So, it is as simple as defining a sorting predicate for heap! That is the key of second heap version. After all it is not

that difficult when you understand the key of problem. And most importantly do NOT have any unrealistic illusion and that

is always my problem in life and in coding.

D.The major functions

1. This is perhaps my first practical using of "make_heap", "pop_heap". In the past, I am not that keen on "algorithm" part

of STL. And they are really powerful.

2. The "predicate" is a bit confusing. It depends how you define your "priority". For example, the default heap is to use

"<" or "less" as predicate to give you the "great heap". In other word, every time you pop_heap you get the greatest one from

the current heap. So, this implies that your "predicate functor" should give false when "first param" has higher priority

than the "second param". i.e. if x has high priority than y, then "myPred(x,y) is false".

In all word, the "predicate" indicates the "less priority order" which is really an awkward expression!

3. When I deal with set, I am always very cautious about iterator when removing because "erase" doesn't guarantee if current

iterator is valid or not if you use "erase(iterator, key)". For insert(it, value), maybe it is safe if you guarantee value

is after "it". But it is not perfect.

E.Further improvement

F.File listing

1. heap_version(second)

2. set_version(first)(This is an awkward one!)

file: heap_version

#include <stdio.h>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
using namespace std;


struct MyClass
{
	string dept;
	string id;
	bool operator==(const MyClass& other) const
	{
		return dept.compare(other.dept)==0&&id.compare(other.id)==0;
	}
	const MyClass operator=(const MyClass& other)
	{
		dept.assign(other.dept);
		id.assign(other.id);
		return *this;
	}
	void display() const
	{
		printf("[%s%s]", dept.c_str(), id.c_str());
	}
};

struct MyClassNameComp
{
	bool operator()(const MyClass& first, const MyClass& second) const
	{
		int result;
		result=first.id.compare(second.id);
		if (result!=0)
		{
			return result>0;
		}
		return first.dept.compare(second.dept)>0;
	}
};


typedef vector<string> StringVector;
typedef set<MyClass, MyClassNameComp> MyClassSet;
typedef pair<MyClass, MyClassSet> MyClassSetMap;


struct MyClassSetMapComp
{
	bool operator()(const MyClassSetMap& first, const MyClassSetMap& second) const
	{
		MyClassSet::iterator it1, it2;
		//first compare with the size of two sets
		if (first.second.size()!=second.second.size())
		{
			return first.second.size()>second.second.size();
		}

		//this means the depend set are identical, then use alphabetic order for name
		return MyClassNameComp()(first.first, second.first);
	}
};

MyClassSetMapComp myClassSetMapComp;
typedef vector<MyClassSetMap> MyClassSetMapVector;
class Prerequisites
{
private:
	MyClassSetMapVector classDependTable;

	void parseString(string str, MyClass& myClass, MyClassSet& myClassSet);	
	void retrieveMyClass(const char* start, size_t len, MyClass& myClass);
	void addMyClassSetMap(MyClass& myClass, MyClassSet& myClassSet);
	void removeMyClassFromMap(MyClass& myClass, int len);
	void copySet(MyClassSet& dest, const MyClassSet& src);
public:
	StringVector orderClasses(StringVector param);
};


void display(const MyClassSet& myClassSet) 
{
	MyClassSet::const_iterator it;
	printf("(");
	for (it=myClassSet.begin(); it!=myClassSet.end(); it++)
	{
		it->display();
	}
	printf(")");
}

void display(const MyClassSetMap& myMap)
{
	printf("{");
	myMap.first.display();	
	display(myMap.second);
	printf("}\n");
}



void Prerequisites::removeMyClassFromMap(MyClass& myClass, int len)
{
	MyClassSet::iterator setIt;
	MyClassSetMap myMap;

	for (int i=0; i<len; i++)
	{
		classDependTable[i].second.erase(myClass); 
	}
}
		

void Prerequisites::addMyClassSetMap(MyClass& myClass, MyClassSet& myClassSet)
{
	classDependTable.push_back(make_pair(myClass, myClassSet));	
}

void Prerequisites::copySet(MyClassSet& dest, const MyClassSet& src)
{
	copy(src.begin(), src.end(), inserter(dest, dest.begin()));
}

StringVector Prerequisites::orderClasses(StringVector param)
{
	int i, len;
	string str;
	StringVector result;
	MyClass myClass;
	MyClassSet myClassSet;
	for (i=0; i<param.size(); i++)
	{
		myClassSet.clear();
		parseString(param[i], myClass, myClassSet);		
		addMyClassSetMap(myClass, myClassSet);
	}
		
	make_heap(classDependTable.begin(), classDependTable.end(), myClassSetMapComp);
	len=classDependTable.size();
	for (i=0; i<len; i++)
	{
		pop_heap(classDependTable.begin(), classDependTable.end()-i, myClassSetMapComp);
		
		removeMyClassFromMap(classDependTable[len-1-i].first, len-i-1);
		str.assign(classDependTable[len-i-1].first.dept);
		str.append(classDependTable[len-i-1].first.id);
		result.push_back(str);
	}
	return result;
}	

void Prerequisites::retrieveMyClass(const char* start, size_t len, MyClass& myClass)
{
	const char* ptr;
	ptr=start;
	while (*ptr>='A'&&*ptr<='Z')
	{
		ptr++;
	}
	myClass.dept.assign(start, ptr-start);
	myClass.id.assign(ptr, len-(ptr-start));
}
	
void Prerequisites::parseString(string str, MyClass& myClass, MyClassSet& myClassSet)
{
	MyClass myClassInserted;
			
	string::size_type pos=0, start, end;
	pos = str.find_first_of(':', pos);
	start=0;
	end=pos;
	retrieveMyClass(str.c_str(), end-start, myClass);
	pos++;
	
	while (true)
	{
		//move to next possible
		pos++;
		if (pos>=str.size())
		{
			break;
		}
		start=pos;
		pos=str.find_first_of(' ', pos);
		if (pos==string::npos)
		{
			//this is the last class
			end=str.size();						
		}
		else
		{
			end=pos;
		}

		retrieveMyClass(str.c_str()+start, end-start, myClassInserted);
		myClassSet.insert(myClassInserted);
		if (pos==string::npos)
		{
			break;					
		}		
	}
}
			

	

///////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////////

file: set_version(bad)

#include <stdio.h>
#include <set>
#include <map>
#include <string>
#include <vector>
using namespace std;


struct MyClass
{
	string dept;
	string id;
	bool operator==(const MyClass& other) const
	{
		return dept.compare(other.dept)==0&&id.compare(other.id)==0;
	}
	const MyClass operator=(const MyClass& other)
	{
		dept.assign(other.dept);
		id.assign(other.id);
		return *this;
	}
	void display() const
	{
		printf("[%s%s]", dept.c_str(), id.c_str());
	}
};

struct MyClassNameComp
{
	bool operator()(const MyClass& first, const MyClass& second) const
	{
		int result;
		result=first.id.compare(second.id);
		if (result!=0)
		{
			return result<0;
		}
		return first.dept.compare(second.dept)<0;
	}
	bool operator()(const MyClass& first, const MyClass& second) 
	{
		int result;
		result=first.id.compare(second.id);
		if (result!=0)
		{
			return result<0;
		}
		return first.dept.compare(second.dept)<0;
	}
};


typedef vector<string> StringVector;
typedef set<MyClass, MyClassNameComp> MyClassSet;
typedef pair<MyClass, MyClassSet> MyClassSetMap;

struct MyClassSetMapComp
{
	bool operator()(const MyClassSetMap& first, const MyClassSetMap& second) const
	{
		MyClassSet::iterator it1, it2;
		//first compare with the size of two sets
		if (first.second.size()!=second.second.size())
		{
			return first.second.size()<second.second.size();
		}
		/*
		//for same size of depending set, we compare the element like alphabetic but according to MyClassName rules
		//this is because those element in front must represent those without depending set, and their order must be 
		//done with alphabetic order. i.e. no-prerequisite class are all available and done by alphabetic order
		for (it1=first.second.begin(), it2=second.second.begin(); it1!=first.second.end();it1++, it2++)
		{
			if (MyClassNameComp()(*it1, *it2))
			{
				return true;
			}
			else
			{
				if (MyClassNameComp()(*it2, *it1))
				{
					return false;
				}
				//it1, it2 must be identical, so go on
			}
		}
		*/
		//this means the depend set are identical, then use alphabetic order for name
		return MyClassNameComp()(first.first, second.first);
	}
	
	bool operator()(const MyClassSetMap& first, const MyClassSetMap& second)
	{
		MyClassSet::iterator it1, it2;
		//first compare with the size of two sets
		if (first.second.size()!=second.second.size())
		{
			return first.second.size()<second.second.size();
		}
		//for same size of depending set, we compare the element like alphabetic but according to MyClassName rules
		//this is because those element in front must represent those without depending set, and their order must be 
		//done with alphabetic order. i.e. no-prerequisite class are all available and done by alphabetic order
		/*
		for (it1=first.second.begin(), it2=second.second.begin(); it1!=first.second.end();it1++, it2++)
		{
			if (MyClassNameComp()(*it1, *it2))
			{
				return true;
			}
			else
			{
				if (MyClassNameComp()(*it2, *it1))
				{
					return false;
				}
				//it1, it2 must be identical, so go on
			}
		}
		*/
		//this means the depend set are identical, then use alphabetic order for name
		return MyClassNameComp()(first.first, second.first);
	}

};

typedef set<MyClassSetMap, MyClassSetMapComp> MyClassSetMapSet;
class Prerequisites
{
private:
	MyClassSetMapSet classDependSets;
	//MyClassSetMap classDecideSet;
	void parseString(string str, MyClass& myClass, MyClassSet& myClassSet);	
	void retrieveMyClass(const char* start, size_t len, MyClass& myClass);
	void addMyClassSetMap(MyClass& myClass, MyClassSet& myClassSet);
	void removeMyClassFromMap(MyClass& myClass);
	void copySet(MyClassSet& dest, const MyClassSet& src);

	
	
public:
	StringVector orderClasses(StringVector param);
};


void display(const MyClassSet& myClassSet) 
{
	MyClassSet::const_iterator it;
	printf("(");
	for (it=myClassSet.begin(); it!=myClassSet.end(); it++)
	{
		it->display();
	}
	printf(")");
}

void display(const MyClassSetMap& myMap)
{
	printf("{");
	myMap.first.display();	
	display(myMap.second);
	printf("}\n");
}

void display(const MyClassSetMapSet& mapSet)
{
	MyClassSetMapSet::const_iterator it;
	for (it=mapSet.begin(); it!=mapSet.end(); it++)
	{
		display(*it);
	}
}



void Prerequisites::removeMyClassFromMap(MyClass& myClass)
{
	MyClassSetMapSet::iterator it;
	MyClassSet::iterator setIt;
	MyClassSetMap myMap;
	while (true)
	{
		it=classDependSets.begin(); 
		while (it!=classDependSets.end())
		{
			setIt=it->second.find(myClass);
			if (setIt==it->second.end())
			{
				it++;
			}
			else
			{
				break;
			}
		}
		if (it==classDependSets.end())
		{
			break;
		}
		//it->second.erase(myClass);
		
		myMap.first=it->first;
		myMap.second.clear();
		copySet(myMap.second, it->second);
		myMap.second.erase(myClass);
		//printf("\nafter erase the class, the inserted map is********\n");
		//display(myMap);

		classDependSets.erase(it);
		classDependSets.insert(myMap);
	}
}
		

void Prerequisites::addMyClassSetMap(MyClass& myClass, MyClassSet& myClassSet)
{
	MyClassSetMapSet::iterator mapIt;
	MyClassSet::iterator setIt;
	MyClassSetMap myMap;
	classDependSets.insert(make_pair(myClass, myClassSet));	
	//display(myClassSet);
	//display(classDependSets);
	
	/*
	//now expand set
	for (mapIt=classDependSets.begin(); mapIt!=classDependSets.end(); mapIt++)
	{
		if (mapIt->second.find(myClass)!=mapIt->second.end())
		{
			for (setIt=myClassSet.begin(); setIt!=myClassSet.end(); setIt++)
			{
				mapIt->second.insert(*setIt);
			}
			myMap.first.assign(mapIt->first);
			copySet(myMap.second, mapIt->second);
			classDependSets.erase(mapIt);
			classDependSets.insert(mapIt, myMap);
		}
	}
	*/
}

void Prerequisites::copySet(MyClassSet& dest, const MyClassSet& src)
{
	MyClassSet::const_iterator it;
	for (it=src.begin(); it!=src.end(); it++)
	{
		dest.insert(*it);
	}
}

StringVector Prerequisites::orderClasses(StringVector param)
{
	int i;
	string str;
	StringVector result;
	MyClass myClass;
	MyClassSetMapSet::iterator it;
	MyClassSet myClassSet;
	MyClassSet::iterator setIt;
	for (i=0; i<param.size(); i++)
	{
		myClassSet.clear();
		parseString(param[i], myClass, myClassSet);		
		addMyClassSetMap(myClass, myClassSet);
	}
		
	//printf("before removing classes\n");
	
	//display(classDependSets);
	//printf("before removing classes\n**************\n");
	do
	{
		it=classDependSets.begin();
		if (it->second.size()!=0)
		{
			display(*it);
			result.clear();
			break;
		}
		str.assign(it->first.dept);
		str.append(it->first.id);
		result.push_back(str);
		myClass=it->first;
		classDependSets.erase(it);
		
		//printf("before remove class:");
		//myClass.display();
		//printf("\n******************\n");
		//display(classDependSets);
		
		removeMyClassFromMap(myClass);
		//printf("\nafter remove class:\n");
		
		//display(classDependSets);
		//printf("\n****************************\n");
	}
	while (classDependSets.size()>0);
	return result;
}	

void Prerequisites::retrieveMyClass(const char* start, size_t len, MyClass& myClass)
{
	const char* ptr;
	ptr=start;
	while (*ptr>='A'&&*ptr<='Z')
	{
		ptr++;
	}
	myClass.dept.assign(start, ptr-start);
	myClass.id.assign(ptr, len-(ptr-start));
}
	
void Prerequisites::parseString(string str, MyClass& myClass, MyClassSet& myClassSet)
{
	MyClass myClassInserted;
			
	string::size_type pos=0, start, end;
	pos = str.find_first_of(':', pos);
	start=0;
	end=pos;
	retrieveMyClass(str.c_str(), end-start, myClass);
	pos++;
	
	while (true)
	{
		//move to next possible
		pos++;
		if (pos>=str.size())
		{
			break;
		}
		start=pos;
		pos=str.find_first_of(' ', pos);
		if (pos==string::npos)
		{
			//this is the last class
			end=str.size();						
		}
		else
		{
			end=pos;
		}

		retrieveMyClass(str.c_str()+start, end-start, myClassInserted);
		myClassSet.insert(myClassInserted);
		if (pos==string::npos)
		{
			break;					
		}		
	}
}

////////////////////////

//test cases:

/*
const char* classSchedule[11]=
{
	"CSE258: CSE244 CSE243 INTR100",
	"CSE221: CSE254 INTR100",
	"CSE254: CSE111 MATH210 INTR100",
	"CSE244: CSE243 MATH210 INTR100",
	"MATH210: INTR100",
	"CSE101: INTR100",
	"CSE111: INTR100",
	"ECE201: CSE111 INTR100",
	"ECE111: INTR100",
	"CSE243: CSE254",
	"INTR100:",
};
*/

/*
const char* classSchedule[]=
{
	"ENGL111: ENGL110"
};
*/

/*
const char* classSchedule[]=
{
	"ENGL111: ENGL110",
	"ENGL110: ENGL111"
};
*/


const char* classSchedule[]=
{
	"CSE121: CSE110",
	"CSE110:",
	"MATH122:",
};

int main()
{
	int i;
	int length=3;
	StringVector strVector, result;
	Prerequisites pre;

	for (i=0; i<length; i++)
	{

		strVector.push_back(string(classSchedule[i]));
	}

	result=pre.orderClasses(strVector);

	for (i=0; i<result.size(); i++)
	{
		printf("%s\n", result[i].c_str());
	}

	return 0;
}