Crossin the River

[Mr. Unstoppable]

Attempt to write an algorithm that simulate the crossing the river problem.

Now the crossing the river problem states that there are 3 missionaries and 3 cannibals on one side of a river. Now you should get them to the other side of the river using these rules:-

- At no time should there be more cannibals than missionary on any side, unless no missionaries on that side.

- No more than 2 passengers on the boat. Please note that a minimum of one passenger have to go back for others to cross.


I know that these instructions might not be clear so let me try a little simulation:

M0 C0---------------------------M3 C3 (this would be starting position)

Now from this position you can 1 missionary 1 Cannibal or two Cannibals.

M1 C1---------------------------M2 C2 (this would be 1st move position)

Now let's us assume that was your move. Now the missionary have to go back as if the cannibal went back there would be M2 C3 and the cannibals would eat the Missionaries.

I hope that was helpfull in your understanding the problem. :eusa_thin :eusa_wall

N.B. The challenge is 100 LOC or Less :eusa_shif :eusa_booh

[pogi_2nr]

in c?
prolog seems more suitable for solving said problem :)

[icymint3]

pogi_2nr, you only saying that because you probably have the code or you recognize it from AI. :eusa_naug
but any solve it in c/c++/c# just for the challenge. :eusa_naug

i thought up a good solution, but your 100 LOC limit makes me feel as if that algorithm will meet its destiny in the dump quite soon. :eusa_doh:

hopefully i can code w/ comments in under 100 lines. :eusa_pray

[Mr. Unstoppable]

icymint3 i did it partially commented in under 100 LOC. :eusa_ange

I have seen your work on here i am surprised that your solution is over 100 LOC. :eusa_eh:

:eusa_doh: If i am to be honest i just realise that i incorporated some stuff that were not needed, and if i exclude display functionality will take approximately 60 LOC when i optimise it. :eusa_shhh

Now that should give you something to sleep on. :icon_lol:

pogi_2nr, as icymint3 said try it in C or C++ and let me see the way your brains work. :D

[pogi_2nr]

lol I started coding this in c this morning... my skills are rusty :p
I feel bad though coz I have other work to be done heh.

[pogi_2nr]

meh.. The box I am working on doesnt have a debugger so I am stuck for now.
This is what I have thus far. In theory it works :) (dont try to run it)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define M 1
#define C 0
typedef int bstate_t[2][2];
struct seenlist_t {
struct seenlist_t *next;
bstate_t datum;
}*seenlist=NULL;
int showmoves(int n,bstate_t *m){
int z=0;
while(n){
printf("%d:%d, ",(*m)[z][M],(*m)[z][C]);
*m++;n--;
}
printf("\n");
return 1;
}
int acceptable(bstate_t bstate){
struct seenlist_t **sl = &seenlist;
//*
for(;*sl;sl = &(*sl)->next){
// if ((*sl)->datum == bstate) return 0;
if (!memcmp((*sl)->datum,&bstate,sizeof(bstate))) return 0;
}
*sl = malloc(sizeof(struct seenlist_t));
(*sl)->next = NULL;memcpy((*sl)->datum,&bstate,sizeof(bstate));
//*/
return ((bstate[0][M] >= bstate[0][C] || !bstate[0][M]) && (bstate[1][M] >= bstate[1][C] || !bstate[0][M]))
&& !(bstate[0][M] < 0 || bstate[1][M] < 0 || bstate[0][C] < 0 || bstate[1][C] < 0);
}
int findmoves(int num,bstate_t *m,int side,int mm,int mc){
bstate_t *newm;
if (num >=20) return 0;

if ((m[num-1][1][M] == m[num-1][1][C]) && (m[num-1][1][M] == 0))
printf("solved!! %d %d %d\n",num,m[num-1][1][M],m[num-1][1][C]);

newm = malloc((1+num) * sizeof(bstate_t));
memcpy(newm,m,num * sizeof(*m));
memcpy(newm+num,newm+num-1,sizeof(bstate_t));
newm[num][0][M] += mm;newm[num][0][C] += mc;
newm[num][1][M] -= mm;newm[num][1][C] -= mc;
if (acceptable(newm[num])){
printf("***:%2d,%d ",num,9);showmoves(num,newm);
if (side % 2){
printf("-%d-",side);
findmoves(num+1,newm,side+1,-1,-1);
findmoves(num+1,newm,side+1,0,-1);
findmoves(num+1,newm,side+1,-1,0);
} else {
printf(".%d.",side);
findmoves(num+1,newm,side+1,1,1);
findmoves(num+1,newm,side+1,0,1);
findmoves(num+1,newm,side+1,1,0);
}
}
free(newm);
return 1;
}
int main(int argc, char **argv){
bstate_t bank= {{0,0},{3,3}};

printf("%d, %d\n",bank[0][M],sizeof(short));
findmoves(1,&bank,1,1,1);
return 0;
}

