Can You Solve the Frog Jumping Puzzle Across the Stones?

[shaan_aragorn]

A small stream has seven equidistant stones in line from one bank to the other. Three black and three white frogs on either side are sitting on the three nearest stones to their respective banks like so: B B B _ W W W with one stone unoccupied in the middle. Can you help both group of frogs to cross to the other side if (a) A frog can only shift to a stone ahead of it or can jump over an opposite colour frog; (b) No frog can move backward or into the water and one stone cannot accommodate more than one frog at a time. The real challenge however is: can you device a strategy for m black and n white frogs (with the assumption that there are m + n + 1 stones laid across) in a similar situation? Can you also come up with a formula for minimum no of steps required?

 

[Jimmy Snyder]

Answer for the 3B-3W problem (in white)

BBB_WWW 0
BBBW_WW 1
BB_WBWW 2
B_BWBWW 3
BWB_BWW 4
BWBWB_W 5
BWBWBW_ 6
BWBW_WB 7
BW_WBWB 8
_WBWBWB 9
W_BWBWB 10
WWB_BWB 11
WWBWB_B 12
WWBW_BB 13
WW_WBBB 14
WWW_BBB 15

15 steps. Note the symmetry between step n and step 15 - n.

 

[RandallB]

Supposedly, this solution has been seen used by mountain goats when two groups approach each other on a ledge only one goat wide. They must have been trained in goat school when they were young.
The rules for all goats (or frogs):
1)Stand and wait if Tail in front of you walks to a Nose pointed towards you.
2)When Nose to Nose, jump over it when space behind it is ready, but stand and wait if they jump over you first.
3)When Tail jumps over nose ahead walk forward to Nose and wait.
4)When no more Noses face you, follow Tail of leader as normal.

BxW for number of jump steps
B+W for number of walk up steps
Total steps = (B+W) + BxW

Passing begins when one leader steps forward Nose to Nose with oncoming leader.

 

[ranger]

May I ask why everyone keeps posting their answers in white

 

[Jimmy Snyder]

May I ask why everyone keeps posting their answers in white

So that people who don't want to read the answer can more easily avoid doing so.

 

[ranger]

So that people who don't want to read the answer can more easily avoid doing so.

Makes perfect sense when you put it that way. Thanks for clearing that up.

 

[Edgardo]

Here's the problem as Flash Game:
http://www.ebaumsworld.com/frogleap.html

 

[Galaxy33]

Never mind.


Galaxy...

 

[Alkatran]

The set of rules given for the solution is really hard to implement because they're from the perspective of each frog (which would be fine for goats). Personally, I prefer this 3rd person pespective:

while not done:
  For each original group of frogs:
    For each frog in the group, from front to back:
      if canJump:
        jump
      else if canWalk:
        walk
        break //from the 'each frog' loop

Easy as pie.

 

[RandallB]

The set of rules given for the solution is really hard to implement because they're from the perspective of each frog (which would be fine for goats). Personally, I prefer this 3rd person pespective:

while not done:
For each original group of frogs:
For each frog in the group, from front to back:
if canJump:
jump
else if canWalk:
walk
break //from the 'each frog' loop

Easy as pie.

A fly in the pie!
As a group taking the left side 1st frog cannot jump, so it walks.
Then second frog cannot jump but since there is now room to walk, it walks.
Same for third – and now they are stuck.

Unless you get one the frogs to eat this fly we’ll have to consider this code has a bug in it.

 

[Alkatran]

A fly in the pie!
As a group taking the left side 1st frog cannot jump, so it walks.
Then second frog cannot jump but since there is now room to walk, it walks.
Same for third – and now they are stuck.
Unless you get one the frogs to eat this fly we’ll have to consider this code has a bug in it.

I think you're missing the very important "break" statement, which is equivalent to "go back to the other group when you walk a frog"

 

[RandallB]

I think you're missing the very important "break" statement, which is equivalent to "go back to the other group when you walk a frog"

Ok I see that in the format now.
But where is the command to get it out of the loop telling the lead frogs alternately walk up the bank on either side to infinity.
No jump commands given to frogs 2 or 3, while walk commands sent leaders going up the bank.
CODE cannot assume "walk" onto a rock is different than "walk" onto or up the bank is different until you code it.
Still a fly in the pie.

 

[Alkatran]

Ok I see that in the format now.
But where is the command to get it out of the loop telling the lead frogs alternately walk up the bank on either side to infinity.
No jump commands given to frogs 2 or 3, while walk commands sent leaders going up the bank.
CODE cannot assume "walk" onto a rock is different than "walk" onto or up the bank is different until you code it.
Still a fly in the pie.

