chapters/chap11.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": 1,
   "id": "295ac6d7",
   "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": "5705b2a6",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Tuples\n",
    "\n",
    "This chapter introduces one more built-in type, the tuple, and then shows how lists, dictionaries, and tuples work together.\n",
    "It also presents tuple assignment and a useful feature for functions with variable-length argument lists: the packing and unpacking operators.\n",
    "\n",
    "In the exercises, we'll use tuples, along with lists and dictionaries, to solve more word puzzles and implement efficient algorithms.\n",
    "\n",
    "One note: There are two ways to pronounce \"tuple\".\n",
    "Some people say \"tuh-ple\", which rhymes with \"supple\".\n",
    "But in the context of programming, most people say \"too-ple\", which rhymes with \"quadruple\"."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19474596",
   "metadata": {},
   "source": [
    "## Tuples are like lists\n",
    "\n",
    "A tuple is a sequence of values. The values can be any type, and they are indexed by integers, so tuples are a lot like lists.\n",
    "The important difference is that tuples are immutable.\n",
    "\n",
    "To create a tuple, you can write a comma-separated list of values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "fb0bdca2",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = 'l', 'u', 'p', 'i', 'n'\n",
    "type(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2ec15d8",
   "metadata": {},
   "source": [
    "Although it is not necessary, it is common to enclose tuples in parentheses."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "5a6da881",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = ('l', 'u', 'p', 'i', 'n')\n",
    "type(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9194a159",
   "metadata": {},
   "source": [
    "To create a tuple with a single element, you have to include a final comma."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e2596ca7",
   "metadata": {},
   "outputs": [],
   "source": [
    "t1 = 'p',\n",
    "type(t1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e39b95a5",
   "metadata": {},
   "source": [
    "A single value in parentheses is not a tuple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a0d350a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "t2 = ('p')\n",
    "type(t2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a64bfb64",
   "metadata": {},
   "source": [
    "Another way to create a tuple is the built-in function `tuple`. With no\n",
    "argument, it creates an empty tuple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c9100ee4",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = tuple()\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3447831",
   "metadata": {},
   "source": [
    "If the argument is a sequence (string, list or tuple), the result is a\n",
    "tuple with the elements of the sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "44bd3d83",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = tuple('lupin')\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e48b980",
   "metadata": {},
   "source": [
    "Because `tuple` is the name of a built-in function, you should avoid using it as a variable name.\n",
    "\n",
    "Most list operators also work with tuples.\n",
    "For example, the bracket operator indexes an element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "92e55b2c",
   "metadata": {},
   "outputs": [],
   "source": [
    "t[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f702785",
   "metadata": {},
   "source": [
    "And the slice operator selects a range of elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "38ee5c2a",
   "metadata": {},
   "outputs": [],
   "source": [
    "t[1:3]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9ed9af2",
   "metadata": {},
   "source": [
    "The `+` operator concatenates tuples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "2e0e311a",
   "metadata": {},
   "outputs": [],
   "source": [
    "tuple('lup') + ('i', 'n')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d7dcd6d",
   "metadata": {},
   "source": [
    "And the `*` operator duplicates a tuple a given number of times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "8bb7d715",
   "metadata": {},
   "outputs": [],
   "source": [
    "tuple('spam') * 2 "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a53ce8bd",
   "metadata": {},
   "source": [
    "The `sorted` function works with tuples -- but the result is a list, not a tuple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "e653e00f",
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50e5cadc",
   "metadata": {},
   "source": [
    "The `reversed` function also works with tuples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "8969188d",
   "metadata": {},
   "outputs": [],
   "source": [
    "reversed(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6d973c5",
   "metadata": {},
   "source": [
    "The result is a `reversed` object, which we can convert to a list or tuple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "65d7ebaa",
   "metadata": {},
   "outputs": [],
   "source": [
    "tuple(reversed(t))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7cb9ee6",
   "metadata": {},
   "source": [
    "Based on the examples so far, it might seem like tuples are the same as lists."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c3f381e",
   "metadata": {},
   "source": [
    "## But tuples are immutable\n",
    "\n",
    "If you try to modify a tuple with the bracket operator, you get a `TypeError`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "b4970fe0",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%expect TypeError\n",
    "t[0] = 'L'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "592ce99c",
   "metadata": {},
   "source": [
    "And tuples don't have any of the methods that modify lists, like `append` and `remove`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "772738cc",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%expect AttributeError\n",
    "\n",
    "t.remove('l')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70772ba2",
   "metadata": {},
   "source": [
    "Recall that an \"attribute\" is a variable or method associated with an object -- this error message means that tuples don't have a method named `remove`.\n",
    "\n",
    "Because tuples are immutable, they are hashable, which means they can be used as keys in a dictionary.\n",
    "For example, the following dictionary contains two tuples as keys that map to integers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "37e67042",
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {}\n",
    "d[1, 2] = 3\n",
    "d[3, 4] = 7"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47ba17ab",
   "metadata": {},
   "source": [
    "We can look up a tuple in a dictionary like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "d809a490",
   "metadata": {},
   "outputs": [],
   "source": [
    "d[1, 2]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2c0a354",
   "metadata": {},
   "source": [
    "Or if we have a variable that refers to a tuple, we can use it as a key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "dfc42a8b",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = (3, 4)\n",
    "d[t]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ea8fc3c",
   "metadata": {},
   "source": [
    "Tuples can also appear as values in a dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "2debf30c",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = tuple('abc')\n",
    "d = {'key': t}\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25655ab3",
   "metadata": {},
   "source": [
    "## Tuple assignment\n",
    "\n",
    "You can put a tuple of variables on the left side of an assignment, and a tuple of values on the right."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "1e94ea37",
   "metadata": {},
   "outputs": [],
   "source": [
    "a, b = 1, 2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92c00ceb",
   "metadata": {},
   "source": [
    "The values are assigned to the variables from left to right -- in this example, `a` gets the value `1` and `b` gets the value `2`.\n",
    "We can display the results like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "99c96c7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "a, b"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6362b36e",
   "metadata": {},
   "source": [
    "More generally, if the left side of an assignment is a tuple, the right side can be any kind of sequence -- string, list or tuple. \n",
    "For example, to split an email address into a user name and a domain, you could write:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "b67881ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "email = 'monty@python.org'\n",
    "username, domain = email.split('@')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d134a94c",
   "metadata": {},
   "source": [
    "The return value from `split` is a list with two elements -- the first element is assigned to `username`, the second to `domain`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "b4515e2b",
   "metadata": {},
   "outputs": [],
   "source": [
    "username, domain"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a7e3c62",
   "metadata": {},
   "source": [
    "The number of variables on the left and the number of values on the\n",
    "right have to be the same -- otherwise you get a `ValueError`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "8e5b4a14",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%expect ValueError\n",
    "a, b = 1, 2, 3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "808c2928",
   "metadata": {},
   "source": [
    "Tuple assignment is useful if you want to swap the values of two variables.\n",
    "With conventional assignments, you have to use a temporary variable, like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "2389d6de",
   "metadata": {},
   "outputs": [],
   "source": [
    "temp = a\n",
    "a = b\n",
    "b = temp"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98496d02",
   "metadata": {},
   "source": [
    "That works, but with tuple assignment we can do the same thing without a temporary variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "5512edec",
   "metadata": {},
   "outputs": [],
   "source": [
    "a, b = b, a"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a66a87bc",
   "metadata": {},
   "source": [
    "This works because all of the expressions on the right side are evaluated before any of the assignments.\n",
    "\n",
    "We can also use tuple assignment in a `for` statement.\n",
    "For example, to loop through the items in a dictionary, we can use the `items` method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "651ab417",
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {'one': 1, 'two': 2}\n",
    "\n",
    "for item in d.items():\n",
    "    key, value = item\n",
    "    print(key, '->', value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd0d4feb",
   "metadata": {},
   "source": [
    "Each time through the loop, `item` is assigned a tuple that contains a key and the corresponding value.\n",
    "\n",
    "We can write this loop more concisely, like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "2c0b7d47",
   "metadata": {},
   "outputs": [],
   "source": [
    "for key, value in d.items():\n",
    "    print(key, '->', value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0513578",
   "metadata": {},
   "source": [
    "Each time through the loop, a key and the corresponding value are assigned directly to `key` and `value`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efedeb37",
   "metadata": {},
   "source": [
    "## Tuples as return values\n",
    "\n",
    "Strictly speaking, a function can only return one value, but if the\n",
    "value is a tuple, the effect is the same as returning multiple values.\n",
    "For example, if you want to divide two integers and compute the quotient\n",
    "and remainder, it is inefficient to compute `x//y` and then `x%y`. It is\n",
    "better to compute them both at the same time.\n",
    "\n",
    "The built-in function `divmod` takes two arguments and returns a tuple\n",
    "of two values, the quotient and remainder."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "fff80eaa",
   "metadata": {},
   "outputs": [],
   "source": [
    "divmod(7, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33f3c57d",
   "metadata": {},
   "source": [
    "We can use tuple assignment to store the elements of the tuple in two variables. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "4a0eb2a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "quotient, remainder = divmod(7, 3)\n",
    "quotient"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "d74ba1b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "remainder"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15079805",
   "metadata": {},
   "source": [
    "Here is an example of a function that returns a tuple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "dad3b3bb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def min_max(t):\n",
    "    return min(t), max(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43c4e1e0",
   "metadata": {},
   "source": [
    "`max` and `min` are built-in functions that find the largest and smallest elements of a sequence. \n",
    "`min_max` computes both and returns a tuple of two values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "fbd90b0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "min_max([2, 4, 1, 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86b60e71",
   "metadata": {},
   "source": [
    "We can assign the results to variables like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "5a101efb",
   "metadata": {},
   "outputs": [],
   "source": [
    "low, high = min_max([2, 4, 1, 3])\n",
    "low, high"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "112b5aa2",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Argument packing\n",
    "\n",
    "Functions can take a variable number of arguments. \n",
    "A parameter name that begins with the `*` operator **packs** arguments into a tuple.\n",
    "For example, the following function takes any number of arguments and computes their arithmetic mean -- that is, their sum divided by the number of arguments. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "0a33e2d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mean(*args):\n",
    "    return sum(args) / len(args)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6044fc1b",
   "metadata": {},
   "source": [
    "The parameter can have any name you like, but `args` is conventional.\n",
    "We can call the function like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "336a08ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "mean(1, 2, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5e8b158",
   "metadata": {},
   "source": [
    "If you have a sequence of values and you want to pass them to a function as multiple arguments, you can use the `*` operator to **unpack** the tuple.\n",
    "For example, `divmod` takes exactly two arguments -- if you pass a tuple as a parameter, you get an error."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "991810bc",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%expect TypeError\n",
    "t = (7, 3)\n",
    "divmod(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a9110db",
   "metadata": {},
   "source": [
    "Even though the tuple contains two elements, it counts as a single argument.\n",
    "But if you unpack the tuple, it is treated as two arguments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "f25ebee1",
   "metadata": {},
   "outputs": [],
   "source": [
    "divmod(*t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da554863",
   "metadata": {},
   "source": [
    "Packing and unpacking can be useful if you want to adapt the behavior of an existing function.\n",
    "For example, this function takes any number of arguments, removes the lowest and highest, and computes the mean of the rest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "7ad64412",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trimmed_mean(*args):\n",
    "    low, high = min_max(args)\n",
    "    trimmed = list(args)\n",
    "    trimmed.remove(low)\n",
    "    trimmed.remove(high)\n",
    "    return mean(*trimmed)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1e05e49",
   "metadata": {},
   "source": [
    "First it uses `min_max` to find the lowest and highest elements.\n",
    "Then it converts `args` to a list so it can use the `remove` method.\n",
    "Finally it unpacks the list so the elements are passed to `mean` as separate arguments, rather than as a single list.\n",
    "\n",
    "Here's an example that shows the effect."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "b2863701",
   "metadata": {},
   "outputs": [],
   "source": [
    "mean(1, 2, 3, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "cc1afa29",
   "metadata": {},
   "outputs": [],
   "source": [
    "trimmed_mean(1, 2, 3, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35e04996",
   "metadata": {},
   "source": [
    "This kind of \"trimmed\" mean is used in some sports with subjective judging -- like diving and gymnastics -- to reduce the effect of a judge whose score deviates from the others. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4572cd2",
   "metadata": {},
   "source": [
    "## Zip\n",
    "\n",
    "Tuples are useful for looping through the elements of two sequences and performing operations on corresponding elements.\n",
    "For example, suppose two teams play a series of seven games, and we record their scores in two lists, one for each team."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "ad3e6f81",
   "metadata": {},
   "outputs": [],
   "source": [
    "scores1 = [1, 2, 4, 5, 1, 5, 2]\n",
    "scores2 = [5, 5, 2, 2, 5, 2, 3]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b44f228b",
   "metadata": {},
   "source": [
    "Let's see how many games each team won.\n",
    "We'll use `zip`, which is a built-in function that takes two or more sequences and returns a **zip object**, so-called because it pairs up the elements of the sequences like the teeth of a zipper."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "9ce313ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "zip(scores1, scores2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9adcf8f9",
   "metadata": {},
   "source": [
    "We can use the zip object to loop through the values in the sequences pairwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "321d9c30",
   "metadata": {},
   "outputs": [],
   "source": [
    "for pair in zip(scores1, scores2):\n",
    "     print(pair)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51d1dabb",
   "metadata": {},
   "source": [
    "Each time through the loop, `pair` gets assigned a tuple of scores.\n",
    "So we can assign the scores to variables, and count the victories for the first team, like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "7eb73d5d",
   "metadata": {},
   "outputs": [],
   "source": [
    "wins = 0\n",
    "for team1, team2 in zip(scores1, scores2):\n",
    "    if team1 > team2:\n",
    "        wins += 1\n",
    "        \n",
    "wins"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad740fcd",
   "metadata": {},
   "source": [
    "Sadly, the first team won only three games and lost the series.\n",
    "\n",
    "If you have two lists and you want a list of pairs, you can use `zip` and `list`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "9529baa8",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = list(zip(scores1, scores2))\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec4249fa",
   "metadata": {},
   "source": [
    "The result is a list of tuples, so we can get the result of the last game like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "dbde77b8",
   "metadata": {},
   "outputs": [],
   "source": [
    "t[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "436486b9",
   "metadata": {},
   "source": [
    "If you have a list of keys and a list of values, you can use `zip` and `dict` to make a dictionary.\n",
    "For example, here's how we can make a dictionary that maps from each letter to its position in the alphabet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "dbb7d0b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "letters = 'abcdefghijklmnopqrstuvwxyz'\n",
    "numbers = range(len(letters))\n",
    "letter_map = dict(zip(letters, numbers))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4de6974",
   "metadata": {},
   "source": [
    "Now we can look up a letter and get its index in the alphabet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "49e3fd8e",
   "metadata": {},
   "outputs": [],
   "source": [
    "letter_map['a'], letter_map['z']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc632542",
   "metadata": {},
   "source": [
    "In this mapping, the index of `'a'` is `0` and the index of `'z'` is `25`.\n",
    "\n",
    "If you need to loop through the elements of a sequence and their indices, you can use the built-in function `enumerate`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "9e4f3e51",
   "metadata": {},
   "outputs": [],
   "source": [
    "enumerate('abc')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92ad45bb",
   "metadata": {},
   "source": [
    "The result is an **enumerate object** that loops through a sequence of pairs, where each pair contains an index (starting from 0) and an element from the given sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "c1dcb46d",
   "metadata": {},
   "outputs": [],
   "source": [
    "for index, element in enumerate('abc'):\n",
    "    print(index, element)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf0b55d7",
   "metadata": {},
   "source": [
    "## Comparing and Sorting\n",
    "\n",
    "The relational operators work with tuples and other sequences.\n",
    "For example, if you use the `<` operator with tuples, it starts by comparing the first element from each sequence.\n",
    "If they are equal, it goes on to the next pair of elements, and so on, until it finds a pair that differ. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "aed20c28",
   "metadata": {},
   "outputs": [],
   "source": [
    "(0, 1, 2) < (0, 3, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65ceea86",
   "metadata": {},
   "source": [
    "Subsequent elements are not considered -- even if they are really big."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "4d9e73b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "(0, 1, 2000000) < (0, 3, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55e4a35e",
   "metadata": {},
   "source": [
    "This way of comparing tuples is useful for sorting a list of tuples, or finding the minimum or maximum.\n",
    "As an example, let's find the most common letter in a word.\n",
    "In the previous chapter, we wrote `value_counts`, which takes a string and returns a dictionary that maps from each letter to the number of times it appears."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "2077dfa9",
   "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": "a80012c1",
   "metadata": {},
   "source": [
    "Here is the result for the string `'banana'`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "b3d40516",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter = value_counts('banana')\n",
    "counter"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc1ea4a7",
   "metadata": {},
   "source": [
    "With only three items, we can easily see that the most frequent letter is `'a'`, which appears three times.\n",
    "But if there were more items, it would be useful to sort them automatically.\n",
    "\n",
    "We can get the items from `counter` like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "8288c28f",
   "metadata": {},
   "outputs": [],
   "source": [
    "items = counter.items()\n",
    "items"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac8dea7a",
   "metadata": {},
   "source": [
    "The result is a `dict_items` object that behaves like a list of tuples, so we can sort it like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "bbbade35",
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(items)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b690d17a",
   "metadata": {},
   "source": [
    "The default behavior is to use the first element from each tuple to sort the list, and use the second element to break ties.\n",
    "\n",
    "However, to find the items with the highest counts, we want to use the second element to sort the list.\n",
    "We can do that by writing a function that takes a tuple and returns the second element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "a4c31795",
   "metadata": {},
   "outputs": [],
   "source": [
    "def second_element(t):\n",
    "    return t[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b964aa14",
   "metadata": {},
   "source": [
    "Then we can pass that function to `sorted` as an optional argument called `key`, which indicates that this function should be used to compute the **sort key** for each item."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "f3d3619a",
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted_items = sorted(items, key=second_element)\n",
    "sorted_items"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4dc96848",
   "metadata": {},
   "source": [
    "The sort key determines the order of the items in the list.\n",
    "The letter with the lowest count appears first, and the letter with the highest count appears last.\n",
    "So we can find the most common letter like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "f078c8a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted_items[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0d8b999",
   "metadata": {},
   "source": [
    "If we only want the maximum, we don't have to sort the list.\n",
    "We can use `max`, which also takes `key` as an optional argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "54030d8f",
   "metadata": {},
   "outputs": [],
   "source": [
    "max(items, key=second_element)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a8327df",
   "metadata": {},
   "source": [
    "To find the letter with the lowest count, we could use `min` the same way."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a62394a5",
   "metadata": {},
   "source": [
    "## Inverting a dictionary\n",
    "\n",
    "Suppose you want to invert a dictionary so you can look up a value and get the corresponding key.\n",
    "For example, if you have a word counter that maps from each word to the number of times it appears, you could make a dictionary that maps from integers to the words that appear that number of times.\n",
    "\n",
    "But there's a problem -- the keys in a dictionary have to be unique, but the values don't. For example, in a word counter, there could be many words with the same count.\n",
    "\n",
    "So one way to invert a dictionary is to create a new dictionary where the values are lists of keys from the original.\n",
    "As an example, let's count the letters in `parrot`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "ef158f81",
   "metadata": {},
   "outputs": [],
   "source": [
    "d =  value_counts('parrot')\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4570eae",
   "metadata": {},
   "source": [
    "If we invert this dictionary, the result should be `{1: ['p', 'a', 'o', 't'], 2: ['r']}`, which indicates that the letters that appear once are `'p'`, `'a'`, `'o'`, and `'t'`, and the letter than appears twice is `'r'`.\n",
    "\n",
    "The following function takes a dictionary and returns its inverse as a new dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "d3607b8d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def invert_dict(d):\n",
    "    new = {}\n",
    "    for key, value in d.items():\n",
    "        if value not in new:\n",
    "            new[value] = [key]\n",
    "        else:\n",
    "            new[value].append(key)\n",
    "    return new"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca5fa025",
   "metadata": {},
   "source": [
    "The `for` statement loops through the keys and values in `d`.\n",
    "If the value is not already in the new dictionary, it is added and associated with a list that contains a single element.\n",
    "Otherwise it is appended to the existing list.\n",
    "\n",
    "We can test it like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "692d9cf8",
   "metadata": {},
   "outputs": [],
   "source": [
    "invert_dict(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cfb1693",
   "metadata": {},
   "source": [
    "And we get the result we expected.\n",
    "\n",
    "This is the first example we've seen where the values in the dictionary are lists.\n",
    "We will see more!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d138cd7",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Debugging\n",
    "\n",
    "Lists, dictionaries and tuples are **data structures**.\n",
    "In this chapter we are starting to see compound data structures, like lists of tuples, or dictionaries that contain tuples as keys and lists as values.\n",
    "Compound data structures are useful, but they are prone to errors caused when a data structure has the wrong type, size, or structure.\n",
    "For example, if a function expects a list if integers and you give it a plain old integer\n",
    "(not in a list), it probably won't work.\n",
    "\n",
    "To help debug these kinds of errors, I wrote a module called `structshape` that provides a function, also called `structshape`, that takes any kind of data structure as an argument and returns a string that summarizes its structure.\n",
    "You can download it from\n",
    "<https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/structshape.py>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "e9f03e91",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/structshape.py');"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "646f4d55",
   "metadata": {},
   "source": [
    "We can import it like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "90ab624a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from structshape import structshape"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86cc6ccc",
   "metadata": {},
   "source": [
    "Here's an example with a simple list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "6794330f",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = [1, 2, 3]\n",
    "structshape(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9de4f6ec",
   "metadata": {},
   "source": [
    "Here's a list of lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "54cd185b",
   "metadata": {},
   "outputs": [],
   "source": [
    "t2 = [[1,2], [3,4], [5,6]]\n",
    "structshape(t2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aced9984",
   "metadata": {},
   "source": [
    "If the elements of the list are not the same type, `structshape` groups\n",
    "them by type."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "04028afd",
   "metadata": {},
   "outputs": [],
   "source": [
    "t3 = [1, 2, 3, 4.0, '5', '6', [7], [8], 9]\n",
    "structshape(t3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f63ff690",
   "metadata": {},
   "source": [
    "Here's a list of tuples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "b5d45c88",
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 'abc'\n",
    "lt = list(zip(t, s))\n",
    "structshape(lt)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9ec67eb",
   "metadata": {},
   "source": [
    "And here's a dictionary with three items that map integers to strings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "15131907",
   "metadata": {},
   "outputs": [],
   "source": [
    "d = dict(lt) \n",
    "structshape(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f29bb82b",
   "metadata": {},
   "source": [
    "If you are having trouble keeping track of your data structures,\n",
    "`structshape` can help."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79d93082",
   "metadata": {},
   "source": [
    "## Glossary\n",
    "\n",
    "**pack:**\n",
    "Collect multiple arguments into a tuple.\n",
    "\n",
    "**unpack:**\n",
    "Treat a tuple (or other sequence) as multiple arguments.\n",
    "\n",
    "**zip object:**\n",
    "The result of calling the built-in function `zip`, can be used to loop through a sequence of tuples.\n",
    "\n",
    "**enumerate object:**\n",
    "The result of calling the built-in function `enumerate`, can be used to loop through a sequence of tuples.\n",
    "\n",
    "**sort key:**\n",
    "A value, or function that computes a value, used to sort the elements of a collection.\n",
    "\n",
    "**data structure:**\n",
    "A collection of values, organized to perform certain operations efficiently."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1471b3c0",
   "metadata": {},
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "c65d68d2",
   "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": "97a0352d",
   "metadata": {},
   "source": [
    "### Ask a virtual assistant\n",
    "\n",
    "The exercises in this chapter might be more difficult than exercises in previous chapters, so I encourage you to get help from a virtual assistant.\n",
    "When you pose more difficult questions, you might find that the answers are not correct on the first attempt, so this is a chance to practice crafting good prompts and following up with good refinements.\n",
    "\n",
    "One strategy you might consider is to break a big problems into pieces that can be solved with simple functions.\n",
    "Ask the virtual assistant to write the functions and test them.\n",
    "Then, once they are working, ask for a solution to the original problem.\n",
    "\n",
    "For some of the exercises below, I make suggestions about which data structures and algorithms to use.\n",
    "You might find these suggestions useful when you work on the problems, but they are also good prompts to pass along to a virtual assistant."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f90e011f",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "In this chapter I said that tuples can be used as keys in dictionaries because they are hashable, and they are hashable because they are immutable.\n",
    "But that is not always true.\n",
    "\n",
    "If a tuple contains a mutable value, like a list or a dictionary, the tuple is no longer hashable because it contains elements that are not hashable. As an example, here's a tuple that contains two lists of integers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "4416fe4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "list0 = [1, 2, 3]\n",
    "list1 = [4, 5]\n",
    "\n",
    "t = (list0, list1)\n",
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02799077",
   "metadata": {},
   "source": [
    "Write a line of code that appends the value `6` to the end of the second list in `t`. If you display `t`, the result should be `([1, 2, 3], [4, 5, 6])`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "e6eda0e4",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "644b1dfb",
   "metadata": {},
   "source": [
    "Try to create a dictionary that maps from `t` to a string, and confirm that you get a `TypeError`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "4fae1acc",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb77a352",
   "metadata": {},
   "source": [
    "For more on this topic, ask a virtual assistant, \"Are Python tuples always hashable?\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bdfc8c27",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Exercise\n",
    "\n",
    "In this chapter we made a dictionary that maps from each letter to its index in the alphabet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "855c7ed2",
   "metadata": {},
   "outputs": [],
   "source": [
    "letters = 'abcdefghijklmnopqrstuvwxyz'\n",
    "numbers = range(len(letters))\n",
    "letter_map = dict(zip(letters, numbers))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8cd720b",
   "metadata": {},
   "source": [
    "For example, the index of `'a'` is `0`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "3c921f68",
   "metadata": {},
   "outputs": [],
   "source": [
    "letter_map['a']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a04c25db",
   "metadata": {},
   "source": [
    "To go in the other direction, we can use list indexing.\n",
    "For example, the letter at index `1` is `'b'`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "b029b0da",
   "metadata": {},
   "outputs": [],
   "source": [
    "letters[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "165ab770",
   "metadata": {},
   "source": [
    "We can use `letter_map` and `letters` to encode and decode words using a Caesar cipher.\n",
    "\n",
    "A Caesar cipher is a weak form of encryption that involves shifting each letter\n",
    "by a fixed number of places in the alphabet, wrapping around to the beginning if necessary. For example, `'a'` shifted by 2 is `'c'` and `'z'` shifted by 1 is `'a'`.\n",
    "\n",
    "Write a function called `shift_word` that takes as parameters a string and an integer, and returns a new string that contains the letters from the string shifted by the given number of places.\n",
    "\n",
    "To test your function, confirm that \"cheer\" shifted by 7 is \"jolly\" and \"melon\" shifted by 16 is \"cubed\".\n",
    "\n",
    "Hints: Use the modulus operator to wrap around from `'z'` back to `'a'`. \n",
    "Loop through the letters of the word, shift each one, and append the result to a list of letters.\n",
    "Then use `join` to concatenate the letters into a string."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7478b18",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use this outline to get started."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "1cc07036",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def shift_word(word, n):\n",
    "    \"\"\"Shift the letters of `word` by `n` places.\n",
    "    \n",
    "    >>> shift_word('cheer', 7)\n",
    "    'jolly'\n",
    "    >>> shift_word('melon', 16)\n",
    "    'cubed'\n",
    "    \"\"\"\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "96560a0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "c026c6d1",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "shift_word('cheer', 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "5814999d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "shift_word('melon', 16)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39a67af9",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use `doctest` to test your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "9464d140",
   "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(shift_word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "779f13af",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Write a function called `most_frequent_letters` that takes a string and prints the letters in decreasing order of frequency.\n",
    "\n",
    "To get the items in decreasing order, you can use `reversed` along with `sorted` or you can pass `reverse=True` as a keyword parameter to `sorted`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d71923e6",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use this outline of the function to get started."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "4309d0b5",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def most_frequent_letters(string):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "52228828",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6354c44",
   "metadata": {
    "tags": []
   },
   "source": [
    "And this example to test your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "3bf2aa0d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "most_frequent_letters('brontosaurus')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ca1e337",
   "metadata": {
    "tags": []
   },
   "source": [
    "Once your function is working, you can use the following code to print the most common letters in *Dracula*, which we can download from Project Gutenberg."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "e4fbf5d9",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "download('https://www.gutenberg.org/cache/epub/345/pg345.txt');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "817ec689",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "string = open('pg345.txt').read()\n",
    "most_frequent_letters(string)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "211c09c9",
   "metadata": {
    "tags": []
   },
   "source": [
    "According to Zim's \"Codes and Secret Writing\", the sequence of letters in decreasing order of frequency in English starts with \"ETAONRISH\".\n",
    "How does this sequence compare with the results from *Dracula*?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cbe9933e",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "In a previous exercise, we tested whether two strings are anagrams by sorting the letters in both words and checking whether the sorted letters are the same.\n",
    "Now let's make the problem a little more challenging.\n",
    "\n",
    "We'll write a program that takes a list of words and prints all the sets of words that are anagrams.\n",
    "Here is an example of what the output might look like:\n",
    "\n",
    "    ['deltas', 'desalt', 'lasted', 'salted', 'slated', 'staled']\n",
    "    ['retainers', 'ternaries']\n",
    "    ['generating', 'greatening']\n",
    "    ['resmelts', 'smelters', 'termless']\n",
    "\n",
    "Hint: For each word in the word list, sort the letters and join them back into a string. Make a dictionary that maps from this sorted string to a list of words that are anagrams of it."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b9ed2a8",
   "metadata": {
    "tags": []
   },
   "source": [
    "The following cells download `words.txt` and read the words into a list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "941719c1",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "d2ec641b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "word_list = open('words.txt').read().split()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4cc2c8c",
   "metadata": {
    "tags": []
   },
   "source": [
    "Here's the `sort_word` function we've used before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "7ae29f73",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def sort_word(word):\n",
    "    return ''.join(sorted(word))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "013819a5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70faa9f5",
   "metadata": {
    "tags": []
   },
   "source": [
    "To find the longest list of anagrams, you can use the following function, which takes a key-value pair where the key is a string and the value is a list of words.\n",
    "It returns the length of the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "fbf9ede3",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def value_length(pair):\n",
    "    key, value = pair\n",
    "    return len(value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dcda6e28",
   "metadata": {
    "tags": []
   },
   "source": [
    "We can use this function as a sort key to find the longest lists of anagrams."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "55435050",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "anagram_items = sorted(anagram_dict.items(), key=value_length)\n",
    "for key, value in anagram_items[-10:]:\n",
    "    print(value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b6d5add",
   "metadata": {
    "tags": []
   },
   "source": [
    "If you want to know the longest words that have anagrams, you can use the following loop to print some of them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "6a9320c2",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "longest = 7\n",
    "\n",
    "for key, value in anagram_items:\n",
    "    if len(value) > 1:\n",
    "        word_len = len(value[0])\n",
    "        if word_len > longest:\n",
    "            longest = word_len\n",
    "            print(value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4fbe939e",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Write a function called `word_distance` that takes two words with the same length and returns the number of places where the two words differ.\n",
    "\n",
    "Hint: Use `zip` to loop through the corresponding letters of the words."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b48dbdc",
   "metadata": {
    "tags": []
   },
   "source": [
    "Here's an outline of the function with doctests you can use to check your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "3d5a75f8",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def word_distance(word1, word2):\n",
    "    \"\"\"Computes the number of places where two word differ.\n",
    "\n",
    "    >>> word_distance(\"hello\", \"hxllo\")\n",
    "    1\n",
    "    >>> word_distance(\"ample\", \"apply\")\n",
    "    2\n",
    "    >>> word_distance(\"kitten\", \"mutton\")\n",
    "    3\n",
    "    \"\"\"\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "id": "a9816dde",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "id": "753a23c1",
   "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(word_distance)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "066eec59",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "\"Metathesis\" is the transposition of letters in a word.\n",
    "Two words form a \"metathesis pair\" if you can transform one into the other by swapping two letters, like `converse` and `conserve`.\n",
    "Write a program that finds all of the metathesis pairs in the word list. \n",
    "\n",
    "Hint: The words in a metathesis pair must be anagrams of each other.\n",
    "\n",
    "Credit: This exercise is inspired by an example at <http://puzzlers.org>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "57649075",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a028806",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Exercise\n",
    "\n",
    "This is a bonus exercise that is not in the book.\n",
    "It is more challenging than the other exercises in this chapter, so you might want to ask a virtual assistant for help, or come back to it after you've read a few more chapters.\n",
    "\n",
    "Here's another Car Talk Puzzler\n",
    "(<http://www.cartalk.com/content/puzzlers>):\n",
    "\n",
    "> What is the longest English word, that remains a valid English word,\n",
    "> as you remove its letters one at a time?\n",
    ">\n",
    "> Now, letters can be removed from either end, or the middle, but you\n",
    "> can't rearrange any of the letters. Every time you drop a letter, you\n",
    "> wind up with another English word. If you do that, you're eventually\n",
    "> going to wind up with one letter and that too is going to be an\n",
    "> English word---one that's found in the dictionary. I want to know\n",
    "> what's the longest word and how many letters does it have?\n",
    ">\n",
    "> I'm going to give you a little modest example: Sprite. Ok? You start\n",
    "> off with sprite, you take a letter off, one from the interior of the\n",
    "> word, take the r away, and we're left with the word spite, then we\n",
    "> take the e off the end, we're left with spit, we take the s off, we're\n",
    "> left with pit, it, and I.\n",
    "\n",
    "Write a program to find all words that can be reduced in this way, and\n",
    "then find the longest one.\n",
    "\n",
    "This exercise is a little more challenging than most, so here are some\n",
    "suggestions:\n",
    "\n",
    "1.  You might want to write a function that takes a word and computes a\n",
    "    list of all the words that can be formed by removing one letter.\n",
    "    These are the \"children\" of the word.\n",
    "\n",
    "2.  Recursively, a word is reducible if any of its children are\n",
    "    reducible. As a base case, you can consider the empty string\n",
    "    reducible.\n",
    "\n",
    "3.  The word list we've been using doesn't contain single letter\n",
    "    words. So you might have to add \"I\" and \"a\".\n",
    "\n",
    "4.  To improve the performance of your program, you might want to\n",
    "    memoize the words that are known to be reducible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "id": "c19bf833",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "2d9764d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "5e4f5d8e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "27d311dd",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "id": "68c27c7e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a34c2014",
   "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
}