CS1101C Lab 4 (Odd Week)

Toads And Frogs Puzzle

The name of your C program file must be called frog.c, files with any other name will not be marked.

You have to be very familiar and comfortable with one-dimensional arrays before attempting this lab.

Preliminary

N frogs ('x') are placed on N successive positions on the left of a string of squares; M toads ('o') occupy M rightmost squares. On the whole, there are M + N + 1 squares, so that just one square remains unoccupied.

Frogs only move rightward; toads move leftward. Every move is either a Slide to the nearby square or a Jump over one position, which is allowed only if the latter is occupied by a fellow of a different kind. In any case, no two animals are allowed in the same square.

The goal is to move toads into M leftmost positions and the frogs into N rightmost positions.

The number of frogs (N) and toads (M) can change between 1 and 10.

Example

xx_ooo (Initial)
x_xooo (Frog slide)
xox_oo (Toad jump)
xoxo_o (Toad slide)
xo_oxo (Frog jump)
_oxoxo (Frog jump)
o_xoxo (Toad slide)
oox_xo (Toad jump)
ooxox_ (Toad jump)
ooxo_x (Frog slide)
oo_oxx (Frog jump)
ooo_xx (Toad slide)

The Task

Write a program frog.c that requests N and M from the user. N and M are integers between 1 and 10. A sample run of the program is shown below. User input is denoted in bold.

$ gcc -Wall frog.c -o frog
$ frog
Enter the number of frogs (N): 2
Enter the number of toads (M): 3
xx_ooo
x_xooo
xox_oo
xoxo_o
xo_oxo
_oxoxo
o_xoxo
oox_xo
ooxox_
ooxo_x
oo_oxx
ooo_xx

Strategy

1. If only one animal can move, make such a move.
2. If one animal's move is jump while another animal's move is slide, we always choose jump.
3. If both animals' moves are jump, the configuration should be "...xo_xo...". In this case, whichever jump you choose, you will be stuck eventually (why is this so?). Such a configuration is called the fatal Jump/Jump and should be avoided.
4. If both animals' moves are slide, we will select the slide such that the next configuration you are getting is not the fatal Jump/Jump.

Points to Note

• For simplicity, we assume that the inputs from the user are always valid. That is, they enter integers in the range between 1 and 10.
• Do not use any two-dimensional arrays or File I/O in your program. One-dimensional arrays are fine; in fact, you would certainly need to use one-dimensional arrays.
• There may be more than one correct solution for each layout. Any correct solution is fine.
• Be very careful with array index out-of-bounds errors. The compiler will not notify you of such problems; you may get the run-time errors "Segmentation Fault", "Bus Error", or other strange logic errors. Understand exactly what your code is doing before compiling!

A total of 9 different hosts have accessed this document in the last 445 days; your host, nsrp-source.comp.nus.edu.sg, has accessed it 5 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.