{
 "metadata": {
  "name": "01_23-27_review"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Introduction"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In this lab, you will be using what we have learnt to solve some problems"
     ]
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Problem 1 :"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Given two positive integers m and n find the g.c.d."
     ]
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Solution :"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "m = 60\n",
      "n = 18\n",
      "\n",
      "if n > m :\n",
      "    k = m\n",
      "    m = n\n",
      "    n = k\n",
      "\n",
      "orig_m = m\n",
      "orig_n = n\n",
      "\n",
      "while n > 0 :\n",
      "    d = n\n",
      "    r = m % n\n",
      "    m = d\n",
      "    n = r\n",
      "\n",
      "print \"The g.c.d.(%d, %d) = %d\" % (orig_m, orig_n, m)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The g.c.d.(60, 18) = 6\n"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Problem 2 :"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Given a list of numbers, find their g.c.d."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "lst = [72, 100, 4, 98]\n",
      "\n",
      "def gcd(m, n) :\n",
      "    \"\"\"Givem two numbers, this finds their g.c.d.\"\"\"\n",
      "    while n > 0 :\n",
      "        d = n\n",
      "        r = m % n\n",
      "        m = d\n",
      "        n = r\n",
      "    return m\n",
      "\n",
      "if len(lst) < 2 :\n",
      "    print \"Need at least two elements to find g.c.d.\"\n",
      "else :\n",
      "    accumulated_gcd = lst[0]\n",
      "    for i in range(len(lst) - 1) :\n",
      "        accumulated_gcd = gcd(accumulated_gcd, lst[i+1])\n",
      "    print \"gcd = %d\" % (accumulated_gcd)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "gcd = 2\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Problem 3 :"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Write a function which takes a positive integer as an argument and returns a list of its prime factors, where the factors are repeated the number of times they occur in the number."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def find_factors(n) :\n",
      "    \"\"\"Given a number returns a list of its factors.\"\"\"\n",
      "    lst_factors = []\n",
      "    d = 2\n",
      "    while n/d > 0 :\n",
      "        if n % d == 0 :\n",
      "            lst_factors.append(d)\n",
      "            n = n / d\n",
      "        else :\n",
      "            d += 1\n",
      "    return lst_factors\n",
      "\n",
      "print \"Factors of 10 are\", find_factors(10)\n",
      "print \"Factors of 720 are\", find_factors(720)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Factors of 10 are [2, 5]\n",
        "Factors of 720 are [2, 2, 2, 2, 3, 3, 5]\n"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Problem 4 :"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Given a list, like the output of the previous problem. Can you form another list which consists of tuples whose first element is the entry of the given list, and the second is the number of times it is repeated in a run (without a break by another object). Here are some examples of what we are looking for\n",
      "\n",
      "[1, 1, 3, 4, 2, 1] -> [(1, 2), (3, 1), (4, 1), (2, 1), (1, 1)]\n",
      "\n",
      "[1,2,1,2,1,1] -> [(1,1), (2,1), (1,1), (2, 1), (1, 2)]"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def runs_in_lst(lst) :\n",
      "    \"\"\"Given a list, returns a list of tuples containing the object and the duration of run for that object.\"\"\"\n",
      "    if len(lst) == 0 :\n",
      "        ret_lst = []\n",
      "    else :\n",
      "        ret_lst = []\n",
      "        curr_obj = lst[0]\n",
      "        curr_pos = 0\n",
      "        repeat = 1\n",
      "        while len(lst) > curr_pos + 1 :\n",
      "            curr_pos += 1\n",
      "            if lst[curr_pos] == curr_obj :\n",
      "                repeat += 1\n",
      "            else :\n",
      "                ret_lst.append((curr_obj, repeat))\n",
      "                curr_obj = lst[curr_pos]\n",
      "                repeat = 1\n",
      "        # Now take care of the last object.\n",
      "        ret_lst.append((curr_obj, repeat))\n",
      "    return ret_lst\n",
      "\n",
      "lst1 = []\n",
      "lst2 = [1]\n",
      "lst3 = [1,2]\n",
      "lst4 = [1,1,3,4,2,1]\n",
      "lst5 = [1,2,1,2,1,1]\n",
      "\n",
      "print lst1, \"->\", runs_in_lst(lst1)\n",
      "print lst2, \"->\", runs_in_lst(lst2)\n",
      "print lst3, \"->\", runs_in_lst(lst3)\n",
      "print lst4, \"->\", runs_in_lst(lst4)\n",
      "print lst5, \"->\", runs_in_lst(lst5)\n",
      "\n",
      "            "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[] -> []\n",
        "[1] -> [(1, 1)]\n",
        "[1, 2] -> [(1, 1), (2, 1)]\n",
        "[1, 1, 3, 4, 2, 1] -> [(1, 2), (3, 1), (4, 1), (2, 1), (1, 1)]\n",
        "[1, 2, 1, 2, 1, 1] -> [(1, 1), (2, 1), (1, 1), (2, 1), (1, 2)]\n"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Problem 5 :"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Given a number output a string which has the prime factors of n in the form $p_1\\wedge e_1 \\cdot p_2\\wedge e_2\\cdots$, for example output for 24 should be of the form $2\\wedge 3 \\cdot 3$. You can use str() to convert numbers to strings."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def stringfactors(n) :\n",
      "    \"\"\"Given a number outputs a string of factors.\"\"\"\n",
      "    lst_of_factors = find_factors(n)\n",
      "    run_lst_of_factors = runs_in_lst(lst_of_factors)\n",
      "    fac = 0 # fac = number of factors already considered.\n",
      "    for (p, e) in run_lst_of_factors :\n",
      "        fac += 1\n",
      "        if fac == 1:\n",
      "            if e == 1 :\n",
      "                prime_str = str(p)\n",
      "            else :\n",
      "                prime_str = str(p) + \"^\" + str(e)\n",
      "        else :\n",
      "            if e == 1 :\n",
      "                prime_str += \" . \" + str(p)\n",
      "            else :\n",
      "                prime_str += \" . \" + str(p) + \"^\" + str(e)\n",
      "                \n",
      "    return prime_str\n",
      "\n",
      "print \"%d = %s\" % (45, stringfactors(45))\n",
      "print \"%d = %s\" % (720, stringfactors(720))\n",
      "print \"%d = %s\" % (54, stringfactors(54))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "45 = 3^2 . 5\n",
        "720 = 2^4 . 3^2 . 5\n",
        "54 = 2 . 3^3\n"
       ]
      }
     ],
     "prompt_number": 5
    }
   ],
   "metadata": {}
  }
 ]
}