1. TJRAK well i must say congratulations.

Defining the problem
LOC
Simplicity of Logic
Diplay Function

I really like your solution. Also like that you beat my 97 LOC.

Goodwork.

Icymint i don't have to tell you goodwork, once again you have proven to be a superior mind and judging from comments i have seen on your work i would say others in here would agree.

2. It is officially Monday so i can go ahead and place my intial solution. Well this was how i approached the problem.

I think my logics are straight forward. I created a struct to store Cannibals and Missionary. Then i used that struct to created a LEFTSIDE and a RIGHTSIDE.

To solve the crossing issue only a if statement coupled with a move heuristics was needed.

if( T.miss == T.can || T.miss == FALSE || T.miss == NUM )return x;

In defining a move scheme, I realised that there was only 3 possible moves when on the rightside and 3 when on the leftside.

Now i am aware and have always been aware that i could greatly reduce the LOC but i don't generally post those i just post intial solution. I am looking bad in my challenge so i may have to really revise it and post my 50 LOC but i doubt i shall. I shall instead humbly accept defeat.

Without further ado here is my solution:
Code:
```// Name        : DPD
// Program     : River Crossing
// Description : This simulate a problem of 3 missionsries and 3 cannibals
//               crossing a river.
// Date        : AUG 3, 2005
// Last Updated: ----------
// Proposed mod: I can makde Right Move and leftMove one Function aand eliminate
//                most of display to make program approximately 80 LOC

#include <stdio.h>
#include <conio.h>

#define NUM 3
enum mode{ FALSE, TRUE };

typedef struct
{
int miss;
int can;
}Players;

//After every move display current postion.
void Display( Players , Players  );
//Accepts move from the righthand.
void LeftMove( Players *, Players * );
//Accepts move from the lefthand
void RightMove( Players *, Players * );
//Test to find a valid move.
int Validate( Players Moves[], Players *);

void main()
{
Players rightSide = {NUM,NUM};
Players leftSide = {0,0};
Display( rightSide, leftSide );
while( TRUE )
{
LeftMove( &leftSide, &rightSide );
Display( rightSide, leftSide );
if( leftSide.miss == NUM && leftSide.can == NUM )return;
RightMove( &leftSide, &rightSide );
Display( rightSide, leftSide );
}
}

void LeftMove( Players *leftSide, Players *rightSide )
{
Players Moves[3]= {{2,0 },{ 0,2 }, { 1,1 }};
int ans;

ans = Validate( Moves, leftSide );

leftSide->miss += Moves[ans].miss;
leftSide->can += Moves[ans].can;

rightSide->miss -= Moves[ans].miss;
rightSide->can -= Moves[ans].can;
}

void RightMove( Players *leftSide, Players *rightSide )
{
Players Moves[3]= { { 0,1 },{1,0 },{ 1,1 }};
int ans;

ans = Validate( Moves, rightSide );
rightSide->miss += Moves[ans].miss;
rightSide->can += Moves[ans].can;

leftSide->miss -= Moves[ans].miss;
leftSide->can -= Moves[ans].can;
}

int Validate( Players Moves[], Players *State )
{
int x;
Players T = {0,0};

for( x = 0; x < NUM; x++ )
{
T.miss = State->miss;
T.can = State->can;

T.miss += Moves[x].miss;
T.can += Moves[x].can;

if( T.miss == T.can || T.miss == FALSE || T.miss == NUM )return x;
}
return -1;
}

void Display( Players rightSide, Players leftSide )
{
printf("Left = M%d C%d     Right = M%d C%d\n", leftSide.miss, leftSide.can,
rightSide.miss, rightSide.can );
getch();
}```
Last edited by Mr. Unstoppable; Aug 8, 2005 at 01:25 AM. Reason: Additional information

3. Nice work TJRAKS

Mine Flop Big time. Spent the last 12 hrs from yestoday evening to this morning and no working code. My code does nothing

