{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Review (optional)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "-"
},
"tags": [
"remove-cell"
]
},
"source": [
"**CS1302 Introduction to Computer Programming**\n",
"___"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-27T11:20:04.656873Z",
"start_time": "2020-11-27T11:20:04.651575Z"
},
"slideshow": {
"slide_type": "fragment"
},
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"%reload_ext mytutor"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Topic 8"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (Concatenate two dictionaries with precedence)** \n",
"\n",
"Define a function `concat_two_dicts` that accepts two arguments of type `dict` such that `concat_two_dicts(a, b)` will return \n",
"\n",
"- a new dictionary containing all the items in `a`, and \n",
"- the items in `b` that have different keys than those in `a`. \n",
"\n",
"The input dictionaries should not be mutated."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"- `{**dict1,**dict2}` creates a new dictionary by unpacking the dictionaries `dict1` and `dict2`.\n",
"- By default, `dict2` overwrites `dict1` if they have identical keys.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T07:39:49.633762Z",
"start_time": "2020-11-23T07:39:49.614955Z"
},
"nbgrader": {
"grade": false,
"grade_id": "concatenate-dict-with-precedence",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def concat_two_dicts(a, b):\n",
" ### BEGIN SOLUTION\n",
" return {**b, **a}\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T07:46:50.655714Z",
"start_time": "2020-11-23T07:46:50.646550Z"
},
"nbgrader": {
"grade": true,
"grade_id": "concatenate-with-precedence1",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"a = {\"x\": 10, \"z\": 30}\n",
"b = {\"y\": 20, \"z\": 40}\n",
"a_copy = a.copy()\n",
"b_copy = b.copy()\n",
"assert concat_two_dicts(a, b) == {\"x\": 10, \"z\": 30, \"y\": 20}\n",
"assert concat_two_dicts(b, a) == {\"x\": 10, \"z\": 40, \"y\": 20}\n",
"assert a == a_copy and b == b_copy\n",
"\n",
"a = {\"x\": 10, \"z\": 30}\n",
"b = {\"y\": 20}\n",
"a_copy = a.copy()\n",
"b_copy = b.copy()\n",
"assert concat_two_dicts(a, b) == {\"x\": 10, \"z\": 30, \"y\": 20}\n",
"assert concat_two_dicts(b, a) == {\"x\": 10, \"z\": 30, \"y\": 20}\n",
"assert a == a_copy and b == b_copy"
]
},
{
"cell_type": "markdown",
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T07:49:28.830728Z",
"start_time": "2020-11-23T07:49:28.823789Z"
}
},
"source": [
"**Exercise (Count characters)** \n",
"\n",
"Define a function `count_characters` which\n",
"\n",
"- accepts a string as an argument, and \n",
"- returns a dictionary that stores counts of each character appearing in the string."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"- Create an empty dictionary `counts`.\n",
"- Use a `for` loop to iterate over each character of `string` to count their numbers of occurrences.\n",
"- The `get` method of `dict` can initialize the count of a new character before incrementing it.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T07:54:10.105803Z",
"start_time": "2020-11-23T07:54:10.102533Z"
},
"nbgrader": {
"grade": false,
"grade_id": "count_characters",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def count_characters(string):\n",
" ### BEGIN SOLUTION\n",
" counts = {}\n",
" for char in string:\n",
" counts[char] = counts.get(char, 0) + 1\n",
" return counts\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T07:57:10.595549Z",
"start_time": "2020-11-23T07:57:10.590268Z"
},
"nbgrader": {
"grade": true,
"grade_id": "test-count_characters",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"assert count_characters(\"abcbabc\") == {\"a\": 2, \"b\": 3, \"c\": 2}\n",
"assert count_characters(\"aababcccabc\") == {\"a\": 4, \"b\": 3, \"c\": 4}\n",
"\n",
"assert count_characters(\"abcdefgabc\") == {\n",
" \"a\": 2,\n",
" \"b\": 2,\n",
" \"c\": 2,\n",
" \"d\": 1,\n",
" \"e\": 1,\n",
" \"f\": 1,\n",
" \"g\": 1,\n",
"}\n",
"assert count_characters(\"ab43cb324abc\") == {\n",
" \"2\": 1,\n",
" \"3\": 2,\n",
" \"4\": 2,\n",
" \"a\": 2,\n",
" \"b\": 3,\n",
" \"c\": 2,\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (Count non-Fibonacci numbers)** \n",
"\n",
"Define a function `count_non_fibs` that \n",
"\n",
"- accepts a container as an argument, and \n",
"- returns the number of items in the container that are not [fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_number)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"- Create a set of Fibonacci numbers up to the maximum of the items in the container.\n",
"- Use `difference_update` method of `set` to create a set of items in the container but not in the set of Fibonacci numbers.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T08:41:44.277705Z",
"start_time": "2020-11-23T08:41:44.261518Z"
},
"nbgrader": {
"grade": false,
"grade_id": "count_non_fibs",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def count_non_fibs(container):\n",
" ### BEGIN SOLUTION\n",
" def fib_sequence_inclusive(stop):\n",
" Fn, Fn1 = 0, 1\n",
" while Fn <= stop:\n",
" yield Fn\n",
" Fn, Fn1 = Fn1, Fn + Fn1\n",
"\n",
" non_fibs = set(container)\n",
" non_fibs.difference_update(fib_sequence_inclusive(max(container)))\n",
" return len(non_fibs)\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T09:00:07.206294Z",
"start_time": "2020-11-23T09:00:07.197807Z"
},
"nbgrader": {
"grade": true,
"grade_id": "test-count_non_fibs",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"assert count_non_fibs([0, 1, 2, 3, 5, 8]) == 0\n",
"assert count_non_fibs({13, 144, 99, 76, 1000}) == 3\n",
"\n",
"assert count_non_fibs({5, 8, 13, 21, 34, 100}) == 1\n",
"assert count_non_fibs({0.1, 0}) == 1"
]
},
{
"cell_type": "markdown",
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T08:21:26.126004Z",
"start_time": "2020-11-23T08:21:26.118100Z"
}
},
"source": [
"**Exercise (Calculate total salaries)** \n",
"\n",
"Suppose `salary_dict` contains information about the name, salary, and working time about employees in a company. An example of `salary_dict` is as follows: \n",
"```Python\n",
"salary_dict = {\n",
" 'emp1': {'name': 'John', 'salary': 15000, 'working_time': 20},\n",
" 'emp2': {'name': 'Tom', 'salary': 16000, 'working_time': 13},\n",
" 'emp3': {'name': 'Jack', 'salary': 15500, 'working_time': 15},\n",
"}\n",
"```\n",
"\n",
"Define a function `calculate_total` that accepts `salary_dict` as an argument, and returns a `dict` that uses the same keys in `salary_dict` but the total salaries as their values. The total salary of an employee is obtained by multiplying his/her salary and his/her working_time. \n",
"E.g., for the `salary_dict` example above, `calculate_total(salary_dict)` should return\n",
"```Python\n",
"{'emp1': 300000, 'emp2': 208000, 'emp3': 232500}.\n",
"```\n",
"where the total salary of `emp1` is $15000 \\times 20 = 300000$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"- Use `items` method of `dict` to return the list of key values pairs, and\n",
"- use a dictionary comprehension to create the desired dictionary by iterating through the list of items.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T09:00:51.515965Z",
"start_time": "2020-11-23T09:00:51.512821Z"
},
"nbgrader": {
"grade": false,
"grade_id": "calculate_total",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def calculate_total(salary_dict):\n",
" ### BEGIN SOLUTION\n",
" return {\n",
" emp: record[\"salary\"] * record[\"working_time\"]\n",
" for emp, record in salary_dict.items()\n",
" }\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T09:00:35.811080Z",
"start_time": "2020-11-23T09:00:35.803410Z"
},
"nbgrader": {
"grade": true,
"grade_id": "test-calculate_total",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"salary_dict = {\n",
" \"emp1\": {\"name\": \"John\", \"salary\": 15000, \"working_time\": 20},\n",
" \"emp2\": {\"name\": \"Tom\", \"salary\": 16000, \"working_time\": 13},\n",
" \"emp3\": {\"name\": \"Jack\", \"salary\": 15500, \"working_time\": 15},\n",
"}\n",
"assert calculate_total(salary_dict) == {\"emp1\": 300000, \"emp2\": 208000, \"emp3\": 232500}\n",
"\n",
"salary_dict = {\n",
" \"emp1\": {\"name\": \"John\", \"salary\": 15000, \"working_time\": 20},\n",
" \"emp2\": {\"name\": \"Tom\", \"salary\": 16000, \"working_time\": 13},\n",
" \"emp3\": {\"name\": \"Jack\", \"salary\": 15500, \"working_time\": 15},\n",
" \"emp4\": {\"name\": \"Bob\", \"salary\": 20000, \"working_time\": 10},\n",
"}\n",
"assert calculate_total(salary_dict) == {\n",
" \"emp1\": 300000,\n",
" \"emp2\": 208000,\n",
" \"emp3\": 232500,\n",
" \"emp4\": 200000,\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (Delete items with value 0 in dictionary)** \n",
"\n",
"Define a function `zeros_removed` that \n",
"\n",
"- takes a dictionary as an argument,\n",
"- mutates the dictionary to remove all the keys associated with values equal to `0`,\n",
"- and return `True` if at least one key is removed else `False`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"- The main issue is that, for any dicionary `d`,\n",
"```Python\n",
" for k in d: \n",
" if d[k] == 0: del d[k]\n",
"```\n",
"raises the [`RuntimeError: dictionary changed size during iteration`](https://www.geeksforgeeks.org/python-delete-items-from-dictionary-while-iterating/). \n",
"- One solution is to duplicate the list of keys, but this is memory inefficient especially when the list of keys is large.\n",
"- Another solution is to record the list of keys to delete before the actual deletion. This is memory efficient if the list of keys to delete is small.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T10:04:05.341884Z",
"start_time": "2020-11-23T10:04:05.336744Z"
},
"nbgrader": {
"grade": false,
"grade_id": "zeros_removed",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def zeros_removed(d):\n",
" ### BEGIN SOLUTION\n",
" for k in (to_delete := [k for k in d if d[k] == 0]):\n",
" del d[k]\n",
" return len(to_delete) > 0\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T09:47:50.274213Z",
"start_time": "2020-11-23T09:47:50.267314Z"
},
"nbgrader": {
"grade": true,
"grade_id": "test-zeros_removed",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"d = {\"a\": 0, \"b\": 1, \"c\": 0, \"d\": 2}\n",
"assert zeros_removed(d) == True\n",
"assert zeros_removed(d) == False\n",
"assert d == {\"b\": 1, \"d\": 2}\n",
"\n",
"d = {\"a\": 0, \"b\": 1, \"c\": 0, \"d\": 2, \"e\": 0, \"f\": \"0\"}\n",
"assert zeros_removed(d) == True\n",
"assert zeros_removed(d) == False\n",
"assert d == {\"b\": 1, \"d\": 2, \"f\": \"0\"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (Fuzzy search a set)** Define a function `search_fuzzy` that accepts two arguments `myset` and `word` such that\n",
"- `myset` is a `set` of `str`s;\n",
"- `word` is a `str`; and\n",
"- `search_fuzzy(myset, word)` returns `True` if `word` is in `myset` by changing at most one character in `word`, and returns `False` otherwise. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"- Iterate over each word in `myset`.\n",
"- Check whether the length of the word is the same as that of the word in the arguments.\n",
"- If the above check passes, use a list comprehension to check if the words differ by at most one character.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T11:27:21.358022Z",
"start_time": "2020-11-23T11:27:21.349898Z"
},
"nbgrader": {
"grade": false,
"grade_id": "search_fuzzy",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def search_fuzzy(myset, word):\n",
" ### BEGIN SOLUTION\n",
" for myword in myset:\n",
" if (\n",
" len(myword) == len(word)\n",
" and len([True for mychar, char in zip(myword, word) if mychar != char]) <= 1\n",
" ):\n",
" return True\n",
" return False\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T11:27:42.519492Z",
"start_time": "2020-11-23T11:27:42.510275Z"
},
"nbgrader": {
"grade": true,
"grade_id": "test-search_fuzzy",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"assert search_fuzzy({\"cat\", \"dog\"}, \"car\") == True\n",
"assert search_fuzzy({\"cat\", \"dog\"}, \"fox\") == False\n",
"\n",
"myset = {\"cat\", \"dog\", \"dolphin\", \"rabbit\", \"monkey\", \"tiger\"}\n",
"assert search_fuzzy(myset, \"lion\") == False\n",
"assert search_fuzzy(myset, \"cat\") == True\n",
"assert search_fuzzy(myset, \"cat \") == False\n",
"assert search_fuzzy(myset, \"fox\") == False\n",
"assert search_fuzzy(myset, \"ccc\") == False"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (Get keys by value)** \n",
"\n",
"Define a function `get_keys_by_value` that accepts two arguments `d` and `value` where `d` is a dictionary, and returns a set containing all the keys in `d` that have `value` as its value. If no key has the query value `value`, then return an empty set."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"Use set comprehension to create the set of keys whose associated values is `value`.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T13:38:07.323600Z",
"start_time": "2020-11-23T13:38:07.318070Z"
},
"nbgrader": {
"grade": false,
"grade_id": "get_keys_by_value",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def get_keys_by_value(d, value):\n",
" ### BEGIN SOLUTION\n",
" return {k for k in d if d[k] == value}\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T13:39:20.729705Z",
"start_time": "2020-11-23T13:39:20.719583Z"
},
"nbgrader": {
"grade": true,
"grade_id": "test-get_keys_by_value",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"d = {\n",
" \"Tom\": \"99\",\n",
" \"John\": \"88\",\n",
" \"Lucy\": \"100\",\n",
" \"Lily\": \"90\",\n",
" \"Jason\": \"89\",\n",
" \"Jack\": \"100\",\n",
"}\n",
"assert get_keys_by_value(d, \"99\") == {\"Tom\"}\n",
"\n",
"d = {\n",
" \"Tom\": \"99\",\n",
" \"John\": \"88\",\n",
" \"Lucy\": \"100\",\n",
" \"Lily\": \"90\",\n",
" \"Jason\": \"89\",\n",
" \"Jack\": \"100\",\n",
"}\n",
"assert get_keys_by_value(d, \"100\") == {\"Jack\", \"Lucy\"}\n",
"d = {\n",
" \"Tom\": \"99\",\n",
" \"John\": \"88\",\n",
" \"Lucy\": \"100\",\n",
" \"Lily\": \"90\",\n",
" \"Jason\": \"89\",\n",
" \"Jack\": \"100\",\n",
"}\n",
"assert get_keys_by_value(d, \"0\") == set()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (Count letters and digits)** \n",
"\n",
"Define a function `count_letters_and_digits` which \n",
"\n",
"- take a string as an argument,\n",
"- returns a dictionary that stores the number of letters and digits in the string using the keys 'LETTERS' and 'DIGITS' respectively."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"Use the class method `fromkeys` of `dict` to initial the dictionary of counts.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T14:02:19.144260Z",
"start_time": "2020-11-23T14:02:19.136266Z"
},
"nbgrader": {
"grade": false,
"grade_id": "count_letters_and_digits",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def count_letters_and_digits(string):\n",
" ### BEGIN SOLUTION\n",
" return {'DIGITS': len([True for c in string if c.isdigit()]),\n",
" 'LETTERS': len([True for c in string if c.isalpha()])}\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T13:59:48.237919Z",
"start_time": "2020-11-23T13:59:48.232794Z"
},
"nbgrader": {
"grade": true,
"grade_id": "test-count_letters_and_digits",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"assert count_letters_and_digits(\"hello world! 2020\") == {\"DIGITS\": 4, \"LETTERS\": 10}\n",
"assert count_letters_and_digits(\"I love CS1302\") == {\"DIGITS\": 4, \"LETTERS\": 7}\n",
"\n",
"assert count_letters_and_digits(\"Hi CityU see you in 2021\") == {\n",
" \"DIGITS\": 4,\n",
" \"LETTERS\": 15,\n",
"}\n",
"assert count_letters_and_digits(\n",
" \"When a dog runs at you, whistle for him. (Philosopher Henry David Thoreau, 1817-1862)\"\n",
") == {\"DIGITS\": 8, \"LETTERS\": 58}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (Dealers with lowest price)** \n",
"\n",
"Suppose `apple_price` is a list in which each element is a `dict` recording the dealer and the corresponding price, e.g., \n",
"\n",
"```Python\n",
"apple_price = [{'dealer': 'dealer_A', 'price': 6799},\n",
" {'dealer': 'dealer_B', 'price': 6749},\n",
" {'dealer': 'dealer_C', 'price': 6798},\n",
" {'dealer': 'dealer_D', 'price': 6749}]\n",
"```\n",
"\n",
"Define a function `dealers_with_lowest_price` that takes `apple_price` as an argument, and returns the `set` of dealers providing the lowest price."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"- Use the class method `setdefault` of `dict` to create a dictionary that maps different prices to different sets of dealers.\n",
"- Compute the lowest price at the same time.\n",
"- Alternatively, use comprehension to find lowest price and then create the desired set of dealers with the lowest price.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T14:30:16.037424Z",
"start_time": "2020-11-23T14:30:16.014173Z"
},
"nbgrader": {
"grade": false,
"grade_id": "dealers_with_lowest_price",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def dealers_with_lowest_price(apple_price):\n",
" ### BEGIN SOLUTION\n",
" lowest_price = min(pricing['price'] for pricing in apple_price)\n",
" return set(pricing['dealer'] for pricing in apple_price\n",
" if pricing['price'] == lowest_price)\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T14:30:16.691574Z",
"start_time": "2020-11-23T14:30:16.682250Z"
},
"nbgrader": {
"grade": true,
"grade_id": "test-dealers_with_lowest_price",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"apple_price = [\n",
" {\"dealer\": \"dealer_A\", \"price\": 6799},\n",
" {\"dealer\": \"dealer_B\", \"price\": 6749},\n",
" {\"dealer\": \"dealer_C\", \"price\": 6798},\n",
" {\"dealer\": \"dealer_D\", \"price\": 6749},\n",
"]\n",
"assert dealers_with_lowest_price(apple_price) == {\"dealer_B\", \"dealer_D\"}\n",
"\n",
"apple_price = [\n",
" {\"dealer\": \"dealer_A\", \"price\": 6799},\n",
" {\"dealer\": \"dealer_B\", \"price\": 6799},\n",
" {\"dealer\": \"dealer_C\", \"price\": 6799},\n",
" {\"dealer\": \"dealer_D\", \"price\": 6799},\n",
"]\n",
"assert dealers_with_lowest_price(apple_price) == {\n",
" \"dealer_A\",\n",
" \"dealer_B\",\n",
" \"dealer_C\",\n",
" \"dealer_D\",\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Topic 7"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise** (Binary addition) \n",
"\n",
"Define a function `add_binary` that \n",
"\n",
"- accepts two arguments of type `str` which represent two non-negative binary numbers, and \n",
"- returns the binary number in `str` equal to the sum of the two given binary numbers."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"- Use comprehension to convert the binary numbers to decimal numbers.\n",
"- Use comprehension to convert the sum of the decimal numbers to a binary number.\n",
"- Alternatively, perform bitwise addition using a recursion or iteration.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T15:55:43.806764Z",
"start_time": "2020-11-23T15:55:43.800743Z"
},
"nbgrader": {
"grade": false,
"grade_id": "add_binary",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def add_binary(*binaries):\n",
" ### BEGIN SOLUTION\n",
" if len(binaries)<1:\n",
" return ''\n",
" if len(binaries)<2:\n",
" return binaries[0]\n",
" k = len([1 for b in binaries if b[-1] == '1'])\n",
" return add_binary(*[b[:-1] for b in binaries if len(b)>1], *((k//2)*'1')) + str(k%2)\n",
"\n",
"def add_binary(*binaries):\n",
" def d2b(d):\n",
" return (d2b(d//2) if d>1 else '') + str(d%2)\n",
" d = sum(int(b, base=2) for b in binaries)\n",
" return d2b(d)\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T15:49:16.101739Z",
"start_time": "2020-11-23T15:49:16.094252Z"
},
"nbgrader": {
"grade": true,
"grade_id": "test-add_binary",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"assert add_binary(\"0\", \"0\") == \"0\"\n",
"assert add_binary(\"11\", \"11\") == \"110\"\n",
"assert add_binary(\"101\", \"101\") == \"1010\"\n",
"\n",
"assert add_binary(\"1111\", \"10\") == \"10001\"\n",
"assert add_binary(\"111110000011\", \"110000111\") == \"1000100001010\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (Even-digit numbers)** \n",
"\n",
"Define a function `even_digit_numbers`, which finds all numbers between `lower_bound` and `upper_bound` such that each digit of the number is an even number. Return the numbers as a list."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"- Use list comprehension to generate numbers between the bounds, and\n",
"- use recursion to check if a number contains only even digits. \n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T16:14:48.151588Z",
"start_time": "2020-11-23T16:14:48.145181Z"
},
"nbgrader": {
"grade": false,
"grade_id": "even_digit_numbers",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def even_digit_numbers(lower_bound, upper_bound):\n",
" ### BEGIN SOLUTION\n",
" def is_even_digit(n):\n",
" return not n or not n % 10 % 2 and is_even_digit(n // 10)\n",
"\n",
" return [n for n in range(lower_bound, upper_bound + 1) if is_even_digit(n)]\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T16:14:52.757608Z",
"start_time": "2020-11-23T16:14:52.753381Z"
},
"nbgrader": {
"grade": true,
"grade_id": "test-even_digit_numbers",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"assert even_digit_numbers(1999, 2001) == [2000]\n",
"assert even_digit_numbers(2805, 2821) == [2806, 2808, 2820]\n",
"\n",
"assert even_digit_numbers(8801, 8833) == [\n",
" 8802,\n",
" 8804,\n",
" 8806,\n",
" 8808,\n",
" 8820,\n",
" 8822,\n",
" 8824,\n",
" 8826,\n",
" 8828,\n",
"]\n",
"assert even_digit_numbers(3662, 4001) == [4000]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (Maximum subsequence sum)** \n",
"\n",
"Define a function `max_subsequence_sum` that \n",
"\n",
"- accepts as an argument a sequence of numbers, and \n",
"- returns the maximum sum over non-empty contiguous subsequences. \n",
"\n",
"E.g., when `[-6, -4, 4, 1, -2, 2]` is given as the argument, the function returns `5` because the nonempty subsequence `[4, 1]` has the maximum sum `5`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"For a list $[a_0, a_1, \\dots]$, let \n",
"\n",
"$$\n",
"c_k:=\\max_{j\\leq k} \\sum_{i=j}^{k} a_i = \\max\\{a_k, c_{k-1}+a_{k}\\},\n",
"$$ \n",
"namely the maximum non-empty tail sum of $[a_0,\\dots,a_{k}]$. \n",
"\n",
"Then, the current best maximum subsequence sum of $[a_0,\\dots,a_{k}]$ is \n",
"\n",
"$$\n",
"b_k := \\max_{j\\leq k} c_j.\n",
"$$\n",
"\n",
"See [Kadane's algorithm](https://en.wikipedia.org/wiki/Maximum_subarray_problem).\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T17:45:31.790323Z",
"start_time": "2020-11-23T17:45:31.786284Z"
},
"nbgrader": {
"grade": false,
"grade_id": "max_subsequence_sum",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def max_subsequence_sum(a):\n",
" ### BEGIN SOLUTION\n",
" b = c = -float(\"inf\")\n",
" for x in a:\n",
" c = max(x, c + x)\n",
" b = max(b, c)\n",
" return b\n",
"\n",
" ## Alternative (less efficient) solution using list comprehension\n",
" # def max_subsequence_sum(a):\n",
" # return max(sum(a[i:j]) for i in range(len(a)) for j in range(i+1,len(a)+1))\n",
"\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T17:46:37.967363Z",
"start_time": "2020-11-23T17:46:37.943521Z"
},
"nbgrader": {
"grade": true,
"grade_id": "test-max_subsequence_sum",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"assert max_subsequence_sum([-1]) == -1\n",
"assert max_subsequence_sum([-6, -4, 4, 1, -2, 2]) == 5\n",
"assert max_subsequence_sum([2.5, 1.4, -2.5, 1.4, 1.5, 1.6]) == 5.9\n",
"\n",
"seq = [-24.81, 25.74, 37.29, -8.77, 0.78, -15.33, 30.21, 34.94, -40.64, -20.06]\n",
"assert round(max_subsequence_sum(seq), 2) == 104.86"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T17:51:36.465818Z",
"start_time": "2020-11-23T17:51:35.962061Z"
},
"nbgrader": {
"grade": true,
"grade_id": "efficiency-max_subsequence_sum",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
}
},
"outputs": [],
"source": [
"# test of efficiency\n",
"assert max_subsequence_sum([*range(1234567)]) == 762077221461"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (Mergesort)** \n",
"\n",
"*For this question, do not use the `sort` method or `sorted` function.*\n",
"\n",
"Define a function called `merge` that\n",
"\n",
"- takes two sequences sorted in ascending orders, and\n",
"- returns a sorted list of items from the two sequences.\n",
"\n",
"Then, define a function called `mergesort` that\n",
"\n",
"- takes a sequence, and\n",
"- return a list of items from the sequence sorted in ascending order.\n",
"\n",
"The list should be constructed by \n",
"\n",
" - recursive calls to `mergesort` the first and second halves of the sequence individually, and\n",
" - merge the sorted halves."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"For `merge(left, right)`:\n",
"\n",
"- If `left` or `right` is empty, just return the non-empty one as a list.\n",
"- Otherwise, take out one of the largest item from `left` and `right` and call merge again on the resulting list.\n",
"- Return the sorted list from the recursive call appended with the largest item that was taken out in the last step.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T17:58:24.722794Z",
"start_time": "2020-11-23T17:58:24.715156Z"
},
"nbgrader": {
"grade": false,
"grade_id": "merge",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def merge(left, right):\n",
" ### BEGIN SOLUTION\n",
" if left and right:\n",
" if left[-1] > right[-1]:\n",
" left, right = right, left\n",
" return merge(left, right[:-1]) + [right[-1]]\n",
" return list(left or right)\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {
"nbgrader": {
"grade": false,
"grade_id": "mergesort",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def mergesort(seq):\n",
" ### BEGIN SOLUTION\n",
" if len(seq) <= 1:\n",
" return list(seq)\n",
" i = len(seq) // 2\n",
" return merge(mergesort(seq[:i]), mergesort(seq[i:]))\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {
"nbgrader": {
"grade": true,
"grade_id": "test-mergesort",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"assert merge([1, 3], [2, 4]) == [1, 2, 3, 4]\n",
"assert mergesort([3, 2, 1]) == [1, 2, 3]\n",
"\n",
"assert mergesort([3, 5, 2, 4, 2, 1]) == [1, 2, 2, 3, 4, 5]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Topic 6"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (Enforce input types)**\n",
"\n",
"Define a function `input_types` that takes a variable number of arguments stored in `types` and returns a decorator that ensures the argument at position `i` of a function has type `types[i]`. More precisely, the decorator calls `raise TypeError()` if an argument at any position `i` does not have `type[i]`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"Complete the definition of `wrapper`:\n",
"\n",
"- Use a `for` loop and the `zip` function to iterate through items of `args` and `types`.\n",
"- Check whether an item in `args` is of the corresponding type in `types`. Raise `TypeError` if not.\n",
"- Return `f` evaluated at the same arguments passed to `wrapper`.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"nbgrader": {
"grade": false,
"grade_id": "input-types",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
}
},
"outputs": [],
"source": [
"import functools\n",
"\n",
"\n",
"def input_types(*types):\n",
" def decorator(f):\n",
" @functools.wraps(f)\n",
" def wrapper(*args, **kwargs):\n",
" ### BEGIN SOLUTION\n",
" for a, t in zip(args, types):\n",
" if not isinstance(a, t):\n",
" raise TypeError()\n",
" return f(*args, **kwargs)\n",
" ### END SOLUTION\n",
"\n",
" return wrapper\n",
"\n",
" return decorator"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"nbgrader": {
"grade": true,
"grade_id": "test_input-types",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
}
},
"outputs": [],
"source": [
"# tests\n",
"@input_types(int, int)\n",
"def sum(x, y):\n",
" return x + y\n",
"\n",
"\n",
"assert sum(1, 1) == 2\n",
"\n",
"try:\n",
" print(sum(1.0, 1))\n",
"except TypeError:\n",
" pass"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise (Arithmetic geometric mean)** \n",
"\n",
"Define a function `arithmetic_geometric_mean_sequence` which\n",
"\n",
"- takes two floating point numbers `x` and `y` and \n",
"- returns a generator that generates the tuple \\\\((a_n, g_n)\\\\) where\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"a_0 &= x, g_0 = y \\\\\n",
"a_n &= \\frac{a_{n-1} + g_{n-1}}2 \\quad \\text{for }n>0\\\\\n",
"g_n &= \\sqrt{a_{n-1} g_{n-1}}\n",
"\\end{aligned}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"Use the `yield` expression to return each tuple of $(a_n,g_n)$ efficiently without redundant computations.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 83,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T16:05:01.507575Z",
"start_time": "2020-11-23T16:05:01.486238Z"
},
"nbgrader": {
"grade": false,
"grade_id": "arithmetic_geometric_mean_sequence",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def arithmetic_geometric_mean_sequence(x, y):\n",
" ### BEGIN SOLUTION\n",
" a, g = x, y\n",
" while True:\n",
" yield a, g\n",
" a, g = (a + g) / 2, (a * g) ** 0.5\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 84,
"metadata": {
"ExecuteTime": {
"end_time": "2020-11-23T16:05:02.134997Z",
"start_time": "2020-11-23T16:05:02.127105Z"
},
"nbgrader": {
"grade": true,
"grade_id": "test-arithmetic_geometric_mean_sequence",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"agm = arithmetic_geometric_mean_sequence(6, 24)\n",
"assert [next(agm) for i in range(2)] == [(6, 24), (15.0, 12.0)]\n",
"\n",
"agm = arithmetic_geometric_mean_sequence(100, 400)\n",
"for sol, ans in zip(\n",
" [next(agm) for i in range(5)],\n",
" [\n",
" (100, 400),\n",
" (250.0, 200.0),\n",
" (225.0, 223.60679774997897),\n",
" (224.30339887498948, 224.30231718318308),\n",
" (224.30285802908628, 224.30285802843423),\n",
" ],\n",
"):\n",
" for a, b in zip(sol, ans):\n",
" assert round(a, 5) == round(b, 5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Challenge"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise** (Integer square root)\n",
"\n",
"The following function computes the integer square root $\\lfloor \\sqrt{n}\\rfloor$ of its non-negative integer argument $n$ using the idea of bisection as suggested by one student in class."
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [],
"source": [
"def isqrt(n):\n",
" def _(n, a, b):\n",
" if a ** 2 <= n < b ** 2:\n",
" if a + 1 == b:\n",
" return a\n",
" c = (a + b) // 2\n",
" return _(n, a, c) or _(n, c, b)\n",
"\n",
" return _(n, 0, n + 1)\n",
"\n",
"\n",
"assert isqrt(10 ** 2) == 10"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For large $n$, the above recursion can fail with `RecursionError: maximum recursion depth exceed in comparison`, e.g., with\n",
"\n",
"```Python\n",
"assert isqrt(10**100**2) == 10**5000\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Rewrite the code to use iteration (not recursion) to avoid the above error."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"Complete the following code so that the value of `c` is assigned to either `b` or `c` depending on whether `n < c**2`.\n",
"\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"nbgrader": {
"grade": false,
"grade_id": "isqrt",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"def isqrt(n):\n",
" a, b = 0, n + 1\n",
" while a + 1 < b:\n",
" c = (a + b) // 2\n",
" ### BEGIN SOLUTION\n",
" if n < c ** 2:\n",
" b = c\n",
" else:\n",
" a = c\n",
" return a\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"nbgrader": {
"grade": true,
"grade_id": "test_isqrt",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"assert isqrt(10**100**2) == 10**5000"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise** \n",
"\n",
"For integers `n` and `k`, complete the following function such that `combination(n, k)` returns a list of all [`k`-subsets (`k`-combinations)](https://en.wikipedia.org/wiki/Combination) of items in `range(n)`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**Hint**\n",
"\n",
"A $k$-subset of items from a non-empty sequence `a` can be obtained either\n",
"\n",
"- as a $k$-subset of items from `a[:-1]`, or\n",
"- by adding `a[-1]` to a $k-1$-subset of items from `a[:-1]`.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"nbgrader": {
"grade": false,
"grade_id": "combination",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"import functools\n",
"\n",
"\n",
"@functools.lru_cache\n",
"def combination(n, k):\n",
" output = []\n",
" if 0 <= k <= n:\n",
" ### BEGIN SOLUTION\n",
" if k == 0:\n",
" output.append(set())\n",
" else:\n",
" output.extend(combination(n - 1, k))\n",
" output.extend({*s, n - 1} for s in combination(n - 1, k - 1))\n",
" ### END SOLUTION\n",
" return output"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"nbgrader": {
"grade": true,
"grade_id": "test_combination",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"# tests\n",
"n = 3\n",
"got = [combination(n, k) for k in range(-1, n+2)]\n",
"expected = [[], [set()], [{0}, {1}, {2}], [{0, 1}, {0, 2}, {1, 2}], [{0, 1, 2}], []]\n",
"for i in range(len(expected)):\n",
" assert set(frozenset(s) for s in got[i]) == set(frozenset(s) for s in expected[i])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise** \n",
"\n",
"In the above recursion, is caching by `lru_cache` useful in avoiding duplicate recursive calls with same arguments? Give an example of how the redundant computer is avoided."
]
},
{
"cell_type": "markdown",
"metadata": {
"nbgrader": {
"grade": true,
"grade_id": "caching",
"locked": false,
"points": 1,
"schema_version": 3,
"solution": true,
"task": false
}
},
"source": [
"Yes. `combination(4, 2)` calls `combination(3, 1)` and `combination(3, 2)`, both of which calls `combination(2, 1)` that returns `[{0}, {1}]`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise**\n",
"\n",
"Complete the function `rf_key` so that `encrypt` and `decrypt` implement the [Rail Fence transposition cipher](https://en.wikipedia.org/wiki/Rail_fence_cipher). In particular, the plaintext\n",
"\n",
"\n",
"WE ARE DISCOVERED FLEE AT ONCE\n",
"\n",
"\n",
"with spaces removed is arranged in `k=3` rails as\n",
"\n",
"\n",
"W...E...C...R...L...T...E\n",
".E.R.D.S.O.E.E.F.E.A.O.C.\n",
"..A...I...V...D...E...N..\n",
"\n",
"\n",
"so the ciphertext is read from the above line-by-line (ignoring the dots) as\n",
"\n",
"\n",
"WECRLTE ERDSOEEFEAOC AIVDEN\n",
"\n",
"\n",
"with spaces removed. The sequence of indices that transpose the plaintext to ciphertext is given by `rf_key(3)(25)` as\n",
"\n",
"```Python\n",
"[0, 4, 8, 12, 16, 20, 24, \n",
" 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, \n",
" 2, 6, 10, 14, 18, 22 ]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"nbgrader": {
"grade": false,
"grade_id": "rf_key",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
}
},
"outputs": [],
"source": [
"def encrypt(plaintext, key):\n",
" \"\"\"\n",
" Encryption function for a general transposition cipher.\n",
"\n",
" Parameters\n",
" ----------\n",
" plaintext: str\n",
" Text to be encrypted.\n",
" key: function\n",
" A function that takes the length of the plaintext as an argument and\n",
" returns a sequence of indices that transpose the plaintext into the\n",
" ciphertext.\n",
"\n",
" Returns\n",
" -------\n",
" str: The ciphertext.\n",
" \"\"\"\n",
" return \"\".join(plaintext[i] for i in key(len(plaintext)))\n",
"\n",
"\n",
"def decrypt(ciphertext, key):\n",
" \"\"\"\n",
" Decryption function for a general transposition cipher.\n",
"\n",
" Parameters\n",
" ----------\n",
" ciphertext: str\n",
" Text to be descrypted.\n",
" key: function\n",
" A function that takes the length of the plaintext as an argument and\n",
" returns a sequence of indices that transpose the plaintext into the\n",
" ciphertext.\n",
"\n",
" Returns\n",
" -------\n",
" str: The plaintext.\n",
" \"\"\"\n",
" return \"\".join(\n",
" ciphertext[i]\n",
" for (i, j) in sorted(enumerate(key(len(ciphertext))), key=lambda x: x[1])\n",
" )\n",
"\n",
"\n",
"def rf_key(k):\n",
" \"\"\"\n",
" Generation of the sequence of indices for Rail Fence transposition cipher.\n",
"\n",
" Parameters\n",
" ----------\n",
" k: positive int\n",
" Number of rails.\n",
"\n",
" Returns\n",
" -------\n",
" Function: The key function that takes the length of the plaintext as an\n",
" argument and returns a sequence of indices that transpose the plaintext\n",
" into the ciphertext.\n",
" \"\"\"\n",
" ### BEGIN SOLUTION\n",
" return lambda n: (\n",
" i\n",
" for r in range(k)\n",
" for c in range(0, n, 2 * (k - 1))\n",
" for i in ((c+r, c+2 * (k - 1) - r) if 0 < r < k - 1 else (c+r,))\n",
" if 0 <= i < n\n",
" )\n",
" ### END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {
"nbgrader": {
"grade": true,
"grade_id": "test-rf_key",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
}
},
"outputs": [],
"source": [
"# tests\n",
"plaintext = \"WE ARE DISCOVERED FLEE AT ONCE\".replace(\" \", \"\")\n",
"key = rf_key(3)\n",
"ciphertext = encrypt(plaintext, key)\n",
"assert ciphertext == 'WECRLTEERDSOEEFEAOCAIVDEN'\n",
"assert plaintext == decrypt(ciphertext, key)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise**\n",
"\n",
"Complete the function `rf_demo` that returns the string that demonstrate the Rail Fence cipher. For the previous example, it should return the string for\n",
"\n",
"\n",
"W...E...C...R...L...T...E\n",
".E.R.D.S.O.E.E.F.E.A.O.C.\n",
"..A...I...V...D...E...N..\n",
""
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {
"nbgrader": {
"grade": false,
"grade_id": "rf_demo",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
}
},
"outputs": [],
"source": [
"def rf_demo(plaintext, k):\n",
" n = len(plaintext)\n",
" arr = [[\".\"] * n for i in range(k)]\n",
" ### BEGIN SOLUTION\n",
" y = [*range(k), *range(k - 2, 0, -1)]\n",
" for i in range(n):\n",
" arr[y[i % len(y)]][i] = plaintext[i]\n",
" ### END SOLUTION\n",
" return \"\\n\".join(\"\".join(_) for _ in arr)"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {
"nbgrader": {
"grade": true,
"grade_id": "test-rf_demo",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"W...E...C...R...L...T...E\n",
".E.R.D.S.O.E.E.F.E.A.O.C.\n",
"..A...I...V...D...E...N..\n"
]
}
],
"source": [
"# tests\n",
"expected = 'W...E...C...R...L...T...E\\n.E.R.D.S.O.E.E.F.E.A.O.C.\\n..A...I...V...D...E...N..'\n",
"got = rf_demo(plaintext,3)\n",
"print(got)\n",
"assert got == expected"
]
}
],
"metadata": {
"celltoolbar": "Create Assignment",
"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.8.12"
},
"latex_envs": {
"LaTeX_envs_menu_present": true,
"autoclose": false,
"autocomplete": true,
"bibliofile": "biblio.bib",
"cite_by": "apalike",
"current_citInitial": 1,
"eqLabelWithNumbers": true,
"eqNumInitial": 1,
"hotkeys": {
"equation": "Ctrl-E",
"itemize": "Ctrl-I"
},
"labels_anchors": false,
"latex_user_defs": false,
"report_style_numbering": false,
"user_envs_cfg": false
},
"rise": {
"enable_chalkboard": true,
"scroll": true,
"theme": "white"
},
"toc": {
"base_numbering": 1,
"nav_menu": {
"height": "195px",
"width": "330px"
},
"number_sections": true,
"sideBar": true,
"skip_h1_title": true,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {
"height": "454.418px",
"left": "1533px",
"top": "110.284px",
"width": "435.327px"
},
"toc_section_display": true,
"toc_window_display": false
},
"widgets": {
"application/vnd.jupyter.widget-state+json": {
"state": {},
"version_major": 2,
"version_minor": 0
}
}
},
"nbformat": 4,
"nbformat_minor": 4
}