midterm2018_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DW mid-terms 2018 solutions <br>\n",
    "### These solutions are student compiled and might contain errors (especially for qn 1 & 2) <br> Credit goes to Team Anonymous on Piazza<br><br> Part A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 'aces'\n",
    "y = 1.23\n",
    "z = x\n",
    "x = y\n",
    "y = z\n",
    "print(x, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q1(a) After the above code is executed, at line 6, what is seen on the screen is 1.23aces. <br><br>By explaining what each line of the code below (for lines 1 to 5) does, show how the code below switches the objects assigned to variables x and y. <br><br>Your explanation must state when objects are created and their data types, and also how names are assigned to these objects. Diagrams could be helpful in your explanation. (6 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sample answer 1:**<br>\n",
    "At line 1, string object 'aces' is assigned to frame 'x'. At line 2, float object of value 1.23 is assigned to frame 'y'. At line 3, a shallow copy of string object 'aces' from frame 'x' is assigned to frame 'z'. At line 4, a shallow copy of the float object of value 1.23 from frame 'y' is assigned to frame 'x' and overwirtes the string object 'aces'. At line 5, a shallow copy of string object 'aces' from frame 'z' is assigned to frame 'y' and overwrites the float object of value 1.23. The final result is: <br>\n",
    "Stack | Object after line 3 > 4 > 5<br>\n",
    "x\t|  'aces' > 1.23 > 1.23<br>\n",
    "y\t|  1.23 > 1.23 > 'aces'<br>\n",
    "z\t|  'aces' > 'aces' > 'aces'<br>\n",
    "The contents of both x & y are fetched when print(x,y) is executed at line 6. Thus, 1.23aces is printed in the order of x then y."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q1(b) When the following code is executed, after line 12, what is seen on the screen is  True. <br><br>   i) Using how names are assigned to objects in memory, explain why. Diagrams could be helpful in your explanation. (3 points) <br><br>ii) The intention of the programmer is to create two lists showing the words for ‘seven’, ‘eight’ and ‘nine’ for both Greek and French. State one modification to the code at line 8 so that line 13 prints out the correct output. (1point)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "french= [ 'sept', 'huit', 'neuf'] # the words mean 'seven','eight','nine'.\n",
    "greek = french # this is line 8\n",
    "greek[0] = 'epta' # 'seven'\n",
    "greek[1] = 'okto' # 'eight'\n",
    "greek[2] = 'enea' # 'nine'\n",
    "print(greek is french) # this is 'line 12'\n",
    "print(french, greek)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sample answer 1:**<br>\n",
    "i) At line 1, a list object is created for frame 'french'. At line 2, frame 'greek' is assigned to refer to the same list object as frame 'french'. Thus, even after the contents of the list is changed, line 12's shallow equivalence check 'is' returns true as both frames 'french' and 'greek' still refers to the same list object in memory. <br><br>\n",
    "ii) I would repace line 8 with 'greek = list(french)' to another list object similar in contents to frame 'french' is created for frame 'greek'.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2 [10 points]\n",
    "### a) Is there anything wrong with the following program? If yes, what is wrong?  (2 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import = int(input(\"Enter a number: \"))\n",
    "if import==2:\n",
    "    print(\"Yes\")\n",
    "else: \n",
    "    print(\"No\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sample solution 1:**<br>\n",
    "Synthax error. 'import' is a reserved keyword in python and neither be used as a variable name nor be assigned to an 'int' type object. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### b) If break is removed from the following programand the program is run, what will be printed out? (2 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_string = \"Computing\"  \n",
    "for character in my_string:\n",
    "    print(character)\n",
    "    if character == \"u\":\n",
    "        print(\"Found 'u' :)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution:** <br>\n",
    "C<br>\n",
    "o<br>\n",
    "m<br>\n",
    "p<br>\n",
    "u<br>\n",
    "Found 'u' :)<br>\n",
    "t<br>\n",
    "i<br>\n",
    "n<br>\n",
    "g<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### c) Look at the following function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def my_function(n):   \n",
    "    return_value = None   \n",
    "    if n == 0 or n == 1:       \n",
    "        return_value = False # not run   \n",
    "    i=2   \n",
    "    while i*0.5:       \n",
    "        if n%i==0:           \n",
    "            return_value = False # not run           \n",
    "            break # not run       \n",
    "        i += 1       \n",
    "        return_value = True    \n",
    "    return return_value\n",
    "my_function(37)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let the function tested to be my_function(37)<br> <br>a) What will be the output? (1 point)<br> <br>b) Identify the lines of the program which will be executed when the input is 37. Do this by entering the codes from those lines to eDimension. (2 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution:** <br>\n",
    "a) True.<br>\n",
    "b) (enter those lines of code not tagged by # not run)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### d) In the context of the 1D projects you have completed so far in this course, look at the following function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def forward(speed, duration):\n",
    "    robot.wheels(speed, speed)\n",
    "    robot.sleep(duration)\n",
    "    robot.wheels(0,0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### a) Why is it not necessary to have a return statement in this function? (1 point)<br><br>b) If we change  robot.wheels(speed, speed) to robot.wheels(speed1, speed2) and the function header is also modified to take in speed1 and speed2, how will the movement of the robot change? You can assume that speed1 and speed2 are different and both speed1 and speed2 are positive numbers. (1 point)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sample solution 1:** <br>\n",
    "a) In the above function to move the robot forward at some speed for some duration, no values are expected to be reused or caught by the function. Hence, no return statement is required. <br><br>\n",
    "b) If speed1 > speed2, the robot will still travel forward but with a leftwards dispalcement. If speed1 < speed2, the robot will still travel forward but with a rightwards dispalcement. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part B <br><br> Q3 [10 points] <br><br> A frustum is a parallel truncation of a right pyramid. A piece of metal is in the shape of a frustum with a square base. The side length of the top square is s1 and the side length of the bottom square is s2. The height of the frustum is H. <br><br>The volume of the frustum is given by the formula: <br> $$Volume = \\frac{H}{3}(A1 + A2 + \\sqrt{A1 \\text{ x } A2})$$ where A1 is the area of the upper square, A2 is the area of the lower square, and H is the height of the frustum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### a) Write a python function area_square(s) that takes the side of a square as an input argument s, and returns the area of the square.<br><br>b) Write a python function vol_frustum(top_area, bottom_area, height) that takes three arguments, a top area, a bottom area and a height in that order, and returns the volume of the frustum.<br><br>c) Write a python function get_volume(s1, s2, height) that takes three arguments, a top side length, a bottom side length and a height and returns the volume of a frustum based on those dimensions. This function should first call area_square to obtain the two needed areas, and then call vol_frustum to evaluate the volume. <br><br>All input arguments and return values are floats. Please round only your final output of get_volume to three decimal places. Please use math.sqrt() to compute the square root in your python code. Note that you get only full marks if your get_volume function makes use of the other two functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "def area_square(s):\n",
    "    return s**2.\n",
    "\n",
    "def vol_frustum(top_area, bottom_area, height):\n",
    "    return (height/3)*(top_area + bottom_area + math.sqrt(top_area*bottom_area))\n",
    "                       \n",
    "def get_volume(s1, s2, height):\n",
    "    return round(vol_frustum(area_square(s1), area_square(s2), height), 3)\n",
    "\n",
    "## TEST CASES ##\n",
    "print('{:.3f}'.format(area_square(2)))\n",
    "print('{:.3f}'.format(area_square(3)))\n",
    "print('{:.3f}'.format(vol_frustum(1,4,2)))\n",
    "print('{:.3f}'.format(vol_frustum(2,2,2)))\n",
    "print('{:.3f}'.format(get_volume(1,2,2)))\n",
    "print('{:.3f}'.format(get_volume(1.5,3.3,5.0)))\n",
    "print('{:.3f}'.format(get_volume(3.6,6.4,4.0)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q4 [10 points]<br><br>Implement a function determinant(matrix) that takes a matrix as input (represented as a nested list) and returns its determinant as output. The function should satisfy the following requirements: <br><br>1) If the input matrixis not of dimension n x n (for 1 ≤n ≤3), the function should return None<br><br> 2) The function is to be implemented withoutimporting any libraries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def determinant(matrix):\n",
    "    M = matrix\n",
    "    try:\n",
    "        a = len(M)\n",
    "        a = len(M[0])\n",
    "    except:\n",
    "        return None\n",
    "    \n",
    "    if len(M) == 1:\n",
    "        for row in M:\n",
    "            if len(row) != 1:\n",
    "                return None\n",
    "        return M[0][0]\n",
    "    if len(M) == 2:\n",
    "        for row in M:\n",
    "            if len(row) != 2:\n",
    "                return None\n",
    "        return M[0][0] * M[1][1] - M[0][1]*M[1][0]\n",
    "    if len(M) == 3:\n",
    "        for row in M:\n",
    "            if len(row) != 3:\n",
    "                return None\n",
    "        return (M[0][0] * M[1][1] * M[2][2] \n",
    "                + M[1][0] * M[2][1] * M[0][2] \n",
    "                + M[2][0] * M[0][1] * M[1][2]\n",
    "                - M[0][2] * M[1][1] * M[2][0]\n",
    "                - M[1][0] * M[0][1] * M[2][2]\n",
    "                - M[0][0] * M[2][1] * M[1][2])\n",
    "    \n",
    "## TEST CASES ##\n",
    "print(determinant([[100]]))\n",
    "print(determinant([[-5, -4],[-2, -3]]))\n",
    "print(determinant([[2, -3, 1], [2, 0, -1],[1, 4, 5]]))\n",
    "print(determinant([[0, 3, 5],[5, 5, 2],[3, 4, 3]]))\n",
    "print(determinant([[23], [-4, 4]]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q5 [15 points] <br><br>The Newton-Raphson (NR) method is an iterative method that approximates the root of a function. The accuracy of the answer is enhanced in successive iterations.<br><br>You need two create two functions: nrootand nroot_complex. The function nroot(n, i, num) is to determine the root of non-negative num. The function nroot_complex(n,i,num) to determine the root of negative num. Thefunction nroot_complex should call nroot to do the NR approximation. Note the output should give a constant$*$1j where j is the imaginary square root of -1. For odd n the output should give a negative value instead of constant$*$1j. This means that:<br><br>• When num is a non-negative number, nroot_complex should give the same result as nroot.<br>• When num is a negative number and n is even, nroot_complex should give a complex number with no real part, and its magnitude is the same as the output of nrootwhen num is positive.<br>• When numis a negative number and n is odd, nroot_complex should give a negative real number, and its magnitude is the same as the output of nroot when numis positive.<br><br>Round the output of nroot to 3 decimal places.Use x = 1 as your initial value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nroot(n,t,num):\n",
    "    x = 1\n",
    "    for i in range(t):\n",
    "        x -= ((x**n - num)/(n*(x**(n-1))))\n",
    "    return round(x,3)\n",
    "\n",
    "def nroot_complex(n,t,num):\n",
    "    if num > 0 or num == 0:\n",
    "        return nroot(n,t,num)\n",
    "    if num < 0 and n%2 == 1:\n",
    "        return -nroot(n,t,-num)\n",
    "    else:\n",
    "        return str(nroot(n,t,-num)) + 'j'\n",
    "    \n",
    "## TEST CASES ##\n",
    "print(nroot(2,5,2))\n",
    "print(nroot_complex(2,5,-4))\n",
    "print(nroot_complex(3,5,-8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q6 [30 points]<br><br>In this problem you will write a program to find a path through MRT stations from a starting station to an ending station with a maximum of one interchange.<br><br> The overall function is called find_path and it takes three arguments: (1) a file object to a text file containing the MRT lines and stations, (2) the starting station, and (3) the ending station. <br><br>This function should return a list of stations from a starting station to an ending station with a maximum of one interchange. The problem is decomposed by writing several other functions, described in the following parts.<br><br> For simplicity, the information given to you in this question is limited to the North South line and the East West line. Also, the branch line to Changi Airport is treated as a separate line. Hence the three lines are labelled in this question as follows: (1) NorthSouthLine (2) EastWestLine (EW) and (3) EastWestLine (CG). <br><br>a) read_stations(f): This function takes in a file object and returnsa dictionary. The dictionary has the MRT lines as its keys. The value of each key is a list of stations in that MRT line. <br><br>b) get_stationline(mrt): This function takes in a dictionary of MRT lines (i.e. the output of part (a) ). The function returns another dictionary which contains all the stations as its keys. The value for each key is a list of the MRT lines for that particular station. Note that if the station is an interchange, the list should contain all the lines calling at that station. <br><br>c) get_interchange(stationline): This function takes in a dictionary of stations and their lines (i.e. the output of part (b)). The function returns another dictionary which contains all the interchange stations as its keys. The value for each key is a list of the MRT lines for that particular interchange stations.<br><br>d) find_path(f, start, end): This function takes in three arguments: (1) the file object to a text file containing all the MRT lines and stations, (2) the startingstation, and (3) the endingstation. The function should return a list of stations starting from the starting station to the ending station with a maximum of one interchange.If there are more than one possible paths, the following considerations should be taken into account:<br><br>• If there is a path without changing MRT lines, the result should return this path.<br>• If the path must involve changing MRT lines, it will return the path with a minimum number of stations and containing only one interchange station.<br>• If no such path can be found as above, it will return None."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## PART A ##\n",
    "def read_stations(s):\n",
    "    st = ''.join(s.readlines()).split(\"=\")\n",
    "    ans = {}\n",
    "    for i in range(int((len(st)-1)/2)):\n",
    "        ans[st[2*i+1]] = (st[2*(i+1)].strip(\"\\n\")).split(\", \")\n",
    "    return ans\n",
    "\n",
    "## PART B ##\n",
    "def get_stationline(mrt):\n",
    "    ans = {}\n",
    "    for lines in mrt:\n",
    "        for station in mrt[lines]:\n",
    "            if station not in ans:\n",
    "                ans[station] = []\n",
    "                ans[station].append(lines)\n",
    "            else:\n",
    "                ans[station].append(lines)\n",
    "    return ans\n",
    "\n",
    "## PART C ##\n",
    "def get_interchange(stationline):\n",
    "    ans = {}\n",
    "    for stations in stationline:\n",
    "        if len(stationline[stations]) > 1:\n",
    "            ans[stations] = stationline[stations]\n",
    "    return ans\n",
    "\n",
    "## PART D ##\n",
    "def create_graph(f):\n",
    "    stations = read_stations(f)\n",
    "    stationline = get_stationline(stations)\n",
    "    interchange = [*get_interchange(stationline)]\n",
    "    network = {}\n",
    "    # Create a dictionary where station (key) is linked to all its connected stations (values)\n",
    "    for line in stations:\n",
    "        stations_ = stations.get(line)\n",
    "        network[stations_[-1]]=[stations_[-2]]  # End stations only conencted to one other station\n",
    "        for station in range(0,len(stations_)-1): \n",
    "            network.setdefault(stations_[station],[stations_[station-1]]).append(stations_[station+1]) \n",
    "        if stations_[0] not in interchange:        \n",
    "             network[stations_[0]]=[stations_[1]] # Removing non interchange connections that loops\n",
    "    network['City Hall'].append('Dhoby Ghaut')   # Add this pesky back edge       \n",
    "    for key in network:\n",
    "        network[key] = set(network.get(key)) # Apply set structure to dictionary values   \n",
    "    return network\n",
    "\n",
    "def bfs_paths(graph, start, goal):\n",
    "    # Since we only want the shortest path, we use Breath First Search on a queue structure for efficiency\n",
    "    queue = [(start, [start])]\n",
    "    while queue:\n",
    "        (vertex, path) = queue.pop(0)\n",
    "        for next in graph[vertex] - set(path):\n",
    "            if next == goal:\n",
    "                yield path + [next]\n",
    "            else:\n",
    "                queue.append((next, path + [next]))\n",
    "                \n",
    "\n",
    "import collections as c                \n",
    "def find_path(f, start, end):\n",
    "   try: \n",
    "    graph = create_graph(f)\n",
    "    possible_paths = list(bfs_paths(graph,start,end))\n",
    "    f.seek(0) # remember to reset readlines() counter to 0\n",
    "    stations = read_stations(f)\n",
    "    stationline = get_stationline(stations)\n",
    "    interchange = [*get_interchange(stationline)]\n",
    "    ans = []\n",
    "    for path in possible_paths:\n",
    "        line_counter = []\n",
    "        for station in path:\n",
    "            line_counter.append(stationline.get(station)[0])\n",
    "        # We count the total number of line types present. More than 1 interchange used if line type > 2   \n",
    "        if len(c.Counter(line_counter)) <= 2:\n",
    "                ans.append(path)\n",
    "    return ans[0] # Since we used BFS, first path found is always the shortest\n",
    "   except:\n",
    "    # A general catch block to return None    \n",
    "    return None    \n",
    "\n",
    "## TEST CASES ##\n",
    "print('Test 1')\n",
    "f=open('mrt_lines_short.txt','r') # Make sure directory is correct\n",
    "ans=find_path(f,'Boon Lay', 'Clementi')\n",
    "print(ans)\n",
    "f.close()\n",
    "print('Test 2')\n",
    "f=open('mrt_lines_short.txt','r') # Make sure directory is correct\n",
    "ans=find_path(f,'Changi Airport', 'Orchard')\n",
    "print(ans)\n",
    "f.close()\n",
    "print('Test 3')\n",
    "f=open('mrt_lines_short.txt','r') # Make sure directory is correct\n",
    "ans=find_path(f,'Boon Lay', 'Bukit Gombak')\n",
    "print(ans)\n",
    "f.close()\n",
    "print('Test 4')\n",
    "f=open('mrt_lines_short.txt','r') # Make sure directory is correct\n",
    "ans=find_path(f,'Tanah Merah', 'Orchard')\n",
    "print(ans)\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q7 [15 points] <br><br> Write a function decompose(pence), that takes as input some number of pence (as an integer), and returns as output an integer expressing how many different ways that the amount can be made up by using the available coins. At present, there are eight coins in general circulation: <br><br>1p, 2p, 5p, 10p, 20p, 50p, £1, and £2<br><br>Note that the function decompose(pence) can be implemented in a number of different ways, including by using brute force (i.e. exhaustive search). However, brute force implementations may only score a maximum of 12 points; the full 15 are only available for more elegant/efficient solutions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sample Solution 1: Naive for loops (Brute force; Don't even try to time it)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decompose(pence):\n",
    "    coins = [1,2,5,10,20,50,100,200]\n",
    "    count = 0\n",
    "    for x1 in range(pence):\n",
    "        for x2 in range(pence):\n",
    "            for x3 in range(pence):\n",
    "                for x4 in range(pence):\n",
    "                    for x5 in range(pence):\n",
    "                        for x6 in range(pence):\n",
    "                            for x7 in range(pence):\n",
    "                                for x8 in range(pence):\n",
    "                                    if (x1 * coins[0] + x2 * coins[1] + x3 * coins[2] + x4 * coins[3]\n",
    "                                     + x5 * coins[4] + x6 * coins[5] + x7 * coins[6] + x8 * coins[7])\n",
    "                                      == pence:\n",
    "                                        count += 1 # Cancer\n",
    "                            \n",
    "    return count + 1\n",
    "\n",
    "## TEST CASES ##    \n",
    "import time\n",
    "start_time = time.time()\n",
    "print (decompose(1))\n",
    "print (decompose(5))\n",
    "print (decompose(7))\n",
    "print (decompose(130))\n",
    "print (decompose(200))\n",
    "print (decompose(700))\n",
    "print(\"--- %s seconds ---\" % (time.time() - start_time)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sample Solution 2: Pure recursion (Exhasutive; ~10mins)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decompose(pence, num_types = len(coins)): \n",
    "    coins = [1,2,5,10,20,50,100,200]\n",
    "    # If pence = 0 then there is only 1 solution\n",
    "    if (pence == 0): \n",
    "        return 1\n",
    "  \n",
    "    # If n is less than 0 then no solution exists \n",
    "    if (pence < 0): \n",
    "        return 0; \n",
    "  \n",
    "    # If there are no coins and n is greater than 0, then no solution exist \n",
    "    if (num_types <=0 and pence >= 1): \n",
    "        return 0\n",
    "      \n",
    "    # Recursion step    \n",
    "    return decompose( pence, num_types - 1 ) + decompose( pence - coins[num_types-1], num_types);\n",
    "\n",
    "## TEST CASES ##    \n",
    "import time\n",
    "start_time = time.time()\n",
    "print (decompose(1))\n",
    "print (decompose(5))\n",
    "print (decompose(7))\n",
    "print (decompose(130))\n",
    "print (decompose(200))\n",
    "print (decompose(700))\n",
    "print(\"--- %s seconds ---\" % (time.time() - start_time)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sample Solution 3: Recursion with some memomisation (Exhasutive with some elegance; ~5mins)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decompose(pence, coins = [1,2,5,10,20,50,100,200]):\n",
    "    \n",
    "    # If pence = 0 then there is only 1 solution\n",
    "    if pence == 0:\n",
    "        return 1\n",
    "    \n",
    "    # If n is less than 0 then no solution exists \n",
    "    if pence < 0:\n",
    "        return 0\n",
    "    num_ways = 0\n",
    "    \n",
    "    # Store previously computed sub-problems in a dictionary to avoid re-computing it\n",
    "    dic_ways = {}\n",
    "    for i in range(len(coins)):\n",
    "        coin = coins[i]\n",
    "        if pence-coin not in dic_ways:\n",
    "            # Recursion step\n",
    "            num_ways += decompose(pence - coin, coins[i:])\n",
    "            dic_ways[pence-coin] = True\n",
    "    return num_ways\n",
    "\n",
    "## TEST CASES ##    \n",
    "import time\n",
    "start_time = time.time()\n",
    "print (decompose(1))\n",
    "print (decompose(5))\n",
    "print (decompose(7))\n",
    "print (decompose(130))\n",
    "print (decompose(200))\n",
    "print (decompose(700))\n",
    "print(\"--- %s seconds ---\" % (time.time() - start_time)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sample solution 4: Expansion of partition equation into series (Elegant but inefficient; ~30s)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sympy import *\n",
    "def decompose(pence):\n",
    "    x = symbols('x')\n",
    "    partition_series = series(1/(( 1 - x)*(1-x**2)*(1-x**5)*(1-x**10)\n",
    "    *(1-x**20)*(1-x**50)*(1-x**100)*(1-x**200)), n = pence+2)\n",
    "    coef = Poly(partition_series.removeO(),x)\n",
    "    return coef.all_coeffs()[1]\n",
    "\n",
    "## TEST CASES ##    \n",
    "import time\n",
    "start_time = time.time()\n",
    "print (decompose(1))\n",
    "print (decompose(5))\n",
    "print (decompose(7))\n",
    "print (decompose(130))\n",
    "print (decompose(200))\n",
    "print (decompose(700))\n",
    "print(\"--- %s seconds ---\" % (time.time() - start_time)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sample solution 5: Smart brute force (Efficent but inelegant; 1.5s)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decompose(pence):\n",
    "    count = 0\n",
    "    for x1 in range(0,pence+1,200):\n",
    "        for x2 in range(x1,pence+1,100):\n",
    "            for x3 in range(x2,pence+1,50):\n",
    "                for x4 in range(x3,pence+1,20):\n",
    "                    for x5 in range(x4,pence+1,10):\n",
    "                        for x6 in range(x5,pence+1,5):\n",
    "                            for x7 in range(x6,pence+1,2):\n",
    "                                count+=1\n",
    "    return count\n",
    "\n",
    "## TEST CASES ##    \n",
    "import time\n",
    "start_time = time.time()\n",
    "print (decompose(1))\n",
    "print (decompose(5))\n",
    "print (decompose(7))\n",
    "print (decompose(130))\n",
    "print (decompose(200))\n",
    "print (decompose(700))\n",
    "print(\"--- %s seconds ---\" % (time.time() - start_time)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sample solution 6: Top-down Dynamic Programming; Recursion with memoization & decorators (Efficient & quite elegant; ~0.002s)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def memoize(func):\n",
    "    cache = dict()\n",
    "    def memoized_func(*args):\n",
    "        if args in cache:\n",
    "            return cache[args]\n",
    "        result = func(*args)\n",
    "        cache[args] = result\n",
    "        return result\n",
    "    return memoized_func\n",
    " ## The above code is a quick and dirty memo fucntion that can be used widely ##\n",
    " ## to speed up problems with overlapping sub-problems (avoid recomputation) ##  \n",
    "\n",
    "@memoize\n",
    "## Pure recursion from sample solution 2 ##\n",
    "def decompose(pence, num_types = len(coins)): \n",
    "    coins = [1,2,5,10,20,50,100,200]\n",
    "    # If pence = 0 then there is only 1 solution\n",
    "    if (pence == 0): \n",
    "        return 1\n",
    "  \n",
    "    # If n is less than 0 then no solution exists \n",
    "    if (pence < 0): \n",
    "        return 0; \n",
    "  \n",
    "    # If there are no coins and n is greater than 0, then no solution exist \n",
    "    if (num_types <=0 and pence >= 1): \n",
    "        return 0\n",
    "      \n",
    "    # Recursion step    \n",
    "    return decompose( pence, num_types - 1 ) + decompose( pence - coins[num_types-1], num_types);\n",
    "\n",
    "## TEST CASES ##    \n",
    "import time\n",
    "start_time = time.time()\n",
    "print (decompose(1))\n",
    "print (decompose(5))\n",
    "print (decompose(7))\n",
    "print (decompose(130))\n",
    "print (decompose(200))\n",
    "print (decompose(700))\n",
    "print(\"--- %s seconds ---\" % (time.time() - start_time)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Sample Solution 7: Bottom-up Dynamic Programming (Most elegant & efficient; ~0.001s)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decompose(pence): \n",
    "   try: \n",
    "    coins = [1,2,5,10,20,50,100,200]\n",
    "    num_types = len(coins)\n",
    "    # table[i] will be storing the number of solutions for \n",
    "    # value i. We need n+1 rows as the table is constructed \n",
    "    # in bottom up manner using the base case (pence = 0) \n",
    "    # We first initialize all table values as 0 \n",
    "    table = [0 for accumulative_num_of_ways in range(pence+1)] \n",
    "  \n",
    "    # If pence = 0 then there is only 1 solution\n",
    "    table[0] = 1\n",
    "  \n",
    "    # Pick all coins one by one and update the table[] values \n",
    "    # after the index greater than or equal to the value of the \n",
    "    # picked coin \n",
    "    for type_ in range(0,num_types): \n",
    "        for value in range(coins[type_],pence+1): \n",
    "            table[value] += table[value-coins[type_]] \n",
    "    # We only want the number of ways to find change for value = pence       \n",
    "    return table[pence]\n",
    "   except:\n",
    "    # Our bottom up approach innately deals with special cases\n",
    "    # this line catches invalid arguments\n",
    "    return 0    \n",
    "\n",
    "## TEST CASES ##    \n",
    "import time\n",
    "start_time = time.time()\n",
    "print (decompose(1))\n",
    "print (decompose(5))\n",
    "print (decompose(7))\n",
    "print (decompose(130))\n",
    "print (decompose(200))\n",
    "print (decompose(700))\n",
    "print(\"--- %s seconds ---\" % (time.time() - start_time)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}