Assignment 4

DUE: Sun April 24, 11 pm
(10% penalty for late submission, up to 1 day late)

Changes, Errata and Helpful Hints

Any changes to this document, typically due to an error on the part of the author, will be logged here.

Collaboration

Collaboration is strongly ENCOURAGED within a programming team, but the program you submit must still represent YOUR OWN original work. Teams should work on the algorithm together, and help debug/test each others code. However, copying code from ANY outside source (any book, current or past students, past solutions, web sites, etc.) is STRICTLY FORBIDDEN. Copy and Paste from another solution, including the solution of a team mate will incur a stiff penalty.

Problem Definition

The mathematician John Horton Conway invented the "Game of Life." Though not a "game" in any traditional sense, it provides interesting behavior that is specified with only a few rules.

LIFE is an organism that lives in a discrete, two-dimensional world. While this world is actually unlimited, we don't have that luxury, so we restrict the area in which LIFE lives to an 80 by 22 grid of cells. Each cell is capable of holding one LIFE cell. Generations mark the passing of time. Each generation brings births and deaths to the LIFE community. The births and deaths follow the following set of rules:

• Each cell has 8 neighbor cells. The neighbors of a cell are the cells directly above, below, to the right, to the left, diagonally above to the right and left, and diagonally below to the right and left.
• If an occupied cell has zero or one neighbors, it dies of loneliness. If an occupied cell has more than three neighbors, it dies of overcrowding.
• If an empty cell has exactly three occupied neighbor cells, there is a birth of a new cell to replace the empty cell.
• Births and deaths are instantaneous and occur at the changes of generation. A cell dying for whatever reason may help cause birth, but a newborn cell cannot resurrect a cell that is dying, nor will a cell's death prevent the death of another, say, by reducing the local population.

For this program you will simulate the "Game of Life." Your program will read in a series of cell coordinates the contain a living LIFE cell.( How this is done is explained below ) After all the coordinates have been read in, your program will display the current "World" of LIFE. You will use astericks ( * ) to represent a living cell, and a blank space to represent empty ( or dead ) cells.

Once the initial configuration has been read in and displayed, time will begin to pass and new generations will happen. ( ie. every iteration of a while loop will signify a the passing of a new generation. Some cells may die, others may be born; your program must calculate these changes and display the resulting world. Between each iteration ( generation ) you should pause momentarily to allow the current configuration to be seen by the user. This can be done with a call to the usleep function which can be used by sharp including unistd.h. A pause of about 1/5th of a second, or 200000 micro seconds should be about right. The program will end when the user types "ctrl-c" and terminates the program. If you choose to implement the extra credit, and draw the Game of LIFE in the graphic window; don't use usleep to pause between generations. Instead, advance to the next generation every time the user clicks the mouse. The reason for this difference is that usleep tends to wreak havoc with how things are drawn in the graphic window.

Reading in the Initial Configuration

Typing in an initial configuration every time you want to run the program can be quite tedious. For this reason we are going to use a handy feature of the unix shell called "file redirection." In linux everything is a file; the monitor is a file, the keyboard, the network card, etc. So when your programs are run they take there input from the "standard input" file. By using file redirection, you can have your program take input from a file other than standard input.

This may be a little bit conceptually weird because you are probably used to thinking in terms of the input to the program being generated while the program is running. However, think about programs that you have run over and over again; you tend to type the input to the program even before you are prompted for it. Expand this idea of pre-emption so that you type all the input to the program before it even gets a chance to start. Now, instead of typing the input into the terminal, type it in emacs and save it to a file. Now we can take that file and give it to your program using file redirection. Suppose you've written the input for your program in a file named "input.txt". To give the files contents to your program for input you would type.

When you read in the initial configuration you do not need to give any prompts to the user, just read in the information. The person writing the file already knows the format ( see below ) so they do not need to be prompted.

Input File Format

The format of the input file will be a list of x and y coordinates that specify which cells contain live cells in the initial configuration. Each set of coordinates will apear on a separate line with one or more spaces separating the x and y coordinate. The following is an example of the format.

We will use the same familiar notion of the upper left hand corner being the point ( 0, 0 ); with the x coordinate growing to the right and the y coordinate growing downward. You may also notice that we start counting at 0 rather than 1.

Some configurations grow from relatively small starting configurations. Others move across the region. Some die out, others reach a stable configuration or repeat a cycle of growth and reduction. As you find interesting configurations, please post them to the mailing list along with a brief comment about what makes the configuration interesting. Extra credit may be awarded to those who contribute interesting configurations.

Hints

The source of this exercise provides a hint that may be useful. Although it talks about a "function"; what it talks about could also be a "member function" of a class.

Assignment Framework

There is no framework for this assignment, you are free to implement it however you choose. However, you must supply a makefile which adheres to the class coding standards along with your source files.

What To Turn In

Submit your work electronically to the correct folder on the cs secure server. Don't forget to include the header template at the top of each file that you submit.

For this assignment you will turn in your source files and makefile.

Example

You can download a sample program right-clicking and save-as here. You will probably need to change the permissions on assn4_sample so that it is user executable. You can do this with the command:

You can also download a sample program that incorporates the extra credit right-clicking and save-as. here. Again, you will need to change the permissions on the file as you did above.

If you want something to try these programs with, you can download this sample input file: assn4_sample_input.

Grading Rubric (10 pts total)

Only write a small portion of code before checking that it still compiles. This way when you get a syntax error, you can be fairly certain the error is in the part you just wrote.

The points for this assignment will be distributed as follows: