Schedule
A.First Edition
This is first edition of my schedule class which is originated from Dr. Peter Grogono who gave me the source
code from a modula3.
The problem is just another routine DFS or DFA problem which is even simpler than some of my discrete mathematics
problems. However, the author of program was such a stingy person that not a single comment was written as if he
felt his program is the easiest to be understood. The strike of "metro" forced me to read the source code in platform
and it is like this:
5 courses and each of them has some lectures to be given during 20 periods. (number of lectures:
int requirement[CourseNumber]={6,10,14,6,4};) And there are basically three kinds of constraints.
1. Course vs. period constraints: Certain course cannot be given at certain period and it is described by a
"available" array:
bool available[CourseNumber][PeriodNumber];
available[0][0]=false;
available[0][1]=false;
available[0][12]=false;
available[0][15]=false;
available[1][2]=false;
available[1][3]=false;
available[1][5]=false;
available[1][8]=false;
available[2][0]=false;
available[2][1]=false;
available[2][2]=false;
available[2][7]=false;
available[2][12]=false;
available[2][17]=false;
available[3][3]=false;
available[3][4]=false;
available[3][5]=false;
available[3][17]=false;
2. Course vs. course constraints: Some courses cannot be given at same period and it is described by a "conflict"
array:
bool conflict[CourseNumber][PeriodNumber];
conflict[0][1] = true;
conflict[0][4] = true;
conflict[1][3] = true;
conflict[2][4] = true;
conflict[3][4] = true;
3. The number of classrooms limits the maximum number of lectures given at same period. However, the problem is
rather simple as all 40 lectures can be given across 20 period * 2 classrooms.
How to arrange lectures?
For a DFA, you need to define the "alphabet", here it is the index of courses. And we should define the symbol-
checking method and necessary output methods.
C.Further improvement
//this is main.cpp
#include <iostream>
#include <iomanip>
#include "DFA.h"
using namespace std;
const int RoomNumber=2;
const int CourseNumber=5;
const int PeriodNumber=20;
//the true means available, instead of false in original problem which is
//against intuition: which course can be given at which period
bool available[CourseNumber][PeriodNumber]={true};
//which two courses cannot be given on same time
bool conflict[CourseNumber][CourseNumber]={false};
//number of lectures required for each course
int requirement[CourseNumber]={6,10,14,6,4};
//to bookkeep the number of lecture scheduled already
int lectureNumber[CourseNumber]={0};
char* weekStr[5]={"mon","tue", "wed","thr","fri"};
class Schedule: public DFA
{
protected:
virtual void output();
virtual bool evaluate();
virtual bool checkSymbol(int sonData);
virtual void doUpdate(int sonData);
virtual void doRestore(int sonData);
public:
void initialize();
};
int main()
{
Schedule S;
S.initialize();
S.setParam(5, 40, NULL, true);
S.search();
cout<<S.getCount()<<endl;
return 0;
}
void Schedule::output()
{
for (int i=0; i<5; i++)
{
cout<<setw(12)<<weekStr[i];
}
cout<<endl;
cout<<"solution no."<<count<<endl;
for (i=0; i<CourseNumber; i++)
{
for (int j=0; j<PeriodNumber; j++)
{
cout<<setw(3);
if (path[j*2]==i||path[j*2+1]==i)
{
cout<<"**";
}
else
{
cout<<"--";
}
}
cout<<endl;
}
}
void Schedule::initialize()
{
for (int i=0;i<CourseNumber; i++)
{
for (int j=0; j<PeriodNumber; j++)
{
available[i][j]=true;
}
}
available[0][0]=false;
available[0][1]=false;
available[0][12]=false;
available[0][15]=false;
available[1][2]=false;
available[1][3]=false;
available[1][5]=false;
available[1][8]=false;
available[2][0]=false;
available[2][1]=false;
available[2][2]=false;
available[2][7]=false;
available[2][12]=false;
available[2][17]=false;
available[3][3]=false;
available[3][4]=false;
available[3][5]=false;
available[3][17]=false;
conflict[0][1] = true;
conflict[0][4] = true;
conflict[1][3] = true;
conflict[2][4] = true;
conflict[3][4] = true;
}
//no special requirement since the maxlevel means success
bool Schedule::evaluate()
{
return level==40;
}
void Schedule::doUpdate(int sonData)
{
lectureNumber[sonData]++;
}
void Schedule::doRestore(int sonData)
{
lectureNumber[sonData]--;
}
bool Schedule::checkSymbol(int sonData)
{
int period = level/RoomNumber; //because the total level=period*number of room
int prevCourse;//, first, second;
//check available, if not, return...else go on test
if (!available[sonData][period])
{
return false;
}
//check conflict only if it is second room slot in same period
if (level%2!=0) //this means level is second course in same period
{
prevCourse=path[level-1];
//cannot conflict with itself
if (prevCourse>=sonData)
{
return false;
}
//who is smaller? first is the smaller
// first=prevCourse<sonData?prevCourse:sonData;
// second=prevCourse<sonData?sonData:prevCourse;
//even the course itself will conflict with itself
//however, I will initialize this info in conflict array
if (conflict[prevCourse][sonData])
{
return false;
}
}
//check if it exceeds the requirement
if (lectureNumber[sonData]==requirement[sonData])
{
return false;
}
return true;
}
//This is file DFA.h
///////////////////////////////////////////////////////
//file: DFA.h-------the header file of DFA class
//author: Qingzhe Huang
//date: Sep. 26, 2003
//class name: DFA---Deterministic Finite Automaton
//Purpose:
// 1. This class is a general searching class and it has
// an another name: DFA---Depth-First-Search.
// For all searching problem, we simply can store all possible choices
// into a choice list, and for each possible state, use a loop to test
// each choice. If return true, we can generate a new node, if not, test
// next. Before this assignment, I write all DFS by generating a tree of class
// nodes, but it simply too complicated. Now that efficiency is not the most
// important issue. I use recursive to simplify all pointer manipulations.
//
// 2. This class is an abstract base class, all derived class need to implement
// two basic function:
// a) checkSymbol: this gives the transition rule
// b) evaluate: this gives the success condition of searching
/////////////////////////////////////////////////////////////////////////////
#ifndef DFA_H
#define DFA_H
//I arbitrarily decide that the search level won't be more than 100 levels
const int MaxSearchLevel= 100;
class DFA
{
protected:
int count;
int symbolCount;
int maxLevel;
char** symbolStr;
int level;//is count, level 0 stores nothing!
bool findAll;
bool countOnly;
int path[MaxSearchLevel];
void generate();
void update(int sonData);
void restore(int sonData);
bool touchDown();
virtual void output();
virtual void doUpdate(int sonData);
virtual void doRestore(int sonData);
//derived class must overload these functions!
virtual bool evaluate()=0;
virtual bool checkSymbol(int sonData)=0;
public:
//size of sigma must be defined, if user has his own label string, must
//pass the string array pointer here, otherwise only output default index
void setParam(int symbolSize, int maxSearchLevel=20, char** symbolString=NULL,
bool findAllChoices=false, bool onlyCount=false);
int getCount() const { return count;}
void search();//simply call generate()
DFA(): count(0){;}
};
#endif
//This is file DFA.cpp
กก
/////////////////////////////////////////////////////////////
//file: DFA.cpp
//This is the implementation of class DFA
////////////////////////////////////////////////////////////
#include <iostream>
#include "DFA.H"
using namespace std;
//////////////////////////////////////////////////////////////////////////
//This function must be called before call search to begin searching
//as it will initialize all parameter of class
//Parameter:
// a)symbolSize: is the size of array of choices
// b)maxSearchLevel: is the max search level set by user, searching will
// stop whenever encounter this level limit.
// c)symbolString: is optional. It will display an array of user-defined
// strings when output
// d)findAllChoices: will not stop when find first target when set to be true
// e)onlyCount: will not output if set to be true
//////////////////////////////////////////////////////////////////////
void DFA::setParam(int symbolSize, int maxSearchLevel, char** symbolString,
bool findAllChoices, bool onlyCount)
{
symbolCount = symbolSize;
maxLevel = maxSearchLevel;
symbolStr = symbolString;
findAll = findAllChoices;
countOnly = onlyCount;
level = 0;
count = 0;
}
void DFA::search()
{
generate();
}
////////////////////////////////////////////////////////////////
//if user pass a string array pointer by "setParam" function, it
//will display result according to that array, otherwise it will
//simply display index of choices
////////////////////////////////////////////////////////////////
void DFA::output()
{
cout<<"Solution No."<<count<<" is:\n";
if (symbolStr==NULL)
{
for (int i=0; i<level; i++)
{
cout<<path[i]<<'\t';
}
}
else
{
for (int i=0; i<level; i++)
{
cout<<symbolStr[path[i]]<<'\t';
}
}
cout<<endl;
}
///////////////////////////////////////////////////////////////
//This is the major function which will recursively call itself to
//make the DFS search automatically.
//It uses a loop to check each choice to see if new node can be generated.
//If true, update itself, recursively call generate.
//It will stop generating when it reaches max Searching level which is setup
//by user at "setParam" function.
//////////////////////////////////////////////////////////////////////////
void DFA::generate()
{
if (level!=0)
{
//check before test bottom
if (evaluate())
{
count++;
if (!countOnly)
{
output();
}
//only want one solution
if (!findAll)
{
return;
}
}
}
//always check to ensure!
if (touchDown())
{
return;
}
for (int i=0; i< symbolCount; i++)
{
if (checkSymbol(i))
{
update(i);
generate();
restore(i);
}
}
}
////////////////////////////////////////////////////////////////////////
//user may want to do some extra updating job, so I leave that choice in
//function "doUpdate" which is a virtual function to be overrided.
//////////////////////////////////////////////////////////////////////
void DFA::update(int sonData)
{
level++;
path[level-1] = sonData;
doUpdate(sonData);
}
//////////////////////////////////////////////////////////////////////
//similarly if user wants extra job for "restoring", a virtual function
//"doRestore" can be overloaded.
/////////////////////////////////////////////////////////////////////
void DFA::restore(int sonData)
{
level--;
doRestore(sonData);
}
////////////////////////////////////////////////////////////////////////
//This function prevents inifinitely deep search in some cases when solution
//is easy to be found in other shallow nodes. Because it stops generating
//more nodes when this max searching level met.
//////////////////////////////////////////////////////////////////////////
bool DFA::touchDown()
{
return level==maxLevel;
}
void DFA::doRestore(int sonData)
{
//leave for user's choices!
}
void DFA::doUpdate(int sonData)
{
//leave for user's choices!
}
The following result is sorting 100 records by different field which is not what I mean to do.
mon tue wed thr fri solution no.1 -- -- ** ** ** ** ** ** -- -- -- -- -- -- -- -- -- -- -- -- ** ** -- -- -- -- -- -- -- ** ** ** ** ** ** ** -- ** -- -- -- -- -- ** ** ** ** -- ** ** ** ** -- ** ** ** ** -- ** ** -- -- ** -- -- -- -- ** ** -- -- -- -- -- -- -- ** -- ** ** ** ** -- -- -- -- -- -- -- -- -- -- ** -- -- -- -- ** -- -- mon tue wed thr fri solution no.2 -- -- ** ** ** ** ** ** -- -- -- -- -- -- -- -- -- -- -- -- ** ** -- -- -- -- -- -- -- ** ** ** ** ** ** -- ** ** -- -- -- -- -- ** ** ** ** -- ** ** ** ** -- ** ** ** ** -- ** ** -- -- ** -- -- -- -- ** ** -- -- -- -- -- -- ** -- -- ** ** ** ** -- -- -- -- -- -- -- -- -- -- ** -- -- -- -- ** -- -- mon tue wed thr fri solution no.3 -- -- ** ** ** ** ** ** -- -- -- -- -- -- -- -- -- -- -- -- ** ** -- -- -- -- -- -- -- ** ** ** ** ** ** -- -- ** ** -- -- -- -- ** ** ** ** -- ** ** ** ** -- ** ** ** ** -- ** ** -- -- ** -- -- -- -- ** ** -- -- -- -- -- -- ** ** -- -- ** ** ** -- -- -- -- -- -- -- -- -- -- ** -- -- -- -- ** -- -- mon tue wed thr fri solution no.4 -- -- ** ** ** ** ** ** -- -- -- -- -- -- -- -- -- -- -- -- ** ** -- -- -- -- -- -- -- ** ** ** ** ** ** -- -- ** -- ** -- -- -- ** ** ** ** -- ** ** ** ** -- ** ** ** ** -- ** ** -- -- ** -- -- -- -- ** ** -- -- -- -- -- -- ** ** -- ** -- ** ** -- -- -- -- -- -- -- -- -- -- ** -- -- -- -- ** -- -- mon tue wed thr fri solution no.5 -- -- ** ** ** ** ** ** -- -- -- -- -- -- -- -- -- -- -- -- ** ** -- -- -- -- -- -- -- ** ** ** ** ** -- ** ** ** -- -- -- -- -- ** ** ** ** -- ** ** ** ** -- ** ** ** ** -- ** ** -- -- ** -- -- -- -- ** ** -- -- -- -- -- ** -- -- -- ** ** ** ** -- -- -- -- -- -- -- -- -- -- ** -- -- -- -- ** -- --
......
กก
mon tue wed thr fri
solution no.80
-- -- ** ** ** ** ** ** -- -- -- -- -- -- -- -- -- -- -- --
** ** -- -- -- -- -- -- -- -- -- ** ** ** ** ** -- ** ** **
-- -- -- ** ** ** ** -- ** ** ** ** -- ** ** ** ** -- ** **
-- -- ** -- -- -- -- ** ** ** ** -- -- -- -- -- ** -- -- --
** ** -- -- -- -- -- -- -- -- -- -- ** -- -- -- -- ** -- --
mon tue wed thr fri
solution no.81
-- -- ** ** ** ** ** ** -- -- -- -- -- -- -- -- -- -- -- --
** ** -- -- -- -- -- -- -- -- -- ** ** ** ** -- ** ** ** **
-- -- -- ** ** ** ** -- ** ** ** ** -- ** ** ** ** -- ** **
-- -- ** -- -- -- -- ** ** ** ** -- -- -- -- ** -- -- -- --
** ** -- -- -- -- -- -- -- -- -- -- ** -- -- -- -- ** -- --
mon tue wed thr fri
solution no.82
-- -- ** ** ** ** ** ** -- -- -- -- -- -- -- -- -- -- -- --
** ** -- -- -- -- -- -- -- -- -- ** ** ** -- ** ** ** ** **
-- -- -- ** ** ** ** -- ** ** ** ** -- ** ** ** ** -- ** **
-- -- ** -- -- -- -- ** ** ** ** -- -- -- ** -- -- -- -- --
** ** -- -- -- -- -- -- -- -- -- -- ** -- -- -- -- ** -- --
mon tue wed thr fri
solution no.83
-- -- ** ** ** ** ** ** -- -- -- -- -- -- -- -- -- -- -- --
** ** -- -- -- -- -- -- -- -- -- ** ** -- ** ** ** ** ** **
-- -- -- ** ** ** ** -- ** ** ** ** -- ** ** ** ** -- ** **
-- -- ** -- -- -- -- ** ** ** ** -- -- ** -- -- -- -- -- --
** ** -- -- -- -- -- -- -- -- -- -- ** -- -- -- -- ** -- --
mon tue wed thr fri
solution no.84
-- -- ** ** ** ** ** ** -- -- -- -- -- -- -- -- -- -- -- --
** ** -- -- -- -- -- -- -- -- -- -- ** ** ** ** ** ** ** **
-- -- -- ** ** ** ** -- ** ** ** ** -- ** ** ** ** -- ** **
-- -- ** -- -- -- -- ** ** ** ** ** -- -- -- -- -- -- -- --
** ** -- -- -- -- -- -- -- -- -- -- ** -- -- -- -- ** -- --
mon tue wed thr fri
solution no.85
-- -- ** ** ** ** -- ** ** -- -- -- -- -- -- -- -- -- -- --
** ** -- -- -- -- ** -- -- ** ** ** ** ** ** -- -- ** -- --
-- -- -- ** ** ** ** -- ** ** ** ** -- ** ** ** ** -- ** **
-- -- ** -- -- -- -- ** -- -- -- -- -- -- -- ** ** -- ** **
** ** -- -- -- -- -- -- -- -- -- -- ** -- -- -- -- ** -- --
mon tue wed thr fri
solution no.86
-- -- ** ** ** ** -- ** ** -- -- -- -- -- -- -- -- -- -- --
** ** -- -- -- -- ** -- -- ** ** ** ** ** -- ** -- ** -- --
-- -- -- ** ** ** ** -- ** ** ** ** -- ** ** ** ** -- ** **
-- -- ** -- -- -- -- ** -- -- -- -- -- -- ** -- ** -- ** **
** ** -- -- -- -- -- -- -- -- -- -- ** -- -- -- -- ** -- --
......