10 Graphs

Purpose: The purpose of this lab is to design a cool animation with grid-like graphs.

Textbook references: Chapter 29: Algorithms that Backtrack

I’ve Got Life, Brothers

Goals: To play the game of life.

Today we’re going to implement Conway’s Game of Life. The word "game" is somewhat disingenuous, as it is actually a simulation of cellular automata, which is a fancy way of saying a grid of cells, where each cell can be in one of a finite amount of states, and the cells all change their state (or remain the same) at the same time depending on a set of rules.

Notice how each cell has a group of neighbors, so we are dealing with a graph. However, because everyone’s neighbors is predetermined based on their location, we don’t need to keep track of it.

Our grid is going to be a fixed-size square of cells. Every cell will have eight neighbors, including cells on the edge of the grid. The cells on the top row will be neighbors of cells on the bottom row and vice versa, and the same is true for cells in the leftmost and rightmost column (meaning our grid is actually a torus).

Starter Code: Below is a data definition that will let us run the game as well as an example of a 4x4 grid for testing purposes.

; A GameOfLife is a [List-of [List-of Boolean]]

; where the length of the outer list is the same as all of the inner lists

; and represents alive (#t) and dead (#f) cells

(define TINY-GAME

(list (list #f #f #f #f)

(list #f #t #t #f)

(list #f #t #f #f)

(list #f #f #f #f)))

Sample Problem Define another constant which shows what TINY-GAME will become after applying the rules of the game.

(define TINY-GAME+1

(list (list #f #f #f #f)

(list #f #t #t #f)

(list #f #t #t #f)

(list #f #f #f #f)))

Sample Problem Finish a function, which, given a coordinate of the grid (two natural numbers) and the grid, outputs a list of the boolean values of its eight neighbors. The main function is provided for you, but you will implement get-cell, a helper function. Hint: list-ref and modulo could be helpful

; neighbors : Nat Nat GameOfLife -> [List-of Boolean]

; The neighbors of i, j in gol (i = row, j = column)

(define (neighbors i j gol)

(list (get-cell (sub1 i) (sub1 j) gol)

(get-cell (sub1 i) j        gol)

(get-cell (sub1 i) (add1 j) gol)

(get-cell i        (sub1 j) gol)

(get-cell i        (add1 j) gol)

(get-cell (add1 i) (sub1 j) gol)

(get-cell (add1 i) j        gol)

(get-cell (add1 i) (add1 j) gol)))

(check-expect (neighbors 1 1 TINY-GAME)

(list #f #f #f

#f    #t

#f #t #f))

(check-expect (neighbors 3 1 TINY-GAME)

(list #f #t #f

#f    #f

#f #f #f))

; get-cell : Nat Nat GameOfLife -> Boolean

; The value of the cell at y, x (looping around the ends of the list if necessary)

(define (get-cell y x gol)

...)

(check-expect (get-cell 0 0 TINY-GAME) #f)

(check-expect (get-cell 4 4 TINY-GAME) #f)

(check-expect (get-cell 1 2 TINY-GAME) #t)

(check-expect (get-cell 5 6 TINY-GAME) #t)

; get-cell : Nat Nat GameOfLife -> Boolean

; The value of the cell at y, x (looping around the ends of the list if necessary)

(define (get-cell y x gol)

(local [(define n     (length gol))

(define y-mod (modulo y n))

(define x-mod (modulo x n))]

(list-ref (list-ref gol y-mod) x-mod)))

Exercise 1 Design a function which given a list of booleans returns the number of elements that are #t.

Exercise 2 Design a function new-value/conway, which given a cell’s current value and the list of its neighbors’ current values, outputs the new value of the cell. locally define a constant which determines the number of neighbors that are alive so it only needs to be computed once.

Remember that a cell lives if it is alive and it has 2 or 3 live neighbors, or if it is dead and has 3 live neighbors.

Exercise 3 Design a function next-grid that given a GameOfLife outputs the new grid. Use your constant from exercise 1 to test it. Use two nested calls to build-list to define this function.

Switch pair programming roles before continuing!

Starter Code: Below are some constants which will help you draw the grid.

(define CELL-SIZE 5)

(define LIVE-CELL (color-frame "cadetblue" (square CELL-SIZE "solid" "seashell")))

(define DEAD-CELL (square CELL-SIZE "solid" "white"))

Exercise 4 Design a function draw-grid which draws a GameOfLife. A function header and test is provided below.

; draw-grid : GameOfLife -> Image

; Draw the game of life

(define (draw-grid gol) ...)

(check-expect (draw-grid TINY-GAME)

(above (beside DEAD-CELL DEAD-CELL DEAD-CELL DEAD-CELL)

(beside DEAD-CELL LIVE-CELL LIVE-CELL DEAD-CELL)

(beside DEAD-CELL LIVE-CELL DEAD-CELL DEAD-CELL)

(beside DEAD-CELL DEAD-CELL DEAD-CELL DEAD-CELL)))

Livin’ Large

So that animation was pretty cool, but it sure took a lot of work to make. Let’s make that simpler.

; A FirstState is a [List-of (list Nat Nat)]

; and represents a list of coordinates that are alive at the onset of the game

Exercise 5 Design a function initial-grid which takes a natural number dictating the size of the grid and a FirstState, and creates a GameOfLife of that size where the coordinates in the first state are alive and the rest are dead. A test and function header are provided for you. As you’ll notice, the left-hand side of the check-expect is much faster to write than TINY-GAME.

; initial-grid : Nat FirstState -> GameOfLife

; A game of life with size grid-size with points in fs alive

; assume grid-size is larger than any number in fs

(define (initial-grid grid-size fs)

...)

(check-expect (initial-grid 4 (list (list 1 1)

(list 1 2)

(list 2 1)))

TINY-GAME)

Switch pair programming roles before continuing!

Exercise 6 Modify your main function to take a number grid-size and a FirstState and run the game with that initial state in a grid of that size. Then, try this out:

(main

50

(list (list 20 20)

(list 20 21)

(list 21 20)

(list 22 20)

(list 20 24)

(list 21 24)

(list 22 24)

(list 22 23)))

So where are these magical numbers coming from? Turns out a lot of people are very fascinated by Conway’s Game of Life, and have discovered a lot of interesting shapes. The first interesting shape we saw in this lab is a glider, and this one is called "glider by the dozens."

Feel free to try out as many shapes as you like!

There’s Got To Be More To Life Than This

As it turns out, there are many life-like cellular automata. Like Conway’s, they are 2D, the cells are alive or dead, and the cells have the same eight neighbors. Also like Conway’s, whether or not a cell is alive in the next state is only dependent on its current state and the amount of neighbors that are alive.

This kind of rule can be summarized with two lists: a list of numbers that describe when a cell is "birthed" (how many neighbors need to be alive when a cell is not for it to be alive in the next state, often abbreviated as B) and when a cell "survives" (how many neighbors need to be alive when a cell is for it to be alive in the next state, often abbreviated as S). For example, in Conway’s game, the birth list is (list 3) and the survival list is (list 2 3). Naturally, then, life and what happens in it amounts to nothing more than B/S.

Exercise 7 Look at the signature for new-value/conway. Since all life-like automata operate under the same general framework, a new ruleset would operate under the same signature.

; A CellUpdate is a [Boolean [List-of Boolean] -> Boolean]

; and represents the rules by which a cell's new value is determined

So, we want a way to make different kinds of CellUpdates quickly. Clearly, we need a function. Finish defining the following function:

; cell-update : [List-of [0, 8]] [List-of [0, 8]] -> CellUpdate

; Output a cell update function with "birth" numbers and "survival" numbers

(define (cell-update birth survival) ...)

Test it by commenting out your old defintion of new-value/conway, and redefine it as (define new-value/conway (cell-update (list 3) (list 2 3))). All of your old tests should still pass.

Switch pair programming roles before continuing!

Exercise 8 Modify your next-grid function to take in a CellUpdate function to use in place of new-value/conway. Your old tests for next-grid should pass when passing in new-value/conway.

Exercise 9 Modify your main function to take a CellUpdate, and define a local function to replace next-grid with a function that takes a GameOfLife and outputs its new state, using the given CellUpdate.

Experiment with as many life-like cell updates as you want! Check out the last paragraph in "Notation for rules" to make sense of the examples.

Switch pair programming roles before continuing!

Circle of Life

For any game of life on an NxN grid, there are 2N2 possible states (since every cell can be either alive or dead). Since the update rule is deterministic (that is, for any current state and update rule, there is exactly one next state) and the number of states is finite, a cycle must exist.

You can probably see this in your simulation; there’s some set of states that the game eventually devolves into that it just keeps repeating over and over again.

We want to figure out, given some initial state, the number of states in its eventual cycle, which we’ll refer to as the size of the cycle. A simple example would be a completely dead grid using Conway’s update rule, in which the cycle size would be 1, as it simply stays dead.

In order to find the cycle, we need to be able to find a state which repeats. This could be an incredibly expensive computation memory-wise using a naive algorithm (2N2 is a big number, after all), but luckily we have a nice tortoise and hare algorithm to help us:

1. Initialize tortoise to state 0

2. Initialize hare to state 1 (apply the update rule once to state 0)

3. If tortoise and hare are the same, stop

4. Otherwise, update tortoise once and hare twice

5. Go to step 3

At the nth iteration of step 3, hare is always n steps ahead of tortoise. Therefore, since the cycle exists and its size is finite, tortosie will eventually equal hare and the algorithm will end on step 3.

A more complicated example is having a single glider using Conway’s update rule in a sufficiently large grid (grid-size > 4). The size of the cycle should be (* grid-size 4).

Exercise 10 Design the function cycle-size that takes an initial state and a CellUpdate and outputs the size of that game’s cycle.

Before you go...

If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.