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

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

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

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

Seriously, good work guys as always i am impressed.

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.

3. Originally Posted by icymint3
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

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

Code:
```#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...
Code:
```#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
s is the side the boat is on, i couldnt use b.
Last edited by icymint3; Aug 9, 2005 at 05:04 PM.

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

Anyway, meeting you in the next challenge.

6. Originally Posted by crosswire
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.

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

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

7. he great

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 but I am not in his league right now.
Last edited by crosswire; Aug 10, 2005 at 08:05 AM.

8. Originally Posted by Mr. Unstoppable
I wonder if TJRAK saw that he turn his code into 14 LOC?
I saw it. But as I said before, IcyMint is the real BIG MAN. He knows his stuff

9. actually i cannot take ful credit for it.

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

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 .

#### Posting Permissions

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