\n",
"\n",
""
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "f0c8eb18",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"from os.path import basename, exists\n",
"\n",
"def download(url):\n",
" \"\"\"Download a file if it isn't already here, and return its filename.\"\"\"\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/porttack/working-in-python/raw/v3/working_in_python.py');\n",
"download('https://github.com/AllenDowney/ThinkPython/raw/v3/diagram.py');\n",
"\n",
"import working_in_python\n",
"# apcsp:begin type=\"note\" chapter=\"07\"\n",
"working_in_python.enable_docstring_reminders()\n",
"# apcsp:end"
]
},
{
"cell_type": "markdown",
"id": "a81d9ad2-9a47-4872-bf65-5a8dfb09c32f",
"metadata": {
"tags": []
},
"source": [
"# Iteration and Search\n",
"\n",
"In 1939 Ernest Vincent Wright published a 50,000 word novel called *Gadsby* that does not contain the letter \"e\". Since \"e\" is the most common letter in English, writing even a few words without using it is difficult.\n",
"To get a sense of how difficult, in this chapter we'll compute the fraction of English words have at least one \"e\".\n",
"\n",
"For that, we'll use `for` statements to loop through the letters in a string and the words in a file, and we'll update variables in a loop to count the number of words that contain an \"e\".\n",
"We'll use the `in` operator to check whether a letter appears in a word, and you'll learn a programming pattern called a \"linear search\".\n",
"\n",
"As an exercise, you'll use these tools to solve a word puzzle called \"Spelling Bee\"."
]
},
{
"cell_type": "markdown",
"id": "389f5162-0a8c-4cc7-99f1-a261e0b39006",
"metadata": {},
"source": [
"## Loops and strings\n",
"\n",
"In Chapter 3 we saw a `for` loop that uses the `range` function to display a sequence of numbers."
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "6b8569b8-1576-45d2-99f6-c7a2c7e100c4",
"metadata": {},
"outputs": [],
"source": [
"for i in range(3):\n",
" print(i, end=' ')"
]
},
{
"cell_type": "markdown",
"id": "937a0af9-5486-4195-8e59-6f819db1cf3f",
"metadata": {},
"source": [
"This version uses the keyword argument `end` so the `print` function puts a space after each number rather than a newline.\n",
"\n",
"We can also use a `for` loop to display the letters in a string."
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "6cb5b573-601c-42f5-a940-f1a4d244f990",
"metadata": {},
"outputs": [],
"source": [
"for letter in 'Gadsby':\n",
" print(letter, end=' ')"
]
},
{
"cell_type": "markdown",
"id": "72044436-ed85-407b-8821-9696648ec29c",
"metadata": {},
"source": [
"Notice that I changed the name of the variable from `i` to `letter`, which provides more information about the value it refers to.\n",
"The variable defined in a `for` loop is called the **loop variable**.\n",
"\n",
"Now that we can loop through the letters in a word, we can check whether it contains the letter \"e\"."
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "7040a890-6619-4ad2-b0bf-b094a5a0e43d",
"metadata": {},
"outputs": [],
"source": [
"for letter in \"Gadsby\":\n",
" if letter == 'E' or letter == 'e':\n",
" print('This word has an \"e\"')"
]
},
{
"cell_type": "markdown",
"id": "644b7df2-4528-48d9-a003-2d21fbefbaab",
"metadata": {},
"source": [
"Before we go on, let's encapsulate that loop in a function."
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "40fd553c-693c-4ffc-8e49-1d7de3c4d4a7",
"metadata": {},
"outputs": [],
"source": [
"def has_e():\n",
" for letter in \"Gadsby\":\n",
" if letter == 'E' or letter == 'e':\n",
" print('This word has an \"e\"')"
]
},
{
"cell_type": "markdown",
"id": "31cfacd9-5721-457a-be40-80cf002723b2",
"metadata": {},
"source": [
"And let's make it a pure function that return `True` if the word contains an \"e\" and `False` otherwise."
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "8a34174b-5a77-482a-8480-14cfdff16339",
"metadata": {},
"outputs": [],
"source": [
"def has_e():\n",
" for letter in \"Gadsby\":\n",
" if letter == 'E' or letter == 'e':\n",
" return True\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "8f45502e-6db3-4fcc-802c-c97398787dbd",
"metadata": {},
"source": [
"We can generalize it to take the word as a parameter."
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "0909121d-5218-49ca-b03e-258206f00e40",
"metadata": {},
"outputs": [],
"source": [
"def has_e(word):\n",
" for letter in word:\n",
" if letter == 'E' or letter == 'e':\n",
" return True\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "590f4399-16d3-4f1c-93bc-b1fe7ce46633",
"metadata": {},
"source": [
"Now we can test it like this:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "3c4d8138-ddf6-46fe-a940-a7042617ceb1",
"metadata": {},
"outputs": [],
"source": [
"has_e('Gadsby')"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "5c463051-b737-49ab-a1d7-4be66fd8331f",
"metadata": {},
"outputs": [],
"source": [
"has_e('Emma')"
]
},
{
"cell_type": "markdown",
"id": "8adf1e92-435e-4b54-837a-bad603ebcafd",
"metadata": {},
"source": [
"## Reading the word list\n",
"\n",
"To see how many words contain an \"e\", we'll need a word list.\n",
"The one we'll use is a list of about 114,000 official crosswords; that is, words that are considered valid in crossword puzzles and other word games. "
]
},
{
"cell_type": "markdown",
"id": "0e3d1c79-5436-42ac-9e29-82fc59936263",
"metadata": {
"tags": []
},
"source": [
"The following cell downloads the word list, which is a modified version of a list collected and contributed to the public domain by Grady Ward as part of the Moby lexicon project (see )."
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "a7b7ac52-64a6-4dd9-98f5-b772a5e0f161",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt');"
]
},
{
"cell_type": "markdown",
"id": "5b383a3c-d173-4a66-bf86-23b329032004",
"metadata": {},
"source": [
"The word list is in a file called `words.txt`, which is downloaded in the notebook for this chapter.\n",
"To read it, we'll use the built-in function `open`, which takes the name of the file as a parameter and returns a **file object** we can use to read the file."
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "1ad13ce7-99be-4412-8e0b-978fe6de25f2",
"metadata": {},
"outputs": [],
"source": [
"file_object = open('words.txt')"
]
},
{
"cell_type": "markdown",
"id": "4414d9b1-cb8e-472e-818c-0555e29b1ad5",
"metadata": {},
"source": [
"The file object provides a function called `readline`, which reads characters from the file until it gets to a newline and returns the result as a string:"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "dc2054e6-d8e8-4a06-a1ea-5cfcf4ccf1e0",
"metadata": {},
"outputs": [],
"source": [
"file_object.readline()"
]
},
{
"cell_type": "markdown",
"id": "d74e9fe9-117e-436a-ade3-3d08dfda2a00",
"metadata": {},
"source": [
"Notice that the syntax for calling `readline` is different from functions we've seen so far. That's because it is a **method**, which is a function associated with an object.\n",
"In this case `readline` is associated with the file object, so we call it using the name of the object, the dot operator, and the name of the method.\n",
"\n",
"The first word in the list is \"aa\", which is a kind of lava.\n",
"The sequence `\\n` represents the newline character that separates this word from the next.\n",
"\n",
"The file object keeps track of where it is in the file, so if you call\n",
"`readline` again, you get the next word:"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "eaea1520-0fb3-4ef3-be6e-9e1cdcccf39f",
"metadata": {},
"outputs": [],
"source": [
"line = file_object.readline()\n",
"line"
]
},
{
"cell_type": "markdown",
"id": "cd466fdb-38ce-4e5b-92c7-05dc23922005",
"metadata": {},
"source": [
"To remove the newline from the end of the word, we can use `strip`, which is a method associated with strings, so we can call it like this."
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "f602bfb6-7a93-4fb8-ade6-6784155a6f1a",
"metadata": {},
"outputs": [],
"source": [
"word = line.strip()\n",
"word"
]
},
{
"cell_type": "markdown",
"id": "6dda6bac-e02e-47ee-9bab-70cef8c27d7a",
"metadata": {},
"source": [
"`strip` removes whitespace characters -- including spaces, tabs, and newlines -- from the beginning and end of the string.\n",
"\n",
"You can also use a file object as part of a `for` loop. \n",
"This program reads `words.txt` and prints each word, one per line:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "cf3b8b7e-5fc7-4bb1-b628-09277bdc5a0d",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"for line in open('words.txt'):\n",
" word = line.strip()\n",
" print(word)"
]
},
{
"cell_type": "markdown",
"id": "93e320a5-4827-487e-a8ce-216392f398a8",
"metadata": {},
"source": [
"Now that we can read the word list, the next step is to count them.\n",
"For that, we will need the ability to update variables."
]
},
{
"cell_type": "markdown",
"id": "b63a6877",
"metadata": {},
"source": [
"## Updating variables\n",
"\n",
"As you may have discovered, it is legal to make more than one assignment\n",
"to the same variable.\n",
"A new assignment makes an existing variable refer to a new value (and stop referring to the old value).\n",
"\n",
"For example, here is an initial assignment that creates a variable."
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "6bf8a104",
"metadata": {},
"outputs": [],
"source": [
"x = 5\n",
"x"
]
},
{
"cell_type": "markdown",
"id": "c9735982",
"metadata": {},
"source": [
"And here is an assignment that changes the value of a variable."
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "0fe7ae60",
"metadata": {},
"outputs": [],
"source": [
"x = 7\n",
"x"
]
},
{
"cell_type": "markdown",
"id": "fbcd1092-ce06-47fc-9204-fce1c9a100a5",
"metadata": {},
"source": [
"The following figure shows what these assignments looks like in a state diagram."
]
},
{
"cell_type": "code",
"execution_count": 18,
"id": "8a09bc24",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"from diagram import make_rebind, draw_bindings\n",
"\n",
"bindings = make_rebind('x', [5, 7])"
]
},
{
"cell_type": "code",
"execution_count": 19,
"id": "36a45674-7f41-4850-98f1-2548574ce958",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"from diagram import diagram, adjust\n",
"\n",
"width, height, x, y = [0.54, 0.61, 0.07, 0.45]\n",
"ax = diagram(width, height)\n",
"bbox = draw_bindings(bindings, ax, x, y)\n",
"# adjust(x, y, bbox)"
]
},
{
"cell_type": "markdown",
"id": "42b7b044-f83b-4483-9a24-64980c688c94",
"metadata": {},
"source": [
"The dotted arrow indicates that `x` no longer refers to `5`.\n",
"The solid arrow indicates that it now refers to `7`.\n",
"\n",
"A common kind of assignment is an **update**, where the new value of\n",
"the variable depends on the old."
]
},
{
"cell_type": "code",
"execution_count": 20,
"id": "ba2ab90b",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"x = 7"
]
},
{
"cell_type": "code",
"execution_count": 21,
"id": "88496dc4",
"metadata": {},
"outputs": [],
"source": [
"x = x + 1\n",
"x"
]
},
{
"cell_type": "markdown",
"id": "d3025706",
"metadata": {},
"source": [
"This statement means \"get the current value of `x`, add one, and assign the result back to `x`.\"\n",
"\n",
"If you try to update a variable that doesn't exist, you get an error, because Python evaluates the expression on the right before it assigns a value to the variable on the left."
]
},
{
"cell_type": "code",
"execution_count": 22,
"id": "4a0c46b9",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"\n",
"z = z + 1"
]
},
{
"cell_type": "markdown",
"id": "03d3959f",
"metadata": {},
"source": [
"Before you can update a variable, you have to **initialize** it, usually\n",
"with a simple assignment:"
]
},
{
"cell_type": "code",
"execution_count": 23,
"id": "2220d826",
"metadata": {},
"outputs": [],
"source": [
"z = 0\n",
"z = z + 1\n",
"z"
]
},
{
"cell_type": "markdown",
"id": "374fb3d5",
"metadata": {},
"source": [
"Increasing the value of a variable is called an **increment**; decreasing the value is called a **decrement**.\n",
"Because these operations are so common, Python provides **augmented assignment operators** that update a variable more concisely.\n",
"For example, the `+=` operator increments a variable by the given amount."
]
},
{
"cell_type": "code",
"execution_count": 24,
"id": "d8e1ac5a",
"metadata": {},
"outputs": [],
"source": [
"z += 2\n",
"z"
]
},
{
"cell_type": "markdown",
"id": "3f4eedf1",
"metadata": {},
"source": [
"There are augmented assignment operators for the other arithmetic operators, including `-=` and `*=`."
]
},
{
"cell_type": "markdown",
"id": "70eeef60-6a34-403a-96bb-aa5c4574a5fe",
"metadata": {},
"source": [
"## Looping and counting\n",
"\n",
"The following program counts the number of words in the word list."
]
},
{
"cell_type": "code",
"execution_count": 25,
"id": "0afd8f88",
"metadata": {},
"outputs": [],
"source": [
"total = 0\n",
"\n",
"for line in open('words.txt'):\n",
" word = line.strip()\n",
" total += 1"
]
},
{
"cell_type": "markdown",
"id": "9bd83ddd",
"metadata": {},
"source": [
"It starts by initializing `total` to `0`.\n",
"Each time through the loop, it increments `total` by `1`.\n",
"So when the loop exits, `total` refers to the total number of words.\n",
""
]
},
{
"cell_type": "code",
"execution_count": 26,
"id": "8686b2eb-c610-4d29-a942-2ef8f53e5e36",
"metadata": {},
"outputs": [],
"source": [
"total"
]
},
{
"cell_type": "markdown",
"id": "54904394",
"metadata": {},
"source": [
"A variable like this, used to count the number of times something happens, is called a **counter**.\n",
"\n",
"We can add a second counter to the program to keep track of the number of words that contain an \"e\"."
]
},
{
"cell_type": "code",
"execution_count": 27,
"id": "89a05280",
"metadata": {},
"outputs": [],
"source": [
"total = 0\n",
"count = 0\n",
"\n",
"for line in open('words.txt'):\n",
" word = line.strip()\n",
" total = total + 1\n",
" if has_e(word):\n",
" count += 1"
]
},
{
"cell_type": "markdown",
"id": "ab73c1e3",
"metadata": {},
"source": [
"Let's see how many words contain an \"e\".\n",
""
]
},
{
"cell_type": "code",
"execution_count": 28,
"id": "9d29b5e9",
"metadata": {},
"outputs": [],
"source": [
"count"
]
},
{
"cell_type": "markdown",
"id": "d2262e64",
"metadata": {},
"source": [
"As a percentage of `total`, about two-thirds of the words use the letter \"e\"."
]
},
{
"cell_type": "code",
"execution_count": 29,
"id": "304dfd86",
"metadata": {},
"outputs": [],
"source": [
"count / total * 100"
]
},
{
"cell_type": "markdown",
"id": "fe002dde",
"metadata": {},
"source": [
"So you can understand why it's difficult to craft a book without using any such words."
]
},
{
"cell_type": "markdown",
"id": "632a992f",
"metadata": {},
"source": [
"## The in operator\n",
"\n",
"The version of `has_e` we wrote in this chapter is more complicated than it needs to be.\n",
"Python provides an operator, `in`, that checks whether a character appears in a string."
]
},
{
"cell_type": "code",
"execution_count": 30,
"id": "fe6431b7",
"metadata": {},
"outputs": [],
"source": [
"word = 'Gadsby'\n",
"'e' in word"
]
},
{
"cell_type": "markdown",
"id": "ede36fe9",
"metadata": {},
"source": [
"So we can rewrite `has_e` like this."
]
},
{
"cell_type": "code",
"execution_count": 31,
"id": "85d3fba6",
"metadata": {},
"outputs": [],
"source": [
"def has_e(word):\n",
" if 'E' in word or 'e' in word:\n",
" return True\n",
" else:\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "f86f6fc7",
"metadata": {},
"source": [
"And because the conditional of the `if` statement has a boolean value, we can eliminate the `if` statement and return the boolean directly."
]
},
{
"cell_type": "code",
"execution_count": 32,
"id": "2d653847",
"metadata": {},
"outputs": [],
"source": [
"def has_e(word):\n",
" return 'E' in word or 'e' in word"
]
},
{
"cell_type": "markdown",
"id": "f2a05319",
"metadata": {},
"source": [
"We can simplify this function even more using the method `lower`, which converts the letters in a string to lowercase.\n",
"Here's an example."
]
},
{
"cell_type": "code",
"execution_count": 33,
"id": "a92a81bc",
"metadata": {},
"outputs": [],
"source": [
"word.lower()"
]
},
{
"cell_type": "markdown",
"id": "57aa625a",
"metadata": {},
"source": [
"`lower` makes a new string -- it does not modify the existing string -- so the value of `word` is unchanged. "
]
},
{
"cell_type": "code",
"execution_count": 34,
"id": "d15f83a4",
"metadata": {},
"outputs": [],
"source": [
"word"
]
},
{
"cell_type": "markdown",
"id": "9f0bd075",
"metadata": {},
"source": [
"Here's how we can use `lower` in `has_e`."
]
},
{
"cell_type": "code",
"execution_count": 35,
"id": "e7958af4",
"metadata": {},
"outputs": [],
"source": [
"def has_e(word):\n",
" return 'e' in word.lower()"
]
},
{
"cell_type": "code",
"execution_count": 36,
"id": "020a57a7",
"metadata": {},
"outputs": [],
"source": [
"has_e('Gadsby')"
]
},
{
"cell_type": "code",
"execution_count": 37,
"id": "0b979b20",
"metadata": {},
"outputs": [],
"source": [
"has_e('Emma')"
]
},
{
"cell_type": "markdown",
"id": "1c39cb6b",
"metadata": {},
"source": [
"## Search\n",
"\n",
"Based on this simpler version of `has_e`, let's write a more general function called `uses_any` that takes a second parameter that is a string of letters.\n",
"It returns `True` if the word uses any of the letters and `False` otherwise."
]
},
{
"cell_type": "code",
"execution_count": 38,
"id": "bd29ff63",
"metadata": {},
"outputs": [],
"source": [
"def uses_any(word, letters):\n",
" for letter in word.lower():\n",
" if letter in letters.lower():\n",
" return True\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "dc2d6290",
"metadata": {},
"source": [
"Here's an example where the result is `True`."
]
},
{
"cell_type": "code",
"execution_count": 39,
"id": "9369fb05",
"metadata": {},
"outputs": [],
"source": [
"uses_any('banana', 'aeiou')"
]
},
{
"cell_type": "markdown",
"id": "2c3c1553",
"metadata": {},
"source": [
"And another where it is `False`."
]
},
{
"cell_type": "code",
"execution_count": 40,
"id": "eb32713a",
"metadata": {},
"outputs": [],
"source": [
"uses_any('apple', 'xyz')"
]
},
{
"cell_type": "markdown",
"id": "b2acc611",
"metadata": {},
"source": [
"`uses_any` converts `word` and `letters` to lowercase, so it works with any combination of cases. "
]
},
{
"cell_type": "code",
"execution_count": 41,
"id": "7e65a9fb",
"metadata": {},
"outputs": [],
"source": [
"uses_any('Banana', 'AEIOU')"
]
},
{
"cell_type": "markdown",
"id": "673786a5",
"metadata": {},
"source": [
"The structure of `uses_any` is similar to `has_e`.\n",
"It loops through the letters in `word` and checks them one at a time.\n",
"If it finds one that appears in `letters`, it returns `True` immediately.\n",
"If it gets all the way through the loop without finding any, it returns `False`.\n",
"\n",
"This pattern is called a **linear search**.\n",
"In the exercises at the end of this chapter, you'll write more functions that use this pattern."
]
},
{
"cell_type": "markdown",
"id": "62cdb3fc",
"metadata": {},
"source": [
"## Doctest\n",
"\n",
"In [Chapter 4](section_docstring) we used a docstring to document a function -- that is, to explain what it does.\n",
"It is also possible to use a docstring to *test* a function.\n",
"Here's a version of `uses_any` with a docstring that includes tests."
]
},
{
"cell_type": "code",
"execution_count": 42,
"id": "3982e7d3",
"metadata": {},
"outputs": [],
"source": [
"def uses_any(word, letters):\n",
" \"\"\"Checks if a word uses any of a list of letters.\n",
" \n",
" >>> uses_any('banana', 'aeiou')\n",
" True\n",
" >>> uses_any('apple', 'xyz')\n",
" False\n",
" \"\"\"\n",
" for letter in word.lower():\n",
" if letter in letters.lower():\n",
" return True\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "2871d018",
"metadata": {},
"source": [
"Each test begins with `>>>`, which is used as a prompt in some Python environments to indicate where the user can type code.\n",
"In a doctest, the prompt is followed by an expression, usually a function call.\n",
"The following line indicates the value the expression should have if the function works correctly.\n",
"\n",
"In the first example, `'banana'` uses `'a'`, so the result should be `True`.\n",
"In the second example, `'apple'` does not use any of `'xyz'`, so the result should be `False`.\n",
"\n",
"To run these tests, we have to import the `doctest` module and run a function called `run_docstring_examples`.\n",
"To make this function easier to use, I wrote the following function, which takes a function object as an argument."
]
},
{
"cell_type": "code",
"execution_count": 43,
"id": "40ef00d3",
"metadata": {},
"outputs": [],
"source": [
"from doctest import run_docstring_examples\n",
"\n",
"def run_doctests(func):\n",
" run_docstring_examples(func, globals(), name=func.__name__)"
]
},
{
"cell_type": "markdown",
"id": "79e3de21",
"metadata": {},
"source": [
"We haven't learned about `globals` and `__name__` yet -- you can ignore them.\n",
"Now we can test `uses_any` like this."
]
},
{
"cell_type": "code",
"execution_count": 44,
"id": "f37cfd36",
"metadata": {},
"outputs": [],
"source": [
"run_doctests(uses_any)"
]
},
{
"cell_type": "markdown",
"id": "432d8c31",
"metadata": {},
"source": [
"`run_doctests` finds the expressions in the docstring and evaluates them.\n",
"If the result is the expected value, the test **passes**.\n",
"Otherwise it **fails**.\n",
"\n",
"If all tests pass, `run_doctests` displays no output -- in that case, no news is good news.\n",
"To see what happens when a test fails, here's an incorrect version of `uses_any`."
]
},
{
"cell_type": "code",
"execution_count": 45,
"id": "58c916cc",
"metadata": {},
"outputs": [],
"source": [
"def uses_any_incorrect(word, letters):\n",
" \"\"\"Checks if a word uses any of a list of letters.\n",
" \n",
" >>> uses_any_incorrect('banana', 'aeiou')\n",
" True\n",
" >>> uses_any_incorrect('apple', 'xyz')\n",
" False\n",
" \"\"\"\n",
" for letter in word.lower():\n",
" if letter in letters.lower():\n",
" return True\n",
" else:\n",
" return False # INCORRECT!"
]
},
{
"cell_type": "markdown",
"id": "34b78be4",
"metadata": {},
"source": [
"And here's what happens when we test it.\n",
""
]
},
{
"cell_type": "code",
"execution_count": 46,
"id": "7a325745",
"metadata": {},
"outputs": [],
"source": [
"run_doctests(uses_any_incorrect)"
]
},
{
"cell_type": "markdown",
"id": "473aa6ec",
"metadata": {},
"source": [
"The output includes the example that failed, the value the function was expected to produce, and the value the function actually produced.\n",
"\n",
"If you are not sure why this test failed, you'll have a chance to debug it as an exercise."
]
},
{
"cell_type": "markdown",
"id": "382c134e",
"metadata": {},
"source": [
"## Glossary\n",
"\n",
"**loop variable:**\n",
"A variable defined in the header of a `for` loop.\n",
"\n",
"**file object:**\n",
"An object that represents an open file and keeps track of which parts of the file have been read or written.\n",
"\n",
"**method:**\n",
" A function that is associated with an object and called using the dot operator.\n",
"\n",
"**update:**\n",
"An assignment statement that give a new value to a variable that already exists, rather than creating a new variables.\n",
"\n",
"**initialize:**\n",
"Create a new variable and give it a value.\n",
"\n",
"**increment:**\n",
"Increase the value of a variable.\n",
"\n",
"**decrement:**\n",
"Decrease the value of a variable.\n",
"\n",
"**counter:**\n",
" A variable used to count something, usually initialized to zero and then incremented.\n",
"\n",
"**linear search:**\n",
"A computational pattern that searches through a sequence of elements and stops when it finds what it is looking for.\n",
"\n",
"**pass:**\n",
"If a test runs and the result is as expected, the test passes.\n",
"\n",
"**fail:**\n",
"If a test runs and the result is not as expected, the test fails."
]
},
{
"cell_type": "markdown",
"id": "69b35605",
"metadata": {},
"source": [
"\n",
"**See also:** the [full vocabulary glossary](https://python.porttack.com/alignment/ap-vocabulary-glossary.html) collects every term in this book, alphabetized, alongside the complete AP CSP exam vocabulary list.\n",
""
]
},
{
"cell_type": "markdown",
"id": "0a2b3510-e8d3-439b-a771-a4a58db6ac59",
"metadata": {},
"source": [
"## Exercises"
]
},
{
"cell_type": "code",
"execution_count": 47,
"id": "bc58db59",
"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": "99eff99e",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"Write a function named `uses_none` that takes a word and a string of forbidden letters, and returns `True` if the word does not use any of the forbidden letters.\n",
"\n",
"Here's an outline of the function that includes two doctests.\n",
"Fill in the function so it passes these tests, and add at least one more doctest."
]
},
{
"cell_type": "code",
"execution_count": 50,
"id": "6c825b80",
"metadata": {},
"outputs": [],
"source": [
"def uses_none(word, forbidden):\n",
" \"\"\"Checks whether a word avoid forbidden letters.\n",
" \n",
" >>> uses_none('banana', 'xyz')\n",
" True\n",
" >>> uses_none('apple', 'efg')\n",
" False\n",
" \"\"\"\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": 51,
"id": "86a6c2c8",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 52,
"id": "2bed91e7",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"run_doctests(uses_none)"
]
},
{
"cell_type": "markdown",
"id": "9465b09f-0c62-49f6-bbe2-365ecf1717ef",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"Write a function called `uses_only` that takes a word and a string of letters, and that returns `True` if the word contains only letters in the string.\n",
"\n",
"Here's an outline of the function that includes two doctests.\n",
"Fill in the function so it passes these tests, and add at least one more doctest."
]
},
{
"cell_type": "code",
"execution_count": 53,
"id": "d0d8c6d6",
"metadata": {},
"outputs": [],
"source": [
"def uses_only(word, available):\n",
" \"\"\"Checks whether a word uses only the available letters.\n",
" \n",
" >>> uses_only('banana', 'ban')\n",
" True\n",
" >>> uses_only('apple', 'apl')\n",
" False\n",
" \"\"\"\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": 54,
"id": "31de091e",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 55,
"id": "8c5133d4",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"run_doctests(uses_only)"
]
},
{
"cell_type": "markdown",
"id": "74259f36",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"Write a function called `uses_all` that takes a word and a string of letters, and that returns `True` if the word contains all of the letters in the string at least once.\n",
"\n",
"Here's an outline of the function that includes two doctests.\n",
"Fill in the function so it passes these tests, and add at least one more doctest."
]
},
{
"cell_type": "code",
"execution_count": 56,
"id": "18b73bc0",
"metadata": {},
"outputs": [],
"source": [
"def uses_all(word, required):\n",
" \"\"\"Checks whether a word uses all required letters.\n",
" \n",
" >>> uses_all('banana', 'ban')\n",
" True\n",
" >>> uses_all('apple', 'api')\n",
" False\n",
" \"\"\"\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": 57,
"id": "5c8be876",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 58,
"id": "ad1fd6b9",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"run_doctests(uses_all)"
]
},
{
"cell_type": "markdown",
"id": "7210adfa",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"*The New York Times* publishes a daily puzzle called \"Spelling Bee\" that challenges readers to spell as many words as possible using only seven letters, where one of the letters is required.\n",
"The words must have at least four letters.\n",
"\n",
"For example, on the day I wrote this, the letters were `ACDLORT`, with `R` as the required letter.\n",
"So \"color\" is an acceptable word, but \"told\" is not, because it does not use `R`, and \"rat\" is not because it has only three letters.\n",
"Letters can be repeated, so \"ratatat\" is acceptable.\n",
"\n",
"Write a function called `check_word` that checks whether a given word is acceptable.\n",
"It should take as parameters the word to check, a string of seven available letters, and a string containing the single required letter.\n",
"You can use the functions you wrote in previous exercises.\n",
"\n",
"Here's an outline of the function that includes doctests.\n",
"Fill in the function and then check that all tests pass."
]
},
{
"cell_type": "code",
"execution_count": 59,
"id": "576ee509",
"metadata": {},
"outputs": [],
"source": [
"def check_word(word, available, required):\n",
" \"\"\"Check whether a word is acceptable.\n",
" \n",
" >>> check_word('color', 'ACDLORT', 'R')\n",
" True\n",
" >>> check_word('ratatat', 'ACDLORT', 'R')\n",
" True\n",
" >>> check_word('rat', 'ACDLORT', 'R')\n",
" False\n",
" >>> check_word('told', 'ACDLORT', 'R')\n",
" False\n",
" >>> check_word('bee', 'ACDLORT', 'R')\n",
" False\n",
" \"\"\"\n",
" return False"
]
},
{
"cell_type": "code",
"execution_count": 60,
"id": "a4d623b7",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 61,
"id": "23ed7f79",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"run_doctests(check_word)"
]
},
{
"cell_type": "markdown",
"id": "0b9589fc",
"metadata": {},
"source": [
"According to the \"Spelling Bee\" rules,\n",
"\n",
"* Four-letter words are worth 1 point each.\n",
"\n",
"* Longer words earn 1 point per letter.\n",
"\n",
"* Each puzzle includes at least one \"pangram\" which uses every letter. These are worth 7 extra points!\n",
"\n",
"Write a function called `score_word` that takes a word and a string of available letters and returns its score.\n",
"You can assume that the word is acceptable.\n",
"\n",
"Again, here's an outline of the function with doctests."
]
},
{
"cell_type": "code",
"execution_count": 62,
"id": "11b69de0",
"metadata": {},
"outputs": [],
"source": [
"def word_score(word, available):\n",
" \"\"\"Compute the score for an acceptable word.\n",
" \n",
" >>> word_score('card', 'ACDLORT')\n",
" 1\n",
" >>> word_score('color', 'ACDLORT')\n",
" 5\n",
" >>> word_score('cartload', 'ACDLORT')\n",
" 15\n",
" \"\"\"\n",
" return 0"
]
},
{
"cell_type": "code",
"execution_count": 63,
"id": "eff4ac37",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 64,
"id": "eb8e8745",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"run_doctests(word_score)"
]
},
{
"cell_type": "markdown",
"id": "82e5283b",
"metadata": {
"tags": []
},
"source": [
"When all of your functions pass their tests, use the following loop to search the word list for acceptable words and add up their scores."
]
},
{
"cell_type": "code",
"execution_count": 65,
"id": "6965f673",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"available = 'ACDLORT'\n",
"required = 'R'\n",
"\n",
"total = 0\n",
"\n",
"file_object = open('words.txt')\n",
"for line in file_object:\n",
" word = line.strip() \n",
" if check_word(word, available, required):\n",
" score = word_score(word, available)\n",
" total = total + score\n",
" print(word, score)\n",
" \n",
"print(\"Total score\", total)"
]
},
{
"cell_type": "markdown",
"id": "dcc7d983",
"metadata": {
"tags": []
},
"source": [
"Visit the \"Spelling Bee\" page at and type in the available letters for the day. The letter in the middle is required.\n",
"\n",
"I found a set of letters that spells words with a total score of 5820. Can you beat that? Finding the best set of letters might be too hard -- you have to be a realist."
]
},
{
"cell_type": "markdown",
"id": "9ae466ed",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"You might have noticed that the functions you wrote in the previous exercises had a lot in common.\n",
"In fact, they are so similar you can often use one function to write another.\n",
"\n",
"For example, if a word uses none of a set forbidden letters, that means it doesn't use any. So we can write a version of `uses_none` like this."
]
},
{
"cell_type": "code",
"execution_count": 66,
"id": "d3aac2dd",
"metadata": {},
"outputs": [],
"source": [
"def uses_none(word, forbidden):\n",
" \"\"\"Checks whether a word avoids forbidden letters.\n",
" \n",
" >>> uses_none('banana', 'xyz')\n",
" True\n",
" >>> uses_none('apple', 'efg')\n",
" False\n",
" >>> uses_none('', 'abc')\n",
" True\n",
" \"\"\"\n",
" return not uses_any(word, forbidden)"
]
},
{
"cell_type": "code",
"execution_count": 67,
"id": "307c07e6",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"run_doctests(uses_none)"
]
},
{
"cell_type": "markdown",
"id": "32aa2c09",
"metadata": {},
"source": [
"There is also a similarity between `uses_only` and `uses_all` that you can take advantage of.\n",
"If you have a working version of `uses_only`, see if you can write a version of `uses_all` that calls `uses_only`."
]
},
{
"cell_type": "markdown",
"id": "fa758462",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"Now write a version of `uses_all` that calls `uses_only` instead of writing a new loop.\n",
"\n",
"Here's the idea: `uses_only(word, available)` is true if every letter in `word` appears in `available`. What question are you asking if you call `uses_only` with `required` and `word` swapped? Compare it to what `uses_all(word, required)` is supposed to check.\n",
"\n",
"Fill in the function so it passes these tests."
]
},
{
"cell_type": "code",
"execution_count": 68,
"id": "83c9d33c",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 69,
"id": "ab66c777",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"run_doctests(uses_all)"
]
},
{
"cell_type": "markdown",
"id": "18f407b3",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"Now write a version of `uses_all` that calls `uses_any`, using a loop.\n",
"\n",
"Here's the idea: for every letter in `required`, check whether `word` uses any of just that one letter. If that's true for every required letter, then `word` uses all of them.\n",
"\n",
"Fill in the function so it passes these tests."
]
},
{
"cell_type": "code",
"execution_count": 70,
"id": "bfd6070c",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 72,
"id": "6980de57",
"metadata": {},
"outputs": [],
"source": [
"run_doctests(uses_all)"
]
},
{
"cell_type": "markdown",
"id": "a7f4edf8",
"metadata": {
"tags": []
},
"source": [
"\n",
"---\n",
"\n",
"**Working in Python** — modified by Eric Brown for a high school Computer Science Principles class. Source and modifications: [github.com/porttack/working-in-python](https://github.com/porttack/working-in-python)\n",
"\n",
"---\n",
"\n",
"\n",
"[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/)\n",
"\n",
"\n",
"---\n",
"\n",
"## Standards alignment\n",
"\n",
"**AP CSP:** [3.8 Iteration](https://python.porttack.com/alignment/apcsp-standards-reference.html#T-3.8) (the `for`-loop / definite-iteration half only) and [3.9 Developing Algorithms](https://python.porttack.com/alignment/apcsp-standards-reference.html#T-3.9) (Big Idea 3, 30–35% of the exam). Also [1.4 Identifying and Correcting Errors](https://python.porttack.com/alignment/apcsp-standards-reference.html#T-1.4) (Big Idea 1, 10–13%), headers only.\n",
"**California 9-12:** [9-12.AP.12](https://python.porttack.com/alignment/ca-cs-standards-reference.html#S-9-12.AP.12), [9-12.AP.20](https://python.porttack.com/alignment/ca-cs-standards-reference.html#S-9-12.AP.20)\n",
"**CSTA 2026:** [HS-PRO-PD-12](https://python.porttack.com/alignment/csta2026-standards-reference.html#T-HS-PRO-PD-12), [HS-PRO-RD-17](https://python.porttack.com/alignment/csta2026-standards-reference.html#T-HS-PRO-RD-17). Also [HS-ALG-PS-02](https://python.porttack.com/alignment/csta2026-standards-reference.html#T-HS-ALG-PS-02) and [HS-PRO-PD-13](https://python.porttack.com/alignment/csta2026-standards-reference.html#T-HS-PRO-PD-13), headers only.\n",
"**CA CTE (ICT):** [C4.9](https://python.porttack.com/alignment/ca-ict-anchor-standards-reference.html#T-C4.9) (Pathway C), [C5.4](https://python.porttack.com/alignment/ca-ict-anchor-standards-reference.html#T-C5.4), and [5.12](https://python.porttack.com/alignment/ca-ict-anchor-standards-reference.html#T-5.12) (Anchor Standards). Also [C4.10](https://python.porttack.com/alignment/ca-ict-anchor-standards-reference.html#T-C4.10), [C5.6](https://python.porttack.com/alignment/ca-ict-anchor-standards-reference.html#T-C5.6), and [5.7](https://python.porttack.com/alignment/ca-ict-anchor-standards-reference.html#T-5.7), headers only.\n",
"\n",
"Chapter 7 builds a linear search — `has_e`, then the more general `uses_any` — out of a `for` loop and the `in` operator, and tests it with doctest instead of print statements. That's 3.9's incremental-algorithm pattern and California's AP.12/AP.20 directly, and CSTA's function-reuse and code-tracing standards in different words. The chapter's strongest cross-framework match is boolean logic itself: `in`-based tests driving search is exactly what CTE's Anchor 5.12 names, and doctest is CTE's testing-as-its-own-step standard in practice.\n",
"\n",
"**Indexing:** the exam's pseudocode has no `in`-style containment check. It spells out the same search as an explicit `FOR EACH` loop with an `IF`.\n",
""
]
}
],
"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
}