Uh, the 'universe' doesn't include a bank in this case. It only has to do with the rock crossing. The problem is trivial after that so why would I write code for it? No one bothered showing the frogs leaving the rocks in their solutions.

 

[RandallB]

Uh, the 'universe' doesn't include a bank in this case. It only has to do with the rock crossing. The problem is trivial after that so why would I write code for it?.

Your right, assuming a closed universe, without 'one bank to the other'; your choice of code works fine for third person rules

No one bothered showing the frogs leaving the rocks in their solutions.

Except the first person rules you didn’t care for; it left them following leader on as normal. The individual rules do work better for wild goats since they had to work out the problem for real, without a third person supervisor. Actually caught on film for some nature show a while back.

 

[Greg825]

I can't get it any simpler than:
m*n + n/2*(n+3) + m/2*(m+3)
for the minimum (and maximum possible number of movements.

Derivation:

say m+n+1=t

there are m*n jumps so we must end up removing m*n from the total number of stones traversed.

t+(t-1)+(t-2)...(t-(n-1)) b frog moves
t+(t-1)+(t-2)...(t-(m-1)) w frog moves

n*t+ (-1-2-3...-(n-1)) brining out t
n*t+ ((n-1)/2 * (-1-(n-1))
n*t+ ((n-1)/2 * (1-n-1))
n*t+ ((n-1)/2 * (-n))
n* (t - (n-1)/2) factoring out n
n* (n+m+1 +(-n+1)/2) replacing t with n+m+1
n* (2m+2n+2-n+1) /2
n* (2m+n+3) /2

same will apply for the w frogs with m and n reversed. thus,
all things considered:

n* (2m+n+3) /2 + m* (2n+m+3) /2 - m*n
m*n + n^2/2 + 3n/2 + n*m + m^2/2 + 3m/2 -m*n
m*n + n/2*(n+3) + m/2*(m+3)

 

[RandallB]

I can't get it any simpler than:
m*n + n/2*(n+3) + m/2*(m+3)
for the minimum (and maximum possible number of movements.

Even simpler to double check
Using link from post #7 setting m=n=3
Your formulas above; jumps = 9 walks =18 total=27
Formulas from post #3; jumps = 9 walks =6 total=15
Actual test run at link site gives 15
Pays to double check

you must have been counting the steps getting out to the starting position

 

[Greg825]

I'm mearly counting the number of moves (steps) to get all the frogs off of all the stones. (Which indeed yields the same number of steps getting out to the start if you were to leave the frogs on the stones.)

If I were to solve it as you did:
I would start with the fact that each frog must traverse z+1 stones where z is the number of frogs of the opposite color. Thus we have w*(b+1) + b*(w+1) traversions. We still have w*b jumps so:
w*(b+1) + b*(w+1) - b*w
wb+w+wb+b -wb
w+b+w*b
:)

 

[RandallB]

If I were to solve it as you did:

You mean as the original problem was given; where "either side" was defined as "the three nearest stones to their respective banks".

If you want to redefine either side as "on the banks" and solve as you tried you'd need about 39 steps anyway.

 

[Greg825]

My interest in a problem has nothing to do with anything that's "given" but what is more thought provoking. When I wrote "If I had solved it as you had" I had already infered that that was how it was originally given, I just didn't care to check. The way I originally solved the problem was by starting all the frogs on the stones in the given configuration, and getting them all off.

I have checked my solution for several different values of m and n.

I do realize now, though, that my mistake was in not specifying exactly what I was solving.

 

[jhe1984]

A small stream has seven equidistant stones in line from one bank to the other. Three black and three white frogs on either side are sitting on the three nearest stones to their respective banks like so: B B B _ W W W with one stone unoccupied in the middle. Can you help both group of frogs to cross to the other side if (a) A frog can only shift to a stone ahead of it or can jump over an opposite colour frog; (b) No frog can move backward or into the water and one stone cannot accommodate more than one frog at a time. The real challenge however is: can you device a strategy for m black and n white frogs (with the assumption that there are m + n + 1 stones laid across) in a similar situation? Can you also come up with a formula for minimum no of steps required?
well, it's more or less a game of complex leapfrog. Answer's in white font below.

1:MMM_NNN
2: MMMN_NN
3: MM_NMNN
4: MMN_MNN
5: M_NMMNN
6:MN_MMNN
7: MNM_MNN
8: MNMNM_N
9: MNMNMN_
10: MNMN_NM
11: MN_NMNM
12: _NMNMNM
13: N_MNMNM
14: NNM_MNM
15: NNMM_NM
16: NNMMN_M
17: NNM_NMM
18: N_MNNMM
19:NNM_NMM
20: NNMN_MM
21: NN_NMMM
22:NNN_MMM