Exercise #1: Identify Groups on a Board

◀ Programming Exercises▶ Identify Groups on a Board - Step 1 Amazon I remember in my freshman year I went to a concert in a concert hall, which was big enough to accommodate an audience of more than one thousand people. However only one or two hundred people showed up.

As you can imagine “groups” began to form among those who knew each other or clicked in a casual conversation. Each group has some number of people sitting close to one another. Of course there were people who sat alone, myself included. Anyway, this piece of memory motivated this exercise.

In this exercise consider a square board on which each square is either empty or occupied by one person. Two people belong to the same group if they share a common edge on the board. In Figure 15.1, there are 11 groups; the largest group has 5 people.

Write a program that lists all groups. Specifically, the program reads a file, given by the command line, which contains the size of the board and the peoples’ coordinates. The file that produces Figure 15.1 looks like this:

10 10
6 4
5 9
9 4
4 8
9 3
9 6
5 3
5 1
0 0
9 5
6 0
1 8
1 7
3 5
7 2
4 5
5 8
5 4
3 4
7 1
5 7
9 2
1 4
1 1

Of the very first pair, the first value is the width of the board and the second one the height of the board. In the following pairs, the first value is the horizontal coordinate and the second one the vertical coordinate. The lower left corner has coordinate (0,0); the vertical coordinate value increases upward and horizontal coordinate value increases eastward.

The program determines which person belongs to which group, and outputs to a file the total number of groups, (for each group) the number of people the group has, and the coordinates of people belonging to that group.

Here is a sample output when the board looks likes Figure 15.1:

There are a total of 11 group(s).

Group 1: 1 person(s).
	0 0

Group 2: 1 person(s).
	1 1

Group 3: 1 person(s).
	1 4

Group 4: 2 person(s).
	1 7
	1 8

Group 5: 3 person(s).
	3 4
	3 5
	4 5

Group 6: 4 person(s).
	4 8
	5 8
	5 9
	5 7

Group 7: 1 person(s).
	5 1

Group 8: 3 person(s).
	5 3
	5 4
	6 4

Group 9: 1 person(s).
	6 0

Group 10: 2 person(s).
	7 1
	7 2

Group 11: 5 person(s).
	9 2
	9 3
	9 4
	9 5
	9 6

Figure 15.1 – a sample board with people (represented by circles)


Suppose the program’s executable is group, then the command line is

./group <inputFile> <outputFile>

Given all this information, you should be able to write the program now. Get started now and see if you are up to the challenge. If you are lost, take a look at my results, which follow our favorite four-step model.

Next let's apply the Four Step Programming Model described in Chapter 11.8!

◀ Programming Exercises▶ Identify Groups on a Board - Step 1