Lab 20 - Spatial Logic

New files

If you downloaded this lab previously, but don’t have life.py, please download again. This will let you run life.py to play the game visually.

You will need to take the code for your two functions in game_of_life.py and put them into the new game_of_life.py file we have given you. This file also has some tests you can run.

Lab Recommendations

1. Draw a picture! The activities in Lab 20 are more complicated and will require one or more helper functions to solve. Drawing it out will help you understand the problem and break it down into smaller, more manageable pieces
2. You are strongly encouraged to add your own test functions to test your helper functions.

• create a new file called my_tests.py
• import your helper functions and test them

3. Discuss your helper methods and tests with other groups in your team. Did you do it the same way? Are there cases you missed?

Activities

free_to_roam.py

Write a function free_to_roam(grid) that finds all positions of ‘m’ (moose) that have at least 3 empty squares around them in all directions.

Break down this problem:

• How do you find all moose that have at least 3 spaces between each and the edge of the grid?
  • Draw out a large grid. Label the coordinates.
  • What spaces have at least 3 spaces between each and the edge of the grid? Indicate their coordinates on your drawing.
  • Given the size of the grid and the radius 3, what ranges should you use to search the valid space?
• How do you know if there is another moose within a radius of 3 spaces from a given position?
  • Draw a large grid. Label the coordinates.
  • Put a moose in the middle. Given it’s coordinates (i,j), what ranges should you use to search the 7x7 box centered at (i,j)?
  • You know there is at least one moose in the box—in the middle—and you want to ignore the middle moose. How do you skip position (i,j)?
• How do you put the solutions to these two problems together to solve the activity?

For example:

grid = [[None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, 'm'],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, 'm', None, None],
        [None, None, None, None, 'm', None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, 'm', None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, 'm', None, None, 'm', None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, 'm', None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]]

free_to_roam(grid)

Should return:

[(5, 4), (11, 3), (15, 3)]

Note that the moose in positions (13, 8) and (13, 10) aren’t free to roam because they are too close to each other. The moose in position (0, 15) and (4, 13) aren’t free to roam because they are too close to the edge of the grid.

four_in_a_row.py

Write a function four_in_a_row(grid) that determines whether grid contains 4 ‘d’ (ducks) in a row. Make sure to test each position horizontally, vertically, and diagonally. Make sure not to create an IndexError by checking off the edge of the grid.

Example 1:

grid = [[None, None, None, None, None, 'd'],
            [None, None, None, None, 'd', None],
            [None, None, None, 'd', None, None],
            [None, None, 'd', None, None, None],
            [None, None, None, None, None, None],
            [None, None, None, None, None, None]]

four_in_a_row(grid)

Would return:

True

Example 2:

grid = [[None, None, None, None, None, None],
            [None, None, None, None, None, None],
            [None, None, None, None, None, None],
            [None, None, None, None, None, None],
            [None, 'd', 'd', 'd', None, None],
            [None, None, None, None, None, None]]

four_in_a_row(grid)

Would return:

False

Conway’s Game of Life

For this problem, write your code in game_of_life.py.

Conway’s Game of Life was developed in 1970 by British mathematician John Horton Conway. The game is perfectly suited for a grid because it uses a two-dimensional grid of cells.

The rules of the game try to mimic how life is created. Every cell in the grid represents a living organism if it is filled in as an asterisk ’*‘. Otherwise the cell is dead and shown as a dot ’.‘. The game consists of a series of rounds. During each round, each cell can either become alive, can die, or can stay the same. The “survival” of each cell in the next round depends on its neighbors:

• Any live cell with two or three live neighbors survives.
• Any dead cell with three live neighbors becomes a live cell.
• All other cells become or stay dead.

These rules are meant to cover some basic ideas about how life survives:

• underpopulation — cells with not enough live neighbors die
• overpopulation — cells with too many live neighbors die
• suitability — cells with just the right enough live neighbors live
• reproduction — dead cells can become alive

These rules are applied to the grid rom the previous round in order to populate the grid of the current round. So, to determine the state of a cell in the new grid, look at the corresponding cell in the old grid, count its neighbors, and apply the appropriate rule.

Using just these simple rules, and an initial starting condition, complex interactions can occur. For example, this pattern, called a block-laying switch engine, has infinite growth and leaves behind small squares.

The rules of this game require you to count all the neighbors surrounding a cell to see how many are alive. Here is an example of the neighbors you need to consider:

Normally, this game is played on an infinite grid. However, we will use a finite grid that wraps around in both the x and y directions. For example:

Grid files

We are going to run the game using files that store a starting grid. These files look like this:

. . . . . .
* * * . . .
. . . * * *
* . * . * .
* * . . * *
. . * * . .

Each . represents a dead cell and each * represents a live cell.

Loading a grid

Write the load_grid(filename) function. This function takes a filename and loads that file into a grid. It should return the new grid.

Computing the next grid

Write the next_grid(grid) function. This function takes a grid, follows Conway’s rules for one round of the game, and returns a new grid that is the result. The rules can be stated more succinctly as:

• Any live cell with two or three live neighbors survives.
• Any dead cell with three live neighbors becomes a live cell.
• All other cells become or stay dead.

This function should loop over all cells in the grid, count the number of alive neighbors each cell has, and then apply Conway’s rules.

You will definitely want to decompose this function into several other functions. You probably want a function that counts the number of alive neighbors for a given cell. You may also want a function that can copy one grid to another.

Hint: Complete this problem without worrying about wrapping. You’ll get most of the points. Then work on wrapping.

A note on rounds: The game is run in rounds. The grid you are passed is for the current round. You need to create a new grid and set alive/dead cells in this new grid that represents the next round. The function should return this new grid.

This makes a lot of sense if you think about it. If you tried to apply the rules to the current grid, then you would be making new cells come alive as you loop through it, causing all your calculations to be off!

For example

grid = [['.', '.', '.', '.', '.', '.', '.', '.', '.'],
        ['.', '.', '.', '.', '.', '.', '*', '.', '.'],
        ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
        ['.', '.', '*', '.', '.', '.', '.', '.', '.'],
        ['.', '*', '*', '*', '.', '.', '.', '.', '.'],
        ['.', '.', '*', '.', '.', '*', '.', '.', '.'],
        ['.', '.', '.', '.', '.', '.', '.', '*', '.'],
        ['.', '.', '.', '.', '.', '.', '*', '.', '.'],
        ['.', '.', '.', '.', '.', '.', '.', '.', '.']]

next_grid(grid)

should return:

[['.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '*', '*', '*', '.', '.', '.', '.', '.'],
 ['.', '*', '.', '*', '.', '.', '.', '.', '.'],
 ['.', '*', '*', '*', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '*', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
 ['.', '.', '.', '.', '.', '.', '.', '.', '.']]

Testing

Before you use the pytest files, try running:

python game_of_life.py

This will run a variety of simple tests and show you any errors.

Running Conway’s Game of Life

Congratulations, if you have written the functions correctly, everything else is done for you!

You can run a wide variety of games with the life.py script. A good place to start is to run the patterns from the Wikipedia page on Conway’s Game of Life. Compare your patterns to the ones on Wikipedia to be sure they work correctly:

python life.py --starter block
python life.py --starter beehive
python life.py --starter loaf
python life.py --starter boat
python life.py --starter tub
python life.py --starter blinker
python life.py --starter toad
python life.py --starter beacon
python life.py --starter glider

If some of these aren’t working, you will want to be sure that you are passing the tests for your next_grid() function.

Once you are satisfied with this, then try running the default setup:

python life.py This will create a 30 x 30 grid and randomly select 20% of the squares to be alive. The speed is set to make one transition every 1/2 of a second.

Finally, you can use the starters available in starters by using:

python life.py --starter [starter]

The available starters include:

stable formations

• block
• beehive
• loaf
• boat
• tub

oscillators

• blinker
• toad
• beacon

spaceships

• glider
• lightweight_spaceship

other

• diehard (dies after 130 rounds — a long time considering it starts with just 7 alive)
• engine (will go forever on an infinite canvas, leaving behind blocks)

For example:

python life.py --starter diehard

You can also control a variety of other aspects of the game with command line arguments. This is the full set of arguments:

--width: sets the width of the board (default 30)
--height: sets the height of the board (default 30)
--starter: sets the starter (default random)
--speed: number of ms between rounds (default 500)
--scale: scales the size of the squares (default 10)
--offset: moves the starter by some offset in both the x and y direction

You can use the following to get a reminder of the possible arguments:

python life.py -h

Here are some good combinations to try:

• good view of the glider: python life.py --starter glider --scale 6 --width 100 --height 100 --speed 3

• slow spaceship: python life.py --starter lightweight_spaceship --offset 10 --speed 100

• fast spaceship: python life.py --starter lightweight_spaceship --offset 10 --speed 3

• fast engine (because the board is small) but stops (because the board is finite): python life.py --starter engine --speed 10 --scale 10 --width 100 --height 80 --offset 20

• larger, slower engine (because the board is big and the scale is small), but goes for longer because there is more room — can really see its effect: python life.py --scale 4 --width 300 --height 100 --starter engine --speed 30

Grading