CS1101C Practical Exam

Session 2 (1000 - 1145 hours)

Aragorn's Walls

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

The deadline for this lab is Wednesday 09 November 2005, 11:45 hours. Strictly no submissions will be accepted after the deadline.

Background

After weeks of patrolling the forest where Frodo with his precious Ring is hiding, Aragorn is tired. He decides to build a wall to completely surround and protect the forest that Frodo is hiding in.

Map

The map consists of a 10 x 10 field. The top left hand-corner has coordinates (0,0), and the top right-hand corner has coordinates (0,9). An example map is shown below.

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . T . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

The meaning of the characters is:

'.' (full-stop): shows a grassy area.
'T' (capital T): shows a tree.
'*' (asterisk): shows a wall.

In the above map, there is a tree at (4,5); the rest are all grassy areas.

Forest

Suppose we know that Frodo is hiding at (4,5). Aragorn will build a wall that completely surrounds the forest that Frodo is hiding in by building eight walls, as shown below:

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . * * * . . .
. . . . * T * . . .
. . . . * * * . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

Two Forests

Suppose we are given a slightly more complicated map:

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . T . . . . .
. . . . . T . . . .
. . . . . T . . . .
. . . . . T T . . .
. . . . . . . . . .
. . . T T . . . . .
. . . . . . . . . .

A forest is defined as a group of trees that are linked together, either horizontally, vertically, or diagonally. Therefore, there are two forests above; the first forest consists of the trees at (3,4), (4,5), (5,5), (6,5), and (6,6). The second forest consists of the two trees at (8,3) and (8,4).

Suppose we know that Frodo is hiding at (4,5). That means that Frodo is hiding somewhere in the first forest. Aragorn will build walls that completely surround the first forest, as shown below:

. . . . . . . . . .
. . . . . . . . . .
. . . * * * . . . .
. . . * T * * . . .
. . . * * T * . . .
. . . . * T * * . .
. . . . * T T * . .
. . . . * * * * . .
. . . T T . . . . .
. . . . . . . . . .

After building all the walls, Aragorn likes to collect statistics for each wall project. He notes that the number of trees in the forest that Frodo is hiding in is 5, and the number of new walls he has built is 18.

Note that the second forest is not protected by walls since there is no one valuable hiding there.

Supposing that Sam suddenly appears at (8,4); i.e., the second forest. Aragorn then starts to build walls for the second wall project, and the new map becomes:

. . . . . . . . . .
. . . . . . . . . .
. . . * * * . . . .
. . . * T * * . . .
. . . * * T * . . .
. . . . * T * * . .
. . . . * T T * . .
. . * * * * * * . .
. . * T T * . . . .
. . * * * * . . . .

Aragorn notes that the number of trees in Sam's forest is 2, and the number of new walls he has built is 8. Since there are existing walls, Aragorn does not build any new walls if it is unnecessary to do so.

Ring of Trees

Here is a complicated example: suppose a new map is:

. . . . . . . . . .
. . . T T T . . . .
. . T . . . T . . .
. T . . . . . T . .
. T . . . . . T . .
. T . . . . . T . .
. . T . . . T . . .
. . . T T T . . . .
. . . . . . . . . .
. . . . . . . . . .

and Frodo is hiding at (7,5). Aragorn will build walls as follows:

. . * * * * * . . .
. * * T T T * * . .
* * T * * * T * * .
* T * * . * * T * .
* T * . . . * T * .
* T * * . * * T * .
* * T * * * T * * .
. * * T T T * * . .
. . * * * * * . . .
. . . . . . . . . .

The number of trees is 16, and number of new walls is 48.

Trees at the Edge

If trees appear at the edge of the map, Aragorn is careful not to build walls off the map, as this is trespassing and he is a very law-abiding citizen. For example, if Frodo is hiding at (4,9) in the following map:

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . T
. . . . . . . . T .
. . . . . . . . . T
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

The walls are built as shown:

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . * *
. . . . . . . * * T
. . . . . . . * T *
. . . . . . . * * T
. . . . . . . . * *
. . . . . . . . . .
. . . . . . . . . .

The statistics from this project is: 3 trees, 10 walls.

Text File

The map and locations of where Frodo, Sam, and the other members of the group are hiding, are stored in a text file called trees1.txt. This text file has been copied into your directory by the pesetup command. (There is an additional text file called trees2.txt which you may use for your own testing.) Here is the text file trees1.txt:

0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 0 1 0 0 0 1
0 0 0 1 1 1 0 0 1 0
0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
4 4
5 8
7 4

The first ten lines of the text file contains the layout of the map. 0 represents a grassy area, and 1 represents a tree.

This is followed by an unknown number of lines which represent the coordinates of Frodo / Sam / group members. Each line consists of two integers which represents the coordinates of the person hiding. In the above text file, someone is hiding at (4,4), and a second person is hiding at (5,8), and a third person is hiding at (7,4). Aragorn builds new walls as necessary to protect each person; and as usual, tree and wall statistics are displayed after each wall project.

You may assume that Frodo / Sam / group members always hide in a forest. They never hide in a grassy area because well... one cannot hide in grass!

Assume also that all the numbers in the file are valid integers. No error checking is required.

Sample Run

Assuming the sample file trees1.txt contains lines as shown above, the following is a sample run:

Initial map:
. . . . . . . . . .
. . . . T . . . . .
. . . T T T . . . .
. . . T . T . . . T
. . . T T T . . T .
. . . . . T . T T .
. . . . . . T . . .
. . . . T . . . . .
. . . . . . . . . .
. . . . . . . . . .

Protect person at (4,4), trees in forest: 15, new walls: 33
. . . * * * . . . .
. . * * T * * . . .
. . * T T T * . * *
. . * T * T * * * T
. . * T T T * * T *
. . * * * T * T T *
. . . . * * T * * *
. . . . T * * * . .
. . . . . . . . . .
. . . . . . . . . .

Protect person at (5,8), trees in forest: 15, new walls: 0
. . . * * * . . . .
. . * * T * * . . .
. . * T T T * . * *
. . * T * T * * * T
. . * T T T * * T *
. . * * * T * T T *
. . . . * * T * * *
. . . . T * * * . .
. . . . . . . . . .
. . . . . . . . . .

Protect person at (7,4), trees in forest: 1, new walls: 5
. . . * * * . . . .
. . * * T * * . . .
. . * T T T * . * *
. . * T * T * * * T
. . * T T T * * T *
. . * * * T * T T *
. . . * * * T * * *
. . . * T * * * . .
. . . * * * . . . .
. . . . . . . . . .

Note that we firstly show the initial map, then we show the the map after each wall project, together with the statistics of each wall project.

You are reminded to follow the sample output exactly; else marks will be deducted.

Remember to submit your program using the submit walls.c command, and check your submission using the check command.

All the best!

UNIX commands

Some useful UNIX commands (in case you forgot what you did in Lab 0):

“dir”: lists all the files in the directory.
“cp a.txt b.txt”: copies a.txt to b.txt.
“mv a.txt b.txt”: moves / renames a.txt to b.txt.
“cat a.txt”: shows the contents of a.txt.