The prominent British mathematician J.H. Conway has made many original contributions to subjects as diverse as the theory of finite simple groups, logic, and combinatorics. He devised the game of Life by starting with previous, technical studies of cellular automata and devising reproduction rules that would make it difficult for a configuration to grow without bound, but for which many configurations would go through interesting progressions. Conway, however, did not publish his observations, but communicated them to Martin Gardner. The popularity of the game skyrocketed when it was discussed inMartin Gardner, "Mathematical Games" (regular column), Scientific American 223, no. 4 (October 1970), 120-123; 224, no. 2 (February 1971), 112-117.
Robert L. Kruse, Data Structures and Program Design, 2e (Prentice-Hall, 1987), p. 30.
One-dimensional Life takes place on a straight line instead of a rectangular grid. Each cell has four neighboring positions: those at distance one or two from it on each side. The rules are similar to those of two-dimensional Life except(Hence a dead cell with zero, one, or four living neighbors stays dead; a living cell with two or four living neighbors stays alive.)
- a dead cell with either two or three living neighbors will become alive in the next generation, and
- a living cell dies if it has zero, one, or three living neighbors.
Ibid., pp. 59-60.
In the game of Life (in either one or two dimensions), all the changes between generations occur simultaneously. That is, between one generation and the next, all the dead cells that are to come alive are vivified (enlivened? spawned? created? born?) at the same time that all the living cells that are scheduled to die pass from their cellular world to the automaton hereafter. For example, the fact that a cell will become alive or die in the next generation does not affect the neighbor count of its neighboring cells until the next generation is actually created; the impending change can neither save a neighboring cell of the current generation from dying nor cause a neighboring cell to become alive.
What is the Game of Life? by Paul Callahan (on the Wonders of Math site)
John Conway's Game of Life (with Java applet)
Jason's Life Page (Jason Summers)
Patterns, Programs, and Links for Conway's Game of Life by Paul Callahan
Write a set of Lisp functions that play the one-dimensional game of Life on an effectively infinite line of cells.
The main function must be named life1D, and it should accept two parameters: the number of generations for which the game is to be played (or life is to be simulated), and an initial configuration, which is specified as a Lisp list of integers in ascending order, where each integer represents the index of a living cell. These indices can be positive or negative, and configurations can grow in either direction without bound (except for the bounds on the range of integers in the particular implementation of Lisp).
For example, the configuration
(1 3 4 5)
represents the configuration
| ··· | * | * | * | * | ··· |
The precise numbers used to specify a configuration do not matter, only the relative positions of alive and dead cells; for example, (2 4 5 6)and (-3 -1 0 1) are alternative specifications of the same configuration specified above. In fact, since this configuration is a rightward glider, the configuration (-3 -1 0 1) will pass through (1 3 4 5) in 4 generations and (2 4 5 6) in 5.
Other configurations to try (the first three as listed in Kruse's book):
| (2 4) | - dies out in 2 generations |
| (2 3) | - oscillates over 2 generations |
| (3 4 5 6 7) | - repeats in 6 generations |
| (10 12 13 14 18 19 20 22) | - after 46 generations, repeats over 6 generations |
For example, the Lisp expression to run the last configuration above for 52 generations would be:
(life1D 52 '(10 12 13 14 18 19 20 22))
Since the last example is two gliders that head toward each other, compare it with (8 10 11 12 20 21 22 24), which takes 54 generations to reach the same repeating pattern, and with (10 12 13 14 17 18 19 21), which reaches an oscillating state within 4 generations.
The output format may be extremely simple: a sequence of Lisp lists, one per line, beginning with the original configuration, followed by the number of generations specified by the user.
For example, the output produced by the function
(life1D 10 '(1 3 4 5))
would be
(1 3 4 5) (2 4 5 6) (3 5 6 7) (4 6 7 8) (5 7 8 9) (6 8 9 10) (7 9 10 11) (8 10 11 12) (9 11 12 13) (10 12 13 14) (11 13 14 15) T
Because all the changes from one generation to another occur simultaneously, you will not want to make these changes to the current configuration, but insert the indices of cells that will be alive in the next generation into a different (initially empty) list.
It is possible to process the current configuration in a single left-to-right pass, provided that you maintain sufficient state information and pass it from one recursive function call to the next via an additional parameter.
Please hand in a hardcopy listing of your solution to this assignment (to ensure that the formatting which you carefully prepared is preserved) and submit the source code for your solution using the following form:
Your assignment submissions are password-protected. These passwords apply only to form data submitted via the Web server. They are separate from (and typically different from) your network password or the password for your Unix account (if you have one).
Your solution should display the following characteristics:
Correctness - The program should conform to the specifications for which it was written. It should include correct handling of special cases, error conditions, etc., except that you may assume that input will be provided in the specified format.
Design and Efficiency - The program should be constructed from small, coherent, independent and loosely coupled functions. Each function should access only its own parameters. The control constructs and data structures used should be those appropriate to the problem at hand. The program should not perform unnecessary steps, use extraneous variables, nor implement the algorithm in a contorted or inefficient way.
Style and Documentation - The program should conform to generally accepted principles of style, such as a consistent pattern of indentation, use of meaningful identifiers, generous use of space, etc. Internal documentation should include program and function headers, and in-line comments to clarify the code.
Knowledge of the language - Your program should provide evidence of your familiarity with the principal control constructs, operators, built-in functions, and data structuring facilities of the assigned language.
In the case of Lisp, you should also demonstrate your grasp of the principles of functional (applicative) programming. Comments should be prefixed according to the standard practice for Lisp.
The weightings of the various factors for grading will be approximately as follows:
| Correctness | 50% | |
| Design and Efficiency | 20% | |
| Style and Documentation | 20% | |
| Idiomatic use of the Lisp language | 10% |
Assignments will be accepted after the due date and time, but late submissions will be assessed a penalty of 1% per hour or portion of an hour.
Copyright © 2004 Jonathan Mohr