Title: Kangaroo problem, np complete :) Post by: Agamemnus on August 02, 2003, 02:58:22 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! Title: Kangaroo problem, np complete :) Post by: xhantt on August 02, 2003, 04:32:19 PM I can't understand JUMP.
Title: kangaroo problem Post by: SCM on August 03, 2003, 10:15:57 PM 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. Title: Kangaroo problem, np complete :) Post by: na_th_an on August 03, 2003, 11:18:39 PM 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.
Title: kangaroo challenge Post by: SCM on August 04, 2003, 07:09:24 PM 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.
Title: Re: kangaroo challenge Post by: Phydaux on August 04, 2003, 10:04:04 PM Quote from: "SCM" 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 :P Just the way I work. Title: Kangaroo problem, np complete :) Post by: Agamemnus on August 05, 2003, 11:20:53 AM arrr
Title: Kangaroo problem, np complete :) Post by: Lanzaa on August 05, 2003, 06:46:58 PM 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 Title: Kangaroo problem Post by: SCM on August 06, 2003, 03:20:22 AM Lanzaa asked
Code: Btw how long is the bridge? In Agamemnus' description of the problem he wroteCode: 'At first the kangaroos line up like this: >>>_<<< (n = 3) 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 a'They need to line up like this: <<<_>>> Code: >>_<< (n=2) or a hop >_><< Code: >_><< jump ><>_< Title: Kangaroo problem, np complete :) Post by: Agamemnus on August 08, 2003, 08:51:30 PM arr arr
Title: Kangaroo problem, np complete :) Post by: Lanzaa on October 02, 2003, 10:01:00 PM Hey will anyone post their solutions please?
Title: Kangaroo problem, np complete :) Post by: Agamemnus on October 02, 2003, 10:17:45 PM Heheh. You haven't waited two months for someone to post one, have you? :o
It's not on this computer... I'll post it.....soon... I also sent someone here a solution, too..... Title: Kangaroo problem, np complete :) Post by: Lanzaa on October 02, 2003, 10:41:05 PM :lol: No i didn't wait 2 months
I just havn't been around for that long and was curios of the answer since I'm trying to figure it out Title: Kangaroo problem, np complete :) Post by: Agamemnus on October 02, 2003, 10:47:53 PM I have found the solution but I cannot contain it within the margin of this paper. :king: :rotfl:
Title: Kangaroo problem Post by: SCM on October 02, 2003, 11:31:48 PM This was my solution (slightly modified):
Code: DEFINT AZ DECLARE SUB DsplMove (Grp%, j%, Pstn%(), LnUp$, Mv$, Move%) DIM LineUp AS STRING SCREEN 0 WIDTH 80, 25 DO VIEW PRINT CLS Title$ = "Kangaroo Problem" LOCATE 1, 32 PRINT Title$; TAB(2); STRING$(78, "=") DO '============================== User Input ========================== LOCATE 10, 18 INPUT "Enter the number of kangaroos per side: ", n Okay = 0 IF n < 10 THEN Okay = 1 ELSE LOCATE 13, 1 IF n > 31 THEN PRINT TAB(22); "Can't display more than 31 kangaroos."; Txt$ = "(You really didn't want to watch" Txt$ = Txt$ + STR$(n * (n + 2)) + " moves anyway)" PRINT TAB(40  LEN(Txt$) \ 2); Txt$ DO: k$ = INKEY$: LOOP WHILE k$ = "" ELSE Txt$ = "This will require" + STR$(n * (n + 2)) Txt$ = Txt$ + " moves. Use n =" + STR$(n) + "? (y/n)" PRINT TAB(40  LEN(Txt$) \ 2); Txt$ DO: k$ = LCASE$(INKEY$): LOOP UNTIL k$ = "y" OR k$ = "n" Okay = (k$ = "y") END IF LOCATE 10, 1: PRINT STRING$(80, " ") LOCATE 13, 1: PRINT STRING$(80, " ") LOCATE 14, 1: PRINT STRING$(80, " ") END IF LOOP UNTIL Okay '============ End User Input ========================== CLS ' set up solution screen  T$ = Title$ + " (n =" + STR$(n) + ")" LOCATE 1, 41  LEN(T$) \ 2 PRINT T$; TAB(2); STRING$(78, "=") VIEW PRINT 3 TO 24 ' End set up solution screen  REDIM Pstn(1, 1 TO n) ' position of each kangaroo FOR i = 1 TO n ' starting from 1 on left Pstn(0, i) = n + 1  i Pstn(1, i) = n + 1 + i NEXT LineUp = STRING$(n, ">") + "_" + STRING$(n, "<") Move = 0 DsplMove Group, j, Pstn(), LineUp, "", Move FOR i = 0 TO n  1 Group = i MOD 2 FOR j = 1 TO i DsplMove Group, j, Pstn(), LineUp, "jump", Move NEXT DsplMove Group, i + 1, Pstn(), LineUp, "hop ", Move NEXT Group = n MOD 2 FOR j = 1 TO n DsplMove Group, j, Pstn(), LineUp, "jump", Move NEXT FOR i = n  1 TO 0 STEP 1 Group = i MOD 2 DsplMove Group, n  i, Pstn(), LineUp, "hop ", Move FOR j = 1 TO i DsplMove Group, n  i + j, Pstn(), LineUp, "jump", Move NEXT NEXT PRINT TAB(28); "Try a different value? (y/n)"; DO: k$ = LCASE$(INKEY$): LOOP UNTIL k$ = "y" OR k$ = "n" LOOP WHILE k$ = "y" SUB DsplMove (Grp, j, Pstn(), LnUp$, Mv$, Move) IF Grp = 0 THEN Char$ = ">" Grp$ = "R" Drctn = 1 ELSE Char$ = "<" Grp$ = "L" Drctn = 1 END IF Dspl$ = RIGHT$(" " + STR$(Move), 4) + ") " IF Move = 0 THEN Dspl$ = Dspl$ + STRING$(10, " ") + LnUp$ ELSE MvLngth = 1  (Mv$ = "jump") MID$(LnUp$, Pstn(Grp, j), 1) = "_" MID$(LnUp$, Pstn(Grp, j) + MvLngth * Drctn, 1) = Char$ Pstn(Grp, j) = Pstn(Grp, j) + MvLngth * Drctn Dspl$ = Dspl$ + Grp$ + LEFT$(RIGHT$(STR$(j) + " ", 2  (j > 9)), 2) Dspl$ = Dspl$ + " " + Mv$ + " " + LnUp$ END IF PRINT TAB(40  LEN(Dspl$) \ 2); Dspl$; IF Move > 0 AND Move MOD 20 = 0 THEN PRINT TAB(23); "PAUSED  Press any key to continue"; DO: k$ = INKEY$: LOOP WHILE k$ = "" IF k$ = "q" OR k$ = CHR$(27) THEN END LOCATE 24, 23: PRINT ; " "; LOCATE 24, 1 END IF Move = Move + 1 END SUB I also have Aga's solution, but I'll allow him to post it. Title: Kangaroo problem, np complete :) Post by: Lanzaa on October 02, 2003, 11:57:54 PM Well can someone post a very simple version of this for me.
This is because I'm in 9th grade math (geometry) and he said it was 10th grade extra credit so i will be confused Title: Kangaroo problem, np complete :) Post by: SCM on October 03, 2003, 12:10:45 AM Copy the program and run it. It displays each move. Use a small number of kangaroos to start. You should see a pattern.
Title: Kangaroo problem, np complete :) Post by: Lanzaa on October 03, 2003, 12:19:41 AM Sure i can solve it by myself i just need to figure out how to program it
all i know is the # of steps used = "n + 1" ^ 2 counting the first one >_< as #1 Title: Kangaroo problem, np complete :) Post by: SCM on October 03, 2003, 03:26:55 PM Lanzaa,
I am sorry I didn't respond earlier. I didn't know what to say. You say that you want to be able to write a program to solve it, but you want a simpler program as an example. I could rewrite it, but then you wouldn't have the chance to do it yourself. I am very happy to help you, but if you are to have any satisfaction in writing the program, you will have to do most of the work. Please, run the program with n = 4. Then group the moves by which way the moving kangaroo is facing (R or L). Then look for a pattern in those groups. This determines your loop structure. When you think you have it, try it with n = 3 to verify it. Let me know what you find. (What is the initial pattern? When does it change? What is the next pattern that comes up? When Does it begin? What happened between these two patterns?) Title: Kangaroo problem, np complete :) Post by: Agamemnus on October 03, 2003, 07:55:37 PM Here is my solution. I suddenly remembered it was in my outbox!! :rotfl:
I also saw a typo... it was "do" instead of "to" in the question.... 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! ' ' ' ' 'ANALYSIS 'An analysis of the problem proceeds in the following fashion: 'Try to solve N = 1 through N = 4 yourself, and look at any patterns emerging. 'You will then be able to extrapolate the general method... ' Try N=1 '>_< 0) they meet 2 '_>< 1) hop one space HOP > ++ 1 '<>_ 2) jump one space JUMP <  3 '<_> 3) hop one space: done HOP > ++ 2 ' Now try N=2 '>>_<< 0) they meet 3 '>_><< 1) hop one space HOP > ++ 2 '><>_< 2) jump one space JUMP <  4 '><><_ 3) hop one space HOP < + 5 '><_<> 4) jump one space JUMP > + 3 '_<><> 5) jump one space JUMP > + 1 '<_><> 6) hop one space HOP < + 2 '<<>_> 7) jump one space JUMP <  4 '<<_>> 8) hop one space HOP > ++ 3 ' Now try N=3 '>>>_<<< 00) they meet 4 '>>_><<< 01) hop one space HOP > ++ 3 1 '>><>_<< 02) jump one space JUMP <  5 +2 '>><><_< 03) hop one space HOP < + 6 +1 '>><_<>< 04) jump one space JUMP > + 4 2 '>_<><>< 05) jump one space JUMP > + 2 2 '_><><>< 06) hop one space HOP > ++ 1 1 '<>_><>< 07) jump one space JUMP <  3 +2 '<><>_>< 08) jump one space JUMP <  5 +2 '<><><>_ 09) jump one space JUMP <  7 +2 '<><><_> 10) hop one space HOP > ++ 6 1 '<><_<>> 11) jump one space JUMP > + 4 2 '<_<><>> 12) jump one space JUMP > + 2 2 '<<_><>> 13) hop one space HOP < + 3 +1 '<<<>_>> 14) jump one space JUMP <  5 +2 '<<<_>>> 15) hop one space HOP > ++ 4 1 'ANSWER: CLS PRINT : INPUT "Number of kangaroos on each side? ", N% move.amount% = N% * N% + 2 * N% spaces.amount% = N% * 2 + 1 DIM SHARED move(move.amount%) AS INTEGER DIM SHARED type1(move.amount%) AS INTEGER DIM SHARED kangaroo.string$: kangaroo.string$ = SPACE$(spaces.amount%) FOR i% = 1 TO spaces.amount% SELECT CASE i% CASE IS < N% + 1: MID$(kangaroo.string$, i%, 1) = ">" CASE IS = N% + 1: MID$(kangaroo.string$, i%, 1) = "_" CASE IS > N% + 1: MID$(kangaroo.string$, i%, 1) = "<" END SELECT NEXT i% k% = 0: j% = 0: k2% = 0: counter% = 1: counter2% = 1 FOR i% = 1 TO move.amount% \ 2 IF j% = k% THEN k% = k% + 1: j% = 0: move(i%) = 1 ELSE j% = j% + 1 IF j2% = k2% THEN k2% = k2% + 1: j2% = 1: temp% = 1  temp% ELSE j2% = j2% + 1 type1%(i%) = temp% NEXT i% FOR i% = move.amount% \ 2 + 1 TO move.amount% i2% = move.amount%  i% + 1: move%(i%) = move%(i2%): type1(i%) = type1(i2%) NEXT i% cur.empty% = N% + 1: s1$ = "_" FOR i% = 1 TO move.amount% IF type1(i%) THEN next.empty% = cur.empty%  move%(i%)  2 ELSE next.empty% = cur.empty% + move(i%) + 2 s2$ = MID$(kangaroo.string$, next.empty%, 1) MID$(kangaroo.string$, next.empty%, 1) = s1$ MID$(kangaroo.string$, cur.empty%, 1) = s2$ cur.empty% = next.empty% PRINT kangaroo.string$ + " "; : IF move%(i%) THEN PRINT "hop" ELSE PRINT "jump" IF CSRLIN = 24 THEN 1 : IF INKEY$ = "" THEN GOTO 1 CLS END IF NEXT i% SYSTEM Title: Re: Kangaroo problem, np complete :) Post by: Agamemnus on July 11, 2009, 02:19:16 AM I was looking for a binary search on the intertubes, and found this. Sorry to
xhantt. I did not see your post. I believe the correct line should be "'A kangaroo JUMP moves the Kangaroo forward two spaces: >>_ to >_>" Is it too late? :D Title: Re: Kangaroo problem, np complete :) Post by: Clippy on July 11, 2009, 05:05:58 PM LOL, I think so! About 6 years too late! ::)
Title: Re: Kangaroo problem, np complete :) Post by: LPG on October 30, 2009, 12:21:20 AM Lol, there is a flash game of this: http://www.novelgames.com/flashgames/game.php?id=2&l=e
This website has lots of other clever puzzles as well. Title: Re: Kangaroo problem, np complete :) Post by: Agamemnus on January 25, 2010, 03:27:48 PM Nice.
