{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_dict = {}\n",
    "grades = {'Ana':'B', 'John':'A+', 'Denise':'A', 'Katy':'A'}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'A+'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grades['John']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "'sylvan'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-3-36a6785f0a13>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mgrades\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'sylvan'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m: 'sylvan'"
     ]
    }
   ],
   "source": [
    "grades['sylvan']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'A'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grades['Sylvan'] = 'A' # add an entry\n",
    "grades['Sylvan']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'John' in grades"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'Daniel' in grades"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "del(grades['Ana'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Denise': 'A', 'John': 'A+', 'Katy': 'A', 'Sylvan': 'A'}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grades"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_keys(['John', 'Denise', 'Katy', 'Sylvan'])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grades.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_values(['A+', 'A', 'A', 'A'])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grades.values()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(1, 3): 'twelve', 4: {1: 0}, 'const': [3.14, 2.7, 8.44]}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = {4:{1:0}, (1,3):\"twelve\", 'const':[3.14,2.7,8.44]}\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ví dụ - Analyze song lyrics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lyrics_to_frequencies(lyrics):\n",
    "    myDict = {}\n",
    "    for word in lyrics:\n",
    "        if word in myDict:\n",
    "            myDict[word] += 1\n",
    "        else:\n",
    "            myDict[word] = 1\n",
    "    return myDict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Because': 1,\n",
       " 'Yes': 1,\n",
       " 'a': 4,\n",
       " 'almost': 1,\n",
       " 'and': 8,\n",
       " 'bad': 3,\n",
       " 'be': 10,\n",
       " 'can': 1,\n",
       " \"can't\": 3,\n",
       " 'fair': 1,\n",
       " 'glad': 7,\n",
       " 'her': 4,\n",
       " 'hurt': 2,\n",
       " 'hurting': 1,\n",
       " 'i': 2,\n",
       " \"it's\": 3,\n",
       " 'kind': 1,\n",
       " 'know': 11,\n",
       " 'knows': 1,\n",
       " 'like': 4,\n",
       " 'lost': 2,\n",
       " 'love': 5,\n",
       " 'loves': 13,\n",
       " 'me': 1,\n",
       " 'mind': 1,\n",
       " 'not': 1,\n",
       " 'now': 1,\n",
       " 'of': 1,\n",
       " 'only': 1,\n",
       " 'oo': 2,\n",
       " 'pologize': 1,\n",
       " 'pride': 1,\n",
       " 'said': 1,\n",
       " 'saw': 1,\n",
       " 'say-yi-yay': 1,\n",
       " 'says': 3,\n",
       " 'she': 20,\n",
       " \"she's\": 1,\n",
       " 'should': 7,\n",
       " 'so': 1,\n",
       " 'that': 7,\n",
       " 'the': 1,\n",
       " 'think': 2,\n",
       " 'thinking': 1,\n",
       " 'to': 3,\n",
       " 'told': 1,\n",
       " 'too': 1,\n",
       " 'up': 1,\n",
       " 'well': 1,\n",
       " 'what': 1,\n",
       " 'with': 4,\n",
       " 'yeah': 28,\n",
       " 'yes': 2,\n",
       " 'yesterday-yi-yay': 1,\n",
       " 'you': 36,\n",
       " \"you're\": 1,\n",
       " \"you've\": 1,\n",
       " 'your': 1}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "she_loves_you = ['she', 'loves', 'you', 'yeah', 'yeah', 'yeah',\n",
    "'she', 'loves', 'you', 'yeah', 'yeah', 'yeah',\n",
    "'she', 'loves', 'you', 'yeah', 'yeah', 'yeah',\n",
    "\n",
    "'you', 'think', \"you've\", 'lost', 'your', 'love',\n",
    "'well', 'i', 'saw', 'her', 'yesterday-yi-yay',\n",
    "\"it's\", 'you', \"she's\", 'thinking', 'of',\n",
    "'and', 'she', 'told', 'me', 'what', 'to', 'say-yi-yay',\n",
    "\n",
    "'she', 'says', 'she', 'loves', 'you',\n",
    "'and', 'you', 'know', 'that', \"can't\", 'be', 'bad',\n",
    "'yes', 'she', 'loves', 'you',\n",
    "'and', 'you', 'know', 'you', 'should', 'be', 'glad',\n",
    "\n",
    "'she', 'said', 'you', 'hurt', 'her', 'so',\n",
    "'she', 'almost', 'lost', 'her', 'mind',\n",
    "'and', 'now', 'she', 'says', 'she', 'knows',\n",
    "\"you're\", 'not', 'the', 'hurting', 'kind',\n",
    "\n",
    "'she', 'says', 'she', 'loves', 'you',\n",
    "'and', 'you', 'know', 'that', \"can't\", 'be', 'bad',\n",
    "'yes', 'she', 'loves', 'you',\n",
    "'and', 'you', 'know', 'you', 'should', 'be', 'glad',\n",
    "\n",
    "'oo', 'she', 'loves', 'you', 'yeah', 'yeah', 'yeah',\n",
    "'she', 'loves', 'you', 'yeah', 'yeah', 'yeah',\n",
    "'with', 'a', 'love', 'like', 'that',\n",
    "'you', 'know', 'you', 'should', 'be', 'glad',\n",
    "\n",
    "'you', 'know', \"it's\", 'up', 'to', 'you',\n",
    "'i', 'think', \"it's\", 'only', 'fair',\n",
    "'pride', 'can', 'hurt', 'you', 'too',\n",
    "'pologize', 'to', 'her',\n",
    "\n",
    "'Because', 'she', 'loves', 'you',\n",
    "'and', 'you', 'know', 'that', \"can't\", 'be', 'bad',\n",
    "'Yes', 'she', 'loves', 'you',\n",
    "'and', 'you', 'know', 'you', 'should', 'be', 'glad',\n",
    "\n",
    "'oo', 'she', 'loves', 'you', 'yeah', 'yeah', 'yeah',\n",
    "'she', 'loves', 'you', 'yeah', 'yeah', 'yeah',\n",
    "'with', 'a', 'love', 'like', 'that',\n",
    "'you', 'know', 'you', 'should', 'be', 'glad',\n",
    "'with', 'a', 'love', 'like', 'that',\n",
    "'you', 'know', 'you', 'should', 'be', 'glad',\n",
    "'with', 'a', 'love', 'like', 'that',\n",
    "'you', 'know', 'you', 'should', 'be', 'glad',\n",
    "'yeah', 'yeah', 'yeah',\n",
    "'yeah', 'yeah', 'yeah', 'yeah'\n",
    "]\n",
    "\n",
    "beatles = lyrics_to_frequencies(she_loves_you)\n",
    "beatles"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['you']"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def most_common_words(freqs):\n",
    "    values = freqs.values()\n",
    "    best = max(freqs.values())\n",
    "    words = []\n",
    "    for k in freqs:\n",
    "        if freqs[k] == best:\n",
    "            words.append(k)\n",
    "    return (words, best)\n",
    "\n",
    "(w, b) = most_common_words(beatles)\n",
    "w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def words_often(freqs, minTimes):\n",
    "    result = []\n",
    "    done = False\n",
    "    while not done:\n",
    "        temp = most_common_words(freqs)\n",
    "        if temp[1] >= minTimes:\n",
    "            result.append(temp)\n",
    "            for w in temp[0]:\n",
    "                del(freqs[w])  #remove word from dictionary\n",
    "        else:\n",
    "            done = True\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(['you'], 36), (['yeah'], 28), (['she'], 20), (['loves'], 13), (['know'], 11), (['be'], 10), (['and'], 8), (['that', 'should', 'glad'], 7), (['love'], 5)]\n"
     ]
    }
   ],
   "source": [
    "print(words_often(beatles, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ví dụ - Fibonacci"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5702887\n"
     ]
    }
   ],
   "source": [
    "def fib_efficient(n, d):\n",
    "    if n in d:\n",
    "        return d[n]\n",
    "    else:\n",
    "        ans = fib_efficient(n-1, d) + fib_efficient(n-2, d)\n",
    "        d[n] = ans\n",
    "        return ans\n",
    "    \n",
    "d = {1:1, 2:2}\n",
    "print(fib_efficient(33, d))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5702887\n"
     ]
    }
   ],
   "source": [
    "def fib(x):\n",
    "    if x == 0 or x == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return fib(x - 1) + fib(x - 2)\n",
    "    \n",
    "print(fib(33))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Biến toàn cục - Global variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9227465\n",
      "function calls 11405773\n",
      "9227465\n",
      "function calls 65\n"
     ]
    }
   ],
   "source": [
    "def fib(n):\n",
    "    global numFibCalls\n",
    "    numFibCalls += 1\n",
    "    if n == 1 or n == 2:\n",
    "        return n\n",
    "    else:\n",
    "        return fib(n-1) + fib(n-2)\n",
    "    \n",
    "def fibef(n, d):\n",
    "    global numFibCalls\n",
    "    numFibCalls += 1\n",
    "    if n in d:\n",
    "        return d[n]\n",
    "    else:\n",
    "        ans = fibef(n-1, d) + fibef(n-2, d)\n",
    "        d[n] = ans\n",
    "        return ans\n",
    "    \n",
    "numFibCalls = 0\n",
    "fibArg = 34\n",
    "\n",
    "print(fib(fibArg))\n",
    "print('function calls', numFibCalls)\n",
    "\n",
    "numFibCalls = 0\n",
    "\n",
    "d = {1:1, 2:2}\n",
    "print(fibef(fibArg, d))\n",
    "print('function calls', numFibCalls)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- - -\n",
    "[Trước: Tuple và List](http://nbviewer.jupyter.org/github/manleviet/introCSusingPython/blob/master/5%20-%20Tuple%2C%20List.ipynb) | \n",
    "[Mục lục](http://nbviewer.jupyter.org/github/manleviet/introCSusingPython/blob/master/index.ipynb) | \n",
    "[Tiếp: Kiểm thử chương trình](http://nbviewer.jupyter.org/github/manleviet/introCSusingPython/blob/master/7%20-%20Ki%E1%BB%83m%20th%E1%BB%AD%20ch%C6%B0%C6%A1ng%20tr%C3%ACnh.ipynb)"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}