3.8. Lab 7: Game of Life

Due Date: 11:59pm February 27, 2024

Labs should be submitted as a single Jupyter notebook to CourseLink Dropbox

This lab counts for 4% of the final grade

To do in advance of this lab:

  • Make sure you have run the code in Allen Downey’s Chapter 6 notebook.

3.8.1. Exercises

Complete the exercises corresponding to Exercise 6.1, 6.2, 6.4 and optionally, 6.5 in Chapter 6 of Think Complexity (version 2):

  1. Start GoL in a random state and run it until it stabilizes. What stable patterns can you identify?

  2. Many named patterns are available in portable file formats. For one source (see http://www.conwaylife.com/wiki/Main_Page) write a function to parse one of these formats and initialize the array.

  1. One variation of GoL, called Highlife, has the same rules as GoL, plus one additional rule: a dead cell with 6 neighbors comes to life.

    You can try out different rules by inheriting from Life and changing the lookup table.

    Modify the supplied table to add the new rule.

  2. (OPTIONAL) If you generalize the Turing machine to two dimensions, or add a read-write head to a 2-D CA, the result is a cellular automaton called a Turmite. It is named after a termite because of the way the read-write head moves, but spelled wrong as an homage to Alan Turing.

    The most famous Turmite is Langton’s Ant, discovered by Chris Langton in 1986. See http://en.wikipedia.org/wiki/Langton_ant.

    The ant is a read-write head with four states, which you can think of as facing north, south, east or west. The cells have two states, black and white.

    The rules are simple. During each time step, the ant checks the color of the cell it is on. If black, the ant turns to the right, changes the cell to white, and moves forward one space. If the cell is white, the ant turns left, changes the cell to black, and moves forward.

    Given a simple world, a simple set of rules, and only one moving part, you might expect to see simple behavior—but you should know better by now. Starting with all white cells, Langton’s ant moves in a seemingly random pattern for more than 10 000 steps before it enters a cycle with a period of 104 steps. After each cycle, the ant is translated diagonally, so it leaves a trail called the highway.

    Write an implementation of Langton’s Ant.

3.8.2. Submission

Please submit a single Jupyter notebook which completes the above exercises, filling in Allen Downey’s Chapter 6 notebook. There are already placeholders in the notebook for your work.