COMP1011 COMP1011 Assignment 1 - 05s2
Computing 1A 05s2 Last updated Mon 22 Aug 2005 10:14
Mail cs1011@cse.unsw.edu.au

# John Conway's Game of Life

Version 1.2

This document has been changed since it was first released.

To see the list of changes see section entitled Changes at the end of this specification.

## Introduction

John Conway's Game of Life is one of the best known examples of emergent behaviour; complex behaviour that arises from deceptively simple rules. The game itself is based on a handful of very simple rules. The results, however, are reminiscent of microscopic life breeding and dying within a petri dish. Your task in this assignment will be to implement the functions that evolve this "life" from generation to generation.

## The Game

Life is played on a rectangular grid of arbitrary size which we shall henceforth refer to as the board. Each square of the board is known as a cell and these can be either live or dead. Each cell has eight adjacent cells, that is orthogonally as well as diagonally opposed cells included. Figure 1 illustrates this; the eight white squares in the diagram below are adjacent to the black one.

Figure 1

### The Rules

There are only two rules:

1. A live cell with exactly two or three adjacent cells stays alive. Otherwise the cell dies.
2. A dead cell with exactly three adjacent cells comes to life (i.e. becomes a live cell). Otherwise it remains dead.

If you like, you can justify the birth and death of cells in the following manner. A live cell with one or no adjacent cell dies as if by loneliness or starvation, while one with four or more also dies but this time from overpopulation. The birth of cells with exactly three adjacent live cells can be thought of as reproduction under precise circumstances.

#### Boundary cases

A cell at a corner of the board only has three adjacent cells, while one on the edge but not in a corner has only five. The cells which lie "outside the board" so to speak can be though of as being dead. That is, for the purposes of applying the rules you can think of the board has being surrounded by a border of dead cells that is one cell in thickness.

### Playing the Game

Life is a zero player game. It's behaviour is completely determined by the initial state of the board. Each turn in the game is known as a generation and applying the rules is known as evolving the board. The generations are numbered from zero so that the initial state of the board is generation zero.

The rules are applied in no particular order to the individual cells. They may be thought of as being updated simultaneously.

#### Example

This figure shows the initial board and the subsequent two generations. Interestingly, Generation 2 is what is known as a stable configuration. Applying the rules to this arrangement of cells will lead to the same configuration. Try it and see.

Figure 2

#### Example

It is also possible for a collection of cells to oscillate between two configurations endlessly (called a cycle of period 2.) All even generations will look like Generation 0 while odd ones will look like Generation 1.

Figure 3

Cells are represented by booleans. `True` and ```False ``` represent live and dead cells respectively.

`type Cell = Bool`

The board is represented as a list of lists of cells. Each list represents a column of the board and all such lists are equal in length.

`type Board = [[Cell]]`

The `Location` type represents the coordinates of a cell in the world.

The location (0,0) represents the lower left corner of the board, the origin.

`type Location = (Int,Int)`

The world is represented by a pair. The first component is the location of the top right hand corner of the board. The locations of cells range from (0,0) to this value. The second component of the pair is the board itself.

As mentioned above, the board is as a list of lists of cells, each such list representing a column of the board. The first element of the first list corresponds to the location (0,0). The last element of the last list corresponds to the top right hand corner of the board.

`type World = (Location, Board)`

The figure below clarifies locations and representation of the world somewhat.

Figure 4

It would be represented as:

`((1,2), [[True, True, False], [False, True, True]]`

## Implementation

In this assignment you will implement the logic that drives the Game of Life. We present the functions in a rough order of difficulty. We provide example invocations of each function. We shall use the following worlds in all examples, save `initWorld`. They represent the world in Figure 4 and Generation 0 of Figure 3 respectively.

```world = ((1,2), [[True, True, False], [False, True, True]]) world2 = ((4,4), [[False, False, False, False, False], [False, False, True, False, False], [False, False, True, False, False], [False, False, True, False, False], [False, False, False, False, False]])```

### Functions

#### `getCell`

`getCell :: World -> Location -> Cell`

Given a game world and a location, yield the liveness at that location.

``` GameOfLife> getCell world (0,0) True GameOfLife> getCell world (1,0) False GameOfLife> getCell world (1,2) True ```

