April 1996 Programmer's Challenge

Mutant Life

Mail solutions to: progchallenge@mactech.com

Due Date: 10 April 1996

Time for a little nostalgia this month. Most of you probably remember John Conway's exploration of cellular automata known as the game of Life. The game is played on a grid of square cells. A cell has one of two states: it can be occupied ("alive") or empty ("dead"). Time proceeds in discrete increments, or generations, and the state of a cell at time N+1 is determined by its state and that of its eight neighbors at time N. In the simplest variations of the game, a "birth" occurs in an empty cell if exactly three of its neighbors were alive in the previous generation. A "death" occurs in an occupied cell surrounded by four or more living cells, or by fewer than two living cells.

This month, the challenge is to write code that will compute the state of a Life-like world some number of generations into the future. The prototype for the code you should write is:

pascal long PropagateLife(
  BitMap cells,           /* the boundaries and population of your automata */
  long numGenerations,    /* number of generations to propagate */
  short birthRules,       /* defines when cells become alive */
  short deathRules        /* defines when cells die */
);
 

Your automata live in a world defined by the rectangle cells.bounds (with top and left coordinates guaranteed to be 0). Their world is actually a torus instead of a rectangle: the cells.bounds.right-1 column of cells is adjacent to column 0, and the cells.bounds.bottom-1 row of cells is adjacent to row 0. The rules for birth and death are generalized from those in the first paragraph and defined by birthRules and deathRules. An empty cell with X occupied neighbors becomes alive in the next generation if the bit (birthRules &(1<<X;)) is set. An occupied cell with Y occupied neighbors dies in the next generation if the bit (deathRules &(1<<Y;)) is set. Any other cell retains its previous state (occupied or empty) from one generation to the next. As an example, the version of the game described in the first paragraph would have birthRules=0x0008 and deathRules=0x01F3.

The initial population of automata is pointed to by cells.baseAddr, one bit per cell, when PropagateLife is called. An occupied cell has the value 1, and an empty cell has the value 0. The cells BitMap is defined in the usual way, with row R found starting at *(cells.baseAddr + R*cells.rowBytes). You are to use birthRules and deathRules to propagate this population ahead for numGenerations generations, stopping only in the event that the population of generation N is identical to that of the immediately preceeding generation. Your code must return the number of generations processed (which will be numGenerations unless a static population was reached). When you return, the memory pointed to by cells.baseAddr must contain the propagated population.

You may allocate auxiliary storage up to 1MB, plus up to 10 copies of the bitmap, if that is helpful, provided (as always) that you deallocate any memory before returning, as I will be calling your code many times.

This month, we continue the language experiment that permits your solution to the Challenge to be coded in C, C++, or Pascal, using your choice among the MPW, Metrowerks, or Symantec compilers for these languages. The environment you choose must support linking your solution with test code written in C. Along with your solution, you should provide a project file or make file that will generate a stand-alone application that calls your solution from C test code.

This will be a native PowerPC Challenge. Now, start propagating ...

Last modified by Bob Boonstra on 3/21/96.