Code:
```#include <list>
#include <stdio.h>

#define		left_bank	0
#define		right_bank	1
#define		max_paths	5

struct State
{
public:
char	ML;	//Count of Missionaries on left bank of river
char	CL;	//Count of Cannibals on left bank of river
char	MR;	//Count of Missionaries on right bank of river
char	CR;	//Count of Cannibals on right bank of river
char	B;	//Boat position; 0 for left bank, 1 for right bank
//char	dummy[3];

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()
{
if(
((ML >= CL)||(ML == 0)) &&
((MR >= CR)||(MR == 0)) &&
((MR >= 0)&&(MR >= 0)) &&
((CR >= 0)&&(CR >= 0))
)
{
return	true;
}
else
return	false;
}
void GetNextState(int PathIndex, State & stateNext)
{
stateNext	=	(*this);
stateNext.B	=	!B;

switch(PathIndex)
{
case 0:								//Move 1M, 1C
if(B == right_bank)
{
stateNext.MR--;
stateNext.CR--;
stateNext.ML++;
stateNext.CL++;
}
else
{
stateNext.MR++;
stateNext.CR++;
stateNext.ML--;
stateNext.CL--;
}
break;
case 1:								//Move 2M
if(B == right_bank)
{
stateNext.MR	-=	2;
stateNext.ML	+=	2;
}
else
{
stateNext.MR	+=	2;
stateNext.ML	-=	2;
}
break;
case 2:								//Move 2C
if(B == right_bank)
{
stateNext.CR	-=	2;
stateNext.CL	+=	2;
}
else
{
stateNext.CR	+=	2;
stateNext.CL	-=	2;
}
break;
case 3:								//Move 1M
if(B == right_bank)
{
stateNext.MR	-=	1;
stateNext.ML	+=	1;
}
else
{
stateNext.MR	+=	1;
stateNext.ML	-=	1;
}
break;
case 4:								//Move 1C
if(B == right_bank)
{
stateNext.CR	-=	1;
stateNext.CL	+=	1;
}
else
{
stateNext.CR	+=	1;
stateNext.CL	-=	1;
}
break;
}
}
bool CompareStates(const State & stateOther)
{
if(
(stateOther.ML == ML) &&
(stateOther.CL == CL) &&
(stateOther.MR == MR) &&
(stateOther.CR == CR) &&
(stateOther.B == B)
)
{
return	true;
}
else
return	false;
}
};

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);

//lpaths.push_back(pathCurrent);

while(true)
{
STATE_OK:

//pathCurrent		=	0;

if(stateCurrent.CompareStates(stateDestination))
{
goto	STATE_END;
}

//State	stateNext;

////Loop through the possible paths but start from the lowest path that has not been explored if it exists
//for(if(lpaths.size)pathCurrent = *lpaths.back(); pathCurrent < max_paths; pathCurrent++)

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

//*lpaths.back()	=	i;
//lpaths.push_back(0);

goto	STATE_OK;
}
}
}

lstates.pop_back();								//If there is nothing to pop then there is no solution
stateCurrent	=	lstates.back();

lpaths.pop_back();
pathCurrent		=	lpaths.back();

pathCurrent++;
}

STATE_END:

FILE *	output	=	fopen("output.txt", "w");

for(itstates = lstates.begin(); itstates != lstates.end(); itstates++)
{
fprintf(output, "M%d C%d     M%d C%d", itstates->ML, itstates->CL, itstates->MR, itstates->CR);
}

return 0;
}```

4. Well Crosswire i am not sure what to say!! I think you should continue to work at it. I just giving this a few more days then i post a similar but more difficult one. I really like the fact that people responing to my challenge though thanks guys. If in the future anyof you should post a challenge i will try to return the favour.

