Conway's Game of Life.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In 1970, British mathematician John Horton Conway developed a cellular automaton known as [The Game of Life](http://en.wikipedia.org/wiki/Conway's_Game_of_Life).  Dyalog's John Scholes put together a video exploration of an [APL implementation of the Game of Life](http://www.youtube.com/watch?v=a9xAKttWgP4&amp;fmt=18).\n",
    "\n",
    "This tutorial steps through much the same path that John took in his presentation allowing you to investigate each individual step.\n",
    "\n",
    "First we'll build the initial board which is a 3 by 3 bit pattern centered in a 5 by 7 board."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 2 3 4 5 6 7 8 9\n",
       "</span>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍳ 9 ⍝ generate the first 9 integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Many APL functions have mnemonic or visual clues to their meaning.  In this case monadic (*monadic* means the function only has one argument) iota `⍳`, the Greek letter for \"i\", implements  the **i**ndex generator function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 2 3\n",
       "4 5 6\n",
       "7 8 9\n",
       "</span>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "3 3 ⍴ ⍳ 9"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dyadic (*dyadic* means the function has two arguments) rho `⍴` implements the **r**eshape function.  As APL executes from right to left, `3 3 ⍴ ⍳ 9` reshapes `⍳ 9` into a 3 by 3 matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 1 1\n",
       "1 1 0\n",
       "0 1 0\n",
       "</span>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(3 3 ⍴ ⍳ 9) ∊ 2 3 4 5 8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dyadic epsilon `∊` implements the \"**e**lement of\" function.  This generates the starting bit pattern.  Now we need to position it within our board.  But first let's save the pattern in a variable named `r`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "r ← (3 3 ⍴ ⍳ 9) ∊ 2 3 4 5 8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can display `r` merely by entering its name."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 1 1\n",
       "1 1 0\n",
       "0 1 0\n",
       "</span>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have our starting pattern, we'll center it in a 5 by 7 board.  The first step is to use the take function `↑` to pad out the pattern to our desired size."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 1 1 0 0 0 0\n",
       "1 1 0 0 0 0 0\n",
       "0 1 0 0 0 0 0\n",
       "0 0 0 0 0 0 0\n",
       "0 0 0 0 0 0 0\n",
       "</span>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5 7 ↑ r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next step is to column-center the pattern..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 0 0 1 1 0 0\n",
       "0 0 1 1 0 0 0\n",
       "0 0 0 1 0 0 0\n",
       "0 0 0 0 0 0 0\n",
       "0 0 0 0 0 0 0\n",
       "</span>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "¯2 ⌽ 5 7 ↑ r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The high minus `¯` is used to denote a negative number.  The symbol `⌽` rotates along the last axis, which is the columns in an array of rank (*rank* is just another term for the number of dimensions an array has — a table is a rank 2 array) 2 greater.\n",
    "\n",
    "Next we row-center the pattern using the `⊖` function which rotates along the first axis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 0 0 0 0 0 0\n",
       "0 0 0 1 1 0 0\n",
       "0 0 1 1 0 0 0\n",
       "0 0 0 1 0 0 0\n",
       "0 0 0 0 0 0 0\n",
       "</span>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "¯1 ⊖ ¯2 ⌽ 5 7 ↑ r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now assign the board to the variable `R`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "R ← ¯1 ⊖ ¯2 ⌽ 5 7 ↑ r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The rules for the Game of Life dictate which cells live based on their number of live neighbors.  So, our next job is to count the neighbors and we'll do this by shifting the board by 1 unit in each direction and summing the result..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────────────┬─────────────┬─────────────┐\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "│0 0 1 1 0 0 0│0 0 0 1 1 0 0│0 0 0 0 1 1 0│\n",
       "│0 1 1 0 0 0 0│0 0 1 1 0 0 0│0 0 0 1 1 0 0│\n",
       "│0 0 1 0 0 0 0│0 0 0 1 0 0 0│0 0 0 0 1 0 0│\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "└─────────────┴─────────────┴─────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 0 ¯1 ⌽¨ ⊂R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, the enclose `⊂` function takes any array and turns it into a rank 0 array, also known as a scalar.  Many APL functions support \"scalar extension\" which distributes the scalar and applies the function to each of the items in the other argument.  In this case, we're using <span class=\"APL\">⌽</span> again to perform column shifts.  The \"each\" operator (an *operator* takes function(s) as arguments and returns a new function) `¨` applies `⌽` between each element of the left argument `1 0 ¯1` and `⊂R`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────────────┬─────────────┬─────────────┐\n",
       "│0 0 1 1 0 0 0│0 0 0 1 1 0 0│0 0 0 0 1 1 0│\n",
       "│0 1 1 0 0 0 0│0 0 1 1 0 0 0│0 0 0 1 1 0 0│\n",
       "│0 0 1 0 0 0 0│0 0 0 1 0 0 0│0 0 0 0 1 0 0│\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "├─────────────┼─────────────┼─────────────┤\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "│0 0 1 1 0 0 0│0 0 0 1 1 0 0│0 0 0 0 1 1 0│\n",
       "│0 1 1 0 0 0 0│0 0 1 1 0 0 0│0 0 0 1 1 0 0│\n",
       "│0 0 1 0 0 0 0│0 0 0 1 0 0 0│0 0 0 0 1 0 0│\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "├─────────────┼─────────────┼─────────────┤\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "│0 0 1 1 0 0 0│0 0 0 1 1 0 0│0 0 0 0 1 1 0│\n",
       "│0 1 1 0 0 0 0│0 0 1 1 0 0 0│0 0 0 1 1 0 0│\n",
       "│0 0 1 0 0 0 0│0 0 0 1 0 0 0│0 0 0 0 1 0 0│\n",
       "└─────────────┴─────────────┴─────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 0 ¯1 ∘.⊖ 1 0 ¯1 ⌽¨ ⊂R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we've used the outer product operator `∘.` which applies its function, in this case `⊖`, between all combinations of the left and right arguments.  So, we wind up with a 3 by 3 array of with our original board in the center and all of the \"1-rotations\" surrounding.\n",
    "\n",
    "We can now add up the neighbors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────────────┬─────────────┬─────────────┐\n",
       "│0 0 1 2 2 1 0│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "│0 1 2 2 1 0 0│0 0 1 2 2 1 0│0 0 0 0 0 0 0│\n",
       "│0 0 1 1 1 0 0│0 1 2 2 1 0 0│0 0 1 2 2 1 0│\n",
       "│0 0 0 0 0 0 0│0 0 1 1 1 0 0│0 1 2 2 1 0 0│\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│0 0 1 1 1 0 0│\n",
       "└─────────────┴─────────────┴─────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/ 1 0 ¯1 ∘.⊖ 1 0 ¯1 ⌽¨ ⊂R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`+/` sums along the last axis. `/` is another operator, called reduce, and applies its function along the last axis of its data.  Notice that `/` \"reduces\" the rank of an array, in this case giving a result of a vector from a 3 by 3 matrix.\n",
    "\n",
    "Next we sum the vector..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────────────┐\n",
       "│0 0 1 2 2 1 0│\n",
       "│0 1 3 4 3 1 0│\n",
       "│0 1 4 5 4 1 0│\n",
       "│0 1 3 3 2 0 0│\n",
       "│0 0 1 1 1 0 0│\n",
       "└─────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/ +/ 1 0 ¯1 ∘.⊖ 1 0 ¯1 ⌽¨ ⊂R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And this gives us a neighbor count of our original matrix.\n",
    "\n",
    "Now, a cell is \"live\" (has a 1) in the next generation if either its neighbor count is 3, or its neighbor count is 4 **and** the cell is alive in the current generation.  So, we can find where the neighbor counts are 3 and 4..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────────────┬─────────────┐\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "│0 0 1 0 1 0 0│0 0 0 1 0 0 0│\n",
       "│0 0 0 0 0 0 0│0 0 1 0 1 0 0│\n",
       "│0 0 1 1 0 0 0│0 0 0 0 0 0 0│\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "└─────────────┴─────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "3 4 = +/ +/ 1 0 ¯1 ∘.⊖ 1 0 ¯1 ⌽¨ ⊂R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And then take any 3, and 4's where there's a 1 in the current generation..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────────────┬─────────────┐\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "│0 0 1 0 1 0 0│0 0 0 1 0 0 0│\n",
       "│0 0 0 0 0 0 0│0 0 1 0 0 0 0│\n",
       "│0 0 1 1 0 0 0│0 0 0 0 0 0 0│\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "└─────────────┴─────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 R ∧ 3 4 = +/ +/ 1 0 ¯1 ∘.⊖ 1 0 ¯1 ⌽¨ ⊂R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since both of these matrices contribute to the next generation, we can use reduce again, this time using the `∨.∧` inner product and disclosing the result using `⊃` to make it a simple matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 0 0 0 0 0 0\n",
       "0 0 1 1 1 0 0\n",
       "0 0 1 0 0 0 0\n",
       "0 0 1 1 0 0 0\n",
       "0 0 0 0 0 0 0\n",
       "</span>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃1 R ∨.∧ 3 4 = +/ +/ 1 0 ¯1 ∘.⊖ 1 0 ¯1 ⌽¨ ⊂R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we've built an expression which produces the next generation for any boolean matrix `R`.  Let's turn this into a function by enclosing it in curly braces `{` `}` and using the formal parameter `⍵<` in place of `R`.  We'll call this function `life`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────────────┬─────────────┬─────────────┐\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│0 0 0 1 0 0 0│\n",
       "│0 0 0 1 1 0 0│0 0 1 1 1 0 0│0 0 1 1 0 0 0│\n",
       "│0 0 1 1 0 0 0│0 0 1 0 0 0 0│0 1 0 0 1 0 0│\n",
       "│0 0 0 1 0 0 0│0 0 1 1 0 0 0│0 0 1 1 0 0 0│\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│0 0 0 0 0 0 0│\n",
       "└─────────────┴─────────────┴─────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "life←{⊃1 ⍵ ∨.∧ 3 4 = +/ +/ 1 0 ¯1 ∘.⊖ 1 0 ¯1 ⌽¨ ⊂⍵}\n",
    "R (life R) (life life R)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Displays the first 3 generations for `R`.\n",
    "\n",
    "Now, we can generalise that by writing a function `gen` which uses the power operator `⍣` to apply `life` to the power of the left argument to the right argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────────────┬─────────────┬─────────────┬─────────────┐\n",
       "│0 0 0 0 0 0 0│0 0 0 1 0 0 0│0 0 1 1 0 0 0│0 1 0 0 0 0 0│\n",
       "│0 0 1 1 1 0 0│0 0 1 1 0 0 0│0 0 1 1 1 0 0│0 1 0 0 1 0 0│\n",
       "│0 0 1 0 0 0 0│0 1 0 0 1 0 0│0 1 0 0 1 0 0│0 1 0 0 1 0 0│\n",
       "│0 0 1 1 0 0 0│0 0 1 1 0 0 0│0 0 1 1 0 0 0│0 1 0 0 1 0 0│\n",
       "│0 0 0 0 0 0 0│0 0 0 0 0 0 0│0 0 1 1 0 0 0│0 1 0 0 1 0 0│\n",
       "└─────────────┴─────────────┴─────────────┴─────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gen←{(life⍣⍵)⍺}\n",
    "R∘gen¨ ⍳4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Displays the next 4 generations for R by binding `R` with `gen` using `∘` and applying it with each of `⍳4`."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Dyalog APL",
   "language": "apl",
   "name": "dyalog-kernel"
  },
  "language_info": {
   "file_extension": ".apl",
   "mimetype": "text/apl",
   "name": "APL"
  },
  "tryapl": {
   "category": "Interesting Explorations",
   "description": "Implementing Conway's Game of Life",
   "name": "Conway's Game of Life"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}