CENG C Programming Take Home Exam 1 Solution

    • Introduction

This assignment aims to get you familiar with multi-dimensional arrays, recursion and simple input/out-put in C.

Spider cannibalism is the act of a spider consuming another individual of the same species as food. In this assignment, you are going to implement a program to solve a spider game on a eld. A grid-like eld contains multiple spaces and spiders on it. The aim is to decide that the given eld evolves to an an ideal eld with only one spider on it or not. In order to reach an ideal eld, one of the spiders will be eaten by another at each turn.

There are some criterias de ning how spiders eat each other and move, which will be explained fur-ther in the following section. Your program has to act according to these speci cations. You will either nd an ideal eld or you will conclude that there cannot be an ideal eld with the given con guration.

In order to solve this problem, you have to have a good understanding of recursion and backtrack-ing. Backtracking is a generic algorithm to generate all/some solutions to a problem. The idea is to

1

incrementally build candidate solutions and \backtrack" (to a previous step) as soon as the candidate is determined as an invalid solution. See https://www.cis.upenn.edu/~matuszek/cit594-2002/Pages/ backtracking.html and hint provided in the speci cations for further information about backtracking.

Keywords: Recursion, Backtracking, Arrays


    • Speci cations

Spiders live on a V-shaped eld where we show a spider with s and an empty space with e. At each turn, only one spider can move. This can be any of the spiders that is able to move.

A spider can only move by jumping over a neighbor spider (i.e., by eating it) to an empty space. A spider can move at most in six di erent directions (i.e., diagonal and horizontal but not vertical). However, it cannot go out of the bounds of the eld.

For example, spider at 16 has 6 candidate positions to go: 03 (top-left, by eating 10), 05 (top-right, by eating 11), 14 (left, by eating 15), 18 (right, by eating 17), 23 (bottom-left, by eating 20) and 25 (bottom-right, by eating 21). However since 10 and 17 is empty (no spider to eat) it cannot move to 03 and 18; and since 25 is not empty, it cannot move to 25.

e e e
e e e e
01
02
03
04
05
06
07
e e e
s e e
08
09
10
11
12

13
e s
s e e

14
15
16
17
18

e s
s e

19
20
21
22


e
e s


23
24
25


e
e


26
27




e



28




An ideal  eld is the one with only one spider on it. Our goal is writing a recursive function that can determine whether a given  eld can evolve to an ideal  eld after a number of moves of the spiders.

Iterative solutions will get NO credits.

If the program can nd such a sequence of moves that converts the initial eld to an ideal one, it will print the solution and terminate (i.e., no need to look for any other solutions). If the eld can not be converted to an ideal one, the program will give a message and terminate. See Output section for the details of the expected output for both cases.

Hint: You should design a recursive function, e.g., CHECK(field) to decide whether a given initial eld may become an ideal eld after a number of turns (and, moves). That is, at a given turn, if the current eld is ideal, the function can stop and return. Otherwise, the function should try every legal (valid) move on the current eld in this turn, and after every move, check again whether the new eld is either an ideal one or may evolve to an ideal one, and if not, undo the last move (and try another one).

Example: Consider the  eld

e e s s
01
02
03
04
e s e
05
06

07
e e

08
09

e

10





2

Now, for this initial eld (clearly not ideal); there are two possible moves: the diagonal one and horizontal one. Assume the algorithm rst tries the diagonal move (spider at position 3 moves to 8 by eating spider at 6): then it checks for the new eld, since the eld is not ideal and there is no more possible moves, it should undo the rst move. Then it tries what happens if it makes the horizontal move (spider at position 4 moves to 2 by eating spider at 3), checks the new board, not yet ideal but there is a possible move, try the diagonal move now, and check the new board, and done; it is ideal! Note that, undoing the previous move at each turn is called backtracking.

There can be more than one solution for nding the ideal eld, i.e. the consecutive moves can be di erent. It is enough to come up with one solution.

There can be any number of empty spaces in the initial  eld con guration.

Number of rows in the eld is not xed, determined by the given value in the input. See next section for details. Hence, try to come up with a generic algorithm to nd valid moves on a eld.


    • Input

Sample input: 4
ssss sse ss s


You are expected to write a program that reads from standard input. You may use redirection for simplicity when testing your code. See https://www.cs.bu.edu/teaching/c/file-io/intro/.

The rst line of the input contains an integer K which represents the length of the eld that spiders live, i.e. the number of lines you are going to read from the standard input.

Following K lines represents K rows of the eld, each one having one less character than the line above, i.e. K; K 1; :::; 2; 1. On these lines you will see two di erent characters, where s being a spider and e being an empty space in the eld.

You are not allowed to use any dynamic data structures (as we have not discussed them in the class yet), so use multi-dimensional arrays to represent the eld.

There will be no erroneous input.


    • Output

Sample output for the input above: e e s e
e e e

e e

e

s s e e

e e e


3

e e

e

s e s s

e e e

e e

e

s e s e

e e s

    • s

e

e e s e

s e s

s s

e

s s e e

s e s

s s

e

s e s s

s e s

s s

e

s s s s

s s s

    • e

e

s s s s

s s e

s s

s


Your program will write to standard output.

If the eld evolves to an ideal one, output will contain the eld after each move, in reverse order. That is, rst one is the latest status of the eld (only one spider on it) and the last one is the initial status given as the input.

Note that, you are required to print the nal eld when your check algorithm decides that it is ideal; and the elds all the way back through the recursive call chain. However, in this case, you should not permanently change your eld with a successful move (otherwise, you will only print the nal (ideal) eld again and again). You should also handle this situation in an appropriate way, so that when the program terminates (either nds an ideal eld or not), the eld array should store the initial eld.



4

Note that there may be more than one possible solution, you have to print one of them. As long as your moves are valid and you found the solution, it is correct.

In some cases, given eld may not evolve to an ideal eld. In that case, print \No ideal eld!" without quotes. (After trying each possible move and concluding that there is no way to go.)

In order to print the eld as above, use the following code snippet. As your code will be evaluated using black-box technique, you have print same as the sample. Replace k and field variables with yours.




for (int i = 0; i < k; ++i) { for (int j = 0; j < i; ++j) {

printf(" ");

}

for (int j = 0; j < (k - i); ++j) {

printf("%c ", field[i][j]);

}

printf("\n");

}

printf("\n");


    • Compile, Run and Test

Make sure that you can compile and run your code on Ineks with: gcc -Wall -o the1 the1.c
./the1 < sample_input.txt






























5