[Concepts in Programming] #Python #Jupyter #Learning

CIP-GeneratorsPy.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Concepts in programming | Generators\n",
    "\n",
    "Following this [Numberphile Video](https://www.youtube.com/watch?v=5jwV3zxXc8E)  \n",
    "we will look at diffrent models of 'lazy' operations that save on computation until they are nessesary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nats(n):\n",
    "    yield n\n",
    "    yield from nats(n+1)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function that utilize the 'yield' command are known as a geneartors The 'yield' command in python is similar to 'return'. Though, the functions operation is suspended until further calls. This allows you to iterate on the previous computation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object nats at 0x000001B04ADB2C10>"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nats(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Executing nats() directly will only return a generator object ref;\n",
    "Therefore, we need to assign the object to a variable.\n",
    "This way we can cleanly call it's properties/attributes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 4, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "l = []\n",
    "s = nats(2) # assign nats\n",
    "l.append(next(s)) # iterate\n",
    "l.append(next(s)) # iterate\n",
    "l.append(next(s)) # iterate\n",
    "l.append(next(s)) # iterate\n",
    "l.append(next(s)) # iterate\n",
    "print(l) # result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see by this example: We have only supplied the function nats(n)\n",
    "with a value of '2', but each concecutive call will yield n+1 of the previous.\n",
    "This highlights the power of generators."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sieve(s):\n",
    "    n = next(s)\n",
    "    yield n\n",
    "    yield from sieve(i for i in s if i%n!=0)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implimenting a sieve structure.  \n",
    "`s` determines the stream for the sieve.  \n",
    "`n` is the next in the sequence, which will be generated.  \n",
    "`i` is the iterative of the stream if the remainder of i divided by n is NOT zero.  \n",
    "This drops the values in the stream that are not cleanly divided.\n",
    "\n",
    "Term: Comprehension expression\n",
    "\n",
    "Using this lets compute a sequence of prime values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Computed Sequence:\n",
      "2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281\n",
      "Number of Prime Values: 339\n"
     ]
    }
   ],
   "source": [
    "l = []\n",
    "r = 339\n",
    "p = sieve(nats(2))\n",
    "for i in range(r):\n",
    "    l.append(next(p))\n",
    "\n",
    "print('Computed Sequence:')\n",
    "print(','.join(str(x) for x in l))\n",
    "print('Number of Prime Values: {}'.format(len(l)))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But, it seems we hit a wall past a certain range, this model do to a protective limitation.  \n",
    "The recursion limit is meant to prevent to avoid a stack overflow or getting stuck in an infinite recursive loop.  \n",
    "With my system set to `3000` we can only generate the first `339` prime values.  \n",
    "However, we can change this limit, just bare in mind not to push the system too hard.  \n",
    "\n",
    "Here is the command to display the current limit.  \n",
    "And to change it we will use the set varient of this command."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4000"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import sys\n",
    "sys.getrecursionlimit()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "New Recursion limit: 4000\n"
     ]
    }
   ],
   "source": [
    "import sys\n",
    "sys.setrecursionlimit(4000)\n",
    "print(\"New Recursion limit: {}\".format(sys.getrecursionlimit()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "Lets go over another application of generators\n",
    "# Sudoku Solver\n",
    "Utilizing backtracking"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define the sudoku grid\n",
    "grid = [[0,0,0,0,0,0,0,0,0],\n",
    "        [0,0,0,0,0,0,0,0,0],\n",
    "        [0,0,0,0,0,0,0,0,0],\n",
    "        [0,0,0,0,0,0,0,0,0],\n",
    "        [0,0,0,0,0,0,0,0,0],\n",
    "        [0,0,0,0,0,0,0,0,0],\n",
    "        [0,0,0,0,0,0,0,0,0],\n",
    "        [0,0,0,0,0,0,0,0,0],\n",
    "        [0,0,0,0,0,0,0,0,0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "def possible(y,x,n):\n",
    "    global grid\n",
    "    for i in range(0,9):\n",
    "        if grid[y][i] == n:\n",
    "            return False\n",
    "    for i in range(0,9):\n",
    "        if grid[i][x] == n:\n",
    "            return False\n",
    "    x0 = (x//3)*3\n",
    "    y0 = (y//3)*3\n",
    "    for i in range(0,3):\n",
    "        for j in range(0,3):\n",
    "            if grid[y0+i][x0+j] == n:\n",
    "                return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve():\n",
    "    global grid\n",
    "    for y in range(9):\n",
    "        for x in range(9):\n",
    "            if grid[y][x] == 0:\n",
    "                for n in range(1,10):\n",
    "                    if possible(y,x,n):\n",
    "                        grid[y][x] = n\n",
    "                        yield from solve()\n",
    "                        grid[y][x] = 0\n",
    "                return\n",
    "    yield np.matrix(grid)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "s = solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 2, 3, 4, 5, 6, 7, 8, 9],\n",
       "        [4, 5, 6, 7, 8, 9, 1, 2, 3],\n",
       "        [7, 8, 9, 1, 2, 3, 4, 5, 6],\n",
       "        [2, 1, 4, 3, 6, 5, 8, 9, 7],\n",
       "        [3, 6, 5, 8, 9, 7, 2, 1, 4],\n",
       "        [8, 9, 7, 2, 1, 4, 3, 6, 5],\n",
       "        [5, 3, 1, 6, 4, 2, 9, 7, 8],\n",
       "        [6, 4, 2, 9, 7, 8, 5, 3, 1],\n",
       "        [9, 7, 8, 5, 3, 1, 6, 4, 2]])"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Get the first solution\n",
    "next(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 2, 3, 4, 5, 6, 7, 8, 9],\n",
       "        [4, 5, 6, 7, 8, 9, 1, 2, 3],\n",
       "        [7, 8, 9, 1, 2, 3, 4, 5, 6],\n",
       "        [2, 1, 4, 3, 6, 5, 8, 9, 7],\n",
       "        [3, 6, 5, 8, 9, 7, 2, 1, 4],\n",
       "        [8, 9, 7, 2, 1, 4, 3, 6, 5],\n",
       "        [5, 3, 1, 6, 4, 2, 9, 7, 8],\n",
       "        [6, 4, 8, 9, 7, 1, 5, 3, 2],\n",
       "        [9, 7, 2, 5, 3, 8, 6, 4, 1]])"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# yield the second solution\n",
    "next(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 2, 3, 4, 5, 6, 7, 8, 9],\n",
       "        [4, 5, 6, 7, 8, 9, 1, 2, 3],\n",
       "        [7, 8, 9, 1, 2, 3, 4, 5, 6],\n",
       "        [2, 1, 4, 3, 6, 5, 8, 9, 7],\n",
       "        [3, 6, 5, 8, 9, 7, 2, 1, 4],\n",
       "        [8, 9, 7, 2, 1, 4, 3, 6, 5],\n",
       "        [5, 3, 1, 6, 4, 2, 9, 7, 8],\n",
       "        [6, 7, 2, 9, 3, 8, 5, 4, 1],\n",
       "        [9, 4, 8, 5, 7, 1, 6, 3, 2]])"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# yield the third solution\n",
    "next(s)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.3 64-bit ('base': conda)",
   "name": "python_defaultSpec_1598700260043"
  },
  "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.8.3-final"
  },
  "orig_nbformat": 2
 },
 "nbformat": 4,
 "nbformat_minor": 2
}