Page 3 of 3 FirstFirst 123
Results 21 to 29 of 29

Thread: Crossin the River

  1. #21
    Join Date
    Sep 2004
    Posts
    1,899
    Rep Power
    20

    Default

    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;
    }
    Selfishness is the gateway to Self Destruction
    Lack of "Wokeness" is to be reincarnated as a tapeworm, whereas more awareness give rise to higher level feelings and relations with others

  2. #22
    Join Date
    Jul 2005
    Posts
    75
    Rep Power
    0

    Default

    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.
    "A computer once beat me at chess, but it was no match for me at kick boxing." - Emo Philips -

  3. #23
    Join Date
    Mar 2004
    Posts
    123
    Rep Power
    0

    Default

    Quote 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
    There is no wrong or right, only consequencies to action

    "It is the duty of man to make his knowledge so complete in life, so as to make it impossible for any other to take advantage of him" - Marcus Garvey

  4. #24
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    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.
    Cultured in Aggression and Koding like a Warrior!!
    “Common sense is instinct. Enough of it is genius.” - George Bernard Shaw.
    "The significant problems we face cannot be solved by the same level of thinking that created them." - Albert Einstein

  5. #25
    Join Date
    Sep 2004
    Posts
    1,899
    Rep Power
    20

    Default

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

    Anyway, meeting you in the next challenge.
    Selfishness is the gateway to Self Destruction
    Lack of "Wokeness" is to be reincarnated as a tapeworm, whereas more awareness give rise to higher level feelings and relations with others

  6. #26
    Join Date
    Jul 2005
    Posts
    75
    Rep Power
    0

    Default

    Quote 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.
    "A computer once beat me at chess, but it was no match for me at kick boxing." - Emo Philips -

  7. #27
    Join Date
    Sep 2004
    Posts
    1,899
    Rep Power
    20

    Default

    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.
    Selfishness is the gateway to Self Destruction
    Lack of "Wokeness" is to be reincarnated as a tapeworm, whereas more awareness give rise to higher level feelings and relations with others

  8. #28
    Join Date
    Mar 2004
    Posts
    123
    Rep Power
    0

    Default

    Quote 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
    There is no wrong or right, only consequencies to action

    "It is the duty of man to make his knowledge so complete in life, so as to make it impossible for any other to take advantage of him" - Marcus Garvey

  9. #29
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    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 .
    Cultured in Aggression and Koding like a Warrior!!
    “Common sense is instinct. Enough of it is genius.” - George Bernard Shaw.
    "The significant problems we face cannot be solved by the same level of thinking that created them." - Albert Einstein

Posting Permissions

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