5. TJRAK good stuff. very clean, clear, clever, cool.
shorter than mine and still could be made shorter by about 12 lines to my estimation.
all you ned to do is comment it so i can feel better about the number of lines of code i used ( yours so simple it dont need comments though ). If you permit me i can show you, otherwise i will rape the code and do it anyway.

Crosswire, Crosswire, you can zip out a lot too, but get it to work first.

6. I got my butt kicked in this one.

And I learnt something from all ya codes.

However, I knew that a lot of areas in my code could have been optimised, but I was wrongly too cool with the length of it, but it look efup. If I get it working, I will optimise it but I aint going to update it here.

7. I was ok for a few hours, then the thought of other coders making shorter solutions than mine prompted this response :

Code:
```#include <stdio.h>

struct State{ unsigned char nuns : 2, cannis : 2, boat : 1; };

void main()
{
State initState = { 3, 3, 1 }, state = initState;
State edges[] = { {0,2}, {2,0}, {1,1}, {0,1} }, eMov;
unsigned char &iState = * ( unsigned char* ) &state;
unsigned offNun, offCanni, iMov;

while( true )
{
printf("\t\t%d %d %c ..", state.nuns, state.cannis, state.boat?'B':' ');
printf(".. %c %d %d\n\n", state.boat?' ':'B',3-state.nuns,3-state.cannis);

if( !iState ) break;

for( iMov = state.boat ? 0 : 3 ; true ; state.boat ? iMov++ : iMov-- )
{
eMov = edges[iMov];

offNun = state.nuns + ( state.boat ? -eMov.nuns : eMov.nuns );
offCanni = state.cannis + ( state.boat ? -eMov.cannis : eMov.cannis );

if( offNun > 3 || offCanni > 3 ) continue;
if( offNun == 0 || offNun == 3 || offNun == offCanni ) break;
}

state.nuns   = offNun;      // the new Missionaries count
state.cannis = offCanni;  // the new Cannibals count
state.boat   = !state.boat;  // the boat has changed sides
}
}```
beat that and i will not post any more code concerning this!!

8. Yow IcyMint3, you're the real thing. I like the way you code.
36 lines of coding (hmmmmm.......). Don't think anyone will try and beat that. Think you people need to give www.devx.com top coder challenges a try.

9. Originally Posted by icymint3
TJRAK good stuff. very clean, clear, clever, cool.
shorter than mine and still could be made shorter by about 12 lines to my estimation.
all you ned to do is comment it so i can feel better about the number of lines of code i used ( yours so simple it dont need comments though ). If you permit me i can show you, otherwise i will rape the code and do it anyway.
We are here to help each other out so go right ahead.

10. TJRAK, i was going to cut up your display function when i realized i'm at 34 LOC. So i decided THATS ENOUGH!!

Code:
```#include <stdio.h>

void trace(int Lm,int Lc,int l,int Rm,int Rc,int r); //Trace the movement of Missionaries and Cannibals

void main()
{
int rM = 0, rC = 0, lB = 1; // l=> left, r=> right, M => missionarie, C=>Cannibals, B=>boat.
trace(3-rM,3-rC,lB,rM,rC,!lB);

while((rC+rM)<6)//Loop until all six are on the other side of the river
{
if(lB) //Boat on the left side of the river
if((rM==0 || rC+2 <= rM) && (rC<2)) //movement of cannibals such that they never outnumber Missionaries
rC+=2;
else
rM+=2;
else
{
if(rM==rC && rM>0)
rM--;
rC--;
}//end else (rB=1)
lB = !lB;   // no need to store left and right boat they are mutually exclusive
trace(3-rM,3-rC,lB,rM,rC,!lB);
}//ends while
}//end main

void trace(int Lm,int Lc,int l,int Rm,int Rc,int r)
{
static count = 1;
printf("%d.\tM%d C%d Boat = %d", count++, Lm, Lc, l);
printf("-------------------");
printf("M%d C%d Boat = %d \n", Rm, Rc, r);
}```

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•