Problem 44709. Toads and Frogs Puzzle

On a one-dimensional board with n + m + 1 cells, there are n counters in the first n cells representing Toads and m counters in the last m cells representing Frogs. The empty cell is represented by X. For illustration, if n = 4 and m = 3, then the problem is as depicted below:

      T T T T X F F F

Toads and Frogs take turns moving. Moves consist of sliding a Toad or Frog into the empty cell or jumping over one opposing creature into the empty cell. (Toads cannot jump over themselves and neither can Frogs.) Toads can only move rightward and Frogs can only move leftward.

What is the total number of moves (i.e. jumps and slides) required for the toads to switch their positions with the frogs as depicted below:

     F F F X T T T T

ALGORITHM: To solve the problem, whenever there is a choice between a slide and a jump, the jump must be made.

ILLUSTRATION: Consider n = 2 toads and m = 1 frog, then the algorithm could proceed as follows:

 T T X F
 T X T F   Slide
 T F T X   Jump
 T F X T   Slide
 X F T T   Jump
 F X T T   Slide

Hence, a total of five moves is required for n = 2 toads and m = 1 frog.

Solution Stats

54.29% Correct | 45.71% Incorrect
Last Solution submitted on Feb 01, 2024

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers18

Suggested Problems

More from this Author18

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!