On this page:
I’ve Got Life, Brothers
Livin’ Large
There’s Got To Be More To Life Than This
Circle of Life
Before you go...

9 Graphs

home work!

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

Textbook references: Chapter 29: Algorithms that Backtrack


Goals: Your new lab partner today will be your HW partner for the next several weeks.

Exercise 1 Sit next to your new partner if they are in this section.

Exercise 2 Exchange contact information with your partner: telephone number, latest-greatest social network scheme, whatever-app.

Exercise 3 Agree to a first meeting time and meeting place. At that meeting, agree to next meeting time and meeting place.

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.

Conway’s Game of Life works as follows:
  • Every cell is either alive or dead.

  • Every cell’s neighbors are the eight cells directly surrounding it.

  • If a cell is alive but has less than two live neighbors, it dies as if by underpopulation.

  • If a cell is alive but has more than three live neighbors, it dies as if by overpopulation.

  • If a cell is alive and has two or three live neighbors, it survives.

  • If a cell is dead and has exactly three live neighbors, it is born as if by reproduction.

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.

(define GameOfLife (signature [ListOf [ListOf 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
(: TINY-GAME GameOfLife)
(define TINY-GAME
  '((#f #f #f #f)
    (#f #t #t #f)
    (#f #t #f #f)
    (#f #f #f #f)))

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

(: TINY-GAME+1 GameOfLife)
(define TINY-GAME+1
  '((#f #f #f #f)
    (#f #t #t #f)
    (#f #t #t #f)
    (#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 (Number Number GameOfLife -> [ListOf 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 (Number Number 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 (Number Number 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 4 Design a function which given a list of booleans returns the number of elements that are #t.

Exercise 5 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 6 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 7 Design a function draw-grid which draws a GameOfLife. A function header and test is provided below.
(define Image (signature (predicate image?)))
(: 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)))

So if we run
(: main (GameOfLife -> GameOfLife))
; Run conway's game of life
(define (main gol)
  (big-bang gol
    [on-tick next-grid 1/10]
    [to-draw draw-grid]))
on TINY-GAME, what happens? Is it any interesting? Spoiler alert: not really. It gets stuck awful fast. Try it out to see why.

But what about...
 (list (list #f #f #f #f #f #f #f)
       (list #f #f #f #f #f #f #f)
       (list #f #f #f #f #f #f #f)
       (list #f #f #f #f #f #f #f)
       (list #f #f #f #f #t #t #t)
       (list #f #f #f #f #t #f #f)
       (list #f #f #f #f #f #t #f)))

Livin’ Large

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

(define Coord
  (signature (predicate (λ (l)
                          (and (list? l)
                               (= (length l) 2)
                               (number? (first l))
                               (number? (second l)))))))
(define FirstState (signature [ListOf Coord]))
; It represents a list of coordinates that are alive at the onset of the game

Exercise 8 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 (Number 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)))

Switch pair programming roles before continuing!

Exercise 9 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:
 (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 10 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.
(define CellUpdate (signature (Boolean [ListOf Boolean] -> Boolean)))
; It 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:
(: range? (Number -> Boolean))
(define (range? n)
  (and (>= n 0)
       (<= n 8)))
; Represents a number in the range 0-8, inclusive
(define Num0-8 (signature (predicate range?)))
(: cell-update ([ListOf Num0-8] [ListOf Num0-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 11 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 12 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.

Why is this the case?

Then, to determine the actual size of the cycle, keep applying the update rule to tortoise until it’s the same as hare. However many times that takes is the size of the cycle.

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 13 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.