3_Iteration_while_loops_and_loop-control.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Iteration: while-loops and loop-control"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using loops to solve useful problems in Python\n",
    "\n",
    "Recall the major control structures: *sequence*, *selection*, *repetition*. Repetition was the case of executing a statement or block of statements more than once\n",
    "\n",
    "<img src=\"files/control_repetition1.png\">\n",
    "\n",
    "Programming languages allow for repetition control structures by the provision of looping constructs. There are two main sorts of loops:\n",
    "\n",
    "- *conditional* loops (\"while\"), which is a loop that repeats until a certain condition is met e.g. successive approximations to solution to equation\n",
    "\n",
    "- *counting* loops (\"for\"), a loop that repeats a preset number of times e.g. changing the brightness of each pixel in an image\n",
    "\n",
    "A key construct in Python (and many languages) is *while*. A while loop has an associated\n",
    "condition and repetition continues as long as the condition is satisfied. Let us consider the pseudocode example from notebook 2:\n",
    "\n",
    "    1. Get a trolley\n",
    "    2. While there are items on shopping list\n",
    "        2.1 Read first item on shopping list\n",
    "        2.2 Get that item from shelf\n",
    "        2.3 Put item in trolley\n",
    "        2.4 Cross item off shopping list\n",
    "    3. Pay at checkout\n",
    "\n",
    "*\"There are items on shopping list\"* equates to a test, that evaluates as **True** or **False** and so can form the *condition* of a *while* loop, i.e. the loop will continue to repeat so long as the condition is satisfied (returns **True**). In Python, a while-loop has the form\n",
    "\n",
    "   <table border=\"1\" style=\"width:auto\">\n",
    "      <tr>\n",
    "        <td>while CONDITION:\n",
    "            <pre>CODE-BLOCK</pre>\n",
    "        </td>\n",
    "        </tr>\n",
    "   </table>\n",
    "\n",
    "This notebook gives you a first chance to use loop constructs in Python, and will illustrate how programs can be used to solve some maths and engineering problems.\n",
    "\n",
    "Run the following cell to see what it does."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "i = 55\n",
    "while i > 10:\n",
    "    print (i)\n",
    "    i = i * 0.8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now modify it, to see what happens if the condition is false before the loop begins. Is the code-block executed once or not at all? What happens if the condition is never going to become false, e.g. if the test was **i < 100**? (NOTE: if needs be, you can interrupt the run by clicking Kernel -> Interrupt. This will bring to a halt all the running cells from this notebook.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Make the modifications mentioned above and run the cell after each one of them. What happens in each case?\n",
    "\n",
    "i = 55\n",
    "while i > 10:\n",
    "    print (i)\n",
    "    i = i * 0.8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b><font size = \"4\">Example: Marking</font></b>\n",
    "\n",
    "While loops can surround an *if-then-else*. Run the following with a number of inputs to see how the switch works and make the program terminate by inputing a value that'll end the *while* loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mark = 1\n",
    "while mark > 0:\n",
    "    mark = int(input('Enter mark: '))\n",
    "    print (\"Mark is\", mark, end = \" \" )\n",
    "    if mark >= 70:\n",
    "        print (\"- first class!\")\n",
    "    elif mark >= 40:\n",
    "        print (\"- that's a pass\")\n",
    "    else:\n",
    "        print (\"- oh dear, that's a fail\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b><font size = \"4\">Exercise: The guessing game</font></b>\n",
    "\n",
    "Python provides special commands to modify the normal flow of a loop: **break** and **continue**. A *break* statement in a loop immediately terminates the current iteration and ends the loop overall."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Without break, this loop would run indefinitely\n",
    "\n",
    "while True:\n",
    "    name = input('Enter name: ')\n",
    "    if name == 'done':\n",
    "        break\n",
    "    print ('Hello', name)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A *continue* statement in a loop immediately terminates the current iteration and starts the next iteration. This has the form\n",
    "\n",
    "    while CONDITION-1:\n",
    "        if CONDITION-2:\n",
    "            STATEMENTS-1\n",
    "            continue\n",
    "        STATEMENTS-2\n",
    "        \n",
    "The same effect can often be achieved without the use of continue:\n",
    "\n",
    "    while CONDITION-1:\n",
    "        if CONDITION-2:\n",
    "            STATEMENTS-1\n",
    "        else:\n",
    "            STATEMENTS-2\n",
    "            \n",
    "Both **break** and **continue** should be used with great care. Their overuse is often symptomatic of bad programming style and the same results can often be achieved by the use of *conditionals* which better show the intended logic of the program."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following cell contains the skeleton of a function definition for a *guessing game*. The code imports a function **randint** (from the **random** module), which is used to generate a random integer, e.g. a call **randint(1,20)** returns a random integer in the range 1 to 20 (where 1 and 20 are also possible values). The function has parameters for \n",
    "   <ul>\n",
    "       <li>The number of guesses allowed</li>\n",
    "       <li>The range from which the code picks a number to be guessed</li>\n",
    "   </ul>\n",
    "\n",
    "Complete the definition of the guess function, so that it behaves as illustrated in the dialogues below, i.e. telling the player how many guesses they have left, reading in their guess, telling them if their guess right, and if not, whether it is *too low* or *too high*. You code will use a *while*-loop to make sure the player is only given the allowed number of attempts. \n",
    "\n",
    "NOTE: a tricky issue is handling the case where the player guesses correctly while further attempts remain, as here the loop must *terminate early*. Since this is a function, a **return** statement could be used to end the entire function call, but then the final \"**GAME OVER**\" statement of the definition would not be reached. Instead, you can use the special *loop-control* command **break**, which causes the loop to end, with execution proceeding to the statements that follow the loop.\n",
    "\n",
    "   <table border=\"1\" style=\"width:auto\">\n",
    "      <tr>\n",
    "        <td><i>guess(3,10):</i>\n",
    "            <br><br>\n",
    "            Welcome! Can you guess my secret number?\n",
    "            <br>\n",
    "            You have 3 guesses remaining\n",
    "            <br>\n",
    "            Make a guess: 4\n",
    "            <br>\n",
    "            No - too low!\n",
    "            <br>\n",
    "            You have 2 guesses remaining\n",
    "            <br>\n",
    "            Make a guess: 7\n",
    "            <br>\n",
    "            Well done! You got it right.\n",
    "            <br>\n",
    "            GAME OVER: thanks for playing. Bye.\n",
    "        </td>\n",
    "        <td>\n",
    "        <i>guess(3,20)</i>\n",
    "        <br><br>\n",
    "        Welcome! Can you guess my secret number?\n",
    "        <br>\n",
    "        You have 3 guesses remaining\n",
    "        <br>\n",
    "        Make a guess: 12\n",
    "        <br>\n",
    "        No - too low!\n",
    "        <br>\n",
    "        You have 2 guesses remaining\n",
    "        <br>\n",
    "        Make a guess: 16\n",
    "        <br>\n",
    "        No - too high!\n",
    "        <br>\n",
    "        You have 1 guesses remaining\n",
    "        <br>\n",
    "        Make a guess: 14\n",
    "        <br>\n",
    "        No - too low!\n",
    "        <br>\n",
    "        No more guesses - bad luck!\n",
    "        <br>\n",
    "        GAME OVER: thanks for playing. Bye.\n",
    "        </td>\n",
    "     </tr>\n",
    "   </table>\n",
    "   \n",
    "As you test your definition, you might ponder the following questions:\n",
    "   <ol>\n",
    "       <li>Is there an *optimal strategy* to follow, i.e. that gives the best chance of success?</li>\n",
    "       <li>Is there a number of guesses that can guarantee success on a given range size (one that is less than the range size itself)?</li>\n",
    "   </ol>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Guessing game function\n",
    "# Complete this function and play a few rounds to see if it works like in the dialogues above\n",
    "\n",
    "def guess(attempts,range):\n",
    "    number = randint(1,range)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b><font size = \"5\">Exercise:  Solving equations using Newton's method</font></b>\n",
    "<br>\n",
    "\n",
    "Newton's method is an effective way to find the roots of an equation, and you can find out about it on Wikipedia: **http://en.wikipedia.org/wiki/Newton's** method. We begin by implementing one of the examples described there in Python: *calculating the square root of a number*. \n",
    "\n",
    "To solve an equation *$f(x)$* = 0, we need to find the value of *$x$* for which the function *$f(x)$* evaluates to zero. In Newton's method we start off with an approximation *$x_0$* of *$x$*, and then use the function *$f$* and its first derivative *$f'$* to produce a better approximation *$x_1$*. This process repeats with each *$x_{i+1}$* being computed from its predecessor *$x_i$* as follows: <font size =\"4\">$ x_{i+1} ~=~ x_i - \\frac{f(x_i)}{f^\\prime(x_i)} $</font>\n",
    "\n",
    "This continues until the value produced is a satisfactory approximation of the required root. This type of iteration is very common in engineering problems (such as finite element analysis where large systems of linear equations are solved to within an error tolerance). From the point of view of programming, this is an ideal candidate for a **while** loop, because we need to keep calculating successive approximations while our current approximation is outside the error tolerance.\n",
    "\n",
    "<b><font size = \"4\">I) Using Newton's method to compute square roots</font></b>\n",
    "\n",
    "Applying this method to find the square root of A, we set the function $f$ to be:\n",
    "<br><br>\n",
    "   <div align =\"center\">\n",
    "   <font size =\"4\">$f(x) = x^2-A$</font>\n",
    "   </div>\n",
    "   \n",
    "i.e. so that f(x) = 0 when x is the desired square root value.\n",
    "\n",
    "This in turn gives first derivative and 'approximation' functions as follows:\n",
    "<br><br>\n",
    "   <div align =\"center\">\n",
    "   <font size =\"4\">$f'(x) = 2x \\qquad x_{i+1} = x_i - \\frac{x_i^2-A}{2x_i}$</font>\n",
    "   </div>\n",
    "   \n",
    "Our pseudocode for solving the problem might be:\n",
    "\n",
    "   <table border=\"1\" style=\"width:auto\">\n",
    "      <tr>\n",
    "        <td>1. start with value A for which to solve (parameter)\n",
    "        <br>\n",
    "        2. set an initial value for our approximation x\n",
    "        <br>\n",
    "        3. set error tolerance E\n",
    "        <br>\n",
    "        4. while difference between $x^2$ and A is greater than E\n",
    "        <br>\n",
    "            &emsp; &emsp; 4.1 calculate a new value of x\n",
    "        <br>\n",
    "        5. display the result\n",
    "        </td>\n",
    "        </tr>\n",
    "   </table>\n",
    "   \n",
    "Working in the cell below define a Python function **MySqrt** to compute square roots using Newton's method. (We call it **MySqrt** to avoid confusion with the function **sqrt** that comes with python's **math** library.) This has one parameter **A**, the value whose square root we seek. Your definition, then, might start as follows:  \n",
    "\n",
    "   <table border=\"1\" style=\"width:auto\">\n",
    "      <tr>\n",
    "        <td>def MySqrt(A):\n",
    "            <pre>x = 1.0 # initial approximation value</pre>\n",
    "            <pre>errorTolerance = 0.001</pre>\n",
    "            <pre>:</pre>\n",
    "            <pre>:</pre>\n",
    "        </td>\n",
    "        </tr>\n",
    "   </table>\n",
    "   \n",
    "Here we have chosen an initial value of 1. For square roots Newton's method is *stable*, so it does not matter too much what you choose as an initial value. We have chosen an error tolerance of 0.001, which will be fine for approximating the square root of numbers larger than 1, but may be no good for smaller numbers. (Why not?)\n",
    "\n",
    "The tricky bit of the code is how to implement the **while** loop condition. Our pseudocode says:\n",
    "\n",
    "   <table border=\"1\" style=\"width:auto\">\n",
    "      <tr>\n",
    "        <td>4. while difference between $x^2$ and A is greater than E</td>\n",
    "      </tr>\n",
    "   </table>\n",
    "   \n",
    "which perhaps suggests a **while** statement in Python such as:\n",
    "\n",
    "   <table border=\"1\" style=\"width:auto\">\n",
    "      <tr>\n",
    "        <td>while (x \\* x - A) >= errorTolerance:</td>\n",
    "      </tr>\n",
    "   </table>\n",
    "   \n",
    "Note that we have used brackets to make the code easier to read. The problem with this condition is that, at any stage, the current approximation x might be either an *underestimate* or *overestimate* of the true value. If it is an underestimate, then the result of **(x \\* x - A)** will be *negative*, and hence a lower value than **errorTolerance**, but this is not the point. What matters is the *magnitude* of **(x \\* x - A)**, a small negative value might satisfy the requirement of being *within tolerance*. What we really want to compare against **errorTolerance** is the *absolute* value of **(x \\* x - A)**, regardless of whether it is positive or negative. The python function **abs** computes the absolute value of a number (i.e. is such that **abs(1)** and **abs(-1)** both return **1**).\n",
    "\n",
    "The other problem we have is how to calculate the new value of **x** with each repeat of the **while** loop. Directly implementing the equation for Newton's method above might give us the following, where **xNew** is the new approximation, computed in terms of the old approximation **x**:\n",
    "\n",
    "   <table border=\"1\" style=\"width:auto\">\n",
    "      <tr>\n",
    "        <td>xNew = x - (x \\* x - A) / (2 \\* x)</td>\n",
    "      </tr>\n",
    "   </table>\n",
    "   \n",
    "The new value now becomes the current approximation, so we might extend the above to become:\n",
    "\n",
    "   <table border=\"1\" style=\"width:auto\">\n",
    "      <tr>\n",
    "        <td>xNew = x - (x \\* x - A) / (2 \\* x)\n",
    "        <br>\n",
    "        x = xNew</td>\n",
    "      </tr>\n",
    "   </table>\n",
    "   \n",
    "In practice, this is equivalent to just saying:\n",
    "\n",
    "   <table border=\"1\" style=\"width:auto\">\n",
    "      <tr>\n",
    "        <td>x = x - (x \\* x - A) / (2 \\* x)</td>\n",
    "      </tr>\n",
    "   </table>\n",
    "   \n",
    "as the calculation on the r.h.s. of \"=\" here is made using the value of **x** at the time that the statement is executed, and only when the calculation is done is the result value assigned to the variable indicated to the left of \"=\", which here happens to be **x**. \n",
    "\n",
    "We have now seen enough for you to complete your definition of **MySqrt**. When it has computed its result, your definition should *return* the computed value (rather than just printing it).\n",
    "\n",
    "Whilst you are developing your definition, include a **print** statement immediately after the **while** statement that prints the current value of **x** at the start of each loop, to help you check that your code is running as you expect. This can then be removed when your definition is complete and working. Test your definition thoroughly, trying a range of di\u000B",
    "erent input values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Insert here your definition for MySqrt function"
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}