If the location argument to `getCell` is out of bounds (i.e. refer to a cell which is not present in the world) the function should signal an error using Haskell's `error` function. An example invocation is:

``` GameOfLife> getCell world (50,21) *** Exception: Cell (50,21) is out of bounds ```

The error message must be exactly of this form. i.e.

`Cell (`x,y```) is out of bounds```

where (x,y) is the location argument given to `getCell`. Note that `error` will automatically print `"*** Exception: "` in front of the string you pass to it. Make sure that you do not add this yourself.

#### `setCell`

`setCell :: World -> Location -> Cell -> World`

Update a location in the world with the given liveness.

``` GameOfLife> setCell world (1,1) False ((1,2), [[True, True, False], [False, False, True]]) GameOfLife> setCell world (1,0) False ((1,2), [[True, True, False], [False, True, True]]) ```

Like `getCell`, `setCell` should also signal an error when it is given a location argument that is out of bounds. The format is the same as for `getCell`.

#### `evolveCell`

`evolveCell :: World -> Location -> Cell`

Compute the next-generation state for the cell at the given location. This is done according the rules presented earlier.

``` GameOfLife>evolveCell world (0,0) True GameOfLife>evolveCell world (0,2) True ```

#### `evolve`

`evolve :: World -> World`

Given a world in the game, produce the next state of the world.

``` GameOfLife>evolve world ((1,2), [[True, True, True], [True, True, True]]) GameOfLife>evolve world2 ((4,4), [[False, False, False, False, False], [False, False, False, False, False], [False, True, True, True, False], [False, False, False, False, False], [False, False, False, False, False]]) ```

#### `initWorld`

`initWorld :: String -> World`

Initialises the world from a string representation.

• The '*' character represents live cells
• The '.' character represents a dead cell
• Each row of the board is terminated by a newline

An example of a valid world is:

```..... .***. .***. ***** .***. ..*.. ```

which as a string looks like:

`".....\n.***.\n.***.\n*****\n.***.\n..*..\n"`

Hint: This is a good world to test your function on. If you look carefully it looks like a large arrow pointing downwards. Make sure your function parses the world so that it has correct orientation.

``` GameOfLife> initWorld ".....\n.***.\n.***.\n*****\n.***.\n..*..\n" ((4,5),[[False, False, True, False, False, False],[False, True, True, True, True, False],[True, True, True, True, True, False], [False, True, True, True, True, False],[False, False, True, False, False, False]]) ```

While testing your other functions you may want to type in the value of a world directly into a `ghci` window. Be careful that you get the order of values correct. Remember, the first element of the first list represents the bottom left hand corner of the board.

### Bonus

If you find this assignment easy and would like some additional challenge, this optional bonus part is for you. Otherwise, you can safely ignore this section of the specification. If you do solve the bonus part, you can get up to two extra marks. However, before starting on the bonus, you must first complete and submit the basic part of the assignment.

An `evolve` function that repeatedly uses `evolveCell` to yield the next generation is likely to be quite inefficient. It should be remembered that indexing into a list using the `!!` operator has a cost proportional to the length of the list. If this operation is used for each cell, the resulting solution will run in time proportional to the square of the number of cells. This is not as efficient as it could be.

For bonus marks, implement a two pass approach to evolution. The first pass should yield a representation of the board where each cell is annotated with the number of adjacent cells. The following pass should evolve each annotated cell in turn. Such a solution will run in a time proportional to the number of cells. For large boards this can make quite a difference.

It should be noted that bonus marks will only be awarded to well designed and well written solutions. It will not be enough for them to simply work.

## Stub files

We are providing you with the skeleton of the solution (which also compiles). It contains:

• Type definitions of `Cell`,`Board` etc
• Type signatures for each function that you are required to implement
• Dummy definitions for those functions

IMPORTANT: You must not alter any of the function signatures in the stub file.

This is because your assignments will be automatically tested against a test harness. This harness expects that the functions will have exactly the types specified above and will fail if any of them do not. Naturally the function bodies may be changed at will.

## Simulator

The Game of Life is made a lot more interesting when you can see your creations creep and crawl across the screen. To aid in this endeavour we have provided a simulator in which to test your final solution. It is bundled as a gzipped tarball and contains the files necessary to compile the simulator against your solution for testing. For further instructions see the README file contained in the tarball.

