Missionary
A.First Edition
This is my first edition of my Missionary class inherited from DFSArray class, so you can also regard it as
an application of DFS class.
Basically you should realize that there are actually 10 possible choices for shipping at every occation.
MM_LR, BB_LR, MB_LR, M_LR, B_LR, MM_RL, BB_RL, MB_RL, M_RL, B_RL: LR stands for from LEFT TO RIGHT, RL is opposite.
And MM stands for two missionaries, BB for two barbarians, M of course stands for one missionary, B stands for
one barbarian, MB stands for one missionary and one barbarian.
So, we actually figure out all possible choices. Then the job is only how to verify the options which is quite
a bit complicated. I designed a structure to hold the info for the ten choices. And in the class Missionary, there
is a private member Position which records the state of game. It is the problem that when and how should we update
this state!
As you know, I already compile the DFS class into object file (.obj file) and from that I use the "lib" command to
make it a .lib file and put it into the "lib" directory under "vc98". And the "DFSArray.h" file was placed in
directory "include". On the project setting menu, I insert the name of "DFSArray.lib". So, this implies that my
DFSArray class is actually not reachable for source code! I cannot change anything from the base class!
This really creates some trouble if your base class is not designed properly. For example, the Position array
cannot be updated when verifying data as in function "validateOption(int sonData)", you have no access to your
son node. Then you can only do the synchronization action when you add son nodes. This is rather complicated!
1. bool Missionary::evaluate()
This function tests the son node, but you need to synchronize Position with "data", otherwise, you will only check
the parent Position as when new node is created, Position are copied from parent.
2. bool Missionary::validateOption(int sonData)
There is a lot of issues needed to be taken care with! First, check if boat is available for the option which is
simple. Second, there should be enough person to be shipped to other side and barbarians can never outnumber
missionaries at either sides of river. Third, check if direct repetition or indirect repetition is made. Direct
means you ship something back immediately after you ship it here. But indirect is a little tricky! At beginning
my program is cunning enough to produce a lot of indirect repetition---after several rounds, it become the original
starting state. So, I add an extra condition-checking function to see if original starting state is reached.
E.Further improvement
1. You tell me!
DFSArray.h (placed in "include" directory under vc98)
#ifndef DFSARRAY_H #define DFSARRAY_H #include <iostream> using namespace std; const int MaxSonCount=8; const int MaxLevel =20; const int MaxOptions = 10; const int MaxNodeCount = 1000; class DFS { private: void initialize(DFS* now); static DFS* nodeList[MaxNodeCount]; static bool findAll; static int optionArray[MaxOptions]; static int optionCount; static char** nameString; static int solutionCount; static int maxLevel; static int domino; void addSon(int sonData); bool touchDown(); void setMaxLevel(int max) { maxLevel = max;} DFS* upDate(); bool hasBrother(); DFS* nextBrother(); bool generate(); DFS* findNext(); DFS* getNode(int theIndex){return nodeList[theIndex];} void putNode(int theIndex) { nodeList[theIndex] = this;} DFS* getParent(){return getNode(parent);} bool hasParent(){return parent!=-1;} protected: int parent; int sonCount; int sonIndex; int son; int depth; int index;//index in nodeList int data; void backTrack(); static int trackRecord[MaxLevel]; virtual DFS* createSon(); virtual bool validateOption(int sonData); virtual void onLeave(); virtual bool evaluate(); virtual void collectResult(); public: int getSolutionCount(){ return solutionCount;} void setOptions(int* array, int size); void setNameStr(char** str){nameString = str;} void beginCount(int max, bool findall=false); }; #endif
DFSArray.lib is placed in "lib" directory under "vc98" directory!
missionary.cpp
#include <DFSArray.h> using namespace std; enum RiverSide {LEFT, RIGHT}; enum People {MISSIONARY, BARBARIAN}; struct Action { int people[2]; RiverSide riverSide; }; Action actionArray[10] = {{{2,0},LEFT}, {{0,2}, LEFT}, {{1,1},LEFT},{{1,0},LEFT}, {{0,1}, LEFT}, {{2,0},RIGHT}, {{0,2}, RIGHT}, {{1,1,}, RIGHT}, {{1,0}, RIGHT},{{0,1},RIGHT}}; //2M, 2B, 1M1B, 1M, 1B and LR means from left to right, RL is opposite enum OptionType {MM_LR, BB_LR, MB_LR, M_LR, B_LR, MM_RL, BB_RL, MB_RL, M_RL, B_RL}; //3 missionary are at left side of river //3 barbarian are also at left side int optionArray[10] = {MM_LR, BB_LR, MB_LR, M_LR, B_LR, MM_RL, BB_RL, MB_RL, M_RL, B_RL}; char* optionString[10] = {"MM_LR", "BB_LR", "MB_LR", "M_LR", "B_LR", "MM_RL", "BB_RL", "MB_RL", "M_RL", "B_RL"}; bool isRoot = true; class Missionary: public DFS { private: int Position[2][2]; RiverSide boat; bool isLooping(int sonData); bool checkData(int sonData); bool initialized; protected: bool validateOption(int sonData); DFS* createSon(); bool evaluate(); public: Missionary(); }; int main() { Missionary M; M.setNameStr(optionString); M.setOptions(optionArray, 10); M.beginCount(20, true); return 0; } Missionary::Missionary() { if (isRoot) { Position[MISSIONARY][LEFT] = 3; Position[MISSIONARY][RIGHT]=0; Position[BARBARIAN][LEFT] = 3; Position[BARBARIAN][RIGHT]=0; isRoot = false; boat = LEFT; } initialized =false; } bool Missionary::evaluate() { if (!initialized&&parent!=-1)//this is the first son { RiverSide river = actionArray[data].riverSide; RiverSide opposite = (river==LEFT?RIGHT:LEFT); //initialize Position so that it reflects the move //this is ackward as I cannot access son Ptr anymore Position[MISSIONARY][river]-= actionArray[data].people[MISSIONARY]; Position[MISSIONARY][opposite] += actionArray[data].people[MISSIONARY]; Position[BARBARIAN][river]-= actionArray[data].people[BARBARIAN]; Position[BARBARIAN][opposite] += actionArray[data].people[BARBARIAN]; boat = (boat==LEFT?RIGHT:LEFT); initialized = true; } return Position[MISSIONARY][RIGHT]==3; } bool Missionary::isLooping(int sonData) { backTrack(); return (trackRecord[depth-1] - sonData==5)||(sonData - trackRecord[depth-1] ==5); } bool Missionary::checkData(int sonData) { RiverSide river = actionArray[sonData].riverSide; RiverSide opposite = (river==LEFT?RIGHT:LEFT); if (river==RIGHT &&Position[MISSIONARY][river] - actionArray[sonData].people[MISSIONARY]==0 &&Position[BARBARIAN][river] - actionArray[sonData].people[BARBARIAN]==0) return false; return ((Position[MISSIONARY][river] - actionArray[sonData].people[MISSIONARY]>= Position[BARBARIAN][river] - actionArray[sonData].people[BARBARIAN]) ||(Position[MISSIONARY][river] - actionArray[sonData].people[MISSIONARY]==0)) && ((Position[MISSIONARY][opposite]+ actionArray[sonData].people[MISSIONARY]>= Position[BARBARIAN][opposite]+actionArray[sonData].people[BARBARIAN]) ||(Position[MISSIONARY][opposite]+ actionArray[sonData].people[MISSIONARY]==0)); } bool Missionary::validateOption(int sonData) { if (!initialized&&parent!=-1)//this is the first son { RiverSide river = actionArray[data].riverSide; RiverSide opposite = (river==LEFT?RIGHT:LEFT); //initialize Position so that it reflects the move //this is ackward as I cannot access son Ptr anymore Position[MISSIONARY][river]-= actionArray[data].people[MISSIONARY]; Position[MISSIONARY][opposite] += actionArray[data].people[MISSIONARY]; Position[BARBARIAN][river]-= actionArray[data].people[BARBARIAN]; Position[BARBARIAN][opposite] += actionArray[data].people[BARBARIAN]; boat = (boat==LEFT?RIGHT:LEFT); initialized = true; } if (boat!=actionArray[sonData].riverSide) { return false; } else { if (Position[MISSIONARY][boat]<actionArray[sonData].people[MISSIONARY]|| Position[BARBARIAN][boat]<actionArray[sonData].people[BARBARIAN]) { return false; } if (!isLooping(sonData)) { if (checkData(sonData)) { return true; } } } return false; } DFS* Missionary::createSon() { DFS* ptr= new Missionary; for (int i=0; i<2; i++) { for (int j=0; j<2; j++) { ((Missionary*)(ptr))->Position[i][j] = Position[i][j]; } ((Missionary*)(ptr))->boat = boat; } return ptr; }
Running result of program:
The route is:BB_LR, B_RL, BB_LR, B_RL, MM_LR, MB_RL, MM_LR, It is number:0 The route is:MB_LR, M_RL, BB_LR, B_RL, MM_LR, MB_RL, MM_LR, It is number:1 Press any key to continue
Do you understand the result? It means 2B go, 1B back, 2B go, 1B back, 2M go, 1M1B back, 2M go-->succeed!