CS1101C Practical Exam

Session 2 (1000 - 1145 hours)

City Skyline

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

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

Background

Imagine you are approaching a bustling city and as you look into the horizon, you notice the outline of the many buildings and how it forms an intricate boundary between heaven and earth. This is the skyline of the city.

Your architect friend, who is in charge of urban redevelopment, would like to find out how the addition of new buildings affect the city skyline. As such he has asked you, the avid programmer, to assist him. He will provide you with the location and size of a list of buildings in the city, and your program will output the skyline as a list of numbers. Fortunately, all buildings are rectangular and they are all sited at ground zero, i.e. the land is actually very flat.

A building is specified as a triplet (L,H,W) where L is the location of the left side of the building, H is the height of the building, and W is the width of the building. In the spirit of simplicity, all values are positive integers. The figure below showns an example of a list of buildings {(1,11,4),(23,13,6),(3,13,6),(14,3,9),(2,6,5),(19,18,3),(12,7,4),(24,4,4)} and the corresponding skyline on the right.

Text File

A text file called “skyline.txt” has been copied into your directory by the pesetup command. This text file contains an unknown number of lines each a triplet consisting of the three positive integer values separated by spaces. The lines are NOT sorted in any particular order. The sample text file contains the following lines:

Task

Your task is to write a program that reads in the text file and generate the skyline as a list of numbers that represents a "path" taken by, say Karel, starting from the left side of the leftmost building, and travelling horizontally and vertically over all lines that make up the skyline. In this respect, the skyline can be seen as a two-dimensional x-y space . The skyline values are alternating x and y values and will always end with the value 0. As an example, the skyline for the above figure is given by the list {1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0}. A partial explanation is given below:

1: Start at x coordinate 1.
11: Go up to y coordinate 11.
3: Go right to x coordinate 3.
13: Go up to y coordinate 13.
9: Go right to x coordinate 9.
0: Go down to y coordinate 0.
And so on...

You are allowed to write your program in anyway you wish, but you are reminded to adhere to the principles of modularity. Write a comment on top of each function, justifying how the function implementation follows the principles of abstraction, cohesion, and coupling.

Sample Output

The following is the sample output using the above sample text file. Remember that we will test your program with other input files.

$ gcc -Wall skyline.c -o skyline
$ ./skyline
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

$

Note that the skyline values are separated by a space. You may assume the following:

The height of each building will not exceed 100;
The location of the right side of the rightmost building will not exceed 100;
The locations of the left side of all buildings will be at least 1.

We will test your programs with other (more complicated) text input files.

Notes

Do not use any structures or any form of dynamic memory allocation (using malloc or calloc) in your program, else no credit will be given.

Remember to submit your program frequently using the submit skyline.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.