hw5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework 5: Iterators, Memoization and Exceptions(18 pts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "name: Robert Frazier\n",
    "\n",
    "email: robertcf@umich.edu\n",
    "\n",
    "This homework assignment took me XX hours in total to complete. (Please help us to gauge the difficulty of the assignment.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Collaboration Disclosure\n",
    "\n",
    "In the cell below, please list *everyone* with whom you discussed any of the homework problems, excluding only the GSIs and the course instructor. \n",
    "\n",
    "If you did not discuss the homework with anyone else, write __\"I did not discuss this homework with anyone.\"__\n",
    "\n",
    "Even if you discuss questions with other, the code you submit must be only yours. All work is checked with the [MOSS plagiarism detector](https://theory.stanford.edu/~aiken/moss/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "## Submission Instructions\n",
    "Your homework solutions should be written entirely in this Jupyter notebook file. Once it contains your solutions, you should submit this notebook through Canvas. \n",
    "\n",
    "\n",
    "Before submitting, please make sure to __Cells->Run All__ executes without errors; errors in your code translate directly to point deductions. \n",
    "In general, you don't need to do explicitly raise errors (e.g. with the ```raise``` function) if we don't ask you to in the problem statement.\n",
    "However, even in cases where we ask you to check for errors, your submission should not contain any examples of your functions actually raising those errors.\n",
    "\n",
    "Note that many parts of this homework where you are expected to type in code will have ```NotImplementedError()``` as a placeholder. You need to delete this function and replace it with your own code.\n",
    "\n",
    "## Homework tips \n",
    "\n",
    "1. **Start early!** If you run into trouble installing things or importing packages, it’s\n",
    "best to find those problems well in advance, not the night before your assignment is\n",
    "due when we cannot help you!\n",
    "\n",
    "2. **Make sure you back up your work!** At a minimum, do your work in a Dropbox\n",
    "folder. Better yet, use git, which is well worth your time and effort to learn.\n",
    "\n",
    "3. **Be careful to follow directions!** Remember that Python is case sensitive. If\n",
    "you are ask you to define a function called my_function and you define a function\n",
    "called My_Function, you will not receive full credit. You may want to copy-paste\n",
    "the function names below to make sure that the functions in your notebook match.\n",
    "\n",
    "## Error checking\n",
    "\n",
    "You do not need to do error checking (raising errors, etc.) in your code unless we explicitly ask you to so in a problem.\n",
    "\n",
    "\n",
    "## Nbgrader\n",
    "\n",
    "We will be using `nbgrader` to grade your jupyter notebook. You will notice some `read-only` cells in the assignment that contain `assert` statements. These are tests that your code must pass for your solution to be correct. If any of the tests fail, you will get an python error and not get points for that question. \n",
    "\n",
    "**Note:** The tests shown not are not comprehensive; additional tests will be used at grading time. You are encouraged to read the problem carefully and verify your code covers all possible cases.\n",
    "\n",
    "**Be careful:** If a jupyter notebook cell takes longer than `60s` to run, the autograder will not grade it and you will receive zero credit for that question."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "---\n",
    "##  Problem 1: Iterator (6 pts)\n",
    "Implement a custom range iterator that mimics some of the basic functionality of Python's built-in `range()` function (You can not use `range()` direclty). This exercise will help you understand how iterators work in Python.\n",
    "\n",
    "**Note:** there is the same question as our in-class practice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "##  Problem 1.1: A custom class called `MyRange` (3 pts)\n",
    "1. Create a class named `MyRange` that takes two integer arguments in its constructor:\n",
    "\n",
    "     **start:**  the first value of the range\n",
    "\n",
    "   \n",
    "     **start:**: the value to stop before (exclusive)\n",
    "\n",
    "3. The class should implement the iterator protocol, making it usable in a for loop.\n",
    "\n",
    "4. Each iteration should return the next integer in the sequence, starting from start and incrementing by 1 each time.\n",
    "The iteration should stop when the value would become equal to or greater than end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8b3ca0dce1c6b74dea5990bd102cf7f2",
     "grade": false,
     "grade_id": "class_my_range",
     "locked": false,
     "schema_version": 3,
     "solution": true
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class MyRange:\n",
    "    def __init__(self, start, end):\n",
    "        self.value = start\n",
    "        self.end = end\n",
    "    \n",
    "    def __iter__(self):\n",
    "        return self\n",
    "    \n",
    "    def __next__(self):\n",
    "        if self.value >= self.end:\n",
    "            raise StopIteration\n",
    "        current = self.value\n",
    "        self.value += 1\n",
    "        return current"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "c9f2f03baf27603b6fcb875f81d83278",
     "grade": true,
     "grade_id": "correct_MYRANGE",
     "locked": false,
     "points": 3,
     "schema_version": 3,
     "solution": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "nums = MyRange(1, 5)\n",
    "assert next(nums) == 1, \"First value should be 1\"\n",
    "assert next(nums) == 2, \"Second value should be 2\"\n",
    "assert next(nums) == 3, \"Third value should be 3\"\n",
    "assert next(nums) == 4, \"Fourth value should be 4\"\n",
    "\n",
    "try:\n",
    "    next(nums)\n",
    "    assert False, \"StopIteration should have been raised\"\n",
    "except StopIteration:\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "##  Problem 1.2: A custom generator called `my_range` (3 pts)\n",
    "Create a function `my_range(start, end)` that generates a sequence of numbers from start to end (exclusive). The function should be implemented as a generator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "6f530107d27c11921c848da328756c5f",
     "grade": false,
     "grade_id": "class_my_range2",
     "locked": false,
     "schema_version": 3,
     "solution": true
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def my_range(start, end):\n",
    "    current = start\n",
    "    while current < end:\n",
    "        yield current\n",
    "        current += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ee3c26ceb70f3345602b1fde74114806",
     "grade": true,
     "grade_id": "correct_range",
     "locked": false,
     "points": 3,
     "schema_version": 3,
     "solution": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "nums = my_range(1, 5)\n",
    "assert next(nums) == 1, \"First value should be 1\"\n",
    "assert next(nums) == 2, \"Second value should be 2\"\n",
    "assert next(nums) == 3, \"Third value should be 3\"\n",
    "assert next(nums) == 4, \"Fourth value should be 4\"\n",
    "\n",
    "try:\n",
    "    next(nums)\n",
    "    assert False, \"StopIteration should have been raised\"\n",
    "except StopIteration:\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Problem 2: Memoization (6 pts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "###  2.1: Climbing stairs (3 pts)\n",
    "You are climbing a staircase. It takes n steps to reach the top.\n",
    "\n",
    "Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Let's try not use recursion in your implementation. Instead, use an iterative approach or use memoization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import factorial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def climb_stairs(n):\n",
    "    ways = 0 #the construction with only 1s \n",
    "    twos = n//2 #how many twos I can fit in the number \n",
    "    ones = n - twos *2 #how many ones I can now use in my construction \n",
    "    while twos > -1: #now going through the remaining options\n",
    "        ways += factorial((twos+ones))/(factorial(ones)*factorial(twos))\n",
    "        twos -= 1\n",
    "        ones += 2\n",
    "    return(int(ways))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "1cdadbb3c4fa6723585209dcc2523c2a",
     "grade": true,
     "grade_id": "correct_stairs",
     "locked": false,
     "points": 3,
     "schema_version": 3,
     "solution": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "assert climb_stairs(1) == 1, \"Test case 1 failed\"\n",
    "assert climb_stairs(2) == 2, \"Test case 2 failed\"\n",
    "assert climb_stairs(3) == 3, \"Test case 3 failed\"\n",
    "assert climb_stairs(7) == 21, \"Test case 4 failed\"\n",
    "assert climb_stairs(35) == 14930352, \"Test case 5 failed (larger input)\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "###  2.2: Two Sum(3 pts)\n",
    "Given an array of integers nums and an integer `target`, return indices of the two numbers such that they add up to `target`.\n",
    "\n",
    "You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.\n",
    "\n",
    "**Note:**: This is a classical interview question. Try to use a dictionary as a \"mini database\" to store and quickly look up values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "1ffaad151cc539ce37a750454b5c7a8c",
     "grade": false,
     "grade_id": "sum",
     "locked": false,
     "schema_version": 3,
     "solution": true
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def two_sum(nums, target):\n",
    "    store = dict()\n",
    "    for a, i in enumerate(nums):\n",
    "        if i > target:\n",
    "            pass\n",
    "        want = target - i\n",
    "        if want in store:\n",
    "            return([store[want],a])\n",
    "        else: \n",
    "            store[i] = a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d598b60172adc77b334b27629949d677",
     "grade": true,
     "grade_id": "correct_two_sum",
     "locked": false,
     "points": 3,
     "schema_version": 3,
     "solution": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "assert two_sum([2, 7, 11, 15], 9) == [0, 1], \"Test case 1 failed\"\n",
    "assert two_sum([3, 2, 4], 6) == [1, 2], \"Test case 2 failed\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Problem 3: Error Handling (6 pts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "###  3.1: Safely Divide(3 pts)\n",
    "Write a function called `safe_divide(a, b)` that safely performs division of a by b. The function should:\n",
    "1) Return the result of a divided by b if b is not zero.\n",
    "\n",
    "2) Return the string \"Cannot divide by zero\" if b is zero.\n",
    "\n",
    "3) Use a try-except block to handle the `ZeroDivisionError`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "e4ad839bb73f8844f03643945868e89f",
     "grade": false,
     "grade_id": "divide",
     "locked": false,
     "schema_version": 3,
     "solution": true
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def safe_divide(a, b):\n",
    "    try:\n",
    "        div = a/b\n",
    "        return(div)\n",
    "    except ZeroDivisionError:\n",
    "        return(\"Cannot divide by zero\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "bea226971289e1a7ef0c9da4d6bb2e94",
     "grade": true,
     "grade_id": "correct_divide",
     "locked": false,
     "points": 3,
     "schema_version": 3,
     "solution": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "assert safe_divide(10, 2) == 5.0, \"Test case 1 failed\"\n",
    "assert safe_divide(10, 0) == \"Cannot divide by zero\", \"Test case 2 failed\"\n",
    "assert isinstance(safe_divide(10, 3), float), \"Test case 5 failed: Result should be a float\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "###  3.2: Raise our own error (3 pts)\n",
    "Create a function called `validate_age(age)` that does the following:\n",
    "\n",
    "Takes an age parameter (integer).\n",
    "1) If age is not int or float, raise `TypeError` with message \"Age must be a number\".\n",
    "2) If the age is less than 0, raise a `ValueError` with message \"Age cannot be negative\".\n",
    "3) If the age is over 150, raise the `ValueError` with the message \"Age cannot be over 150\".\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "908c73107c674d8686b291592f65b4be",
     "grade": false,
     "grade_id": "validate",
     "locked": false,
     "schema_version": 3,
     "solution": true
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def validate_age(age):\n",
    "    if not isinstance(age, (int, float)):\n",
    "        raise TypeError(\"Age must be a number\")\n",
    "    elif age < 0:\n",
    "        raise ValueError(\"Age cannot be negative\")\n",
    "    elif age > 150:\n",
    "        raise ValueError(\"Age cannot be over 150\")\n",
    "    else:\n",
    "        return \"Valid age: \" + str(age)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a391e19aa086f3a37b10a6f44608137f",
     "grade": true,
     "grade_id": "correct_error",
     "locked": false,
     "points": 3,
     "schema_version": 3,
     "solution": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "assert validate_age(25) == \"Valid age: 25\", \"Test for valid age failed\"\n",
    "try:\n",
    "    validate_age(\"twenty\")\n",
    "    assert False, \"Non-numeric age should raise TypeError\"\n",
    "except TypeError as e:\n",
    "    assert str(e) == \"Age must be a number\", \"Incorrect error message for non-numeric input\"\n",
    "    \n",
    "try:\n",
    "    validate_age(-5)\n",
    "    assert False, \"Negative age should raise ValueError\"\n",
    "except ValueError as e:\n",
    "    assert str(e) == \"Age cannot be negative\", \"Incorrect error message for negative age\"\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "general",
   "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.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}