09-py-Iterators-recursion-linkedlists.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "lst = [x * 2 for x in range(21)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 "
     ]
    }
   ],
   "source": [
    "for n in lst:\n",
    "    print(n, end=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "dct = { x: 2*x for x in range(11)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 0, 1: 2, 2: 4, 3: 6, 4: 8, 5: 10, 6: 12, 7: 14, 8: 16, 9: 18, 10: 20}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 --> 0\n",
      "1 --> 2\n",
      "2 --> 4\n",
      "3 --> 6\n",
      "4 --> 8\n",
      "5 --> 10\n",
      "6 --> 12\n",
      "7 --> 14\n",
      "8 --> 16\n",
      "9 --> 18\n",
      "10 --> 20\n"
     ]
    }
   ],
   "source": [
    "for key, value in dct.items():\n",
    "    print(key, \"-->\", value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0  2  4  6  8  10  12  14  16  18  20  22  24  26  28  30  32  34  36  38  40  "
     ]
    }
   ],
   "source": [
    "it = iter(lst)\n",
    "while True:\n",
    "    try:\n",
    "        n = next(it)\n",
    "        print(n, end=\"  \")\n",
    "    except StopIteration:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyIterator:\n",
    "    def __init__(self, max):\n",
    "        self.max = max\n",
    "        self.value = 0\n",
    "\n",
    "    def __next__(self):\n",
    "        if self.value < self.max:\n",
    "            res = self.value\n",
    "            self.value += 1\n",
    "            return res\n",
    "        else:\n",
    "            raise StopIteration()\n",
    "    \n",
    "    def __iter__(self):\n",
    "        return self"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.MyIterator at 0x108333fa0>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myIt = MyIterator(5)\n",
    "myIt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(myIt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  "
     ]
    }
   ],
   "source": [
    "myIt = MyIterator(20)\n",
    "while True:\n",
    "    try:\n",
    "        n = next(myIt)\n",
    "        print(n, end=\"  \")\n",
    "    except StopIteration:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  "
     ]
    }
   ],
   "source": [
    "myIt = MyIterator(20)\n",
    "for i in myIt:\n",
    "    print(i, end=\"  \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a  b  c  d  e  f  g  a  b  c  d  e  f  g  a  b  c  d  e  f  g  a  b  c  d  e  f  g  a  b  c  d  e  f  g  "
     ]
    }
   ],
   "source": [
    "lst1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g']\n",
    "\n",
    "for _ in range(5):\n",
    "    for i in lst1:\n",
    "        print(i, end=\"  \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursion\n",
    "Recursion is all about breaking a big problem into smaller occurrences of that same problem.\n",
    "\n",
    "Recursion:\n",
    "- Solving a problem using recursion depends on solving smaller occurrences of the same problem.\n",
    "\n",
    "Recursive programming: \n",
    "- Writing functions that call themselves to solve problems recursively.\n",
    "- An equally powerful substitute for iteration (loops) and well-suited to solving certain types of problems\n",
    "\n",
    "Why learn recursion?\n",
    "- \"Cultural experience\" – think differently about problems\n",
    "- Solves some problems more naturally than iteration\n",
    "- Can lead to elegant, simplistic, short code (when used well)\n",
    "- Many programming languages (\"functional\" languages such as Scheme, ML, and Haskell) use recursion exclusively (no loops)\n",
    "\n",
    "Recursion and cases:\n",
    "- Every recursive algorithm involves at least 2 cases:\n",
    "    - base case: A simple occurrence that can be answered directly.\n",
    "    - recursive case: A more complex occurrence of the problem that cannot be directly answered, but can instead be described in terms of smaller occurrences of the same problem.\n",
    "\n",
    "- Some recursive algorithms have more than one base or recursive case, but all have at least one of each.\n",
    "- A crucial part of recursive programming is identifying these cases."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*****\n"
     ]
    }
   ],
   "source": [
    "def printStars(n):\n",
    "    for i in range(n):\n",
    "        print(\"*\", end='')\n",
    "    print()\n",
    "    \n",
    "printStars(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def printStars(n):\n",
    "    if n == 1:\n",
    "        print('*', end='')\n",
    "    elif n == 2:\n",
    "        print('**', end='')\n",
    "    else: ...\n",
    "        \n",
    "printStars(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ArrayList:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "        \n",
    "    def append(self, val):\n",
    "        self.data.append(None)\n",
    "        self.data[len(self.data)-1] = val\n",
    "        \n",
    "    def __iter__(self):\n",
    "        for i in range(len(self.data)):\n",
    "            yield self.data[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "***\n"
     ]
    }
   ],
   "source": [
    "def printStars(n):\n",
    "    if n == 1:\n",
    "        print('*')\n",
    "    elif n == 2:\n",
    "        print('*', end='')\n",
    "        printStars(1)\n",
    "    elif n == 3:\n",
    "        print('*', end='')\n",
    "        printStars(2)\n",
    "    else: ...\n",
    "        \n",
    "printStars(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "**********\n"
     ]
    }
   ],
   "source": [
    "def printStars(n):\n",
    "    if n == 0:\n",
    "        print()\n",
    "    else:\n",
    "        print('*', end='')\n",
    "        printStars(n-1)\n",
    "        \n",
    "printStars(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "12 // 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "112"
     ]
    }
   ],
   "source": [
    "# n >=0\n",
    "\n",
    "def toBinary(n):\n",
    "    if n < 5:\n",
    "        print(n, end='')\n",
    "    else:\n",
    "        toBinary(n//5)\n",
    "        toBinary(n % 5)\n",
    "        \n",
    "toBinary(32)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = ArrayList()\n",
    "for x in range(10):\n",
    "    l.append(2**x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1  2  4  8  16  32  64  128  256  512  "
     ]
    }
   ],
   "source": [
    "for x in l:\n",
    "    print(x, end='  ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation of Linked Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ArrayList(ArrayList):\n",
    "    def __repr__(self):\n",
    "        return '[' + ', '.join(repr(x) for x in self) + ']'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedList:\n",
    "    class Node:\n",
    "        def __init__(self, val, next=None):\n",
    "            self.val = val\n",
    "            self.next = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.size = 0\n",
    "    \n",
    "    def prepend(self, value): # O(1)\n",
    "        self.head = LinkedList.Node(value, self.head)\n",
    "        self.size += 1\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "        \n",
    "    def __iter__(self):\n",
    "        n = self.head\n",
    "        while n:\n",
    "            yield n.val\n",
    "            n = n.next\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return '[' + ', '.join(repr(x) for x in self) + ']'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.prepend(i)\n",
    "lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementing `append`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedList (LinkedList):\n",
    "    def __init__(self):\n",
    "        self.head = self.tail = None\n",
    "        self.size = 0\n",
    "        \n",
    "    def prepend(self, value): # O(1)\n",
    "        self.head = LinkedList.Node(value, next=self.head)\n",
    "\n",
    "        if self.tail is None:\n",
    "            self.tail = self.head\n",
    "        \n",
    "        self.size += 1\n",
    "        \n",
    "    def append(self, value): # O(1)\n",
    "        if not self.tail:\n",
    "            self.prepend(value)\n",
    "        else:\n",
    "            self.tail.next = self.tail = LinkedList.Node(value)\n",
    "            self.size += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.append(i)\n",
    "lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementing deletion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedList (LinkedList):\n",
    "    def del_head(self): # O(1)\n",
    "        assert len(self) > 0\n",
    "        self.head = self.head.next\n",
    "        self.size -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.append(i)\n",
    "lst.del_head()\n",
    "lst.del_head()\n",
    "lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Deleting the tail\n",
    "class LinkedList (LinkedList):\n",
    "    def del_tail(self): # O(N)\n",
    "        assert len(self) > 0\n",
    "        if self.head.next is None:\n",
    "            # there is only one node\n",
    "            self.head = self.tail = None\n",
    "        else: \n",
    "            # we have at least two nodes\n",
    "\n",
    "            # step 1: find the node prior to the tail\n",
    "            n = self.head\n",
    "            while n.next.next: # O(N)\n",
    "                n = n.next\n",
    "            \n",
    "            # step 2: remove the last node and update the tail reference\n",
    "            n.next = None\n",
    "            self.tail = next\n",
    "        \n",
    "        self.size -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.append(i)\n",
    "lst.del_tail()\n",
    "lst.del_tail()\n",
    "lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 9"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.4 64-bit",
   "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.10.4"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "aee8b7b246df8f9039afb4144a1f6fd8d2ca17a180786b69acc140d282b71a49"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}