{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TD0 Python is back"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"-7"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import random\n",
"\n",
"random.randint(-10, 10)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0, 0, 0]\n",
"[0, 0, 0]\n",
"[0, 0, 0]\n",
"[0, 42, 0]\n",
"[0, 42, 0]\n",
"[0, 42, 0]\n"
]
}
],
"source": [
"def print_matrix(m):\n",
" for l in m:\n",
" print(l)\n",
"\n",
"m = [[0] * 3] * 3\n",
"print_matrix(m)\n",
"m[1][1] = 42\n",
"print_matrix(m)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0, 2, 4, 6, 8]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[ i for i in range(10) if i % 2 == 0 ]\n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0, 0, 0]\n",
"[0, 0, 0]\n",
"[0, 0, 0]\n",
"[0, 0, 0]\n",
"[0, 42, 0]\n",
"[0, 0, 0]\n"
]
}
],
"source": [
"m = [ [0] * 3 for i in range(3) ]\n",
"print_matrix(m)\n",
"m[1][1] = 42\n",
"print_matrix(m)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def buildlist(nb, val = None, alea = None):\n",
" if val == None and alea:\n",
" return [ random.randint(alea[0], alea[1]) for i in range(nb) ]\n",
" return [ val ] * nb\n",
"\n",
"def buildmatrix(line, col, val = None):\n",
" return [ [ val ] * col for i in range(line) ]\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"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",
"[-157, 146, -145, -166, 235, -180, -186, -143, 136, 145]\n",
"[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n"
]
}
],
"source": [
"print(buildlist(10))\n",
"print(buildlist(10, 42))\n",
"print(buildlist(10, alea=(-256, 256)))\n",
"print(buildlist(10, val=0, alea=(-256,256)))"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"([0, 1, 2, 3, 4], 5, [6, 7, 8, 9, 10])"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def split_list(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",
"split_list([i for i in range(11)])"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"([0, 1, 2, 3, 4], 5, [6, 7, 8, 9, 10])"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"l = [i for i in range(11)]\n",
"\n",
"l[:len(l) // 2], l[len(l) // 2], l[len(l) // 2 + 1:]"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"9"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"l[-2]\n"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0, 1, 3, 4, 5, 6, 7, 8, 9, 10]"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"l[2:6] = l[3:6]\n",
"l"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": true
},
"outputs": [],
"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)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"l = [ random.randint(-65536, 65536) for i in range(1000000) ]\n",
"l.sort()"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"9396 572786 9396\n"
]
}
],
"source": [
"x = random.randint(-65536, 65536)\n",
"p = binsearch(l, x)\n",
"print(x, p, l[p])"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from algopy import bintree\n",
"import load_tree\n",
"import graphviz"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(15(8(1()())(12(10()())()))(28(20()(23()()))(42(35()())(66()()))))\n"
]
},
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"b = load_tree.load_bintree('files/bst.tree')\n",
"print('(15(8(1()())(12(10()())()))(28(20()(23()()))(42(35()())(66()()))))')\n",
"graphviz.Source(bintree.dot_simple(b))"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n"
]
}
],
"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 printBST(b):\n",
" if b:\n",
" print(\">\", b.key, \"<\", sep='')\n",
" printBST(b.left)\n",
" printBST(b.right)\n",
"\n",
"\n",
"n = searchBST(8, b)\n",
"print(n)"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def insertBST(x, B):\n",
" if B == None:\n",
" return bintree.BinTree(x, None, None)\n",
" else:\n",
" if x != B.key:\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",
"b2 = insertBST(27, b)\n",
"graphviz.Source(bintree.dot_simple(b))"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def copy(B):\n",
" if B == None:\n",
" return None\n",
" return bintree.BinTree(B.key, copy(B.left), copy(B.right))"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def empty_it(l):\n",
" return l\n",
"\n",
"def add42(l):\n",
" l.append(42)\n"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0, 1, 2, 3, 4]\n",
"[0, 1, 2, 3, 4]\n",
"[0, 1, 2, 3, 4, 42]\n"
]
}
],
"source": [
"l = [ i for i in range(5) ]\n",
"print(l)\n",
"empty_it(l)\n",
"print(l)\n",
"add42(l)\n",
"print(l)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"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
}