It supposidly does a depthfirst search for the solution.. meh :icon_evil

[leoandru]

MAD!! pogi dust off him programming skills. I should take a good look at that code! I may never see it again. :p

[Mr. Unstoppable]

Pogi i want a few people to post before i show my code.

However i have decided to change the parameters of the challenge. :icon_evil

It is my challenge i can do what i want to. :icon_mrgr

The challenge is the shortest LOC with the easiest understood logic. :eusa_danc

In effect i thing you may have beat my 97 lines of code and i am a poor sport LOL. :eusa_wall

Anyways i set Monday as the time i am going to show my solution to the world. :eusa_danc

With logics so simple any idiot can understand even if i take out the comments to reduce LOC. :eusa_clap

Leoandru we need you to post to show your skills

Basically i want to see icymint, crosswire, Pogi and Yourself throw down i ain't in you guys league. Seei changed the parameters to make sure it fair. Want me to put a cash prize in there too?

Until then......................

[icymint3]

Ok, so as i was saying i had this very bright idea to do it, very new i tell you.
But the flaw, IT LONG.

///////////////////////////////////////////////////////////////////////////
Algorithm 1.... Grandpa of Formalities

there are 3 cannibals and 3 missionaries and a boat and a river with 2 banks.
there are many states that they can all be combined into that are unique, but only a few of them will be relevant.

I see a graph of states (missionaries, cannibals ), connected by edges
Step 1.
(3,3) (3,2) (3,1) (3,0)
(2,3) (2,2) (2,1) (2,0)
(1,3) (1,2) (1,1) (1,0)
(0,3) (0,2) (0,1) (0,0)

4 * 4 = 16 nodes

as far as the people are concerned. thats one side of the graph. taking the side of the river the boat is on into consideration gives us another layer on top of that.

4 * 4 * 2 = 32 nodes

for a move from the left to the right we can take
(1 missionary & 0 cannibal),
(2 missionary & 0 cannibal)
(1 missionary & 1 cannibal)
(0 missionary & 2 cannibal)
(0 missionary & 1 cannibal)

Step 2.
there you have it form the valid edges from each node in the graph to another node.

Step 3.
eliminate all edges which lead to a bad node, ie one that threatens the missionaries.

Step 4.
find the shortest path from the start node (3,3) to the end node (0,0).

End of Solution

Problem
it uses very complicated algorithms.

/////////////////////////////////////////////////////////////////////////////////////
Algorithm 2

simplify previous algorithm and optimize for space.

/////////////////////////////////////////////////////////////////////////////////////
Algorithm 3

that was just for the learning experience. dump all that code, start from scratch and go for obfuscation. least LOC wins. the logic was also more compact and efficient... i dont want to say it is optimal( but i think so).
it uses some A*, bfs, dfs heuristics and fancy logic techniques. there is even some weird form of linked list in there.

The Code:


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

