34 LOC Unmo mek mi feel so bad. Good going icymint and TJRAK. Nuff ratings, each code was excellent.
Anyways, I tried to cut down the code in mine 148 no look pretty.
Warning! The following code can be hazardous to your eyes
Code:
#include <list>
#include <stdio.h>
#define left_bank 0
#define right_bank 1
#define max_paths 5
struct State
{
char ML, CL, MR, CR, B;
State(char ml = 0, char cl = 0, char mr = 0, char cr = 0, char b = 0) : ML(ml), CL(cl), MR(mr), CR(cr), B(b){}
bool IsSateValid() { return ( ((ML >= CL)||(ML == 0)) && ((MR >= CR)||(MR == 0)) && ((MR >= 0)&&(ML >= 0)) && ((CR >= 0)&&(CL >= 0)) ); }
void GetNextState(int PathIndex, State & stateNext)
{
int mr = 0, cr = 0; //Number to move to the right bank
switch(PathIndex)
{
case 0: //Move 1M, 1C
mr = 1;
cr = 1;
break;
case 1: //Move 2M
mr = 2;
break;
case 2: //Move 2C
cr = 2;
break;
case 3: //Move 1M
mr = 1;
break;
case 4: //Move 1C
cr = 1;
break;
}
if(B == right_bank) //If boat on the left bank
{
mr *= -1;
cr *= -1;
}
stateNext = (*this);
stateNext.B = !B;
stateNext.MR += mr;
stateNext.CR += cr;
stateNext.ML -= mr;
stateNext.CL -= cr;
}
bool CompareStates(const State & stateOther) { return ( (stateOther.ML == ML) && (stateOther.CL == CL) && (stateOther.MR == MR) && (stateOther.CR == CR) && (stateOther.B == B) );}
};
int main()
{
/*
Start at the first state.
Save it to the current path.
(NOTE : Each state has 5 branches.)
Go to the next valid state using the lowest branch
Save that branch, all being OK
If the next valid state is a dead-end state, go back to the previous state and take the next higher branch and update the branch taken for that state(and keep going back if neccessary)
(NOTE: In effect this will delete the dead-end state from the list of states that are visited)
(A dead-end state is one which does not lead to a previously visited state in the current path)
(NOTE: If there are no new valid state then it satisfies the criteria for a dead-end state)
Check the state to see if it is the goal
*/
std::list<int> lpaths; //List of paths taken between states
std::list<int>::iterator itpaths;
std::list<State> lstates; //List of states that define the current path
std::list<State>::iterator itstates;
//Initial state and currebt state
State stateCurrent(0, 0, 3, 3, right_bank);
State stateDestination(3, 3, 0, 0, left_bank);
State stateNext;
int pathCurrent = 0;
//Save the current state to the current path
lstates.push_back(stateCurrent);
while(true)
{
STATE_OK:
if(stateCurrent.CompareStates(stateDestination))
goto STATE_END;
for( ; pathCurrent < max_paths; pathCurrent++)
{
stateCurrent.GetNextState(pathCurrent, stateNext);
if(stateNext.IsSateValid())
{
bool NextStateHasBeenVisitedBefore = false;
//Check if the next state has been visited before
for(itstates = lstates.begin(); itstates != lstates.end(); itstates++)
{
if(stateNext.CompareStates(*itstates))
NextStateHasBeenVisitedBefore = true;
}
if(!NextStateHasBeenVisitedBefore) //If next state is not a dead-end state
{
//Go to that state and save path
stateCurrent = stateNext;
lstates.push_back(stateCurrent);
lpaths.push_back(pathCurrent);
pathCurrent = 0; //The next current path is default to zero
goto STATE_OK;
}
}
}
DEAD_END_STATE:
lstates.pop_back(); //If there is nothing to pop then there is no solution
lpaths.pop_back(); //If there is nothing to pop then there is no solution
stateCurrent = lstates.back();
pathCurrent = lpaths.back();
pathCurrent++;
}
STATE_END:
//Display
for(itstates = lstates.begin(); itstates != lstates.end(); itstates++)
printf("M%d C%d M%d C%d\n", itstates->ML, itstates->CL, itstates->MR, itstates->CR);
return 0;
}