{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TD 0 - Le retour de python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on method randint in module random:\n",
      "\n",
      "randint(a, b) method of random.Random instance\n",
      "    Return random integer in range [a, b], including both end points.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "help(random.randint)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [0] * 10\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = []\n",
    "for i in range(10):\n",
    "    l.append(0)\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 0, 0], [0, 0, 0], [0, 0, 0]]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = [[0] * 3] * 3\n",
    "m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 42, 0], [0, 42, 0], [0, 42, 0]]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m[1][1] = 42\n",
    "m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 2, 4, 6, 8]\n",
      "['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']\n"
     ]
    }
   ],
   "source": [
    "print([ i for i in range(10) if i % 2 == 0 ])\n",
    "print([c for c in \"abcdefghijklmnopqrstuvwxyz\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 0, 0], [0, 0, 0], [0, 0, 0]]\n",
      "[[0, 0, 0], [0, 42, 0], [0, 0, 0]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "37"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = [ [0] * 3 for i in range(3)]\n",
    "print(m)\n",
    "m[1][1] = 42\n",
    "print(m)\n",
    "random.randint(0, 42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def buildlist(nb, val = None, alea = None):\n",
    "    if not val and alea:\n",
    "        return [ random.randint(*alea) for i in range(nb) ]\n",
    "    return [val] * nb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[None, None, None, None, None, None, None, None, None, None]\n",
      "[42, 42, 42, 42, 42, 42, 42, 42, 42, 42]\n",
      "[11, -15, 31, 42, -19, -49, 48, -30, 1, 28]\n"
     ]
    }
   ],
   "source": [
    "print(buildlist(10))\n",
    "print(buildlist(10, 42))\n",
    "print(buildlist(10, alea=(-50,50)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 0, 0], [0, 0, 0], [0, 0, 0]]\n",
      "[0, 0, 0]\n",
      "[0, 0, 0]\n",
      "[0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "def buildmatrix(line, col, val = None):\n",
    "    return [ buildlist(col, val) for i in range(line) ]\n",
    "\n",
    "print(buildmatrix(3,3,0))\n",
    "def print_matrix(m):\n",
    "    for l in m:\n",
    "        print(l)\n",
    "print_matrix(buildmatrix(3,3,0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([0, 1, 2, 3, 4], 5, [6, 7, 8, 9])"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def splitlist(l):\n",
    "    n = len(l)\n",
    "    l1 = []\n",
    "    for i in range(n // 2):\n",
    "        l1.append(l[i])\n",
    "    l2 = []\n",
    "    for i in range(n // 2 + 1, n):\n",
    "        l2.append(l[i])\n",
    "    return l1, l[n // 2], l2\n",
    "\n",
    "splitlist([i for i in range(10)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([0, 1, 2, 3, 4], 5, [6, 7, 8, 9])"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [ i for i in range(10) ]\n",
    "l[:len(l) // 2], l[len(l) // 2], l[len(l) // 2 + 1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "l[0:42]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 1, 2, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [ i for i in range(10) ]\n",
    "l[1:4] = l[0:3]\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def binsearch(v,x):\n",
    "    left, right = 0, len(v)\n",
    "    while left < right:\n",
    "        mid = left + (right - left) // 2\n",
    "        if x == v[mid]:\n",
    "            return mid\n",
    "        if x < v[mid]:\n",
    "            right = mid\n",
    "        else:\n",
    "            left = mid + 1\n",
    "    return left\n",
    "\n",
    "def binsearch_rec(v, x, left, right):\n",
    "    if left >= right:\n",
    "        return left\n",
    "    mid = left + (right - left) // 2\n",
    "    if x == v[mid]:\n",
    "        return mid\n",
    "    if x < v[mid]:\n",
    "        return binsearch_rec(v, x, left, mid)\n",
    "    return binsearch_rec(v, x, mid + 1, right)\n",
    "\n",
    "binsearch_rec([i for i in range(10)], 3.5, 0, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "l = [ random.randint(-65536, 65536) for i in range(1000000) ]\n",
    "l.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14412 609949 14412\n"
     ]
    }
   ],
   "source": [
    "x = random.randint(-65536, 65536)\n",
    "p = binsearch(l, x)\n",
    "print(x, p, l[p])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [],
   "source": [
    "from algopy import bintree\n",
    "import load_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def searchBST(x, B):\n",
    "    if B == None or x == B.key:\n",
    "        return B\n",
    "    else:\n",
    "        if x < B.key:\n",
    "            return searchBST(x, B.left)\n",
    "        else:\n",
    "            return searchBST(x, B.right)\n",
    "\n",
    "def insertBST(x, B):\n",
    "    if B == None:\n",
    "        return binTree.BinTree(x, None, None)\n",
    "    else:\n",
    "        if x == B.key:\n",
    "            return B\n",
    "        else:\n",
    "            if x < B.key:\n",
    "                B.left = insertBST(x, B.left)\n",
    "            else:\n",
    "                B.right = insertBST(x, B.right)\n",
    "            return B\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = load_tree.load_bintree('files/bst.tree')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "42\n"
     ]
    }
   ],
   "source": [
    "print(searchBST('42', b).key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "b = insertBST('27', b)\n",
    "print(searchBST('27', b).key)\n",
    "print(searchBST('42', b))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}