04-iteration.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8z5cONg8rUrX",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Iteration\n",
    "\n",
    "## Programming Fundamentals (NB04)\n",
    "\n",
    "### MIEIC/2020-21\n",
    "\n",
    "#### João Correia Lopes\n",
    "\n",
    "FEUP/DEI and INESC TEC"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "MZzE7pYorju5",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Goals\n",
    "\n",
    "By the end of this class, the student should be able to:\n",
    "\n",
    "- Describe how to do iterations using `while` statements\n",
    "- Describe *middle-test* and *post-test* loops using the `break` and `continue` statements\n",
    "- Choose between `for` and `while` loops\n",
    "- Use nested loops for nested data (for example list of pairs)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "eR5Lh1jNroE2",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Bibliography\n",
    "\n",
    "- Peter Wentworth, Jeffrey Elkner, Allen B. Downey, and Chris Meyers, *How to Think Like a Computer Scientist — Learning with Python 3* (Section 3.3)\n",
    "\n",
    "- Brad Miller and David Ranum, Learning with Python: Interactive Edition. Based on material by Jeffrey Elkner, Allen B. Downey, and Chris Meyers (Chapter 8)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "fxtTHNoKPrAL",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# 3.3 Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "7OzPLY5nV86k",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Iteration\n",
    "\n",
    "- Computers are often used to automate repetitive tasks\n",
    "\n",
    "- Repeating identical or similar tasks without making errors is\n",
    "    something that computers do well and people do poorly\n",
    "\n",
    "- Repeated execution of a set of statements is called **iteration**\n",
    "\n",
    "- Python provides several language features to make it easier\n",
    "\n",
    "    - We've already seen the `for` statement\n",
    "\n",
    "    - We're going to look at the `while` statement\n",
    "\n",
    "- Before we do that, let's just review a few ideas ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "RhCMFHvrPyx6",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.1 Assignment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "XipXFNAuWQ70",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Assignment revisited\n",
    "\n",
    "- It is legal to make more than one assignment to the same variable\n",
    "\n",
    "- A new assignment makes an existing variable refer to a new value\n",
    "\n",
    "- Because Python uses the equal token (`=`) for assignment, it is\n",
    "    tempting to interpret a statement like `a = b` as a Boolean test.\n",
    "\n",
    "- Unlike mathematics, it is not!\n",
    "\n",
    "- Remember that the Python token for the equality operator is `==`\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/assignment.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "UupqO8kc_BXZ",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "See the Runestone Interactive vídeo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "1LmhvaCc_DzO",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import YouTubeVideo\n",
    "YouTubeVideo('G86akhNFHZA')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "kYshn-6hP14z",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.2 Updating variables\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "TTZ9vQEAXst_",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Updating variables revisited\n",
    "\n",
    "\n",
    "- When an assignment statement is executed, the right-hand side\n",
    "    expression (i.e. the *expression* that comes after the assignment\n",
    "    token) is evaluated first\n",
    "\n",
    "- This produces a *value*\n",
    "\n",
    "- Then the assignment is made, so that the variable (assignable) on\n",
    "    the left-hand side now *refers to* the new value\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "BGjZFonTep7Z",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "\n",
    "- Before you can update a variable, you have to **initialize** it to\n",
    "    some starting value, usually with a simple assignment\n",
    "\n",
    "- Updating a variable by adding 1 to it, is called an **increment**\n",
    "\n",
    "- Subtracting 1 is called a **decrement**\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/assignment.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "6NssNwmq-EwD",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Runestone Interactive vídeo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "6Z151X12-Q-q",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import YouTubeVideo\n",
    "YouTubeVideo('Px1c-3GP-5o')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NwUYq0LNQIRp",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.3 The `for` loop revisited\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "TRnGJowLZRzj",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "\n",
    "- Recall that the for loop processes each item in a list\n",
    "\n",
    "- Each item in turn is (re-)assigned to the loop variable and the body\n",
    "    of the loop is executed\n",
    "\n",
    "- Running through all the items in a list is called **traversing the\n",
    "    list**, or traversal\n",
    "\n",
    "\n",
    "> *Let us write some code now to sum up all the elements in a list of\n",
    "    numbers*\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/for.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "YK5jJVvJHR5e",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "You may remember this:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "bY19x4HHHX2X",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for f in [\"Joe\", \"Amy\", \"Brad\", \"Angelina\", \"Zuki\", \"Thandi\", \"Paris\"]:\n",
    "    print(\"Hi\", f, \"Please come to my party on Saturday\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Tsbev9rvQL85",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.4 The `while` statement\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "6qJAEXSzZtIk",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### `while` syntax\n",
    "\n",
    "```\n",
    "while <CONDITION>:\n",
    "   <STATEMENTS>\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "cg2zKeMgZ09n",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### `while` flowchart\n",
    "\n",
    "![while](images/04/while.png)\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/while.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "dgumbJf6ZgEk",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Infinite loop\n",
    "\n",
    "- The body of the loop should change the value of one or more\n",
    "    variables so that *eventually*<sup>1</sup> the condition becomes false and the\n",
    "    loop terminates\n",
    "\n",
    "- Otherwise the loop will repeat forever, which is called an\n",
    "    **infinite loop**\n",
    "\n",
    "<sup>1</sup> We use the adverb eventually to mean \"in the end\", especially when\n",
    "    something has involved a long time, or a lot of effort or problems\n",
    "    [Cambridge dictionary](https://dictionary.cambridge.org)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "xF-PIUp_bHZf",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Choosing between `for` and `while`\n",
    "\n",
    "- **Definite iteration** --- we know ahead of time some definite\n",
    "    bounds for what is needed\n",
    "\n",
    "    - Use a for loop if you know, before you start looping, the\n",
    "        maximum number of times that you'll need to execute the body\n",
    "\n",
    "    - Examples: \"iterate this weather model for 1000 cycles\", or\n",
    "        \"search this list of words\", \"find all prime numbers up to\n",
    "        10000\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "vodeFM_Ge_LF",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "\n",
    "- **Indefinite iteration** --- we're not sure how many iterations\n",
    "    we'll need --- we cannot even establish an upper bound!\n",
    "\n",
    "    - if you are required to repeat some computation until some\n",
    "        condition is met, and you cannot calculate in advance when (of\n",
    "        if) this will happen, you'll need a while loop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "HVJIvTFJIwko",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Randomly Walking Turtles\n",
    "\n",
    "Suppose we want to entertain ourselves by watching a turtle wander around randomly inside the screen. When we run the program we want the turtle and program to behave in the following way:\n",
    "\n",
    "1. The turtle begins in the center of the screen.\n",
    "\n",
    "1. Flip a coin. If it’s *heads* then turn to the left 90 degrees. If it’s *tails* then turn to the right 90 degrees.\n",
    "\n",
    "1. Take 50 steps forward.\n",
    "\n",
    "1. If the turtle has moved outside the screen then stop, otherwise go back to step 2 and repeat.\n",
    "\n",
    "\n",
    "$\\Rightarrow$\n",
    "[thinkcspy interactive](https://runestone.academy/runestone/books/published/thinkcspy/MoreAboutIteration/RandomlyWalkingTurtles.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Hj_AsGMUJFdi",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### pseudo-code\n",
    "\n",
    "So based on the problem description above, we can outline a program as follows:\n",
    "\n",
    "\n",
    "```\n",
    "create a window and a turtle\n",
    "\n",
    "while the turtle is still in the window:\n",
    "    generate a random number between 0 and 1\n",
    "    if the number == 0 (heads):\n",
    "        turn left\n",
    "    else:\n",
    "        turn right\n",
    "    move the turtle forward 50\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8Yw1lTwGRJ-S",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The first version without testing the boundaries of the window:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "H7AZpQ7GRT5p",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import random\n",
    "import turtle\n",
    "\n",
    "def is_in_screen(w, t):\n",
    "    \"\"\"\n",
    "    Determines if turtle t is inside the boundaries of screen w\n",
    "    \"\"\"\n",
    "    if random.random() > 0.1:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "wn = turtle.Screen()\n",
    "wn.setup(600, 600) \n",
    "wn.bgcolor(\"green\")\n",
    "\n",
    "tess = turtle.Turtle()\n",
    "tess.shape('turtle')\n",
    "\n",
    "while is_in_screen(wn, tess):\n",
    "    coin = random.randrange(0, 2)  # throw the coin\n",
    "    if coin == 0:                  # heads\n",
    "        tess.left(90)\n",
    "    else:                          # tails\n",
    "        tess.right(90)\n",
    "\n",
    "    tess.forward(50)\n",
    "\n",
    "wn.mainloop()\n",
    "turtle.bye()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "e0MOyPteS4Oy",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Code for `is_in_screen`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ZgxE2KcDS_eq",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def is_in_screen(w, t):\n",
    "    \"\"\"\n",
    "    Determines if turtle t is inside the boundaries of screen w\n",
    "    \"\"\"\n",
    "    left_bound = -w.window_width() / 2\n",
    "    right_bound = w.window_width() / 2\n",
    "    top_bound = w.window_height() / 2\n",
    "    bottom_bound = -w.window_height() / 2\n",
    "\n",
    "    turtle_x = t.xcor()  # get current x position\n",
    "    turtle_y = t.ycor()  # get current y position\n",
    "\n",
    "    still_in = True\n",
    "    if turtle_x > right_bound or turtle_x < left_bound:\n",
    "        still_in = False\n",
    "    if turtle_y > top_bound or turtle_y < bottom_bound:\n",
    "        still_in = False\n",
    "\n",
    "    return still_in"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "jmyBKhfOTKIQ",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Get the code from here:\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/random_walk.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4-GaAHiSQPK9",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.5 The Collatz 3n + 1 sequence\n",
    "\n",
    "For another example of indefinite iteration, let’s look at a sequence that has fascinated mathematicians for many years. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ZJCFUdsaeSxJ",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Collatz conjecture\n",
    "\n",
    "\n",
    "\n",
    "> **Computational rule**:\\\n",
    "\\\n",
    "The rule for creating the sequence is to **start** from\n",
    "some given n,\\\n",
    "and to generate the **next term** of the sequence from n,\\\n",
    "either by halving n, (whenever n is even),\\\n",
    "or else by multiplying it by three and adding 1.\\\n",
    "The sequence **terminates** when n reaches 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "vcn9GCOefyYL",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = 1027371\n",
    "while n != 1:\n",
    "    print(n, end=\", \")\n",
    "    if n % 2 == 0:\n",
    "        n = n // 2\n",
    "    else:\n",
    "        n = n * 3 + 1\n",
    "print(n, end=\".\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Mp7rVFAPgCfx",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/colatz.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "WCWwKypCQSKK",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.7 Counting digits\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "pgq11vbNgLSE",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### counter\n",
    "\n",
    " The following snippet *counts* the number of decimal digits\n",
    "in a positive integer:\n",
    "\n",
    "\n",
    "```\n",
    "  n = 3029\n",
    "  count = 0\n",
    "  while n != 0:\n",
    "     count = count + 1\n",
    "     n = n // 10\n",
    "  print(count)\n",
    "```\n",
    " This snippet demonstrates an important pattern of\n",
    "computation called a **counter**.\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/counter.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8cKQ9WoyQVNw",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.9 Tables\n",
    "\n",
    "- One of the things loops are good for is generating tables\n",
    "\n",
    "- Output a sequence of values in the left column and 2 raised to the\n",
    "    power of that value in the right column\n",
    "\n",
    "    - using the \"tab separator\" *escape sequence*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "CzWfj_9Lgj80",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(\"n\", '\\t', \"2**n\")     # table column headings\n",
    "print(\"---\", '\\t', \"-----\")\n",
    "\n",
    "for x in range(11):          # generate values for columns\n",
    "    print(x, '\\t', 2 ** x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "xFP44sKCgmBA",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/tables.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "aWq6u0nJQYPV",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.10 Two-dimensional tables\n",
    "\n",
    "- A two-dimensional table is a table where you read the value at the\n",
    "    intersection of a row and a column.\n",
    "\n",
    "- Let's say you want to print a multiplication table for the values\n",
    "    from 1 to 6\n",
    "\n",
    "- A good way *to start* is to write a loop that prints the multiples\n",
    "    of 2, all on one line:\n",
    "\n",
    "    - `end=\" \"` argument in the print function suppresses the newline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "grzJ8QSWzcx0",
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(\"First line:\")\n",
    "for i in range(1, 7):\n",
    "    print(2 * i, end=\"   \")\n",
    "print()\n",
    "print(\"\\nto be continued...\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "rTGj2Zv7zmxs",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/tables.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "MfsscAwF0OKB",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.11 The `break` statement\n",
    "\n",
    "- The **break** statement is used to *immediately leave the body of\n",
    "    its loop*\n",
    "\n",
    "- The next statement to be executed is the first one after the body:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "mcvXWURD0X_C",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for i in [12, 16, 17, 24, 29]:\n",
    "    if i % 2 == 1:    # If the number is odd\n",
    "        break         # ... immediately exit the loop\n",
    "    print(i)\n",
    "print(\"done.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "m0YTZIpIQOSy",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/break.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "AKZFku5HQhcz",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.12 Other flavours of loops\n",
    "\n",
    "- `for` and `while` loops do their tests at the start: They're called\n",
    "    **pre-test loops**\n",
    "\n",
    "- Sometimes we'd like to have the **middle-test loop** with the exit\n",
    "    test in the middle of the body\n",
    "\n",
    "- Or a **post-test loop** that puts its exit test as the last thing in\n",
    "    the body"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ere-20PD1XPI",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Middle-exit loop\n",
    "\n",
    "![break](images/04/break.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "mIFqdveE1hGC",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "total = 0\n",
    "while True:\n",
    "    response = input(\"Enter the next number. (Leave blank to end)\")\n",
    "    if response == \"\" or response == \"-1\":\n",
    "        break\n",
    "    total += int(response)\n",
    "print(\"The total of the numbers you entered is \", total)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "voNCI5FB17Ie",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Post-test loop\n",
    "\n",
    "\n",
    "```\n",
    "while True:\n",
    "   play_the_game_once()\n",
    "   response = input(\"Play again? (yes or no)\")\n",
    "   if response != \"yes\":\n",
    "      break\n",
    "print(\"Goodbye!\")\n",
    "```\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/break.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "S4beccoDQksR",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.13 An example\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "jnzDRZ3P2kBW",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### A simple guessing game\n",
    "\n",
    "- The *guessing game* program makes use of the mathematical law of\n",
    "    **trichotomy**:\n",
    "\n",
    "    - given real numbers a and b, exactly one of these three must be\n",
    "        true:\n",
    "\n",
    "    - a \\> b, a \\< b, or a == b\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/guess.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "loSntQunQn2a",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.14 The continue statement\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NS-WiwiW3tZV",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- This is a control flow statement that causes the program to\n",
    "    immediately skip the processing of the rest of the body of the loop,\n",
    "    *for the current iteration*\n",
    "\n",
    "- But the loop still carries on running for its remaining iterations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "eKaPzzoc3yP2",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for i in [12, 16, 17, 24, 29, 30]:\n",
    "    if i % 2 == 1:      # If the number is odd\n",
    "        continue        # Don't process it\n",
    "    print(i)\n",
    "print(\"done.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "aRdIB0jO33OU",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/continue.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "A2hjV5qVQqvM",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.15 Paired Data\n",
    "\n",
    "We’ve already seen lists of names and lists of numbers in Python.  \n",
    "We’re going to peek ahead and show a more advanced way of representing our data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ocLk_7vG4ALG",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### A pair of things\n",
    "\n",
    "\n",
    "- Making a *pair of things* in Python is as simple as putting them\n",
    " into parentheses\n",
    "\n",
    "\n",
    "```\n",
    "# a pair\n",
    "year_born = (\"Kim Basinger\", 1953)\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "FUccbfFf4KSV",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "```\n",
    "# a list of pairs\n",
    "celebs = [(\"Jack Nicholson\", 1937),\n",
    "          (\"Kim Basinger\", 1953),\n",
    "          (\"Brad Pitt\", 1963),\n",
    "          (\"Sharon Stone\", 1958)]\n",
    "```\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/pairs.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's try it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "celeb = (\"Kim Basinger\", 1953)\n",
    "print(celeb)\n",
    "print(len(celeb))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "celebs = [(\"Jack Nicholson\", 1937), (\"Kim Basinger\", 1953),\n",
    "          (\"Brad Pitt\", 1963), (\"Sharon Stone\", 1968)]\n",
    "print(celebs)\n",
    "print(len(celebs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for name, year in celebs:\n",
    "    if year < 1960:\n",
    "        print(name)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Lx7yW31wQt4G",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.16 Nested Loops for Nested Data\n",
    "\n",
    "- Now we'll come up with an even more adventurous list of structured\n",
    "    data\n",
    "\n",
    "- In this case, we have a list of students\n",
    "\n",
    "- Each student has a name which is paired up with another list of\n",
    "    subjects that they are enrolled for\n",
    "\n",
    "\n",
    "```\n",
    "  students = [\n",
    "               (\"John\", [\"FPRO\", \"LBAW\"])\n",
    "             ]\n",
    "```\n",
    "\n",
    "Load the following code in Spyder and try it:\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/nested.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "5Ce1EmdLQw91",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.17 Newton’s method for finding square roots\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "rAY7YFRy4xEh",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Newton's method\n",
    "\n",
    "\n",
    "- Loops are often used in programs that compute numerical results by\n",
    "    starting with an approximate answer and iteratively improving it\n",
    "\n",
    "- For example, in Newton's method for finding square root n.\n",
    "\n",
    "- Starting with almost any approximation, a better approximation can\n",
    "    be computed (closer to the actual answer) with the following\n",
    "    formula:\n",
    "\n",
    "    - `better = 0.5 * (approximation + n/approximation)`\n",
    "\n",
    "- One of the amazing properties of this particular algorithm is how\n",
    "    quickly it converges to an accurate answer (a great advantage for\n",
    "    doing it manually)\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/blob/master/lectures/04/newton.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let's try it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = int(input(\"input number n: \"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "threshold = 0.001      # use more precision if needed\n",
    "approximation = n/2    # Start with some or other guess at the answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "while True:\n",
    "    better = (approximation + n/approximation)/2\n",
    "    #print(better)\n",
    "\n",
    "    if abs(approximation - better) < threshold:\n",
    "        print(\"approx root: \", better)\n",
    "        break\n",
    "\n",
    "    approximation = better"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "c_cHwFlgU-H2",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### The Accumulator Pattern\n",
    "\n",
    "- Newton’s method to calculate square roots is an example of an algorithm that repeats as long as it can improve the result\n",
    "\n",
    "- It’s just a variation of our **accumulator pattern**\n",
    "\n",
    "- Many algorithms work this way and so require the use of indefinite iteration\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "GUXfHIyIWzlZ",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Anotther example\n",
    "\n",
    "Let's see another accumulator pattern program that add up the reciprocals of powers of two:\n",
    "\n",
    "$$\\frac{1}{2^0} + \\frac{1}{2^1} + \\frac{1}{2^2} + \\ldots + \\frac{1}{2^n}$$\n",
    "\n",
    "You may have studied this sequence in a math class and learned that the sum approaches but never reaches 2.0. \n",
    "\n",
    "That is true in theory. However, when we implement this summation in a program, we see something different."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "JMsiEfMSXFqD",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "the_sum  = 0\n",
    "a_number = 0\n",
    "\n",
    "while the_sum < 2.0:\n",
    "    the_sum = the_sum + 1/2**a_number\n",
    "    a_number = a_number + 1\n",
    "\n",
    "#print(a_number)\n",
    "print(the_sum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "iqIYMlITXdKt",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "\n",
    "### Modify the program...\n",
    "\n",
    "If the sum never reaches 2.0, the loop would never terminate. \n",
    "But the loop does stop! \n",
    "How many repetitions did it make before it stopped?\n",
    "\n",
    "On line 8 (not indented), print the value of `a_number` and you will see.\n",
    "\n",
    "But why did it reach 2.0?\n",
    "\n",
    "Are those math teachers wrong?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "xTNGKjhcQzpU",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 3.3.18 Algorithms\n",
    "\n",
    "- Newton's method is an example of an **algorithm**:\n",
    "\n",
    "    - it is a mechanical process for solving a category of problems\n",
    "        (in this case, computing square roots)\n",
    "\n",
    "- Some kinds of knowledge are not algorithmic:\n",
    "\n",
    "    - learning dates from history or multiplication tables involves\n",
    "        memorization of specific solutions\n",
    "\n",
    "- But the techniques for addition with carrying, subtraction with\n",
    "    borrowing, and long division are all algorithms\n",
    "\n",
    "- One of the characteristics of algorithms is that they do not require\n",
    "    any intelligence to carry out.\n",
    "\n",
    "    - They are mechanical processes in which each step follows from\n",
    "        the last according to a simple set of rules\n",
    "\n",
    "- And they're designed to solve a general class or category of\n",
    "    problems, not just a single problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "CsqRSGe65E42",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Computational thinking\n",
    "\n",
    "\n",
    "> Using algorithms and automation as the basis\n",
    "for approaching problems is rapidly transforming our society.\n",
    "\n",
    "\n",
    "- Understanding that hard problems can be solved by step-by-step\n",
    "    algorithmic processes (and having technology to execute these\n",
    "    algorithms for us) is one of the major breakthroughs that has had\n",
    "    enormous benefits\n",
    "\n",
    "- But, some of the things that people do naturally, without difficulty\n",
    "    or conscious thought, are the hardest to express algorithmically\n",
    "    (e.g. NLP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Zz-UtV8ORH_t",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Ticket to leave"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "C-hchAExRRVh",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## Moodle activity\n",
    "\n",
    "[LE04: Iteration](https://moodle.up.pt/course/view.php?id=1738#section-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "uV1OP6ahRYne",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "\n",
    "$\\Rightarrow$ \n",
    "[Go back to the Table of Contents](00-contents.ipynb)\n",
    "\n",
    "$\\Rightarrow$ \n",
    "[Read the Preface](00-preface.ipynb)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "None",
  "colab": {
   "collapsed_sections": [
    "8z5cONg8rUrX"
   ],
   "name": "04-iteration.ipynb",
   "private_outputs": true,
   "provenance": [],
   "toc_visible": true
  },
  "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"
  },
  "rise": {
   "enable_chalkboard": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}