////////////////////////////////////////////////////////////////////////////////
// ANDREW HALL a.k.a Kodeci //
// icymint3@yahoo.com | icymint3@gmail.com | alphanexxus@yahoo.com //
////////////////////////////////////////////////////////////////////////////////


// I pack my data really tight, 3 needs 2 bits to represent
struct State{ unsigned char nuns : 2, cannis : 2, boat : 1; };

State states[32]; // this is a stack, game tree, list, buffer... whatever
State move(State curr); // the motion controller

void main()
{
State initState = { 3, 3, 1 }, state = initState;
unsigned char &iState = * ( unsigned char* ) &state;

// make the moves
do { state = states[iState] = move( state ); }while( iState );

// show the moves... states is manipulated as a linked list
for( state = initState; true ; state = states[iState] )
{
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; // stop when theres nothing on the source bank
} //getch();
}

State move( State mask )
{
// define all move offsets... except the Suicidal Missionary :{1,0}
static State edges[] = { {0,2}, {2,0}, {1,1}, {0,1} }, eMov;
// number of Missionaries & Cannibals on the left side after moving
unsigned offNun, offCanni;

// init: if boat on this side, start from largest move... else smallest
// update: if boat on this side, move down to next best move, else move up

for( unsigned iMov = mask.boat ? 0 : 3 ; true ; mask.boat ? iMov++ : iMov-- )
{
// select the next best offset
eMov = edges[iMov];

// if boat on this side, then move them away --, else welcome them back ++
offNun = mask.nuns + ( mask.boat ? -eMov.nuns : eMov.nuns );
offCanni = mask.cannis + ( mask.boat ? -eMov.cannis : eMov.cannis );

// because values are unsigned, all invalid moves fall off the positive
// side. in that case jut continue to the next best move
if( offNun > 3 || offCanni > 3 ) continue;

// if no life is threatened, make the move
if( offNun == 0 || offNun == 3 || offNun == offCanni ) break;
}

// compile the new move data before sending it off
mask.nuns = offNun; // the new Missionaries count
mask.cannis = offCanni; // the new Cannibals count
mask.boat = !mask.boat; // the boat has changed sides

return mask; // return the all important move
}

[TJRAK]

Well, i gave this a try and came up with the following solution

#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 lM = 3, lC = 3, rM = 0, rC = 0, lB = 1, rB=0; // l=> left, r=> right, M => missionarie, C=>Cannibals, B=>boat.
int m2 = 2, m1 = 1; //number of people to be ub the boat
trace(lM,lC,lB,rM,rC,rB);

while((rC+rM)<6)//Loop until all six are on the other side of the river
{
if(lB==1) //Boat on the left side of the river
{
if((rM==0 || rC+2 <= rM) && (lC>=2)) //movement of cannibals such that they never outnumber Missionaries
{
lC-=m2;
rC+=m2;
}
else
{
lM-=m2;
rM+=m2;
}
lB--;
rB++;
trace(lM,lC,lB,rM,rC,rB);
}//end lB=1
else
if(rB==1) //Boat on the right side of the river
{
if(rM==rC && rM>0)
{
rM-=m1;
rC-=m1;
lM+=m1;
lC+=m1;
}
else
{
rC-=m1;
lC+=m1;
}
lB++;
rB--;
trace(lM,lC,lB,rM,rC,rB);
}//end else (rB=1)
}//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);
}

I know it might not be as complex as most of you'll solution, but it works.
Going to try and implement it using some other method.

[Mr. Unstoppable]

TJRAK well i must say congratulations.

Defining the problem :eusa_clap
LOC :eusa_clap
Simplicity of Logic :eusa_clap
Diplay Function :eusa_thin

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.

[Mr. Unstoppable]

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:

// 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();
}

[crosswire]

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



#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;
}
}
}

DEAD_END_STATE:

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

[Mr. Unstoppable]

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.

[icymint3]

TJRAK good stuff. very clean, clear, clever, cool. :eusa_clap :eusa_clap :eusa_clap
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.

