chapters/chap10.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1331faa1",
   "metadata": {},
   "source": [
    "You can order print and ebook versions of *Think Python 3e* from\n",
    "[Bookshop.org](https://bookshop.org/a/98697/9781098155438) and\n",
    "[Amazon](https://www.amazon.com/_/dp/1098155432?smid=ATVPDKIKX0DER&_encoding=UTF8&tag=oreilly20-20&_encoding=UTF8&tag=greenteapre01-20&linkCode=ur2&linkId=e2a529f94920295d27ec8a06e757dc7c&camp=1789&creative=9325)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "e55de5cd",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from os.path import basename, exists\n",
    "\n",
    "def download(url):\n",
    "    filename = basename(url)\n",
    "    if not exists(filename):\n",
    "        from urllib.request import urlretrieve\n",
    "\n",
    "        local, _ = urlretrieve(url, filename)\n",
    "        print(\"Downloaded \" + str(local))\n",
    "    return filename\n",
    "\n",
    "download('https://github.com/AllenDowney/ThinkPython/raw/v3/thinkpython.py');\n",
    "download('https://github.com/AllenDowney/ThinkPython/raw/v3/diagram.py');\n",
    "\n",
    "import thinkpython"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "737e79eb",
   "metadata": {},
   "source": [
    "# Dictionaries\n",
    "\n",
    "This chapter presents a built-in type called a dictionary.\n",
    "It is one of Python's best features -- and the building block of many efficient and elegant algorithms.\n",
    "\n",
    "We'll use dictionaries to compute the number of unique words in a book and the number of times each one appears.\n",
    "And in the exercises, we'll use dictionaries to solve word puzzles."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be7467bb",
   "metadata": {},
   "source": [
    "## A dictionary is a mapping\n",
    "\n",
    "A **dictionary** is like a list, but more general.\n",
    "In a list, the indices have to be integers; in a dictionary they can be (almost) any type.\n",
    "For example, suppose we make a list of number words, like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "20dd9f32",
   "metadata": {},
   "outputs": [],
   "source": [
    "lst = ['zero', 'one', 'two']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa626f88",
   "metadata": {},
   "source": [
    "We can use an integer as an index to get the corresponding word."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "9b6625c0",
   "metadata": {},
   "outputs": [],
   "source": [
    "lst[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c38e143b",
   "metadata": {},
   "source": [
    "But suppose we want to go in the other direction, and look up a word to get the corresponding integer.\n",
    "We can't do that with a list, but we can with a dictionary.\n",
    "We'll start by creating an empty dictionary and assigning it to `numbers`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "138952d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers = {}\n",
    "numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3acce992",
   "metadata": {},
   "source": [
    "The curly braces, `{}`, represent an empty dictionary.\n",
    "To add items to the dictionary, we'll use square brackets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "007ef505",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers['zero'] = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1dbe12c3",
   "metadata": {},
   "source": [
    "This assignment adds to the dictionary an **item**, which represents the association of a **key** and a **value**.\n",
    "In this example, the key is the string `'zero'` and the value is the integer `0`.\n",
    "If we display the dictionary, we see that it contains one item, which contains a key and a value separated by a colon, `:`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "753a8fbc",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad32c23d",
   "metadata": {},
   "source": [
    "We can add more items like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "835aac1e",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers['one'] = 1\n",
    "numbers['two'] = 2\n",
    "numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "278901e5",
   "metadata": {},
   "source": [
    "Now the dictionary contains three items.\n",
    "\n",
    "To look up a key and get the corresponding value, we use the bracket operator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "c0475cee",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers['two']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df5724e6",
   "metadata": {},
   "source": [
    "If the key isn't in the dictionary, we get a `KeyError`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "30c37eef",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%expect KeyError\n",
    "numbers['three']\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a027a6b",
   "metadata": {},
   "source": [
    "The `len` function works on dictionaries; it returns the number of items."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "1b4ea0c2",
   "metadata": {},
   "outputs": [],
   "source": [
    "len(numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58221e96",
   "metadata": {},
   "source": [
    "In mathematical language, a dictionary represents a **mapping** from keys to values, so you can also say that each key \"maps to\" a value.\n",
    "In this example, each number word maps to the corresponding integer.\n",
    "\n",
    "The following figure shows the state diagram for `numbers`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "eba36a24",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from diagram import make_dict, Binding, Value\n",
    "\n",
    "d1 = make_dict(numbers, dy=-0.3, offsetx=0.37)\n",
    "binding1 = Binding(Value('numbers'), d1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "9016bf4b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from diagram import diagram, adjust, Bbox\n",
    "\n",
    "width, height, x, y = [1.83, 1.24, 0.49, 0.85]\n",
    "ax = diagram(width, height)\n",
    "bbox = binding1.draw(ax, x, y)\n",
    "# adjust(x, y, bbox)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b092aa61",
   "metadata": {},
   "source": [
    "A dictionary is represented by a box with the word \"dict\" outside and the items inside.\n",
    "Each item is represented by a key and an arrow pointing to a value.\n",
    "The quotation marks indicate that the keys here are strings, not variable names."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a0a128a",
   "metadata": {},
   "source": [
    "## Creating dictionaries\n",
    "\n",
    "In the previous section we created an empty dictionary and added items one at a time using the bracket operator.\n",
    "Instead, we could have created the dictionary all at once like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "19dfeecb",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers = {'zero': 0, 'one': 1, 'two': 2}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31ded5b2",
   "metadata": {},
   "source": [
    "Each item consists of a key and a value separated by a colon.\n",
    "The items are separated by commas and enclosed in curly braces.\n",
    "\n",
    "Another way to create a dictionary is to use the `dict` function.\n",
    "We can make an empty dictionary like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "39b81034",
   "metadata": {},
   "outputs": [],
   "source": [
    "empty = dict()\n",
    "empty"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfb215c9",
   "metadata": {},
   "source": [
    "And we can make a copy of a dictionary like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "88fa12c5",
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers_copy = dict(numbers)\n",
    "numbers_copy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "966c5539",
   "metadata": {},
   "source": [
    "It is often useful to make a copy before performing operations that modify dictionaries."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a948f62",
   "metadata": {
    "tags": []
   },
   "source": [
    "## The in operator\n",
    "\n",
    "The `in` operator works on dictionaries, too; it tells you whether something appears as a *key* in the dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "025cad92",
   "metadata": {},
   "outputs": [],
   "source": [
    "'one' in numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80f6b264",
   "metadata": {},
   "source": [
    "The `in` operator does *not* check whether something appears as a value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "65de12ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "1 in numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84856c8b",
   "metadata": {},
   "source": [
    "To see whether something appears as a value in a dictionary, you can use the method `values`, which returns a sequence of values, and then use the `in` operator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "87ddc1b2",
   "metadata": {},
   "outputs": [],
   "source": [
    "1 in numbers.values()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45dc3d16",
   "metadata": {},
   "source": [
    "The items in a Python dictionary are stored in a **hash table**, which is a way of organizing data that has a remarkable property: the `in` operator takes about the same amount of time no matter how many items are in the dictionary.\n",
    "That makes it possible to write some remarkably efficient algorithms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "4849b563",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt');"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bba0522c",
   "metadata": {},
   "source": [
    "To demonstrate, we'll compare two algorithms for finding pairs of words where one is the reverse of another -- like `stressed` and `desserts`.\n",
    "We'll start by reading the word list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "830b1208",
   "metadata": {},
   "outputs": [],
   "source": [
    "word_list = open('words.txt').read().split()\n",
    "len(word_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab29fb8a",
   "metadata": {},
   "source": [
    "And here's `reverse_word` from the previous chapter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "49231201",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse_word(word):\n",
    "    return ''.join(reversed(word))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93f7ac1b",
   "metadata": {},
   "source": [
    "The following function loops through the words in the list.\n",
    "For each one, it reverses the letters and then checks whether the reversed word in the word list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "a41759fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def too_slow():\n",
    "    count = 0\n",
    "    for word in word_list:\n",
    "        if reverse_word(word) in word_list:\n",
    "            count += 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4ebb84d",
   "metadata": {},
   "source": [
    "This function takes more than a minute to run.\n",
    "The problem is that the `in` operator checks the words in the list one at a time, starting at the beginning.\n",
    "If it doesn't find what it's looking for -- which happens most of the time -- it has to search all the way to the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "33bcddf8",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# %time too_slow()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2acb6c50",
   "metadata": {},
   "source": [
    "And the `in` operator is inside the loop, so it runs once for each word.\n",
    "Since there are more than 100,000 words in the list, and for each one we check more than 100,000 words, the total number of comparisons is the number of words squared -- roughly -- which is almost 13 billion. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "f2869dd0",
   "metadata": {},
   "outputs": [],
   "source": [
    "len(word_list)**2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5dbf01b7",
   "metadata": {},
   "source": [
    "We can make this function much faster with a dictionary.\n",
    "The following loop creates a dictionary that contains the words as keys."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "300416d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "word_dict = {}\n",
    "for word in word_list:\n",
    "    word_dict[word] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7f6a1b7",
   "metadata": {},
   "source": [
    "The values in `word_dict` are all `1`, but they could be anything, because we won't ever look them up -- we will only use this dictionary to check whether a key exists.\n",
    "\n",
    "Now here's a version of the previous function that replaces `word_list` with `word_dict`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "9d3dfd8d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def much_faster():\n",
    "    count = 0\n",
    "    for word in word_dict:\n",
    "        if reverse_word(word) in word_dict:\n",
    "            count += 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f41e54c",
   "metadata": {},
   "source": [
    "This function takes less than one hundredth of a second, so it's about 10,000 times faster than the previous version."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "82b36568",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%time much_faster()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cd91c99",
   "metadata": {},
   "source": [
    "In general, the time it takes to find an element in a list is proportional to the length of the list.\n",
    "The time it takes to find a key in a dictionary is almost constant -- regardless of the number of items."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "aa079ed3",
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {'a': 1, 'b': 2}\n",
    "d['a'] = 3\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3bfa8a5",
   "metadata": {},
   "source": [
    "## A collection of counters\n",
    "\n",
    "Suppose you are given a string and you want to count how many times each letter appears.\n",
    "A dictionary is a good tool for this job.\n",
    "We'll start with an empty dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "7c21ff00",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter = {}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34a9498a",
   "metadata": {},
   "source": [
    "As we loop through the letters in the string, suppose we see the letter `'a'` for the first time.\n",
    "We can add it to the dictionary like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "7d0afb00",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter['a'] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bca9fa11",
   "metadata": {},
   "source": [
    "The value `1` indicates that we have seen the letter once.\n",
    "Later, if we see the same letter again, we can increment the counter like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "ba97b5ea",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter['a'] += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "274ea014",
   "metadata": {},
   "source": [
    "Now the value associated with `'a'` is `2`, because we've seen the letter twice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "30ffe9b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ca8f99d",
   "metadata": {},
   "source": [
    "The following function uses these features to count the number of times each letter appears in a string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "36f95332",
   "metadata": {},
   "outputs": [],
   "source": [
    "def value_counts(string):\n",
    "    counter = {}\n",
    "    for letter in string:\n",
    "        if letter not in counter:\n",
    "            counter[letter] = 1\n",
    "        else:\n",
    "            counter[letter] += 1\n",
    "    return counter"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "735c758b",
   "metadata": {},
   "source": [
    "Each time through the loop, if `letter` is not in the dictionary, we create a new item with key `letter` and value `1`.\n",
    "If `letter` is already in the dictionary we increment the value associated with `letter`.\n",
    "\n",
    "Here's an example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "d6f1048e",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter = value_counts('brontosaurus')\n",
    "counter"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ac1fea4",
   "metadata": {},
   "source": [
    "The items in `counter` show that the letter `'b'` appears once, `'r'` appears twice, and so on."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "912bdf5d",
   "metadata": {},
   "source": [
    "## Looping and dictionaries\n",
    "\n",
    "If you use a dictionary in a `for` statement, it traverses the keys of the dictionary.\n",
    "To demonstrate, let's make a dictionary that counts the letters in `'banana'`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "310e1489",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter = value_counts('banana')\n",
    "counter"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe263f3d",
   "metadata": {},
   "source": [
    "The following loop prints the keys, which are the letters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "da4ec7fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "for key in counter:\n",
    "    print(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf1b7824",
   "metadata": {},
   "source": [
    "To print the values, we can use the `values` method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "859fe1ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "for value in counter.values():\n",
    "    print(value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "721135be",
   "metadata": {},
   "source": [
    "To print the keys and values, we can loop through the keys and look up the corresponding values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "7242ab5b",
   "metadata": {},
   "outputs": [],
   "source": [
    "for key in counter:\n",
    "    value = counter[key]\n",
    "    print(key, value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efa1bce5",
   "metadata": {},
   "source": [
    "In the next chapter, we'll see a more concise way to do the same thing."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a160c0ef",
   "metadata": {},
   "source": [
    "## Lists and dictionaries\n",
    "\n",
    "You can put a list in a dictionary as a value.\n",
    "For example, here's a dictionary that maps from the number `4` to a list of four letters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "29cd8207",
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {4: ['r', 'o', 'u', 's']}\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "815a829f",
   "metadata": {},
   "source": [
    "But you can't put a list in a dictionary as a key.\n",
    "Here's what happens if we try."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "ca9ff511",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%expect TypeError\n",
    "letters = list('abcd')\n",
    "d[letters] = 4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2469b08a",
   "metadata": {},
   "source": [
    "I mentioned earlier that dictionaries use hash tables, and that means that the keys have to be **hashable**.\n",
    "\n",
    "A **hash** is a function that takes a value (of any kind) and returns an integer.\n",
    "Dictionaries use these integers, called hash values, to store and look up keys.\n",
    "\n",
    "This system only works if a key is immutable, so its hash value is always the same.\n",
    "But if a key is mutable, its hash value could change, and the dictionary would not work.\n",
    "That's why keys have to be hashable, and why mutable types like lists aren't.\n",
    "\n",
    "Since dictionaries are mutable, they can't be used as keys, either.\n",
    "But they *can* be used as values."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acfd2720",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Accumulating a list\n",
    "\n",
    "For many programming tasks, it is useful to loop through one list or dictionary while building another.\n",
    "As an example, we'll loop through the words in `word_dict` and make a list of palindromes -- that is, words that are spelled the same backward and forward, like \"noon\" and \"rotator\".\n",
    "\n",
    "In the previous chapter, one of the exercises asked you to write a function that checks whether a word is a palindrome.\n",
    "Here's a solution that uses `reverse_word`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "0647278e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_palindrome(word):\n",
    "    \"\"\"Check if a word is a palindrome.\"\"\"\n",
    "    return reverse_word(word) == word"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af545fcd",
   "metadata": {},
   "source": [
    "If we loop through the words in `word_dict`, we can count the number of palindromes like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "9eff9f2c",
   "metadata": {},
   "outputs": [],
   "source": [
    "count = 0\n",
    "\n",
    "for word in word_dict:\n",
    "    if is_palindrome(word):\n",
    "        count +=1\n",
    "        \n",
    "count"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73c1ce1e",
   "metadata": {},
   "source": [
    "By now, this pattern is familiar.\n",
    "\n",
    "* Before the loop, `count` is initialized to `0`.\n",
    "\n",
    "* Inside the loop, if `word` is a palindrome, we increment `count`.\n",
    "\n",
    "* When the loop ends, `count` contains the total number of palindromes.\n",
    "\n",
    "We can use a similar pattern to make a list of palindromes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "609bdd9a",
   "metadata": {},
   "outputs": [],
   "source": [
    "palindromes = []\n",
    "\n",
    "for word in word_dict:\n",
    "    if is_palindrome(word):\n",
    "        palindromes.append(word)\n",
    "\n",
    "palindromes[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be909f3b",
   "metadata": {},
   "source": [
    "Here's how it works:\n",
    "\n",
    "* Before the loop, `palindromes` is initialized with an empty list.\n",
    "\n",
    "* Inside the loop, if `word` is a palindrome, we append it to the end of `palindromes`.\n",
    "\n",
    "* When the loop ends, `palindromes` is a list of palindromes.\n",
    "\n",
    "In this loop, `palindromes` is used as an **accumulator**, which is a variable that collects or accumulates data during a computation.\n",
    "\n",
    "Now suppose we want to select only palindromes with seven or more letters.\n",
    "We can loop through `palindromes` and make a new list that contains only long palindromes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "c2db1187",
   "metadata": {},
   "outputs": [],
   "source": [
    "long_palindromes = []\n",
    "\n",
    "for word in palindromes:\n",
    "    if len(word) >= 7:\n",
    "        long_palindromes.append(word)\n",
    "        \n",
    "long_palindromes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa8ed275",
   "metadata": {},
   "source": [
    "Looping through a list like this, selecting some elements and omitting others, is called **filtering**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ed50837",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Memos\n",
    "\n",
    "If you ran the `fibonacci` function from [Chapter 6](section_fibonacci), maybe you noticed that the bigger the argument you provide, the longer the function takes to run."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "13a7ed35",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    \n",
    "    if n == 1:\n",
    "        return 1\n",
    "\n",
    "    return fibonacci(n-1) + fibonacci(n-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b5203c2",
   "metadata": {},
   "source": [
    "Furthermore, the run time increases quickly.\n",
    "To understand why, consider the following figure, which shows the **call graph** for\n",
    "`fibonacci` with `n=4`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "7ed6137a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from diagram import make_binding, Frame, Arrow\n",
    "\n",
    "bindings = [make_binding('n', i) for i in range(5)]\n",
    "frames = [Frame([binding]) for binding in bindings]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "a9374c39",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "arrowprops = dict(arrowstyle=\"-\", color='gray', alpha=0.5, ls='-', lw=0.5)\n",
    "\n",
    "def left_arrow(ax, bbox1, bbox2):\n",
    "    x = bbox1.xmin + 0.1\n",
    "    y = bbox1.ymin\n",
    "    dx = bbox2.xmax - x - 0.1\n",
    "    dy = bbox2.ymax - y\n",
    "    arrow = Arrow(dx=dx, dy=dy, arrowprops=arrowprops)\n",
    "    return arrow.draw(ax, x, y)\n",
    "\n",
    "def right_arrow(ax, bbox1, bbox2):\n",
    "    x = bbox1.xmax - 0.1\n",
    "    y = bbox1.ymin\n",
    "    dx = bbox2.xmin - x + 0.1\n",
    "    dy = bbox2.ymax - y\n",
    "    arrow = Arrow(dx=dx, dy=dy, arrowprops=arrowprops)\n",
    "    return arrow.draw(ax, x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "12098be7",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from diagram import diagram, adjust, Bbox\n",
    "\n",
    "width, height, x, y = [4.94, 2.16, -1.03, 1.91]\n",
    "ax = diagram(width, height)\n",
    "\n",
    "dx = 0.6\n",
    "dy = 0.55\n",
    "\n",
    "bboxes = []\n",
    "bboxes.append(frames[4].draw(ax, x+6*dx, y))\n",
    "\n",
    "bboxes.append(frames[3].draw(ax, x+4*dx, y-dy))\n",
    "bboxes.append(frames[2].draw(ax, x+8*dx, y-dy))\n",
    "\n",
    "bboxes.append(frames[2].draw(ax, x+3*dx, y-2*dy))\n",
    "bboxes.append(frames[1].draw(ax, x+5*dx, y-2*dy))\n",
    "bboxes.append(frames[1].draw(ax, x+7*dx, y-2*dy))\n",
    "bboxes.append(frames[0].draw(ax, x+9*dx, y-2*dy))\n",
    "\n",
    "bboxes.append(frames[1].draw(ax, x+2*dx, y-3*dy))\n",
    "bboxes.append(frames[0].draw(ax, x+4*dx, y-3*dy))\n",
    "\n",
    "left_arrow(ax, bboxes[0], bboxes[1])\n",
    "left_arrow(ax, bboxes[1], bboxes[3])\n",
    "left_arrow(ax, bboxes[3], bboxes[7])\n",
    "left_arrow(ax, bboxes[2], bboxes[5])\n",
    "\n",
    "right_arrow(ax, bboxes[0], bboxes[2])\n",
    "right_arrow(ax, bboxes[1], bboxes[4])\n",
    "right_arrow(ax, bboxes[2], bboxes[6])\n",
    "right_arrow(ax, bboxes[3], bboxes[8])\n",
    "\n",
    "bbox = Bbox.union(bboxes)\n",
    "# adjust(x, y, bbox)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ee2a87c",
   "metadata": {},
   "source": [
    "A call graph shows a set of function frames, with lines connecting each frame to the frames of the functions it calls.\n",
    "At the top of the graph, `fibonacci` with `n=4` calls `fibonacci` with ` n=3` and `n=2`.\n",
    "In turn, `fibonacci` with `n=3` calls `fibonacci` with `n=2` and `n=1`. And so on.\n",
    "\n",
    "Count how many times `fibonacci(0)` and `fibonacci(1)` are called. \n",
    "This is an inefficient solution to the problem, and it gets worse as the argument gets bigger.\n",
    "\n",
    "One solution is to keep track of values that have already been computed by storing them in a dictionary.\n",
    "A previously computed value that is stored for later use is called a **memo**.\n",
    "Here is a \"memoized\" version of `fibonacci`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "28e443f5",
   "metadata": {},
   "outputs": [],
   "source": [
    "known = {0:0, 1:1}\n",
    "\n",
    "def fibonacci_memo(n):\n",
    "    if n in known:\n",
    "        return known[n]\n",
    "\n",
    "    res = fibonacci_memo(n-1) + fibonacci_memo(n-2)\n",
    "    known[n] = res\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2ac4dd7",
   "metadata": {},
   "source": [
    "`known` is a dictionary that keeps track of the Fibonacci numbers we already know\n",
    "It starts with two items: `0` maps to `0` and `1` maps to `1`.\n",
    "\n",
    "Whenever `fibonacci_memo` is called, it checks `known`.\n",
    "If the result is already there, it can return immediately.\n",
    "Otherwise it has to compute the new value, add it to the dictionary, and return it.\n",
    "\n",
    "Comparing the two functions, `fibonacci(40)` takes about 30 seconds to run.\n",
    "`fibonacci_memo(40)` takes about 30 microseconds, so it's a million times faster.\n",
    "In the notebook for this chapter, you'll see where these measurements come from."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6f39f84",
   "metadata": {
    "tags": []
   },
   "source": [
    "To measure how long a function takes, we can use `%time` which is one of Jupyter's \"built-in magic commands\".\n",
    "These commands are not part of the Python language, so they might not work in other development environments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "af818c11",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# %time fibonacci(40)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "7316d721",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%time fibonacci_memo(40)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec969e51",
   "metadata": {},
   "source": [
    "## Debugging\n",
    "\n",
    "As you work with bigger datasets it can become unwieldy to debug by printing and checking the output by hand. Here are some suggestions for debugging large datasets:\n",
    "\n",
    "1.  Scale down the input: If possible, reduce the size of the dataset. For example if the\n",
    "    program reads a text file, start with just the first 10 lines, or\n",
    "    with the smallest example you can find. You can either edit the\n",
    "    files themselves, or (better) modify the program so it reads only\n",
    "    the first `n` lines.\n",
    "\n",
    "    If there is an error, you can reduce `n` to the smallest value where the error occurs.\n",
    "    As you find and correct errors, you can increase `n` gradually."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a62288b",
   "metadata": {},
   "source": [
    "2. Check summaries and types: Instead of printing and checking the entire dataset, consider\n",
    "    printing summaries of the data -- for example, the number of items in\n",
    "    a dictionary or the total of a list of numbers.\n",
    "\n",
    "    A common cause of runtime errors is a value that is not the right type. For debugging this kind of error, it is often enough to print the type of a value."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c749ea3c",
   "metadata": {},
   "source": [
    "3. Write self-checks: Sometimes you can write code to check for errors automatically. For\n",
    "    example, if you are computing the average of a list of numbers, you\n",
    "    could check that the result is not greater than the largest element\n",
    "    in the list or less than the smallest. This is called a \"sanity\n",
    "    check\" because it detects results that are \"insane\".\n",
    "\n",
    "    Another kind of check compares the results of two different computations to see if they are consistent. This is called a \"consistency check\"."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "749b91e9",
   "metadata": {},
   "source": [
    "4. Format the output: Formatting debugging output can make it easier to spot an error. We saw an example in [Chapter 6](section_debugging_factorial). Another tool you might find useful is the `pprint` module, which provides a `pprint` function that displays built-in types in a more human-readable format (`pprint` stands for \"pretty print\").\n",
    "\n",
    "    Again, time you spend building scaffolding can reduce the time you spend debugging."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9820175f",
   "metadata": {},
   "source": [
    "## Glossary\n",
    "\n",
    "**dictionary:**\n",
    " An object that contains key-value pairs, also called items.\n",
    "\n",
    "**item:**\n",
    " In a dictionary, another name for a key-value pair.\n",
    "\n",
    "**key:**\n",
    " An object that appears in a dictionary as the first part of a key-value pair.\n",
    "\n",
    "**value:**\n",
    " An object that appears in a dictionary as the second part of a key-value pair. This is more specific than our previous use of the word \"value\".\n",
    "\n",
    "**mapping:**\n",
    "  A relationship in which each element of one set corresponds to an element of another set.\n",
    "\n",
    "**hash table:**\n",
    "A collection of key-value pairs organized so that we can look up a key and find its value efficiently.\n",
    "\n",
    "**hashable:**\n",
    " Immutable types like integers, floats and strings are hashable.\n",
    " Mutable types like lists and dictionaries are not.\n",
    "\n",
    "**hash function:**\n",
    "A function that takes an object and computes an integer that is used to locate a key in a hash table.\n",
    "\n",
    "**accumulator:**\n",
    " A variable used in a loop to add up or accumulate a result.\n",
    "\n",
    "**filtering:**\n",
    "Looping through a sequence and selecting or omitting elements.\n",
    "\n",
    "**call graph:**\n",
    "A diagram that shows every frame created during the execution of a program, with an arrow from each caller to each callee.\n",
    "\n",
    "**memo:**\n",
    " A computed value stored to avoid unnecessary future computation."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "906c1236",
   "metadata": {},
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1e3c12ec",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# This cell tells Jupyter to provide detailed debugging information\n",
    "# when a runtime error occurs. Run it before working on the exercises.\n",
    "\n",
    "%xmode Verbose"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "170f1deb",
   "metadata": {},
   "source": [
    "### Ask an assistant\n",
    "\n",
    "In this chapter, I said the keys in a dictionary have to be hashable and I gave a short explanation. If you would like more details, ask a virtual assistant, \"Why do keys in Python dictionaries have to be hashable?\"\n",
    "\n",
    "In [a previous section](section_dictionary_in_operator), we stored a list of words as keys in a dictionary so that we could use an efficient version of the `in` operator.\n",
    "We could have done the same thing using a `set`, which is another built-in data type.\n",
    "Ask a virtual assistant, \"How do I make a Python set from a list of strings and check whether a string is an element of the set?\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "badf7d65",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Dictionaries have a method called `get` that takes a key and a default value. \n",
    "If the key appears in the dictionary, `get` returns the corresponding value; otherwise it returns the default value.\n",
    "For example, here's a dictionary that maps from the letters in a string to the number of times they appear."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "06e437d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter = value_counts('brontosaurus')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3f6458d",
   "metadata": {},
   "source": [
    "If we look up a letter that appears in the word, `get` returns the number of times it appears."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "fc328161",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter.get('b', 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49bbff3e",
   "metadata": {},
   "source": [
    "If we look up a letter that doesn't appear, we get the default value, `0`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "674b6663",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter.get('c', 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ac3210f",
   "metadata": {},
   "source": [
    "Use `get` to write a more concise version of `value_counts`.\n",
    "You should be able to eliminate the `if` statement."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5413af6e",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "What is the longest word you can think of where each letter appears only once?\n",
    "Let's see if we can find one longer than `unpredictably`.\n",
    "\n",
    "Write a function named `has_duplicates` that takes a sequence -- like a list or string -- as a parameter and returns `True` if there is any element that appears in the sequence more than once."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9879d9e7",
   "metadata": {
    "tags": []
   },
   "source": [
    "To get you started, here's an outline of the function with doctests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "1744d3e9",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def has_duplicates(t):\n",
    "    \"\"\"Check whether any element in a sequence appears more than once.\n",
    "    \n",
    "    >>> has_duplicates('banana')\n",
    "    True\n",
    "    >>> has_duplicates('ambidextrously')\n",
    "    False\n",
    "    >>> has_duplicates([1, 2, 2])\n",
    "    True\n",
    "    >>> has_duplicates([1, 2, 3])\n",
    "    False\n",
    "    \"\"\"\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "061e2903",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8c85906",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use `doctest` to test your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "62dcdf4d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from doctest import run_docstring_examples\n",
    "\n",
    "def run_doctests(func):\n",
    "    run_docstring_examples(func, globals(), name=func.__name__)\n",
    "\n",
    "run_doctests(has_duplicates)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce4df190",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use this loop to find the longest words with no repeated letters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "a1143193",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "no_repeats = []\n",
    "\n",
    "for word in word_list:\n",
    "    if len(word) > 12 and not has_duplicates(word):\n",
    "        no_repeats.append(word)\n",
    "        \n",
    "no_repeats"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afd5f3b6",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Write function called `find_repeats` that takes a dictionary that maps from each key to a counter, like the result from `value_counts`.\n",
    "It should loop through the dictionary and return a list of keys that have counts greater than `1`.\n",
    "You can use the following outline to get started."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "9ea333ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_repeats(counter):\n",
    "    \"\"\"Makes a list of keys with values greater than 1.\n",
    "    \n",
    "    counter: dictionary that maps from keys to counts\n",
    "    \n",
    "    returns: list of keys\n",
    "    \"\"\"\n",
    "    return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "bbd6d241",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9b0cbec",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use the following examples to test your code.\n",
    "First, we'll make a dictionary that maps from letters to counts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "ac983c6f",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "counter1 = value_counts('banana')\n",
    "counter1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3aa62942",
   "metadata": {
    "tags": []
   },
   "source": [
    "The result from `find_repeats` should be `['a', 'n']`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "214345d8",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "repeats = find_repeats(counter1)\n",
    "repeats"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3eaf77f8",
   "metadata": {
    "tags": []
   },
   "source": [
    "Here's another example that starts with a list of numbers.\n",
    "The result should be `[1, 2]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "10e9d54a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "counter1 = value_counts([1, 2, 3, 2, 1])\n",
    "repeats = find_repeats(counter1)\n",
    "repeats"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c700d84",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Suppose you run `value_counts` with two different words and save the results in two dictionaries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "c97e2419",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter1 = value_counts('brontosaurus')\n",
    "counter2 = value_counts('apatosaurus')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "deb14c7a",
   "metadata": {},
   "source": [
    "Each dictionary maps from a set of letters to the number of times they appear.\n",
    "Write a function called `add_counters` that takes two dictionaries like this and returns a new dictionary that contains all of the letters and the total number of times they appear in either word.\n",
    "\n",
    "There are many ways to solve this problem.\n",
    "Once you have a working solution, consider asking a virtual assistant for different solutions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "6cf70355",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "6a729a14",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f88110a9",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "A word is \"interlocking\" if we can split it into two words by taking alternating letters.\n",
    "For example, \"schooled\" is an interlocking word because it can be split into \"shoe\" and \"cold\".\n",
    "\n",
    "To select alternating letters from a string, you can use a slice operator with three components that indicate where to start, where to stop, and the \"step size\" between the letters.\n",
    "\n",
    "In the following slice, the first component is `0`, so we start with the first letter.\n",
    "The second component is `None`, which means we should go all the way to the end of the string.\n",
    "And the third component is `2`, so there are two steps between the letters we select."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "56783358",
   "metadata": {},
   "outputs": [],
   "source": [
    "word = 'schooled'\n",
    "first = word[0:None:2]\n",
    "first"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d432332d",
   "metadata": {},
   "source": [
    "Instead of providing `None` as the second component, we can get the same effect by leaving it out altogether.\n",
    "For example, the following slice selects alternating letters, starting with the second letter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "77fa8483",
   "metadata": {},
   "outputs": [],
   "source": [
    "second = word[1::2]\n",
    "second"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8c4e3ba",
   "metadata": {},
   "source": [
    "Write a function called `is_interlocking` that takes a word as an argument and returns `True` if it can be split into two interlocking words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "e5e1030c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2787f786",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use the following loop to find the interlocking words in the word list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "e04a5c73",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ced5aa90",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a7f4edf8",
   "metadata": {
    "tags": []
   },
   "source": [
    "[Think Python: 3rd Edition](https://allendowney.github.io/ThinkPython/index.html)\n",
    "\n",
    "Copyright 2024 [Allen B. Downey](https://allendowney.com)\n",
    "\n",
    "Code license: [MIT License](https://mit-license.org/)\n",
    "\n",
    "Text license: [Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-nc-sa/4.0/)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}