english/5_NestedLoops.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "collapsed": true
      },
      "source": [
        "# Introduction to Programming with Python\n",
        "\n",
        "# Unit 5: Nested Loops\n",
        "\n",
        "Let us start with revisiting the exercise from the last unit. We needed to:\n",
        "\n",
        "1. Write a function `fact` that will calculate a factorial $n!=1\\cdot2\\cdot\\dots\\cdot n$\n",
        "2. Print a table of factorials from 1 to 7\n",
        "\n",
        "Let's start with a function:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "trusted": true
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "5040"
            ]
          },
          "execution_count": 2,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "def fact(n):\n",
        "    acc = 1\n",
        "    for i in range(2,n+1):\n",
        "        acc = acc*i\n",
        "    return acc\n",
        "\n",
        "fact(7)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Here we are using a special technique: we introduce a variable called **accumulator**, which initially takes the value 1, and then it is multiplied in turn by 2, 3, and so on, up to $n$. It happens inside a loop. When the loop is done - we return the value of accumulator, which is equal to the factorial.\n",
        "\n",
        "The number which changes from 2 to $n$ inside a loop is called a **loop counter**. It is the variable that is used in the `for` expression, when we are saying `for i in ...`. Very often programmers call those variables `i`, `j`, `k` and so on, but it is just a tradition. Most probably, it is because `i` stands for **index**, or for **integer** (and loop counters are often integers).\n",
        "\n",
        "An important thing to note here is that in our case we need the value of loop counter to change from 2 to $n$. If we write for loop in this way:\n",
        "\n",
        "```python\n",
        "for i in range(n):\n",
        "    ...\n",
        "```\n",
        "then `i` will change from 0 to $n-1$, and the loop will repeat $n$ times. In our case, we want the values of `i` to start at 2, and end with the value $n$ inclusive, so we need to write a loop like this:\n",
        "\n",
        "```python\n",
        "for i in range(2,n+1):\n",
        "    ...\n",
        "```\n",
        "\n",
        "Important things to remember:\n",
        "\n",
        "* First argument of `range` specifies the starting value of the counter. If the argument is missing - it defaults to 0\n",
        "* Second argument of `range` specifies when we need to end the loop, and loop is over just before the counter reaches specified value. So it is essentially the last counter value plus 1\n",
        "\n",
        "Now, to print the table of factorial values, we use another loop:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "trusted": true
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "1! = 1\n",
            "2! = 2\n",
            "3! = 6\n",
            "4! = 24\n",
            "5! = 120\n",
            "6! = 720\n",
            "7! = 5040\n"
          ]
        }
      ],
      "source": [
        "for i in range(1,8):\n",
        "    print(f'{i}! = {fact(i)}')"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Notice how elegantly we use the string interpolation here, putting the expression `fact(i)` right inside the curly braces inside the string. We do not even need to use an additional variable here!"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Nested Loops\n",
        "\n",
        "In our case, to print the table we used a loop from 1 to 7, and inside it to calculate the factorial another loop was used inside the function `fact`. If we were to write everything inside one big piece of code, we would write something like this:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {
        "trusted": true
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "1! = 1\n",
            "2! = 2\n",
            "3! = 6\n",
            "4! = 24\n",
            "5! = 120\n",
            "6! = 720\n",
            "7! = 5040\n"
          ]
        }
      ],
      "source": [
        "for i in range(1,8):\n",
        "    acc = 1\n",
        "    for j in range(2,i+1):\n",
        "        acc *= j\n",
        "    print(f'{i}! = {acc}')"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "When we have a loop inside another loop, we call it **nested loops**. Two important things are worth noticing here:\n",
        "\n",
        "* We need to use different names to name counter variables in nested loops. In our case, we use `i` as the counter of **outer loop**, and `j` as counter of **inner loop**.\n",
        "* The counter of outer loop can be used inside the range expression in the inner loop.\n",
        "\n",
        "We also introduce another operation here, `*=`, which is very useful whenever we are dealing with an accumulator. The expression `acc *= j` in our program is equivalent to `acc = acc * j`, but it is shorter, and is still quite clear in terms of meaning."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Drawing a Rectangular City\n",
        "\n",
        "In the previous unit, we have learnt how to draw a streen of several houses. Now it's time to use the notion of nested loops to draw a rectangular city with a number of streets! What we need to keep in mind is that after drawing one street we need to move the turtle back to the beginning of a street, and down. We will also define the configuration of a city (number of rows and columns) in variables in our code - it is always a good idea to do so, to make code more customizable."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Run this cell if you are using the tutorial via Google Colab\n",
        "!pip install jturtle"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "trusted": true
      },
      "outputs": [],
      "source": [
        "import jturtle as turtle"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "trusted": true
      },
      "outputs": [
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQoAAAD4CAYAAAAU5qhvAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvqOYd8AAAEs9JREFUeJzt3XmwpFV5x/HvGWZn2IZh3wnigiKCA7JvIsiYUciMIhJRBEE2kUA0KAIxcY+7UeMSFEVRVFQwklLLRIMaUXEHVEBmWAcUjWUpLk/+OO9l7rz0e8/by9zurvl+qk5Nvef0r7hVfe/T79KcJ0UEkjSVGcP+ASSNPguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhcZCSmm9lNL5KaWefmer/HkDyKch5Wf2k++XhULj4ijgNcChPeaXVPmDesw/vcrv32P+2Cq/T4/55VV+cY/5vqSIGMZ/V2otpTQTuAG4llwoFkfEn7vIzwK+B/wHcDCwd0T8pYv8bOD7wDXAAcC+PeR/BHwW2A/YL7r4w0spzQF+DHwG2Bs4sJv8IHhGoXFwKnAPcB7wO+D5XeZfBKys8g8CJ3aZPwO4FTi/Oj6hy/zZwE1VfhZwfJf5c4AfVvn5wLO6zPcvIhyOkR3ApsC9wOOq472Au4GNWuYXAauA3arjxcCdwIYt85tX+UdXx08C7gA2aJnfArgP2LU63o9ctBa0zG9V5Xepjg8EbgfmT+f74KWHRlpK6e3AjIg4Y9Lc+4FfRcR5LfL/CvwpIs6eNHcpcE9EvLRF/j3A7yLiJZPmLgNWRMQFLfLvAx6Y/LOmlC4Hfh4RF7bI/ztw7+SfNaV0BfCTiLi4lB+YYX9iOBxNA9iNfDaxaW1+SyZ9Sk+Rfxz5kmVhbX6NT+kp8nuQz142qc1vA9wP7FzI7wncRe3sB9iuyu9YyHc8+wF2qPLbT9t7MexfBoej0wAS8J/AWQ3r5wOfK+S/DJzesP4y4KpC/ivAqQ3rLwc+Wch/FTi5Yf2VwMcL+euA5zesXwJ8dNrej2H/QjgcnQawlHynf1bD+hzgp8BRDevHAD8AZjaszwV+DhzRsL6M/KRkvYb1eeQbnIc1rD8L+O4U+fnAL4CDG9aPB64nX3Z1Wl8fWEF+ArL2349h/0I4HPVRFYGfAUcWXrcU+Em9mFRF4Bbg8EL+GPLThJm1+XnAbcChhfwy8mPTen6iCBxUyD+L/Nh3vdr8RBHYv5A/Hvh2UzEZ5PBmpkZOSmkJcHU3mYh46BuLKaWl5O8c9Jo/BvhUH/llwCf6yD8TuKLX/NpgodBISilFm1/+6stUD9Zfu67nB80vXGmsRcQfza99FgpJRTOH/QNIbaSU1rhG7vZUe13P98szCo2NiEj9/IGs6/l+WCgkFVkoJBV5j0Jjo36dbn76WCg0Fvq9Nl/X8/3y0kNSkWcUGlnDPlUf9/wg+RVuSUVeekgqslBIKrJQSCqyUEgqslBoLKSUFqaUbkopbdBjflGVX9BjfouU0o0ppfk95req8nN7zG9b5ef0ku+XhULj4hRgY+AFPeZfWOW7bR40Ob8J8Lwe86cCC+m++VA9/7c95vuztvfaczj6HazeXv9IcjOezbrMT2yvfxR5+/9FXea3q+UXdpnfflL+Hmrb/7fI71jln0oXzY8GOfwehUbe5CY4KaW3AHMj4rQu8h8CVkbEBZ0aCrXIfwS4JSIu7NRQqEX+Y8CNEXFxp4ZCLfKfAL4fEa/q1FBoWgz708LhmGpQa4JDPv2/B9ijZX6NFoDk0/eHWhS2yO9P3hF7/ep4jRaFLfJrtAAENmNSi8IW+UPIO4LPq44nWhQ+clrfh2H/IjgcTYPcBOfr1JrgAKeRm/OkQn4G8E3gubX5M8jNgdrkrweeU5s/m9ycqJRfD/gOcFxt/iXAF1rmvwcsr82fB1w9ne+FNzM1yo4nd//+YG3+feQzg78p5Ce6jn+4Nv8ecvPhZxTyJ5K7n19em38XsC3w14X888nd1+tb778T2Ak4upA/GXgAuLI2/zbgkSmlowr5wRn2p4bD0WmwugnOfg3rh5E7dc1rWF9AvuR4UsP6k8mdwuY2rG9IvuRZ3LB+JLlT2ZyG9Y3IfUf3alg/GrgJmN2wvjH5xmXHSyxykXpY86O1NTyj0Kh6KfDfEXFdp8WI+DL5tP7chvw/AF+KiG805L9Ibjl4TkP+AuDaiPhWQ/5a4EbyZUgnrwCuiYhvN+Q/Ty5UZzbkXwl8JiJuaFi/mnzv4/SG9cEa9ieHw1Ef5MeB9wHbFl63M/mx4TYd5u+rz3fI71K9buuG+a0K+V2r123ZYX4VsEUh/6jqdZs3zE/5GBh4TJvXDWK4H4VG0abVWJFSq42dVpJvfNbzK1vm76jlF1b5O1vm7+qQXwTc3TJ/T0P+3pb5e2v5gfN7FBpJbVvqNb12Xc8PmvcoJBVZKCQVeY9CY2HYLfnGPd8vzyg0NmLMW/oNO98PC4WkIi89NDaGvf39uOf7YaHQWOj3lHtdz/fLSw9JRRYKSUVeemhkDfuaftzzg+RXuCUVeekhqchCIanIQiGpyEKhsZFS2sz8cFgoNBZSSrsBd6WUdukxv3uV37nH/BOq/A495p9Y5bftMb9vld+6l3y/fOqhsZBSupJq16mIeE4P+U+TN6xdERHP7SH/WWAD4LaI6LotYUrpGvKGwT+LiJO7zCby9v5zgJsi4tRu//v98oxCIy+ldAjwRGAZcFBKab8u84cDjweWA4enlJ7UZf4p5P0plwNHppQWd5l/KvAI8s+/JKW0Zzd5YAm5LeFy4BkppT26zPdvbW/K6XD0M1jdBGdZdXwC8C1yW8A2+Znk3baPqY5PBL7RRX4W8CNgaXV8EnAdheY9tfyNwJLq+BTgq13kZwM3A0dVx62aHw16eEahUXcy8Cvgk9Xx5cCfgLaXDy8kbz57VXV8GflMuu3ly2nkzXc/Vx1fSv7jfXbL/Bnk/iOfr44/QO458syW+bOAmyPiC9Xxe8ltFUvNjwZr2J8YDkfToKHPKLA3k/qRTpHv2GcU2Jf8x7+gkF9U5Xerza/Rj3SKfMc+o8BBwC+o+pFOke/YZxQ4lEn9SKdjeDNTIyul9GbyH9PDbt6llC4F7o6Il02RfxswMyIe1iQnpXQZcHtEvHyK/DuBv0TEWR3WLiffmHzlFPl3A7+PiIc1GUopXQH8OCIumSL/XuA3EfF3HdauBG6IiH9qyg/UsD81HI5Og0ITHGBrcvOfv2pY363KL2pY36bK79Sw/jjy2cTChvXtqvwODeuPJ58NbdKwvkOV365h/QnkloIbN6zvRIfmR2treI9Co+pNwKsjYlWnxYi4E3hjNdZQPU58M/CqiLivIX9H9Zo3NOTfAlwSEb9syK8gNwt+/RT5iyLiVw35X5CbFb+uIf9W4MKIeKAhfyvwbuC1ndYHbtifHA5HfQBHkZ8UdGzgO+l1c4FbgENr80uAH1No4AvMI1/rH1ybXwr8kHzZMlV+PvlewwG1+WPIT2rWK+QnGjHvW5tfBny3RX6iEfM+a/s98R6FRk5KaX3gt91kYtJWcQPILwD+r4/8BsBvhpVfGywUGknDbsk37vlB8x6FpCK3wtNYGHanrXHP98szCo2NGPNOXcPO98NCIanIQiGpyHsUGhvD3v5+3PP9sFBoLPR7bb6u5/vlpYekIs8oNLKGfao+7vlB8puZkoq89JBUZKGQVGShkFRkoZBUZKHQWEgpzUopvS6l1NOTupTS7AHl1+sxP2cA+df2mu+XhULjYgnwEuCIHvNLq/xhPeaPrfKH9JhfVuUP6DF/HHAu0FXzo0Hx8ahGXkppNrkJz0fI3bL2iIg/dpGfQ94a7zJyP4wnRMSfusjPBX4CfAh4BrBnRPy5i/y8SfmnAYu7zM8nbw14KXA0sHdE/KVtfhA8o9A4OBu4CbiE3M/jtC7z55D3wLyEvDP3C7vMn0vew/Ji4AFyU6JunEfubnYR8Dug296lf0/uTnYR8CC529n0Wtubcjoc/QxyE5xVwK7V8WPJ2+hv2jK/JbmJzi7V8e7kbfQ7bsPfIb91ld+5Op5yG/0O+W2r/I7V8V7AXcBGLfPbV/ntq+PFtGh+NOjhpYdGWtUE59cRcd6kuXcARMSZLfIfAFZFxEsnzb0LeDAiXtwi/0Hgjoi4YNLcvwG/jYhzW+Q/DNwaERdOmns/8MuIOL9F/qPkDuYXT5q7lELzo4Eb9ieGw9E0gD3Jn94b1eY3pUOrwA75jp++rG7195hCfh/ydvgb1OY3r/KPKuT3A1ZSa13I6rOcXQv5A4HbqbUeBLZi0lnStLwXw/5lcDg6DSCRu36f0rB+JvBFGrp6V/n/AU5qWH8xcO0U+RnkrucnNqyfC3x+ip9/Bvm+xAkN6+cDnyvkvw08u2H9ZcBV0/Z+DPsXwuHoNMjdvhub4JD/z+cfAU9vWH82cD0wo2F9FvlJxNMa1k8A/neK/GzyDdajG9ZPBL4+RX4O8FPgyIb1k4CvTVHIJpofPXla3o9h/0I4HPXB6g5cBxVedwTwc2BObX6iA9f+hfxR1R/r7Nr8guqSYd9CfgkdOpoBG1SXLHsX8kvp0NEM2JB8w3OvQv4YWnQ0G8RwPwqNooPJd/v/K7fhLPo9+VJjwiHkpw1fa5n/Qy1/GLmJ8XU95g8nPy35Zsv8g7X8EeT7GNe3zP+xlh84n3poJLXtfpVSmgH8uf7adT0/aH7hSmMt+vyG4rqeb8tCIanIexQaC8NuyTfu+X55RqGxEWPe0m/Y+X5YKCQVeemhsTHs7e/HPd8PC4XGQr+n3Ot6vl9eekgqslBIKvLSQyNr2Nf0454fJL/CLanISw9JRRYKSUUWCklFFgpJRRYKjYWU0uYppZUppY17zG9Z5TfsMb9NlV/QY367Kr9+j/kdU0orqmZC085CoXFxBhDA6T3mz6zyL+oz323zoQlnVf9223xocj4Bp/SY78/a3mvP4eh3sLoJzgHVv1t3md+xlt+yy/zOVe7A6t8tusw/YlJ+FbBZl/lHVrmDyG0KFk33e+D3KDTyUkofA26MiItTSq8hF4rWbfVSSp8Avh8Rr0opvZ78h3ZSF/lPAddHxKtTSv9C7hPS+pM9pfQZ4LqIeF1K6S3A3IhofWaSUroa+EpEvDGl9Hbyzt5ntM0PxLA/LRyOqQa1Jjis3uF6n5b5Q4DbgHnV8cQO14tb5g8HbiX/cQNsTG5KtGfL/FOAn1HtFA5sQm5puEfL/FOBm6l2+gYW0qL50cDfh2H/IjgcTQNYD/gOcFxt/kRyc56OPTNq+RuA5bX5k8jNgTr2zJj0upnAD4Bja/OnkJsTtck/rPcI+T7HV1rkO/YeId+v+VIpP8jhzUyNsueRu39fUZu/jHwj/vhC/gXAr4Era/OXkhvoHFfIn0K+N/Dp2vwHyGc2ywv508gtDT9bm38f+czg2EL+dHJ/k2tq8+8hN29+eiE/OMP+1HA4Og1gI6ZoggPsS4e+npPWJy4ROp7ik29srgDWb1hfSL5E2L1h/WDyH/H8hvWJ/qiPbVg/jHxJM69hfaI/6qMb1p9Mbn40dzreD29maiSllN4AbBIRJ0/xmg8Dt0XEKzqsvYlcBE6dIv9R4OaIuKjD2lvJHbwaH8emlD4O/DAi/rHD2juAiIizHp586DWfBL4TEf/cYe1dwB8i4pwp8lcB34iI1za9ZmCG/cnhcNQH+XHiKgqPIcndwO4HdqrNP4oWjyHJj13vB3aozT+GFo8hyY9d7we2q80/tsovLOR3rvLb1OZ3J5/NbFLI70J+7LrV2n5P3I9Co2gusAi4u2VLvVtYs6Xe7Cp/b8v8bR3ymwGrWuZvr+VnVfn7W+ZXdshvDvyyZf7OWn7gvPTQSGrbUq/ptet6ftB86iGpyEIhqch7FBoLw27JN+75fnlGobERY97Sb9j5flgoJBV56aGxMezt78c93w8LhcZCv6fc63q+X156SCqyUEgq8tJDI2vY1/Tjnh8kv8ItqchLD0lFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklF/w/qTbJVednVHwAAAABJRU5ErkJggg==",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        }
      ],
      "source": [
        "rows = 5 # number of rows (streets)\n",
        "cols = 5 # number of columns (houses in a street)\n",
        "sep = 5 # separation between houses\n",
        "w = 10 # house size\n",
        "\n",
        "from pycourse import house, square\n",
        "        \n",
        "for _ in range(rows):\n",
        "    # draw one street\n",
        "    for _ in range(cols):\n",
        "        house(w) # draw a house\n",
        "        # move turtle to the next house\n",
        "        turtle.penup()\n",
        "        turtle.right(90)\n",
        "        turtle.forward(w+sep)\n",
        "        turtle.left(90)\n",
        "        turtle.pendown()\n",
        "    # move turtle to the beginning of a street\n",
        "    turtle.left(90)\n",
        "    turtle.penup()\n",
        "    turtle.forward(cols*(w+sep)) # width of the whole street\n",
        "    turtle.right(90)\n",
        "    turtle.backward(2*w+sep)\n",
        "    turtle.pendown()\n",
        "        \n",
        "turtle.done()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Please note that we are using comments `#` quite extensively, to help you understand what goes on inside the code. Comments help other people as well as yourself after few weeks to understand the code.\n",
        "\n",
        "Another useful trick that we are using here is called **anonymous variable** `_`. If we do not care about the value of a loop counter, we can use underscore instead of a variable name, which means *we do not care about the value*. It help people who read the code to understant that variable value is not important, and also saves you the effort of having to come up with new loop counter name each time inside nested loops."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Nested Loops vs. One Loop\n",
        "\n",
        "It is possible to rewrite the same logic using one big loop instead of two nested loops. In our case, whenever we encounter a street end, we need to return the turtle to the beginning of the street and move it down. Suppose the variable `i` denotes the loop counter, i.e. house number, in which case the end of the street is encountered when this number is divisible by `cols`, i.e. the remainder of `i` divided by `cols` is 0. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 25,
      "metadata": {
        "trusted": true
      },
      "outputs": [
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQoAAAD4CAYAAAAU5qhvAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvqOYd8AAAEs9JREFUeJzt3XmwpFV5x/HvGWZn2IZh3wnigiKCA7JvIsiYUciMIhJRBEE2kUA0KAIxcY+7UeMSFEVRVFQwklLLRIMaUXEHVEBmWAcUjWUpLk/+OO9l7rz0e8/by9zurvl+qk5Nvef0r7hVfe/T79KcJ0UEkjSVGcP+ASSNPguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhaQiC4WkIguFpCILhcZCSmm9lNL5KaWefmer/HkDyKch5Wf2k++XhULj4ijgNcChPeaXVPmDesw/vcrv32P+2Cq/T4/55VV+cY/5vqSIGMZ/V2otpTQTuAG4llwoFkfEn7vIzwK+B/wHcDCwd0T8pYv8bOD7wDXAAcC+PeR/BHwW2A/YL7r4w0spzQF+DHwG2Bs4sJv8IHhGoXFwKnAPcB7wO+D5XeZfBKys8g8CJ3aZPwO4FTi/Oj6hy/zZwE1VfhZwfJf5c4AfVvn5wLO6zPcvIhyOkR3ApsC9wOOq472Au4GNWuYXAauA3arjxcCdwIYt85tX+UdXx08C7gA2aJnfArgP2LU63o9ctBa0zG9V5Xepjg8EbgfmT+f74KWHRlpK6e3AjIg4Y9Lc+4FfRcR5LfL/CvwpIs6eNHcpcE9EvLRF/j3A7yLiJZPmLgNWRMQFLfLvAx6Y/LOmlC4Hfh4RF7bI/ztw7+SfNaV0BfCTiLi4lB+YYX9iOBxNA9iNfDaxaW1+SyZ9Sk+Rfxz5kmVhbX6NT+kp8nuQz142qc1vA9wP7FzI7wncRe3sB9iuyu9YyHc8+wF2qPLbT9t7MexfBoej0wAS8J/AWQ3r5wOfK+S/DJzesP4y4KpC/ivAqQ3rLwc+Wch/FTi5Yf2VwMcL+euA5zesXwJ8dNrej2H/QjgcnQawlHynf1bD+hzgp8BRDevHAD8AZjaszwV+DhzRsL6M/KRkvYb1eeQbnIc1rD8L+O4U+fnAL4CDG9aPB64nX3Z1Wl8fWEF+ArL2349h/0I4HPVRFYGfAUcWXrcU+Em9mFRF4Bbg8EL+GPLThJm1+XnAbcChhfwy8mPTen6iCBxUyD+L/Nh3vdr8RBHYv5A/Hvh2UzEZ5PBmpkZOSmkJcHU3mYh46BuLKaWl5O8c9Jo/BvhUH/llwCf6yD8TuKLX/NpgodBISilFm1/+6stUD9Zfu67nB80vXGmsRcQfza99FgpJRTOH/QNIbaSU1rhG7vZUe13P98szCo2NiEj9/IGs6/l+WCgkFVkoJBV5j0Jjo36dbn76WCg0Fvq9Nl/X8/3y0kNSkWcUGlnDPlUf9/wg+RVuSUVeekgqslBIKrJQSCqyUEgqslBoLKSUFqaUbkopbdBjflGVX9BjfouU0o0ppfk95req8nN7zG9b5ef0ku+XhULj4hRgY+AFPeZfWOW7bR40Ob8J8Lwe86cCC+m++VA9/7c95vuztvfaczj6HazeXv9IcjOezbrMT2yvfxR5+/9FXea3q+UXdpnfflL+Hmrb/7fI71jln0oXzY8GOfwehUbe5CY4KaW3AHMj4rQu8h8CVkbEBZ0aCrXIfwS4JSIu7NRQqEX+Y8CNEXFxp4ZCLfKfAL4fEa/q1FBoWgz708LhmGpQa4JDPv2/B9ijZX6NFoDk0/eHWhS2yO9P3hF7/ep4jRaFLfJrtAAENmNSi8IW+UPIO4LPq44nWhQ+clrfh2H/IjgcTYPcBOfr1JrgAKeRm/OkQn4G8E3gubX5M8jNgdrkrweeU5s/m9ycqJRfD/gOcFxt/iXAF1rmvwcsr82fB1w9ne+FNzM1yo4nd//+YG3+feQzg78p5Ce6jn+4Nv8ecvPhZxTyJ5K7n19em38XsC3w14X888nd1+tb778T2Ak4upA/GXgAuLI2/zbgkSmlowr5wRn2p4bD0WmwugnOfg3rh5E7dc1rWF9AvuR4UsP6k8mdwuY2rG9IvuRZ3LB+JLlT2ZyG9Y3IfUf3alg/GrgJmN2wvjH5xmXHSyxykXpY86O1NTyj0Kh6KfDfEXFdp8WI+DL5tP7chvw/AF+KiG805L9Ibjl4TkP+AuDaiPhWQ/5a4EbyZUgnrwCuiYhvN+Q/Ty5UZzbkXwl8JiJuaFi/mnzv4/SG9cEa9ieHw1Ef5MeB9wHbFl63M/mx4TYd5u+rz3fI71K9buuG+a0K+V2r123ZYX4VsEUh/6jqdZs3zE/5GBh4TJvXDWK4H4VG0abVWJFSq42dVpJvfNbzK1vm76jlF1b5O1vm7+qQXwTc3TJ/T0P+3pb5e2v5gfN7FBpJbVvqNb12Xc8PmvcoJBVZKCQVeY9CY2HYLfnGPd8vzyg0NmLMW/oNO98PC4WkIi89NDaGvf39uOf7YaHQWOj3lHtdz/fLSw9JRRYKSUVeemhkDfuaftzzg+RXuCUVeekhqchCIanIQiGpyEKhsZFS2sz8cFgoNBZSSrsBd6WUdukxv3uV37nH/BOq/A495p9Y5bftMb9vld+6l3y/fOqhsZBSupJq16mIeE4P+U+TN6xdERHP7SH/WWAD4LaI6LotYUrpGvKGwT+LiJO7zCby9v5zgJsi4tRu//v98oxCIy+ldAjwRGAZcFBKab8u84cDjweWA4enlJ7UZf4p5P0plwNHppQWd5l/KvAI8s+/JKW0Zzd5YAm5LeFy4BkppT26zPdvbW/K6XD0M1jdBGdZdXwC8C1yW8A2+Znk3baPqY5PBL7RRX4W8CNgaXV8EnAdheY9tfyNwJLq+BTgq13kZwM3A0dVx62aHw16eEahUXcy8Cvgk9Xx5cCfgLaXDy8kbz57VXV8GflMuu3ly2nkzXc/Vx1fSv7jfXbL/Bnk/iOfr44/QO458syW+bOAmyPiC9Xxe8ltFUvNjwZr2J8YDkfToKHPKLA3k/qRTpHv2GcU2Jf8x7+gkF9U5Xerza/Rj3SKfMc+o8BBwC+o+pFOke/YZxQ4lEn9SKdjeDNTIyul9GbyH9PDbt6llC4F7o6Il02RfxswMyIe1iQnpXQZcHtEvHyK/DuBv0TEWR3WLiffmHzlFPl3A7+PiIc1GUopXQH8OCIumSL/XuA3EfF3HdauBG6IiH9qyg/UsD81HI5Og0ITHGBrcvOfv2pY363KL2pY36bK79Sw/jjy2cTChvXtqvwODeuPJ58NbdKwvkOV365h/QnkloIbN6zvRIfmR2treI9Co+pNwKsjYlWnxYi4E3hjNdZQPU58M/CqiLivIX9H9Zo3NOTfAlwSEb9syK8gNwt+/RT5iyLiVw35X5CbFb+uIf9W4MKIeKAhfyvwbuC1ndYHbtifHA5HfQBHkZ8UdGzgO+l1c4FbgENr80uAH1No4AvMI1/rH1ybXwr8kHzZMlV+PvlewwG1+WPIT2rWK+QnGjHvW5tfBny3RX6iEfM+a/s98R6FRk5KaX3gt91kYtJWcQPILwD+r4/8BsBvhpVfGywUGknDbsk37vlB8x6FpCK3wtNYGHanrXHP98szCo2NGPNOXcPO98NCIanIQiGpyHsUGhvD3v5+3PP9sFBoLPR7bb6u5/vlpYekIs8oNLKGfao+7vlB8puZkoq89JBUZKGQVGShkFRkoZBUZKHQWEgpzUopvS6l1NOTupTS7AHl1+sxP2cA+df2mu+XhULjYgnwEuCIHvNLq/xhPeaPrfKH9JhfVuUP6DF/HHAu0FXzo0Hx8ahGXkppNrkJz0fI3bL2iIg/dpGfQ94a7zJyP4wnRMSfusjPBX4CfAh4BrBnRPy5i/y8SfmnAYu7zM8nbw14KXA0sHdE/KVtfhA8o9A4OBu4CbiE3M/jtC7z55D3wLyEvDP3C7vMn0vew/Ji4AFyU6JunEfubnYR8Dug296lf0/uTnYR8CC529n0Wtubcjoc/QxyE5xVwK7V8WPJ2+hv2jK/JbmJzi7V8e7kbfQ7bsPfIb91ld+5Op5yG/0O+W2r/I7V8V7AXcBGLfPbV/ntq+PFtGh+NOjhpYdGWtUE59cRcd6kuXcARMSZLfIfAFZFxEsnzb0LeDAiXtwi/0Hgjoi4YNLcvwG/jYhzW+Q/DNwaERdOmns/8MuIOL9F/qPkDuYXT5q7lELzo4Eb9ieGw9E0gD3Jn94b1eY3pUOrwA75jp++rG7195hCfh/ydvgb1OY3r/KPKuT3A1ZSa13I6rOcXQv5A4HbqbUeBLZi0lnStLwXw/5lcDg6DSCRu36f0rB+JvBFGrp6V/n/AU5qWH8xcO0U+RnkrucnNqyfC3x+ip9/Bvm+xAkN6+cDnyvkvw08u2H9ZcBV0/Z+DPsXwuHoNMjdvhub4JD/z+cfAU9vWH82cD0wo2F9FvlJxNMa1k8A/neK/GzyDdajG9ZPBL4+RX4O8FPgyIb1k4CvTVHIJpofPXla3o9h/0I4HPXB6g5cBxVedwTwc2BObX6iA9f+hfxR1R/r7Nr8guqSYd9CfgkdOpoBG1SXLHsX8kvp0NEM2JB8w3OvQv4YWnQ0G8RwPwqNooPJd/v/K7fhLPo9+VJjwiHkpw1fa5n/Qy1/GLmJ8XU95g8nPy35Zsv8g7X8EeT7GNe3zP+xlh84n3poJLXtfpVSmgH8uf7adT0/aH7hSmMt+vyG4rqeb8tCIanIexQaC8NuyTfu+X55RqGxEWPe0m/Y+X5YKCQVeemhsTHs7e/HPd8PC4XGQr+n3Ot6vl9eekgqslBIKvLSQyNr2Nf0454fJL/CLanISw9JRRYKSUUWCklFFgpJRRYKjYWU0uYppZUppY17zG9Z5TfsMb9NlV/QY367Kr9+j/kdU0orqmZC085CoXFxBhDA6T3mz6zyL+oz323zoQlnVf9223xocj4Bp/SY78/a3mvP4eh3sLoJzgHVv1t3md+xlt+yy/zOVe7A6t8tusw/YlJ+FbBZl/lHVrmDyG0KFk33e+D3KDTyUkofA26MiItTSq8hF4rWbfVSSp8Avh8Rr0opvZ78h3ZSF/lPAddHxKtTSv9C7hPS+pM9pfQZ4LqIeF1K6S3A3IhofWaSUroa+EpEvDGl9Hbyzt5ntM0PxLA/LRyOqQa1Jjis3uF6n5b5Q4DbgHnV8cQO14tb5g8HbiX/cQNsTG5KtGfL/FOAn1HtFA5sQm5puEfL/FOBm6l2+gYW0qL50cDfh2H/IjgcTQNYD/gOcFxt/kRyc56OPTNq+RuA5bX5k8jNgTr2zJj0upnAD4Bja/OnkJsTtck/rPcI+T7HV1rkO/YeId+v+VIpP8jhzUyNsueRu39fUZu/jHwj/vhC/gXAr4Era/OXkhvoHFfIn0K+N/Dp2vwHyGc2ywv508gtDT9bm38f+czg2EL+dHJ/k2tq8+8hN29+eiE/OMP+1HA4Og1gI6ZoggPsS4e+npPWJy4ROp7ik29srgDWb1hfSL5E2L1h/WDyH/H8hvWJ/qiPbVg/jHxJM69hfaI/6qMb1p9Mbn40dzreD29maiSllN4AbBIRJ0/xmg8Dt0XEKzqsvYlcBE6dIv9R4OaIuKjD2lvJHbwaH8emlD4O/DAi/rHD2juAiIizHp586DWfBL4TEf/cYe1dwB8i4pwp8lcB34iI1za9ZmCG/cnhcNQH+XHiKgqPIcndwO4HdqrNP4oWjyHJj13vB3aozT+GFo8hyY9d7we2q80/tsovLOR3rvLb1OZ3J5/NbFLI70J+7LrV2n5P3I9Co2gusAi4u2VLvVtYs6Xe7Cp/b8v8bR3ymwGrWuZvr+VnVfn7W+ZXdshvDvyyZf7OWn7gvPTQSGrbUq/ptet6ftB86iGpyEIhqch7FBoLw27JN+75fnlGobERY97Sb9j5flgoJBV56aGxMezt78c93w8LhcZCv6fc63q+X156SCqyUEgq8tJDI2vY1/Tjnh8kv8ItqchLD0lFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklFFgpJRRYKSUUWCklF/w/qTbJVednVHwAAAABJRU5ErkJggg==",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        }
      ],
      "source": [
        "for i in range(1,rows*cols+1):\n",
        "    house(w) # draw a house\n",
        "    # move turtle to the next house\n",
        "    turtle.penup()\n",
        "    turtle.right(90)\n",
        "    turtle.forward(w+sep)\n",
        "    turtle.left(90)\n",
        "    turtle.pendown()\n",
        "    if i%cols == 0: # end-of-street encountered\n",
        "        # move turtle to the beginning of a street\n",
        "        turtle.left(90)\n",
        "        turtle.penup()\n",
        "        turtle.forward(cols*(w+sep)) # width of the whole street\n",
        "        turtle.right(90)\n",
        "        turtle.backward(2*w+sep)\n",
        "        turtle.pendown()\n",
        "        \n",
        "turtle.done()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This example shows us that it is always possible to write the same program in many different ways. And there are often different criteria to determine which way is better:\n",
        "\n",
        "* **code clarity** - it is always better to have a clear and readable code, because it is easier to write and maintain\n",
        "* **program efficiency** - sometimes simpler or shorter code does not mean better performance, so we need to take performance considerations into account\n",
        "\n",
        "Ofter we end up having to compromise between simplicity and performance. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Sierpiński Triangle\n",
        "\n",
        "Now that we know loops, let me show you a very beautiful example of how a simple computer program can generate infinite complexity and beauty. We will learn how to draw so-called [**Sierpiński Triangle**](https://en.wikipedia.org/wiki/Sierpiński_triangle) - a fractal structure that looks like this:\n",
        "\n",
        "<img src=\"images/Sierpinski_triangle.png\" width=\"30%\"/>\n",
        "\n",
        "([photo](https://commons.wikimedia.org/w/index.php?curid=8862246) from [Wikipedia](https://en.wikipedia.org/wiki/Sierpiński_triangle) by Beojan Stanislaus, CC BY-SA 3.0)\n",
        "\n",
        "This figure is surprisingly easy to draw! We need to implement the following algorithm:\n",
        "\n",
        "1. Select three vertices of a triangle, $(x_1,y_1)$, $(x_2,y_2)$ and $(x_3,y_3)$.\n",
        "2. Set coordinates of current point $(x,y)$ to some initial value.\n",
        "3. Randomly pick one of the vertices $i\\in\\{1,2,3\\}$\n",
        "4. Calculate new point coordinates as *midpoint* between current point and selected vertice: \n",
        "$$x \\leftarrow \\frac{x_i+x}{2}$$\n",
        "$$y \\leftarrow \\frac{y_i+x}{2}$$\n",
        "5. Draw a point at coordinates $(x,y)$\n",
        "6. Repeat from step 3\n",
        "\n",
        "This process sounds like a loop than never ends, or so-called **infinite loop**. In practice, we definitely want our program to stop at some point, so we just program sufficiently large for-loop.\n",
        "\n",
        "To begin with, let's define the list of triangle vertices as a list of coordinate pairs. We have not discussed yet what lists are, but for now please consider it just a collection of pairs, from which we would be able to pick one pair using `random.choice` function which we have seen before:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 16,
      "metadata": {
        "trusted": true
      },
      "outputs": [],
      "source": [
        "vertices = [(0,00),(100,0),(50,100)]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now let's program the main loop. Here we use coordinate-based graphics and `turtle.point` to draw the dot, and to make the dot smaller we specify additional parameter, `pointstyle`. Please note that this loop can take a moment to execute!"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 17,
      "metadata": {
        "trusted": true
      },
      "outputs": [
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQEAAAD4CAYAAADsBlOYAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvqOYd8AAAEltJREFUeJztnWF3rqquRu0d5///5Z4Pd7tPVlYCiYKCmXOMjrYWMS/CQwjR/vz+/h4AUJf/e9sAAHgXRACgOIgAQHEQAYDiIAIAxUEEAIqDCAAUBxEAKA4iAFAcRACgOIgAQHEQAYDiIAIAxUEEAIqDCAAUBxEAKA4iAFAcRACgOIgAQHEQAYDiIAIAxUEEAIqDCMAlfn5+eFf9R0AEAIqDCAAUBxGAy7Ak+AaIAKQ4B/7v7+/P7+/vD0KwP4gAhDkHvP4Oe4MIQJrf398f+R32BhGAFN7AxyvYlx/+NTncRcYJ3rYF8uAJQIifn5/f80see9MmGAMiAF1+fn5+z90Ab0eAnYJ9+c/bBsAeyAEu3X4G/v4gAtDEG/zesdNreMI2GAMiAE1aA5rB/g0QAXDpeQG98xCJPUAEoEl0IMtlAEuCvWB3AFwYyDUgWQhMvKh/Sxj0OYjIHiACEMZz83H/94blAPyF5QV4Tw56HoPOLoR1QQTgD64sA/R5MsMQIVgfRAD+RW/tWQNbn3MOdl0e9oGYAPyBFIKoV2AFBK/mGMDzkCcA/9J7QlA/MyAHu+cl4B2sD54A/AtR/prgCcBUWBasD54AQHHYHYC/YgEj1/G8mXh9EAH4l9ExgWhiEbwLIlAcOVPPEAC9Q8A7CteDmEBxZu0IeFuHvGtgPfAECqP3+s9j8vvVeo+jn1QEa8AWYVF6HsCdmdo7l9l/TfAE4DiO9pODV+vy/k8BHsFaEBMoSC/XX5N9v2A0XRjPYA0QAWhCKvH3YTkALplZ/SyfKXvPOhgFIlAM638K9spHy2XfK8Dbh9aA5UAhMnv0ehmQWRZky0ZtgjmwRViUrCDc+fvd68NcWA4UwRp0IwRA1hP5R6XnEkC+g5BlwbsgAoWwBKCXH9D7l+RneSkEmdiALA/vgAgUIOvOWwOz9crx6A5CRETgeRCBIkRnZ+maWwNfDnjtAcg6dFl5vvcPTFgSvAMi8HEyLw/1zpNlrV0Dq3zvEWIG/DogAkWwBqE3Y2thsP7bsHWuNbh1HKLl+vN24ndABAqgg3a92V/vJMhovvzduk5rba/jB60YQe4TxkBgbEgWgqUgSPg8JAt9lJZbDiDBEyjAjrPrjjbvCiLwQbwtvR0GFR7M87Ac+Di7CACD/z3wBD4GbjRkYYvwY3jZePL7avQeNnranmogAh/CeyJvhyScVjbj6rbvDiLwMfQTf/LR3bdts7ASk6zjMA9iAh/EG/QrDqxe6vLKAvYVEIGP4LnMnku9wsDyBr081nqm4Sy/wmfZGUTgA6w4w0fgXYRrQEygGCvtFNx9GQmMARH4AFde9T3XopgNWVd+h12OHSFjsBDeI8Jv2BJ9nbn1DgMYCyLwEXqz5IqDKbrOJ/g3F5YDH6D1Tj8L+ZKRpwVBv9Go9xIS+ftqIvYVEIGN8WZSPUj0G33Oc56eYaP2SiyhwCsYCyKwIXI2jc78K82eli2WcGXOh+uQJ/BRdAxghWCgRc9OL5i52ufYGTyBzZGzYu9lInrgPJkzoB9sav3sPQDVyiaE6+AJbEhrjS/LyRmz9WTh7JnVClxatl0Z2HgD90EENmPWYJ2dljvTboTgHiwHNmJX9xcBWBtEYDNmroV3HFC7CuNKIAIb8YSrPnpQyXX/yLp1HAExuA4isAGzo/h6II28jvZcGKzrwbMDG9Da1rvrHegdhjt1ter1dimuwhbhONgd2IA3AmB3r9lKER4lXDPqrgjLgcXxZtDTfb8zG86eSVuPB1+tszXQEYBrIAIboJcAo2bTlrjI612hFWi8Y7u3DGBpcB1EYGG02+s9TTd6sHrXi2J5KOexu2t5aydj5u5GBRCBjejl2GfrsQaqdfwKViryqFhA69kClgR5CAwuitXRW2WznV/PntYOxIzAoLxexu5sMBBBiIMILEq2E0fLZwd4pvyssrPrrg7LgQXJuuWj9+CfYrbNu7XHW5AstCieq67JuNaW2x9dZkTqz9jcsssqm/EY8ABy4AksRjYWEDkWqcurJ+ONnN9nzfCRYChpynkQgcWQs2l0ByAyYGV9mUEiB5VX1vJGMoITSSqK2DxqG7IaLAcWJBoBbw2eSPlW4o21tRcRjNbfe3VHMwE9O0ZuR1YCT2AhWjP/nSy51kzuiUU0h6B3vGVPpGw09fhO3kR1EIEN6O216+OROrLLg5YN51fUNi84GXX5rTpaZRGHNojAIsgBdXXWteqwriN/z67dtcstr93yVlq29ZYv+nN7y5Ozbnm81x5AstASWLOhDLR53/W5sj5Zx/mzdy39d1lXpG7r98wx71rS3sg5VrtYngP8CZ7AIsgZzBvw3vaXPNcTAF1Gu/KWIHjX6GEJmq5P7yJEdkVagU1P3PR14W/wBKAMeAU2eAIv0pr1YDwMfhtEYAEIXM2H9vVBBF5Gr/thPNFt1KogAi9hRfzpnM+A4P4JgcGXaEWz6aTzwfv6H3gCL2ANep2IA+NgOdAGEXiYlgdA5xyPNeNHH4iqAsuBF+hls+GqjsVKwnrbppXAE3gQmanXy/9nlrqHzsGIPHBUFURgETyXFa5heVdeyvXTtq0Gy4EHwRVdk+r3BU/gYTIzD7PUdTJtV1kAjgMReJRoZ2PwX8d6ojJSvnKbIwKL0Xp0GOJE8i5k0LByWyMCD5CN/FvPyEMfK/DXgrb9fxCBRSF6nUd6UJnnMbJLiK/B7sBkIm/X0eVJHsqTeWEI7fkneAITGbUTQIe9R/QBraoBQkRgEnpmiribVsygspuaxWs7Ta99q7U1IjAJOdtY2YDem3jl7zxgFEO793pAt15ISqYmMYFpWANcHotuSbXeBAz/w/KivNePa6w3M8vzvw6ewCR0pFr/zeqQ2nuwvAm8gT+xBu/5u/Vzq47Wz1E7dgRPYAIzZ5Jqs1SEWdH+KrsIeAKDmTkjVOmUGWYKgPz+ZfAEBsNAfZ6ZbV7hfuIJDETOHqNnEL1WrTBDtfDeDzCq3kpbhojAQGQw8DjmisHXZ6cW1hbgzCXB12E5MJkR7qSXSnwcNcXAa1MChNfAExiIl9xzd0Zp7XFXma00TydSfbmdEYHJ3JlB5Pr0yzNRFi/34jjuD9aKWZqIwACshJVRA9dKMZ65Dl4dL/h6t729pKPzmCzzNf7ztgG7463XR6afemmvX+2UEbyBebZTts2t+yXriaZ57wiewE289wR43kG03qhH8eXO2UIP2NZDQdG6znqsXZ0vJw+xO3CTTKdboeyuZL0q2joOnsANrs7sM+uHte7LDiACF7my3o8G81pBqjv17sqVQTdjmfRFL+A4WA7c5oqb2isvA4HRx2C/2Dktem0i/z5y0H65ndkduIA1w7Sy2LJ1R7carY75xdlKB+4i5SJC2toN6F3jS23McuAiMirdi97LL3nunXqjZb6AbL+eqEa3Uq1jXv1fzxtABJLovWP9N6u8/L3VgaytKW/LqgKZz629hYxIyzqsshlh3hFE4AJWtppX1sr2a0WkvU4YERzPvq/hfT6rjVptEVm+Zc/fEUQgwTlT6Jtvuauy88jyemmg6z5/lsc9OywbvzJbRT6jFSuwPClLiD1RtZYE1r29+/lWAhFIIDuC7HR6xtEdypuRdH1nGW9d2zr2pdlfD25r8Fmi6bWF9bNVpwwkynuhr+edvyuIQJDMze55Cjry34t+e7sArWt+gZYonn+P1GEdbwUQW8s3LdqRYOXqkCcQpOWersxudluCB3PBEwiwo+LvZOvu7L40QASC7HaDd5xJd/NavgIi0MEKBL5rUYxd7JTI/fhd7JfCtauAIQINdp6Zeimzq6F3UHYTgp13ZxCBj7JjHEOzuoB5Oxa7tTkPEAXYyd3Tyxcrt2FVWgk871gUI5J6vDJsESZZ+SZH8g1Wt91LzlkNz77ePVgRlgMddnP5rDTZ49gzUHgc69rdSlN+x6LrIAIGXtrpqh3yOPpPK3ri8Daey7/6ToGXlnwc+wkBywGDyLbgatF3LxC48nq1JVy9z7ICln1WWvE71sXBE1CcN85am1oBwhVnqeP4+2nClXcLPC9Ff4aV0B7Wqm0bAU9AkY1Ir6L2GTtWsPlKO2fKQxy2CA2yHfNNsu6njG/sNKBWsDUb+d9FuFgOCKTL3BvgctnwthhkOtlKLvaVtlulrTP94xnLroMI/ENmhpRlVumU+mcLnd76tu0RVrI3kzS2Q9zoBBH4h+xNWyXPXQ7slgezivt/1UV+27W+IkZv2xyFmMA/WIOkNXBWuLFXBnbmMz5BK0OwlZX3tM2Wx9Wzb+XtWQmewJFz11a+mSctbyBSbha9tlvZbfZyRayylph5daxAeRHouc/RpcHTMQLrOp7L6pWda6FNa8liZQ1awrVCMNb6HN5nW33SKC8Cx/F3xNebMb2B9fRN9mIRrWi0JVJPRq+tJCzLPlleH7cSt2Zj3XO9M6QTh6zzVtlJsigtAt469Djsfxqiz9PK/8RSwVtvej+3Ot0by4GIfd4x717NoiVUWqQin2XVpWRpEehxDjYdFJKzkRSLJ5Redzrv9xa9pcJo9IDxbNQzqp55r0To79ps4XlVVh3ys6zqCZRNG15VlVvsaPNxzNsqm7kFt8v23ghKewIzVXm3untLhzv1jq7zZGZMY1bdZzuv5BGUFoEZrHRzrzDL/hlewEzhmrnseDIgG6GsCMyI1uo14k6C0Ircj6h75mCaVffoOr1dp7cpKQKzVX5G4E3bPFq8Zi4F5PdR19HB2hntPCOYpwPJo+q9QykRsDqhtdV3lxmur96ROI+PuoaVFnsHq6OPcoM9IRzdHjNyEvROxwreQKlnB6yMtFF1Wzdzxiyif76zY+AN1NG7EF7Czx10PSPaevZug3f/Rl8rS0lPwGv4ETckmvxyp95RS4JWZ39ieXCnDi9x6GrdrT4xasb2Joq79d6llAhY7qhM6Lgzo1p1SPW/0zk92+52IGvNqxNc7tosB+eo5YDXpnfr9j73iABkq463vYESImApuQz83K1b1qc7/VnuynW82W30utrqnFfbpmWznMWvdPzRyxRJK+Pv/Plq3VafWGmnoETGoO7orQ551xto3cxs3douTwyyg8Or1+qgV2yODPi7cYwWd9rZOv9u/2jdxxGxnbuUEoG3686WPY74Cy1XWFtmA2srtF227gyr2NGjxHLgOGIzSDYIdOWmzXD7Mu515jOODIqNIGtHtPxVL2pk3W8KeRkRiJKdbTKDL2rDlVkve40o0TVx1o5se1w5L+pFZUQxeu07QdUr593h0yKgg3+jb2I02i0j4xm1z8zwM+2I1p+pV5ad1dZR4YrYoevt1Z35fCNiUnf4rAjIm3YeG9XAGWGxAoaRzuad69Ud8R4ydpzlZdmIHZG6r86+UbHILmGya/doffK+ZD7r097AZ0XgOP5u1F7H7JWxyme9jMjAu+r+9gaqJTA9GyOz1Gnz+ffWrK3r69mhZ/XegJLlIoNPC12rnGzDnmBo2yPtYdn0BJ/dHfAa3jqeLXsc/X3lXt0ZuzN2WMezM12mPa7Y9+R9GdVOd++LRdbmWXzSE8i4YPKcaFmrbu/81gygZ9xWR/NmDF1HdO1s2dD7PNk2tepsDTCr7mg7n/ZFj7fayLovXlnvepbdT7v5UT4pAifemtZyd72Oom9cRgAsPPdauunSTuliyzo8N9OyrecaR9rDmzl7beoNbH2eZ7dlbwvLjjsDsLdc8PqHtl2Lc3R58wSfFoETvU70ZqPezdD1yL/JQazL659l+da1ZQeRZaQwtOrVZXR9Xnu0hEXbKs+X3owWr5anJL967WSV64lyVNCs9rC8K+219SYKTyy98t6xWXwuJqBvjm7MXoP3ZlZZptWxW7O0/LvlGfTKtWyJdChPGFqd2jveOlfbP6Jjt2Zm6zqta1ttJ+uOeluWbboefZ6uu9XPZvM5T8ATAGsGkcesGU3Wp/+ur+nNwNbMqTuWVbc1gPQ51udu/Szr9WzR9ngd0fq7rCtatzX7WmW07VadrXtreSg98ZPl5EyuP7s+3yqr28ITJKs9ZvM5TwAAcnzOEwCAHIgAQHEQAYDiIAIAxUEEAIqDCAAUBxEAKA4iAFAcRACgOIgAQHEQAYDiIAIAxUEEAIqDCAAUBxEAKA4iAFAcRACgOIgAQHEQAYDiIAIAxUEEAIqDCAAUBxEAKA4iAFAcRACgOIgAQHEQAYDiIAIAxUEEAIqDCAAUBxEAKA4iAFAcRACgOIgAQHEQAYDiIAIAxUEEAIqDCAAUBxEAKA4iAFAcRACgOP8FEOmryC+d50wAAAAASUVORK5CYII=",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        }
      ],
      "source": [
        "import random\n",
        "\n",
        "x,y = 150,150\n",
        "for _ in range(3000):\n",
        "    vx, vy = random.choice(vertices)\n",
        "    x = (x+vx)/2\n",
        "    y = (y+vy)/2\n",
        "    turtle.point((x,y),pointstyle=',')\n",
        "turtle.done()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Isn't this picture beautiful?! I find it very fascinating that we can achieve potentially infinite complexity with quite a short code.\n",
        "\n",
        "While the figure is beautiful, our code can still be improved. In our code we think in terms of individual coordinates $x$ and $y$, while we can switch to higher level thinking, and keep in mind the points, and not coordinates. \n",
        "\n",
        "To do that, let's first define a function `midpoint` to calculate the position of middle point between points `a` and `b`. Let me remind you that if `a` denotes a pair of point coordinates, then `a[0]` denotes the first coordinate ($x$), and `a[1]` -- second coordinate ($y$).\n",
        "\n",
        "Using this function, the code becomes a lot cleaner:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 19,
      "metadata": {
        "trusted": true
      },
      "outputs": [
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQEAAAD4CAYAAADsBlOYAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvqOYd8AAADiVJREFUeJztndm25CoOBe1e9/9/Ofuhy+tSagnEYDMo4qVycGLMsbaEEK779/tdABCX/8zuAADMBREACA4iABAcRAAgOIgAQHAQAYDgIAIAwUEEAIKDCAAEBxEACA4iABAcRAAgOIgAQHAQAYDgIAIAwUEEAIKDCAAEBxEACA4iABAcRAAgOIgAQHAQAYDgIAIACfd9h3sG/83/OwAQGyIBgOAgAgDBQQQAgoMIAAQHEQAIDiIAEBxEACA4iABAcBABgOAgAgDBQQQAgoMIAAQHEQAIDiIAEBxEACA4iABAcBABgOAgAgDBQQQAgoMIAAQHEQAIDiIAEBxEACA4iABAcBABgOAgAgDBQQQAgoMIAAQHEQAIDiIAEBxEACA4iABAcBABgOAgAgDBQQQAgoMIAAQHEQjGfd+/2X2AtUAEAIKDCATivu/f7/e7iQYgBREIQioAv9/vnt0fWAdEIBiPABANwAMiEIDH4KXhIwRwXdd1/37cBwCR+Wd2B+AbpNcnLwAPTAcO5r7v32P8qdEjAJCCCByMNPbf73fLz8gLACJwMF4DRwhigwgciqcegJoBuC5E4GispcHaY+BsWCI8EOnhteQgUQA8EAkEQUsS4v3huhCB49A8vCwVxvghhenAQeSMW9szkEYDbC6KCxWDB6LVAmgVg6nREx3EhUjgEPDi0Ao5gUMY5dHJG8QDETgELeSvNWSZLxjVN1gbpgMHoBl7ixGz0zAmJAY3R8sFtITyFBTFhenAAbzhwckJxAER2Jxne7BM6NUasbXtGDE4H0RgY55kYG9C72lDExP5Gs4DEdgUOYfX5vI1xivb+epJRAjMfFgd2JRRSTvvcweui9WCUyES2BCPp+dZAuAFEQhOKQFIFHA+iMBmeL13Ore3jvWUGmsPJ4GzICewOVaxUMvzBbUnErW0DXtBJLARuS3Bnt/WfG/lHRCA80AENqS0hq+t91tLiOn30ugtr8+04CzYO7AZch5vGbxV+CPb6skXwBkgApshPXuuwk97epAUBykE2mPGrN/DGZAY3ACW6eBNEAGA4JAYXJw0ebdCGK6tUMDeIAIbsOI0ADE4B0RgI1ZJyj2rD6v0B/pABBbGKuCZ3R8eSHoWiMCiaCW82mv5m7f7pfWJaGBvEIGFyZUIj3rCcE1frP/UlGhgbxCBBcnVBcwwuFR4tJJjkoR7Q53AYqw4327dlQh7QCSwITPm4iN2KsKaIAILUvKo2sNA36KmZJlIYE8QgYXIbeyZ2Z/ntWdVYnafoR52ES6EtXc/97SftzcX1T5ejGhgP4gEFsHrQb+KEGrO8VQP1v4O1gARWIhSWK15/bcjADlF0fqkHYMY7AMisADaU4K07+X7t3cYph4+NW5LGFbIY0A9iMAiWA/1TDfqSIPUngQ8oi+PoUuBsZ5YdFIeIKKIUSw0mVGJvZHFOqPaooBoD4gEFqHXA40KxUd7woiedTeIBA5i5HLhihEKvAN1AhMp1QC0ttPTn+d1T3sr7n8AG6YDkxi1A08aXO+0IF0RkO23tNXbBrwPkcBERkQBsp3nfW172vEtxpurJyAqWBMigQlYj+mqNTprb39Ln+T5e4yW5wvsBSIwCW9FXokRHlY+LES23VpCnLZBIdG6MB2YhFYi3JKR14yr1tjeqPpLpyRvb3KCPlgiXBCPd/dGAKXjVmsHvofpwIfUzNt7jxm5K7H3+97j4V0QgQUZEQXUhPUeD+8533N867lgDojAR3iTbFquINderq1SQs5bq+DN9o+OGOAbEIGP0bbkyu9TA9eSftrKgjympi85L57uZCz1J+2/bOfUXYcngAh8gGYoueNTY7EKilIv3zI1aFnLL0UUOQHwtANzQAQ+wDNfll79MdI3jDcnHFo/rOvI5Qtyy56ywAnmggi8jFYMJF9rhpb+mxqSFRmkolHKPWh7A2TYb00VcklCy+DT7zH89aBO4ANK4bI0qtSQpQjUfJeeOz2XFB1pvLnfaOfOXQ+rBeuDCLyMZ84OMBOmAy9C6As7gAi8hHe9PzKMyxowHXgRLVEGsBpEAjAFq9AJvgcReAFtOY2bXadUQQnvgwgMRssFePcNRCFXkATfw0NFXsBasyc38C/aWDA+c0AEXsAq6LkubnStkMl6D9/A6sBAKAzqhzH8HnICgyltEoqeAPOMQeTxmQHTgUF4k39RvZwn1Lc2WcG7EAkMQtv1lyJXDSJ7O0+0xGrKdyACA/AatfchINY52no3HxkFlHZT9owT1IMIdFIb5rbe2LsaRCkqSj+Thr+z8O0EItCJ9bQdeVzuxn+/l+uhLZ3uKnS7gwh0oHkv7Zjryj/N5/2ezsd6cMrzWqseJC/wDdQJdGAlsLSn+3ifxHMSuScWecaDIqtvQAQaobqtDMm9PWA6sAAnhryjBCBy3uQrEIEGcg/y7GnrJEZuoT5xfFYCEeig9+ZMcwUnebs3ruek8VkNRKCSUTfjyXvpn1WP3iiH5zF8A3sHBtB6s58Y5o5c/jxxfFaESKCTlpvdigJO8XSa1265Nq1+4JQxWglEoIKcx6+9OTXx2N3zaeNjFQJ52krfRyqs+hpEwIl2I7d4qfRYLYG2u6ezdgHWGPDz+zS3kLaz+xitBsVCTkaue5fa2XHZ0Fs8der17wyRgBOPB/IujZWO2c3b1QiAp71R7YAPRMDByGXBUz1cqThoVJm1Nh2DPpgOFPA+LyA9xkqQeY9J2UE0PHP/2mNKx+0wLruACDiQia6S8ZYKZU7bfFQan5b2Su2cNoYzYTpQIDVmLeSVxTGWAGieULajRQKrh7zyujSjrF0B8UYTu+VOVgURyOBZ+rPW+3Nz13QJrNSH1T2dN4nnWebTjsmVDlNANAZEwECbw6fvn8+sWoGSMFi/ydUjrIqnQlAbR48QyChMtkERUT/sHXAgjdPjkSzvnzNoS1BWJbcSkBqmFABLMLRpUkksRmxUig6JQWgCwzsHpgMK3qKfr1ipL9eFAJwGIrARq4hBqTDoa7TcDPhBBASrrT97cglfsqqxkRtoBxEwWGVKMLII50R2S6auCInBP1heZKZ3SaOA3FLll/2R517N+yKY9RAJ/CEXcs/wLnJJclY/JJ6KwK9YJVrbHUTgD1ap70yPIktjVyqMWaVPWg3HrL7sCtOBP2gVblbV2+y+zEiCyfOnn82amqTjoEUECIIPROBaz4Os2J/rGvPUoK8gN+CH6YCTr+ae3vNEng97rxsB8BFeBLzr8KvdUF9PTUp7+78UJO/ORfkadMKLwENuD/tXa9CPIHlv8q+EwLM68VWC8Pl75IRnpdWUHQgtAqlxe7zZF5V71g679L22rfYttN2AWv++8L7eFYlVVi52IexWYm+YK49566byFuLMLmjy9ukLrFUS69kDX/dvF0JHAtrNktu7PgPpYWXE8qYoyXNpJboz9zVoUZI1PkwNbMKKgHVz5Ipz3s4NeKKAtE9veznr/NbxaX9Gj5GWL9H6o/3NiALyhBQBzcPJG1fzeum/b/dP65fMYXzRr+f8uao8aXRv9EWOgxYhpceX+gz/Eq5YKL0hpJHJz5/Xz3da1PBVX2djjZs2Lx/d75r2rL8p2IQWgd52rmvMTTaiTyMNb6UxsoQGxsF0oPH319U/99XC+l5621nR2EaODQnC/yeUCGjJpRZGrT8/bawSBWjToNZ2RkU31zUu2tJeQyARGOVxR3vuN7zubAO2ci49fVpFuE8kjAjI5bURN9Xzb8tNrq1ntxrLyOKdEcYyKuKS/WkdH+oG8oSoGMzdBDU3qnbj9HgprQahFu06Wq/N6k/t9Y0SpVGeWyYWiQj+JlwkcF3tc02rOCVts4Y0Gmj1nNpvRrbTKpJyTb92fLQ6iJax1pZ/SRD+TRgReOjx3NaNXXtTaobfYyi9c/D0euTKR0+/nnZaRUkrAGppJ/197zTuRI4XgZzR93gEeXN7byrL8GvnvlKQ5Ode5PxdFtq0eN/nd605D3n+liVZTaDldIBpwf84vlio5PlT7+k5rnSu66rfmdjShucGHtXnmnOO6M9XfR65BLkzx0cC15X3Yh7vUnPzeow3d8zI7PWIkHekoXj7442ocsfVTNWiTwuOFQFPdvsJpUcapnVMTciuhdPy+9JUpmceL89VOsaTO/Bev2esPeH8CNGOwrEiIP+4pRs0dxN7IgXtX8+xWj+sa6jpW8lQakJqz/XkDKomxC+JhZbEzPXZe97IHF8nULoJasJ3LXdQM1du6YvVfq4P0gBKBtFjvFpfPOfS2k4/swRAnsvz97DGR/Yn1++TOTIS8GTMPZ7YOi7FCs3l+bWbt3RuDe3aSiLheV+bdU9fe8a31OdR/fP2R34X0fgfjhSB6/r7JpKhaqr66Y2czsVLnkj+TrYtz6P1T56jNtv9vNcMTPbPK3DWdT39K33mOcY6d8mja9fhEY/0/N7cRCSOmw5ohlFzbEkg5O/Tf0vnetotfe4JTXPGmn6WXkdJrHLjoWGF9rn3pXHQPpNTstz5PZGK9rfV+hSFo+sErJvPeq39zvqsZKgeL+8RgJzHtMJY6SnlOFifae2UxkX7zhIOKTDa30I7Rp6jdH3WOGljWxqDCBwtAgBQ5ticAAD4QAQAgoMIAAQHEQAIDiIAEBxEACA4iABAcBABgOAgAgDBQQQAgoMIAAQHEQAIDiIAEBxEACA4iABAcBABgOAgAgDBQQQAgoMIAAQHEQAIDiIAEBxEACA4iABAcBABgOAgAgDBQQQAgoMIAAQHEQAIDiIAEBxEACA4iABAcBABgOAgAgDBQQQAgoMIAAQHEQAIDiIAEBxEACA4iABAcBABgOAgAgDB+S91+gOyD4HGbwAAAABJRU5ErkJggg==",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          },
          "output_type": "display_data"
        }
      ],
      "source": [
        "def midpoint(a,b):\n",
        "    return ((a[0]+b[0])/2,(a[1]+b[1])/2)\n",
        "\n",
        "p = 150,150\n",
        "for _ in range(3000):\n",
        "    v = random.choice(vertices)\n",
        "    p = midpoint(p,v)\n",
        "    turtle.point(p, pointstyle=',')\n",
        "turtle.done()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Exercise: Polygons\n",
        "\n",
        "Coming back to our original topic of nested loops, please do the following exercise:\n",
        "1. Define a function `poly` that will draw a polygon with a given number of sides (and a given size). You most probably want to use turtle graphics for this!\n",
        "2. Draw three polygons with number of sides of 3 (triangle), 5 and 7. You should end up with a picture like this:\n",
        "\n",
        "![Polygons](images/PolygonTask.PNG)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "trusted": true
      },
      "outputs": [],
      "source": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3.6",
      "language": "python",
      "name": "python36"
    },
    "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.6.6"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}