Note that you can develop the functions in `GameOfLife.hs` independent of this simulator, just with GHCi. However, once you have implemented all the functions, you will find the simulator useful to see how your worlds evolve.

LifeClient.tar.gz - to unpack, use the command `tar xzf LifeClient.tar.gz` on Linux

If you plan to work on your assignment on your own machine (instead of CSE lab computers), you must install the library `wxHaskell` in addition to GHC; see our software downloads.

Important: It seems as if the `LifeClient` does not work properly on Windows. Hence, please use it on the CSE lab machines if you don't have Linux at home. The `LifeClient` is not essential to solve this assignment. So, you can still solve the assignment at home; however, if you want to see the animation, you need to do that at uni if you haven't got Linux at home.

In the absence of the `LifeClient`, you can use the following function to convert a `World` to a character representation.

```import Data.List

showWorld :: World -> String
showWorld (_, board) =
unlines (map (map toChar) board')
where
board' = reverse (transpose board)
toChar True = '*'
toChar False ='.'```

## Diary

Every time you work at your assignment solution document what you did and what the outcomes where in your assignment diary. The diary must be a plain text file called `diary.txt`. Create and edit it in Xemacs, or some other text editor, not with some word processing software. The file must be saved in ASCII format.

Although this part of the assignment is assessable it is actually designed to help you. Writing down how you plan to design something and problems you encountered along the way can be of enormous benefit in arriving at a working solution. As such, you should not write this document at the very end. Not only will it show, you will also have missed out on any benefit it might have provided.

You must submit your assignment by 23:58 on Sunday 28 August, 2005 10:00AM on Monday 29 August, 2005.

If you wish to submit an assignment late, you may do so, but the maximum available mark for late assignments is reduced by 10% per day for up to five days. Assignments that are more than 5 days late will be awarded zero marks. So if your assignment is worth 85% and you submit it one day late you still get 85%, but if you submit it two days late you get 80%, and so on.

Assignment extensions are only awarded for serious and unforeseeable events. Having a cold for a few days, deleting your assignment by mistake, going on holiday, going abroad, work commitments, etc do not qualify. Therefore aim to complete your assignments before the due date in case of last minute illness, and make regular backups of your work. We cannot stress this last point enough. "Regular backups" does not mean every few days - it should be done after every significant change to your code. No extension will be granted without a fully documented submission for special consideration at the Student Centre.

Remember that we check for plagiarism (i.e., copied code and team work) and there are serious penalties. See the plagiarism information in the Course Outline.

## Submission

Your solution should be submitted using the `give` command. Type the following at the unix command line:

`give cs1011 ass1 GameOfLife.hs diary.txt`

For those of you who wish to submit the solution outlined in the Bonus section also type the following:

`give cs1011 ass1_bonus GameOfLife.hs diary.txt`

Remember, this is a separate solution. The original must still be submitted

### Early submission

There is a single mark for early submission of a draft. To receive this mark your solution must:

• compile,
• have `getCell` and `setCell` fully implemented, and
• be submitted by 23:58 28 August, 2005 11:00AM 22 August, 2005 using the command

`give cs1011 ass1_draft GameOfLife.hs diary.txt`

Note how the assignment specifier for the early submissions and final submission are different (i.e., they are `ass1_draft` and `ass1`, respectively).

Important hint: The `give` program allows you to submit your assignment multiple times and only your last submission will be marked. So, there is no harm in submitting partial solutions before the deadline. Do not leave your first submission until the last minute. Always submit some intermediate versions early.

## Marking

 Category Marks Early submission 1 Diary 2 Automarking (functionality) 8 Subjective (style & structure) 4 Bonus (optional) 2

It is a generally accepted software engineering principle that it is not simply enough for a program to be understood by the machine; it must also be human readable. For the subjective part of the marking we will be awarding marks for programs that have good comments, useful names, and good decomposition and overall design. Good decomposition practices are things such as placing repeatedly used computations in `where` clauses and breaking complex functions up into calls to small, less complex functions. Source files should also be no wider than 80 characters.

## Questions or Problems?

 Date Change 17 August, 2005 Added `showWorld` function 21 August, 2005 New deadline