02_workshop.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Game of Life\n",
    "\n",
    "Code examples from [Think Complexity, 2nd edition](https://thinkcomplex.com).\n",
    "\n",
    "Copyright 2019 Allen Downey, [MIT License](http://opensource.org/licenses/MIT)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following class implements the Game of Life."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.signal import correlate2d\n",
    "from time import sleep\n",
    "from IPython.display import clear_output\n",
    "\n",
    "class Life:\n",
    "    \"\"\"Implementation of Conway's Game of Life.\"\"\"\n",
    "    kernel = np.array([[1, 1, 1],\n",
    "                       [1,10, 1],\n",
    "                       [1, 1, 1]])\n",
    "\n",
    "    table = np.zeros(20, dtype=np.uint8)\n",
    "    table[[3, 12, 13]] = 1\n",
    "\n",
    "    def __init__(self, n, m=None):\n",
    "        \"\"\"Initializes the attributes.\n",
    "\n",
    "        n: number of rows\n",
    "        m: number of columns\n",
    "        \"\"\"\n",
    "        m = n if m is None else m\n",
    "        self.grid = np.zeros((n, m), np.uint8)\n",
    "\n",
    "    def add_cells(self, row, col, *strings):\n",
    "        \"\"\"Adds cells at the given location.\n",
    "\n",
    "        row: top row index\n",
    "        col: left col index\n",
    "        strings: list of strings of 0s and 1s\n",
    "        \"\"\"\n",
    "        for i, s in enumerate(strings):\n",
    "            self.grid[row+i, col:col+len(s)] = np.array([int(b) for b in s])\n",
    "            \n",
    "    def step(self):\n",
    "        \"\"\"Executes one time step.\"\"\"\n",
    "        c = correlate2d(self.grid, self.kernel, mode='same')\n",
    "        self.grid = self.table[c]\n",
    "        \n",
    "    def draw(self):\n",
    "        \"\"\"Draws the cells.\"\"\"\n",
    "        \n",
    "        a = self.grid\n",
    "\n",
    "        n, m = a.shape\n",
    "        plt.axis([0, m, 0, n])\n",
    "        plt.xticks([])\n",
    "        plt.yticks([])\n",
    "\n",
    "        cmap = plt.get_cmap('Greens')\n",
    "        options = dict(interpolation='nearest', alpha=0.8,\n",
    "                   vmin=0, vmax=1, origin='upper')\n",
    "        options['extent'] = [0, m, 0, n]\n",
    "    \n",
    "        self.im = plt.imshow(a, cmap, **options)\n",
    "\n",
    "    def animate(self, frames, interval=None):\n",
    "        \"\"\"Animate the automaton.\n",
    "\n",
    "        frames: number of frames to draw\n",
    "        interval: time between frames in seconds\n",
    "        \"\"\"\n",
    "        plt.figure()\n",
    "        try:\n",
    "            for i in range(frames-1):\n",
    "                self.draw()\n",
    "                plt.show()\n",
    "                if interval:\n",
    "                    sleep(interval)\n",
    "                self.step()\n",
    "                clear_output(wait=True)\n",
    "            self.draw()\n",
    "            plt.show()\n",
    "        except KeyboardInterrupt:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following function creates a `Life` object and sets the initial condition using strings of `0` and `1` characters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_life(n, m, row, col, *strings):\n",
    "    \"\"\"Makes a Life object.\n",
    "    \n",
    "    n, m: rows and columns of the Life array\n",
    "    row, col: upper left coordinate of the cells to be added\n",
    "    strings: list of strings of '0' and '1'\n",
    "    \"\"\"\n",
    "    life = Life(n, m)\n",
    "    life.add_cells(row, col, *strings)\n",
    "    return life"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Game of Life entities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Under GoL rules, some configurations are stable, meaning that they don't change from one time step to the next.  These patterns are sometimes called \"still lifes\".\n",
    "\n",
    "One example is a \"beehive\", which is the following pattern of 6 cells."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# beehive\n",
    "life = make_life(3, 4, 0, 0, '0110', '1001', '0110')\n",
    "life.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's what it looks like after one step:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "life.step()\n",
    "life.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some patterns, called \"oscillators\", cycle through a series of configurations that returns to the initial configuration and repeats.\n",
    "\n",
    "A \"toad\" is an oscillator with period 2.  Here's are its two configurations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# toad\n",
    "plt.subplot(1, 2, 1)\n",
    "life = make_life(4, 4, 1, 0, '0111', '1110')\n",
    "life.draw()\n",
    "\n",
    "plt.subplot(1, 2, 2)\n",
    "life.step()\n",
    "life.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's what it looks like as an animation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "life.step()\n",
    "life.animate(frames=4, interval=0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some patterns repeat, but after each cycle, they are offset in space.  They are called \"spaceships\".\n",
    "\n",
    "A \"glider\" is a spaceship that translates one unit down and to the right with period 4. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# glider\n",
    "glider = ['010', '001', '111']\n",
    "life = make_life(4, 4, 0, 0, *glider)\n",
    "\n",
    "plt.figure(figsize=(12,5))\n",
    "\n",
    "for i in range(1, 6):\n",
    "    plt.subplot(1, 5, i)\n",
    "    life.draw()\n",
    "    life.step()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's an animation showing glider movement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "life = make_life(10, 10, 0, 0, '010', '001', '111')\n",
    "life.animate(frames=32, interval=0.2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** If you start GoL from a random configuration, it usually runs chaotically for a while and then settles into stable patterns that include blinkers, blocks, and beehives, ships, boats, and loaves.\n",
    "\n",
    "For a list of common \"natually\" occurring patterns, see Achim Flammenkamp, \"[Most seen natural occurring ash objects in Game of Life](http://wwwhomes.uni-bielefeld.de/achim/freq_top_life.html)\",\n",
    "\n",
    "Start GoL in a random state and run it until it stabilizes (try 1000 steps).\n",
    "What stable patterns can you identify?\n",
    "\n",
    "Hint: use `numpy.random.randint`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Methuselas\n",
    "\n",
    "Most initial conditions run for a short time and reach a steady state.  But some initial conditional run for a surprisingly long time; they are called [Methuselahs](https://en.wikipedia.org/wiki/Methuselah_(cellular_automaton))\n",
    "\n",
    "One of the simplest examples is the \"r-pentomino\", which starts with only five live cells, but it runs for 1103 steps before stabilizing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# r pentomino\n",
    "rpent = ['011', '110', '010']\n",
    "life = make_life(3, 3, 0, 0, *rpent)\n",
    "life.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are the start and finish configurations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# r pentomino\n",
    "rpent = ['011', '110', '010']\n",
    "\n",
    "plt.subplot(1, 2, 1)\n",
    "life = make_life(120, 120, 50, 45, *rpent)\n",
    "life.draw()\n",
    "\n",
    "for i in range(1103):\n",
    "    life.step()\n",
    "\n",
    "plt.subplot(1, 2, 2)\n",
    "life.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here's the animation that shows the steps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "life = make_life(120, 120, 50, 45, *rpent)\n",
    "life.animate(frames=1200)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rabbits\n",
    "\n",
    "Another example is [rabbits](https://web.archive.org/web/20081221152607/http://www.argentum.freeserve.co.uk/lex_r.htm#rabbits), which starts with only nine cells and runs 17331 steps before reaching steady state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "from os.path import basename, exists\n",
    "\n",
    "def download(url):\n",
    "    filename = basename(url)\n",
    "    if not exists(filename):\n",
    "        from urllib.request import urlretrieve\n",
    "        local, _ = urlretrieve(url, filename)\n",
    "        print('Downloaded ' + local)\n",
    "        \n",
    "download('https://github.com/AllenDowney/ComplexityScience/raw/master/Cell2D.py')\n",
    "download('https://github.com/AllenDowney/ComplexityScience/raw/master/Life.py')\n",
    "download('https://github.com/AllenDowney/ComplexityScience/raw/master/LifeRabbits.py')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To run my implementation of rabbits, open a terminal and run\n",
    "\n",
    "```\n",
    "python LifeRabbits.py\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conway's conjecture\n",
    "\n",
    "Patterns like these prompted Conway to conjecture, as a challenge, that there are no initial conditions where the number of live cells grows unboundedly.\n",
    "\n",
    "Gosper's glider gun was the first entity to be discovered that produces an unbounded number of live cells, which refutes Conway's conjecture."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "glider_gun = [\n",
    "    '000000000000000000000000100000000000',\n",
    "    '000000000000000000000010100000000000',\n",
    "    '000000000000110000001100000000000011',\n",
    "    '000000000001000100001100000000000011',\n",
    "    '110000000010000010001100000000000000',\n",
    "    '110000000010001011000010100000000000',\n",
    "    '000000000010000010000000100000000000',\n",
    "    '000000000001000100000000000000000000',\n",
    "    '000000000000110000000000000000000000'\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's the initial configuration:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "life = make_life(11, 38, 1, 1, *glider_gun)\n",
    "life.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here's what it looks like running:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "life = make_life(50, 50, 2, 2, *glider_gun)\n",
    "life.animate(frames=500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** In this animation, you might notice that the boundary interferes with the escaping gliders, but it doesn't affect the behavior of the gun.\n",
    "\n",
    "For fun, change `step` so it passes the keywords `boundary='wrap'` to `correlate2d`, and see what happens.\n",
    "\n",
    "Don't forget to remove it before you proceed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Puffer train\n",
    "\n",
    "Another way to \"refute\" Conway's conjecture is a [puffer train](https://en.wikipedia.org/wiki/Puffer_train)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "download('https://github.com/AllenDowney/ComplexityScience/raw/master/LifePuffer.py')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To see a puffer train run, open a terminal and run\n",
    "\n",
    "```\n",
    "python LifePuffer.py\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementing Game of Life\n",
    "\n",
    "This section explains how the implementaion we've been using works.\n",
    "\n",
    "As an example, I'll start with an array of random cells:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = np.random.randint(2, size=(10, 10), dtype=np.uint8)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following is a straightforward translation of the GoL rules using `for` loops and array slicing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = np.zeros_like(a)\n",
    "rows, cols = a.shape\n",
    "for i in range(1, rows-1):\n",
    "    for j in range(1, cols-1):\n",
    "        state = a[i, j]\n",
    "        neighbors = a[i-1:i+2, j-1:j+2]\n",
    "        k = np.sum(neighbors) - state\n",
    "        if state:\n",
    "            if k==2 or k==3:\n",
    "                b[i, j] = 1\n",
    "        else:\n",
    "            if k == 3:\n",
    "                b[i, j] = 1\n",
    "\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a smaller, faster version using cross correlation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.signal import correlate2d\n",
    "\n",
    "kernel = np.array([[1, 1, 1],\n",
    "                   [1, 0, 1],\n",
    "                   [1, 1, 1]])\n",
    "\n",
    "c = correlate2d(a, kernel, mode='same')\n",
    "b = (c==3) | (c==2) & a\n",
    "b = b.astype(np.uint8)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using a kernel that gives a weight of 10 to the center cell, we can simplify the logic a little."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "kernel = np.array([[1, 1, 1],\n",
    "                   [1,10, 1],\n",
    "                   [1, 1, 1]])\n",
    "\n",
    "c = correlate2d(a, kernel, mode='same')\n",
    "b = (c==3) | (c==12) | (c==13)\n",
    "b = b.astype(np.uint8)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "More importantly, the second version of the kernel makes it possible to use a look up table to get the next state, which is faster and even more concise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "table = np.zeros(20, dtype=np.uint8)\n",
    "table[[3, 12, 13]] = 1\n",
    "c = correlate2d(a, kernel, mode='same')\n",
    "b = table[c]\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Highlife\n",
    "\n",
    "One variation of GoL, called \"Highlife\", has the\n",
    "same rules as GoL, plus one additional rule: a dead cell with 6\n",
    "neighbors comes to life.\n",
    "\n",
    "You can try out different rules by inheriting from `Life` and changing the lookup table.\n",
    "\n",
    "**Exercise:** Modify the table below to add the new rule."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Starter code\n",
    "\n",
    "class MyLife(Life):\n",
    "    \"\"\"Implementation of Life.\"\"\"\n",
    "\n",
    "    table = np.zeros(20, dtype=np.uint8)\n",
    "    table[[3, 12, 13]] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One of the more interesting patterns in Highlife is the replicator, which has the following initial configuration.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "replicator = [\n",
    "    '00111',\n",
    "    '01001',\n",
    "    '10001',\n",
    "    '10010',\n",
    "    '11100'\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make a `MyLife` object with `n=100` and use `add_cells` to put a replicator near the middle.\n",
    "\n",
    "Make an animation with about 200 frames and see how it behaves."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Try out some other rules and see what kind of behavior you get."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}