Qbasicnews.com
July 18, 2019, 08:21:38 PM
 Pages: [1] 2
 Author Topic: Kangaroo problem, np complete :)  (Read 21356 times)
Agamemnus
x/ \z

Posts: 3491

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

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

 « Reply #1 on: August 02, 2003, 04:32:19 PM »

I can't understand JUMP.
 Logged
SCM
Wandering Guru

Posts: 311

 « Reply #2 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.
 Logged

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
*/-\*

Posts: 8244

 « Reply #3 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.
 Logged

SCUMM (the band) on Myspace!
ComputerEmuzone Games Studio
underBASIC, homegrown musicians
[img]http://www.ojodepez-fanzine.net/almacen/yoghourtslover.png[/i
SCM
Wandering Guru

Posts: 311

 « Reply #4 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.
 Logged

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
Senior Member

Posts: 200

 « Reply #5 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

Just the way I work.
 Logged

END OF LINE.
Agamemnus
x/ \z

Posts: 3491

 « Reply #6 on: August 05, 2003, 11:20:53 AM »

arrr
 Logged

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
Forum Regular

Posts: 105

 « Reply #7 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
 Logged
SCM
Wandering Guru

Posts: 311

 « Reply #8 on: August 06, 2003, 03:20:22 AM »

Code:
Btw how long is the bridge?
In Agamemnus' description of the problem he wrote
Code:
'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 a
Code:
>>_<<      (n=2)
hop    >_><<
or a
Code:
>_><<
jump   ><>_<
 Logged

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
x/ \z

Posts: 3491

 « Reply #9 on: August 08, 2003, 08:51:30 PM »

arr arr
 Logged

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
Forum Regular

Posts: 105

 « Reply #10 on: October 02, 2003, 10:01:00 PM »

Hey will anyone post their solutions please?
 Logged
Agamemnus
x/ \z

Posts: 3491

 « Reply #11 on: October 02, 2003, 10:17:45 PM »

Heheh. You haven't waited two months for someone to post one, have you?

It's not on this computer... I'll post it.....soon...

I also sent someone here a solution, too.....
 Logged

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
Forum Regular

Posts: 105

 « Reply #12 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
 Logged
Agamemnus
x/ \z

Posts: 3491

 « Reply #13 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:
 Logged

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.
SCM
Wandering Guru

Posts: 311

 « Reply #14 on: October 02, 2003, 11:31:48 PM »

This was my solution (slightly modified):
Code:
DEFINT A-Z

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

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)
 Pages: [1] 2