Kangaroo problem, np complete :) Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 08-02-2003, 10:58 PM This was originally a 10th grade maths extra credit problem. I made a computer program to solve it and display the kangaroo steps recently. Can you solve it and/or make a program that shows each step? Here it is, the Kangaroo Problem (I rewrote it from memory) Code:```'The point of this program is to solve 'the Kangaroo Problem, defined as follows: 'There are N kangaroos crossing a bridge from both sides. '(so 2N kangaroos total) ' 'They need to get to their respective other sides. 'The only problem is that the bridge is so narrow 'that they can only move forward and not sideways. ' 'At first the kangaroos line up like this: >>>_<<< (n = 3) 'They need to line up like this:           <<<_>>> ' 'Kangaroos can HOP and JUMP. 'A kangaroo HOP moves the Kangaroo forward one space: >_ to _> 'A kangaroo JUMP moves the Kangaroo forward two spaces: ><_ to >_> ' 'How to HOP and JUMP the kangaroos to the other side? '(two kangaroos can't occupy one space!) 'HINT Try to solve the problems with small N's first!``` Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. xhantt Member Posts: 90 Threads: 8 Joined: Aug 2003 08-03-2003, 12:32 AM I can't understand JUMP. SCM Senior Member Posts: 309 Threads: 15 Joined: Jul 2003 08-04-2003, 06:15 AM Agamemnus, The solution is fairly straight foreward. Your comment about starting with simple cases is a good general strategy, and worked well for me here. The code took me longer to write than I would like to admit. It would be nice to see some others try this problem, so I am PMing my solution and code to you. Feel free to post them. Xhantt, The kangaroos can only move straight forward one space(hop) or two spaces (jump). This all you need to worry about. By moving them one or two spaces, you will either solve the problem or create a road block. hrist Jesus came into the world to save sinners, of whom I am first.(I Timothy 1:15) For God so loved the world, that He gave His only begotten Son, that whoever believes in Him should not perish, but have eternal life.(John 3:16) na_th_an Posting Freak Posts: 6,419 Threads: 74 Joined: Mar 2002 08-04-2003, 07:18 AM I think this is solved using backtracking and cutting recursive branches which are detected to be inviable, just like the priest, the wolf and the goose problem. Maybe I try a simple approach later. SCUMM (the band) on Myspace! ComputerEmuzone Games Studio underBASIC, homegrown musicians [img]http://www.ojodepez-fanzine.net/almacen/yoghourtslover.png[/i SCM Senior Member Posts: 309 Threads: 15 Joined: Jul 2003 08-05-2003, 03:09 AM It's not the way a programmer is likely to think, but some times a pencil and a piece of paper is a good start. hrist Jesus came into the world to save sinners, of whom I am first.(I Timothy 1:15) For God so loved the world, that He gave His only begotten Son, that whoever believes in Him should not perish, but have eternal life.(John 3:16) Phydaux Member Posts: 199 Threads: 2 Joined: May 2003 08-05-2003, 06:04 AM Quote:It's not the way a programmer is likely to think, but some times a pencil and a piece of paper is a good start. Thats the way I always start a serious project, or when I try to figure out a problem... pencil and paper gives so much freedom. I have a desk full of notlets, mostly parts of envelopes and scraps of messed up print jobs with little equations and drawings on them Just the way I work. url=http://www.spreadfirefox.com/?q=affiliates&id=60131&t=79][/url] END OF LINE. Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 08-05-2003, 07:20 PM arrr Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. Lanzaa Member Posts: 99 Threads: 20 Joined: Dec 2002 08-06-2003, 02:46 AM so hop is __>___ to ___>__ and jump is __>___ to ____>_ or __><__ to ___<>_ Btw how long is the bridge? im just coming out of algebra one AKA 8th grade math SCM Senior Member Posts: 309 Threads: 15 Joined: Jul 2003 08-06-2003, 11:20 AM Lanzaa askedCode:`Btw how long is the bridge?`In Agamemnus' description of the problem he wroteCode:```'At first the kangaroos line up like this: >>>_<<< (n = 3) 'They need to line up like this:           <<<_>>>```Think of the bridge as being 2*n+1 spaces long. Since there are 2*n kangaroos, there is always one free space to move into by either aCode:```>>_<<      (n=2)     hop    >_><<``` or a Code:```>_><<           jump   ><>_<``` hrist Jesus came into the world to save sinners, of whom I am first.(I Timothy 1:15) For God so loved the world, that He gave His only begotten Son, that whoever believes in Him should not perish, but have eternal life.(John 3:16) Agamemnus Posting Freak Posts: 3,368 Threads: 195 Joined: Jan 2003 08-09-2003, 04:51 AM arr arr Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war." Visit www.neobasic.net to see rubbish in all its finest. « Next Oldest | Next Newest »