VP 28: Conway's Game of Life (25 pts + 55 extra)

What You Need

Any computer with Python 3. You can also use an online Python environment, such as https://colab.research.google.com

Life

This is a "cellular automaton" invented in 1970.

Rules

The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead (or populated and unpopulated, respectively). Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

Any live cell with fewer than two live neighbours dies, as if by underpopulation.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by overpopulation.
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

For example, consider the following initial state:

....... ....... ...#... ..A.#.. ..###.. ....... .......

The cell marked A started out dead.

It has three living neighbors, one to the top right, and two below it.

Therefore, it becomes alive, by rule 4, above.

Simulating a few cycles from this initial state produces the following configurations: Before any cycles:

Starting condition ....... ....... ...#... ....#.. ..###.. ....... ....... Total active: 5 After 1 cycles ....... ....... ....... ..#.#.. ...##.. ...#... ....... Total active: 5 After 2 cycles ....... ....... ....... ....#.. ..#.#.. ...##.. ....... Total active: 5 After 3 cycles ....... ....... ....... ...#... ....##. ...##.. ....... Total active: 5 After 4 cycles ....... ....... ....... ....#.. .....#. ...###. ....... Total active: 5

VP 28.1: 2-D Life (10 pts)
Use this initial state:
....... ....... ....#.. ....#.. ..###.. ....... .......
Starting with your given initial configuration, simulate four cycles.
How many cells are alive after the fourth cycle?
That's the flag.

3-D Life

Now extend the game to three dimensions.

The same rules apply, but now each cell has 26 neighbors, not 8.

Here's an example, showing 3 cycles from the same starting configuration.

The printouts omit empty lines.

The starting configuration only has live cells in a plane (z = 0), but as cycles proceed, the cells in other planes become alive.

Starting condition z=0 ............#............ .............#........... ...........###........... Total active: 5 After 1 cycles z=-1 ...........#............. .............#........... ............#............ z=0 ...........#.#........... ............##........... ............#............ z=1 ...........#............. .............#........... ............#............ Total active: 11 After 2 cycles z=-2 ............#............ z=-1 ............#............ ...........#..#.......... ..............#.......... ...........#............. z=0 ..........##............. ..........##............. ..........#.............. ..............#.......... ...........###........... z=1 ............#............ ...........#..#.......... ..............#.......... ...........#............. z=2 ............#............ Total active: 21 After 3 cycles z=-2 ...........##............ ...........###........... z=-1 ...........#............. ............#............ .........#............... ..............##......... ..........#...#.......... ...........#.#........... ............#............ z=0 ............#............ .........#............... ..............##......... ..........##.#........... ............#............ z=1 ...........#............. ............#............ .........#............... ..............##......... ..........#...#.......... ...........#.#........... ............#............ z=2 ...........##............ ...........###........... Total active: 38

After six cycles, there are 112 living cubes.

VP 28.2: 3-D Life: Simple Case (15 pts)
Use this input data:
### ###
Starting with your given initial configuration, simulate six cycles.
How many cubes are alive after the sixth cycle?

VP 28.3: 3-D Life: Complex Case (10 pts extra)
Use this input data:
.#..#### .#.#...# #..#.#.# ###..##. ..##...# ..##.### #.....#. ..##..##
Starting with your given initial configuration, simulate six cycles.
How many cubes are alive after the sixth cycle?

Fourth Dimension

Extend the problem to four dimensions.

Each hypercube now has 80 neighbors.

Here are the results from the same test case, showing the number of living cubes and the time required for each cycle.

Notice that the time increases linearly with the number of living cubes, becoming quite long by the eighth cycle.

After 1 cycles Total active: 29 Time: 5.519 After 2 cycles Total active: 60 Time: 11.209 After 3 cycles Total active: 320 Time: 18.514 After 4 cycles Total active: 188 Time: 79.801 After 5 cycles Total active: 1056 Time: 51.564 After 6 cycles Total active: 848 Time: 253.532 After 7 cycles Total active: 3384 Time: 212.24 After 8 cycles Total active: 2720 Time: 794.799

Here are the details for the first two cycles:

Starting condition z=0, w=0 0 -1 .........#......... 0 ..........#........ 1 ........###........ Total active: 5 After 1 cycles z=-1, w=-1 0 0 ........#.......... 1 ..........#........ 2 .........#......... z=0, w=-1 0 0 ........#.......... 1 ..........#........ 2 .........#......... z=1, w=-1 0 0 ........#.......... 1 ..........#........ 2 .........#......... z=-1, w=0 0 0 ........#.......... 1 ..........#........ 2 .........#......... z=0, w=0 0 0 ........#.#........ 1 .........##........ 2 .........#......... z=1, w=0 0 0 ........#.......... 1 ..........#........ 2 .........#......... z=-1, w=1 0 0 ........#.......... 1 ..........#........ 2 .........#......... z=0, w=1 0 0 ........#.......... 1 ..........#........ 2 .........#......... z=1, w=1 0 0 ........#.......... 1 ..........#........ 2 .........#......... Total active: 29 After 2 cycles z=-2, w=-2 0 1 .........#......... z=0, w=-2 0 -1 .......###......... 0 .......##.##....... 1 .......#...#....... 2 ........#..#....... 3 ........###........ z=2, w=-2 0 1 .........#......... z=-2, w=0 0 -1 .......###......... 0 .......##.##....... 1 .......#...#....... 2 ........#..#....... 3 ........###........ z=2, w=0 0 -1 .......###......... 0 .......##.##....... 1 .......#...#....... 2 ........#..#....... 3 ........###........ z=-2, w=2 0 1 .........#......... z=0, w=2 0 -1 .......###......... 0 .......##.##....... 1 .......#...#....... 2 ........#..#....... 3 ........###........ z=2, w=2 0 1 .........#......... Total active: 60

VP 28.4: 4-D Life: Complex Case (15 pts extra)
Use this input data (the same as in flag 28.3):
.#..#### .#.#...# #..#.#.# ###..##. ..##...# ..##.### #.....#. ..##..##
Starting with your given initial configuration, simulate four cycles.
How many hypercubes are alive after the fourth cycle?
The flag is covered by a green rectangle in the image below.

VP 28.5: 4-D Life: Complex Case (30 pts extra)
Improve your 4-D life program to use a binary search.
I recommend hashing each value with MD5 to create a single searchable value for each living hypercube.
Use this starting condition:
....... ....... ...#... ....#.. ..###.. ....... .......
Starting with your given initial configuration, simulate ten cycles.
How many hypercubes are alive after the tenth cycle?
The flag is covered by a green rectangle in the image below.

Source

Adapted from the Advent of Code.

Posted 9-15-24
Video added 10-9-24