{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"grade": false,
"grade_id": "cell-7850c17f2b74b4f8",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"# Part 0: Representing numbers as strings\n",
"\n",
"The following exercises are designed to reinforce your understanding of how we can view the encoding of a number as string of digits in a given base.\n",
"\n",
"> If you are interested in exploring this topic in more depth, see the [\"Floating-Point Arithmetic\" section](https://docs.python.org/3/tutorial/floatingpoint.html) of the Python documentation."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"grade": false,
"grade_id": "cell-451d6ed7e49d5e04",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Integers as strings\n",
"\n",
"Consider the string of digits:\n",
"\n",
"```python\n",
" '16180339887'\n",
"```\n",
"\n",
"If you are told this string is for a decimal number, meaning the base of its digits is ten (10), then its value is given by\n",
"\n",
"$$\n",
" [\\![ \\mathtt{16180339887} ]\\!]_{10} = (1 \\times 10^{10}) + (6 \\times 10^9) + (1 \\times 10^8) + \\cdots + (8 \\times 10^1) + (7 \\times 10^0) = 16,\\!180,\\!339,\\!887.\n",
"$$\n",
"\n",
"Similarly, consider the following string of digits:\n",
"\n",
"```python\n",
" '100111010'\n",
"```\n",
"\n",
"If you are told this string is for a binary number, meaning its base is two (2), then its value is\n",
"\n",
"$$\n",
" [\\![ \\mathtt{100111010} ]\\!]_2 = (1 \\times 2^8) + (1 \\times 2^5) + \\cdots + (1 \\times 2^1).\n",
"$$\n",
"\n",
"(What is this value?)\n",
"\n",
"And in general, the value of a string of $d+1$ digits in base $b$ is,\n",
"\n",
"$$\n",
" [\\![ s_d s_{d-1} \\cdots s_1 s_0 ]\\!]_b = \\sum_{i=0}^{d} s_i \\times b^i.\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"grade": false,
"grade_id": "cell-984e8904a5b92c45",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"**Bases greater than ten (10).** Observe that when the base at most ten, the digits are the usual decimal digits, `0`, `1`, `2`, ..., `9`. What happens when the base is greater than ten? For this notebook, suppose we are interested in bases that are at most 36; then, we will adopt the convention of using lowercase Roman letters, `a`, `b`, `c`, ..., `z` for \"digits\" whose values correspond to 10, 11, 12, ..., 35.\n",
"\n",
"> Before moving on to the next exercise, run the following code cell. It has three functions, which are used in some of the testing code. Given a base, one of these functions checks whether a single-character input string is a valid digit; and the other returns a list of all valid string digits. (The third one simply prints the valid digit list, given a base.) If you want some additional practice reading code, you might inspect these functions."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"grade": false,
"locked": true,
"solution": false
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
   "The valid base 6 digits: 0, 1, 2, 3, 4, 5\n",
   "The valid base 16 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f\n",
   "The valid base 23 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, g, h, i, j, k, l, m\n"
]
}
],
"source": [
"def is_valid_strdigit(c, base=2):\n",
" if type (c) is not str: return False # Reject non-string digits\n",
" if (type (base) is not int) or (base < 2) or (base > 36): return False # Reject non-integer bases outside 2-36\n",
" if base < 2 or base > 36: return False # Reject bases outside 2-36\n",
" if len (c) != 1: return False # Reject anything that is not a single character\n",
" if '0' <= c <= str (min (base-1, 9)): return True # Numerical digits for bases up to 10\n",
" if base > 10 and 0 <= ord (c) - ord ('a') < base-10: return True # Letter digits for bases > 10\n",
" return False # Reject everything else\n",
"\n",
"def valid_strdigits(base=2):\n",
" POSSIBLE_DIGITS = '0123456789abcdefghijklmnopqrstuvwxyz'\n",
" return [c for c in POSSIBLE_DIGITS if is_valid_strdigit(c, base)]\n",
"\n",
"def print_valid_strdigits(base=2):\n",
" valid_list = valid_strdigits(base)\n",
" if not valid_list:\n",
"    msg = '(none)'\n",
" else:\n",
"    msg = ', '.join([c for c in valid_list])\n",
" print('The valid base ' + str(base) + ' digits: ' + msg)\n",
" \n",
"# Quick demo:\n",
"print_valid_strdigits(6)\n",
"print_valid_strdigits(16)\n",
"print_valid_strdigits(23)"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"grade": false,
"locked": true,
"solution": false
}
},
"source": [
"**Exercise 0** (3 points). Write a function, `eval_strint(s, base)`. It takes a string of digits `s` in the base given by `base`. It returns its value as an integer.\n",
"\n",
"That is, this function implements the mathematical object, $[\\![ s ]\\!]_b$, which would convert a string $s$ to its numerical value, assuming its digits are given in base $b$. For example:\n",
"\n",
"```python\n",
" eval_strint('100111010', base=2) == 314\n",
"```\n",
"\n",
"> Hint: Python makes this exercise very easy. Search Python's online documentation for information about the `int()` constructor to see how you can apply it to solve this problem. (You have encountered this constructor already, in Notebook/Assignment 2.)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"nbgrader": {
"grade": false,
"grade_id": "eval_strint",
"locked": false,
"schema_version": 1,
"solution": true
}
},
"outputs": [],
"source": [
"def eval_strint(s, base=2):\n",
" assert type(s) is str\n",
" assert 2 <= base <= 36\n",
" \n",
" sum = 0;\n",
" for x in s:\n",
"    if (x>='0') and (x<='9'):\n",
"          dig = ord(x) - ord('0')\n",
"    else:\n",
"          dig = ord(x) - ord('a') + 10\n",
"    sum = sum * base + dig;\n",
"    \n",
" return sum\n",
"    "
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"grade": true,
"grade_id": "eval_strint_test0",
"locked": true,
"points": "1",
"schema_version": 1,
"solution": false
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
   "'16180339887' -> 16180339887\n",
   "\n",
   "(Passed!)\n"
]
}
],
"source": [
"# Test: `eval_strint_test0` (1 point)\n",
"\n",
"def check_eval_strint(s, v, base=2):\n",
" v_s = eval_strint(s, base)\n",
" msg = \"'{}' -> {}\".format (s, v_s)\n",
" print(msg)\n",
" assert v_s == v, \"Results do not match expected solution.\"\n",
"\n",
"# Test 0: From the videos\n",
"check_eval_strint('16180339887', 16180339887, base=10)\n",
"print (\"\\n(Passed!)\")"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"grade": true,
"grade_id": "eval_strint_test1",
"locked": true,
"points": "1",
"solution": false
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
   "'100111010' -> 314\n",
   "\n",
   "(Passed!)\n"
]
}
],
"source": [
"# Test: `eval_strint_test1` (1 point)\n",
"check_eval_strint('100111010', 314, base=2)\n",
"print (\"\\n(Passed!)\")"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"grade": true,
"grade_id": "eval_strint_test2",
"locked": true,
"points": "1",
"solution": false
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
   "'a205b064' -> 2718281828\n",
   "\n",
   "(Passed!)\n"
]
}
],
"source": [
"# Test: `eval_strint_test2` (1 point)\n",
"check_eval_strint('a205b064', 2718281828, base=16)\n",
"print (\"\\n(Passed!)\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"grade": false,
"grade_id": "cell-ba1a6cefcc7cb356",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Fractional values\n",
"\n",
"Recall that we can extend the basic string representation to include a fractional part by interpreting digits to the right of the \"fractional point\" (i.e., \"the dot\") as having negative indices. For instance,\n",
"\n",
"$$\n",
" [\\![ \\mathtt{3.14} ]\\!]_{10} = (3 \\times 10^0) + (1 \\times 10^{-1}) + (4 \\times 10^{-2}).\n",
"$$\n",
"\n",
"Or, in general,\n",
"\n",
"$$\n",
" [\\![ s_d s_{d-1} \\cdots s_1 s_0 \\, \\underset{\\Large\\uparrow}{\\Huge\\mathtt{.}} \\, s_{-1} s_{-2} \\cdots s_{-r} ]\\!]_b = \\sum_{i=-r}^{d} s_i \\times b^i.\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exercise 1** (4 points). Suppose a string of digits `s` in base `base` contains up to one fractional point. Complete the function, `eval_strfrac(s, base)`, so that it returns its corresponding floating-point value.\n",
"\n",
"Your function should *always* return a value of type `float`, even if the input happens to correspond to an exact integer.\n",
"\n",
"Examples:\n",
"\n",
"```python\n",
" eval_strfrac('3.14', base=10) ~= 3.14\n",
" eval_strfrac('100.101', base=2) == 4.625\n",
" eval_strfrac('2c', base=16) ~= 44.0 # Note: Must be a float even with an integer input!\n",
"```\n",
"\n",
"> _Comment._ Because of potential floating-point roundoff errors, as explained in the videos, conversions based on the general polynomial formula given previously will not be exact. The testing code will include a built-in tolerance to account for such errors.\n",
">\n",
"> _Hint._ You should be able to construct an elegant solution that reuses the function, `eval_strint()`, from Exercise 0."
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"nbgrader": {
"grade": false,
"grade_id": "eval_strfrac",
"locked": false,
"schema_version": 1,
"solution": true
}
},
"outputs": [],
"source": [
"def is_valid_strfrac(s, base=2):\n",
" return all([is_valid_strdigit(c, base) for c in s if c != '.']) \\\n",
"    and (len([c for c in s if c == '.']) <= 1)\n",
" \n",
"def eval_strfrac(s, base=2):\n",
" assert is_valid_strfrac(s, base), \"'{}' contains invalid digits for a base-{} number.\".format(s, base)\n",
" \n",
" dot = s.find('.')\n",
" if (dot == -1):\n",
"    return eval_strint(s, base) * 1.0\n",
" \n",
" s1 = s[:dot]\n",
" s2 = s[dot+1:]\n",
" \n",
" val1 = eval_strint(s1, base) * 1.0\n",
"\n",
"    \n",
" val2 = 0\n",
" p = 1\n",
" for x in s2:\n",
"    p /= base\n",
"    if (x>='0') and (x<='9'):\n",
"          dig = ord(x) - ord('0')\n",
"    else:\n",
"          dig = ord(x) - ord('a') + 10\n",
"\n",
"    \n",
"    val2 += p * dig\n",
" \n",
" return val1 + val2\n",
" \n",
" ###\n",
" ### YOUR CODE HERE\n",
" ###\n"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
   "text/plain": [
   "0.75"
   ]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"eval_strfrac('0.11', 2)"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"grade": true,
"grade_id": "eval_strfrac_test0",
"locked": true,
"points": "1",
"schema_version": 1,
"solution": false
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
   "[3.14]_{10} ~= 3.14: You computed 3.14, which differs by 0.0.\n",
   "[100.101]_{2} ~= 4.625: You computed 4.625, which differs by 0.0.\n",
   "[11.0010001111]_{2} ~= 3.1396484375: You computed 3.1396484375, which differs by 0.0.\n",
   "[f.a]_{16} ~= 15.625: You computed 15.625, which differs by 0.0.\n",
   "\n",
   "(Passed!)\n"
]
}
],
"source": [
"# Test 0: `eval_strfrac_test0` (1 point)\n",
"\n",
"def check_eval_strfrac(s, v_true, base=2, tol=1e-7):\n",
" v_you = eval_strfrac(s, base)\n",
" assert type(v_you) is float, \"Your function did not return a `float` as instructed.\"\n",
" delta_v = v_you - v_true\n",
" msg = \"[{}]_{{{}}} ~= {}: You computed {}, which differs by {}.\".format(s, base, v_true,\n",
"                                                                         v_you, delta_v)\n",
" print(msg)\n",
" assert abs(delta_v) <= tol, \"Difference exceeds expected tolerance.\"\n",
" \n",
"# Test cases from the video\n",
"check_eval_strfrac('3.14', 3.14, base=10)\n",
"check_eval_strfrac('100.101', 4.625, base=2)\n",
"check_eval_strfrac('11.0010001111', 3.1396484375, base=2)\n",
"\n",
"# A hex test case\n",
"check_eval_strfrac('f.a', 15.625, base=16)\n",
"\n",
"print(\"\\n(Passed!)\")"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"deletable": false

Download Calendar.py and use_calendar.py. Complete all functions...