[crosswire]

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.

[icymint3]

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


#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!!

[TJRAK]

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.

[TJRAK]

TJRAK good stuff. very clean, clear, clever, cool. :eusa_clap :eusa_clap :eusa_clap
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.

[icymint3]

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


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

[crosswire]

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

#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;
}

[Mr. Unstoppable]

You feel bad crosswire? I got beaten in my own challenge. :icon_frow

I am officially banning everybody from taking part in any challenge i place in any forum lol. :D

Seriously, good work guys as always i am impressed. :eusa_clap

All unuu fi seh is unuu ready and i send on the next one. I think this one will be tougher and way more challenging.

[TJRAK]

lB = !lB; // no need to store left and right boat they are mutually exclusive[/CODE]
I kinda figured that out but just wanted to finish the code and get the result out. It's one or the other but I just couldn't bother, plus I had 65 lines of coding.
Your the real Big Man still.


Think we are ready for the next challenge

[icymint3]

Continuing on TJRAK's code, i get really ugly and came up with my final efforts:
not for the faint of heart!


#include <stdio.h>

void main()
{
char nM = 3, nC = 3, s = 1, ix = 1, *frmt = ".B%d.\t%d:%d %c%s%c %d:%d\n";

for( int strongStep ; strongStep = nM + nC == 4, true ; ) //Loop until ...
{
printf(frmt+2,ix++,nM,nC,frmt[s],".................",frmt[!s],3-nM,3-nC);
if( !nM && !nC ) break;
nM+= s ? -2 * strongStep : nC == nM;
nC+= s ? -2 * !strongStep : 1;
s = !s;
}//ends while
}//end main

for thjose like crosswire who aint afraid of goto...

#include <stdio.h>

void main()
{
char nM = 3, nC = 3, s = 1, ix = 1, *frmt = ".B%d.\t%d:%d %c%s%c %d:%d\n";
int strongStep ;
goto display;
update: strongStep = nM + nC == 4;
nM+= s ? -2 * strongStep : nC == nM;
nC+= s ? -2 * !strongStep : 1;
s = !s;
display: printf(frmt+2,ix++,nM,nC,frmt[s],"............",frmt[!s],3-nM,3-nC);
if( nM | nC ) goto update;
}

now i cant even index my stuff withoutgetting them highlighted :D
s is the side the boat is on, i couldnt use b.

[crosswire]

My butt is so kicked, Way to show us how its done.

Anyway, meeting you in the next challenge.

[Mr. Unstoppable]

My butt is so kicked, Way to show us how its done.

Anyway, meeting you in the next challenge.

Crosswire i agree, icymint3 thinking on another level. :eusa_thin

I wonder if TJRAK saw that he turn his code into 14 LOC? :icon_eek:

Icymint nuff respect we soon have to crown you king or Programming. :eusa_clap

[crosswire]

he great :eusa_clap :eusa_clap :eusa_clap :eusa_clap :eusa_clap

My vote too : He' the reigning KING

Any one can write a peice of code but not everyone can optimizing it, not even half as much as icymint did. I will try take his crown :icon_mrgr but I am not in his league right now.

[TJRAK]

I wonder if TJRAK saw that he turn his code into 14 LOC? :icon_eek:
I saw it. But as I said before, IcyMint is the real BIG MAN. He knows his stuff

[icymint3]

actually i cannot take ful credit for it. :eusa_snoo

1.if the limit was not set to 100 LOC it would have been solved in about 300 lines (Mr. Unstoppable :eusa_clap ).

2.if TJRAK didnt do that weird solution i would not have cut it to 34.

3.and finally the 14 LOC also comes from TJRAK's solution.

4.all that being said, i really cannot take credit because i dont believe it is an algorithm that solves the River Crossing Problem, but one that generates a known sequence. That, in and of itself makes it quite an ugly solution.

i still prefer my first solution :eusa_liar .