|COMP1011 COMP1011 Assignment 1 - 05s2|
|Computing 1A 05s2||
Mon 22 Aug 2005 10:14
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.
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.
There are only two rules:
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.
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.
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.
Cells are represented by booleans.
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]]
Location type represents the coordinates of a cell
in the world.
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.
It would be represented as:
((1,2), [[True, True, False], [False, True, True]]
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]])
getCell :: World -> Location -> Cell
Given a game world and a location, yield the liveness at that location.
GameOfLife> getCell world (0,0)
GameOfLife> getCell world (1,0)
GameOfLife> getCell world (1,2)
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
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.
) is out of
where (x,y) is the location argument given to
getCell. Note that
error will automatically
"*** Exception: " in front of the string you pass
to it. Make sure that you do not add this yourself.
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]])
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
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)
GameOfLife>evolveCell world (0,2)
evolve :: World -> World
Given a world in the game, produce the next state of the world.
((1,2), [[True, True, True], [True, True, True]])
((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 :: String -> World
Initialises the world from a string representation.
An example of a valid world is:
which as a string looks like:
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
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.
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
!! 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.
We are providing you with the skeleton of the solution (which also compiles). It contains:
To begin on the assignment download the file GameOfLife.hs.
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.
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
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.
- to unpack, use the command
tar xzf LifeClient.tar.gz on
If you plan to work on your assignment on your own machine (instead of CSE
lab computers), you must install the library
addition to GHC; see our
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.
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
import Data.List showWorld :: World -> String showWorld (_, board) = unlines (map (map toChar) board') where board' = reverse (transpose board) toChar True = '*' toChar False ='.'
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
Sunday 28 August, 2005
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.
Your solution should be submitted using the
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
There is a single mark for early submission of a draft. To receive this mark your solution must:
setCellfully implemented, and
give cs1011 ass1_draft GameOfLife.hs diary.txt
Note how the assignment specifier for the early
submissions and final submission are different (i.e.,
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.
|Subjective (style & structure)||4|
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.
Ask your tutor, or post to the message board.
|17 August, 2005||
|21 August, 2005||