Page 2 of 3 FirstFirst 123 LastLast
Results 11 to 20 of 29

Thread: Crossin the River

  1. #11
    Join Date
    Jul 2005
    Posts
    75
    Rep Power
    0

    Default

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

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

    Default

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

  3. #13
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    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;
    				}
    			}
    		}
    
    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;
    }
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

  4. #14
    Join Date
    Jul 2005
    Posts
    75
    Rep Power
    0

    Default

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

  5. #15
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    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.
    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

  6. #16
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    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.
    Let's act on what we agree on now, and argue later on what we don't.
    Black men leave Barbeque alone if Barbeque don't trouble you

  7. #17
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

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

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

    Default

    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.
    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. #19
    Join Date
    Mar 2004
    Posts
    123
    Rep Power
    0

    Default

    Quote 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.
    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

  10. #20
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

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