Page 1 of 3 123 LastLast
Results 1 to 10 of 29

Thread: Crossin the River

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

    Default Crossin the River

    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.

    N.B. The challenge is 100 LOC or Less
    Last edited by Mr. Unstoppable; Aug 4, 2005 at 05:31 PM. Reason: Typo
    "A computer once beat me at chess, but it was no match for me at kick boxing." - Emo Philips -

  2. #2
    Join Date
    Jan 2005
    Posts
    3,151
    Rep Power
    0

    Default

    in c?
    prolog seems more suitable for solving said problem

  3. #3
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

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

    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.

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

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

    Default

    icymint3 i did it partially commented in under 100 LOC.

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

    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.

    Now that should give you something to sleep on.

    pogi_2nr, as icymint3 said try it in C or C++ and let me see the way your brains work.
    Last edited by Mr. Unstoppable; Aug 4, 2005 at 09:29 PM.
    "A computer once beat me at chess, but it was no match for me at kick boxing." - Emo Philips -

  5. #5
    Join Date
    Jan 2005
    Posts
    3,151
    Rep Power
    0

    Default

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

  6. #6
    Join Date
    Jan 2005
    Posts
    3,151
    Rep Power
    0

    Default

    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)
    Code:
    #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

  7. #7
    Join Date
    Oct 2004
    Posts
    4,814
    Rep Power
    24

    Default

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

  8. #8
    Join Date
    Jul 2005
    Posts
    75
    Rep Power
    0

    Default

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

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

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

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

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

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

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

    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......................
    Last edited by Mr. Unstoppable; Aug 5, 2005 at 08:13 PM.
    "A computer once beat me at chess, but it was no match for me at kick boxing." - Emo Philips -

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

    Default

    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:
    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
    }
    Last edited by icymint3; Aug 5, 2005 at 09:01 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

  10. #10
    Join Date
    Mar 2004
    Posts
    123
    Rep Power
    0

    Default

    Well, i gave this a try and came up with the following solution
    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 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.
    Last edited by TJRAK; Aug 8, 2005 at 04:29 PM. Reason: Add a few comments then got lazy. Plus I had to prepare for class
    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

Posting Permissions

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