{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Timetable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to build your timetable!\n",
    "\n",
    "We suppose that you have:\n",
    "- a weekly scheduling \n",
    "- two hours slot, only 8-10, 10-12, 12-14, 14-16, 16-18\n",
    "- from 8:00 to 18:00 \n",
    "- from Monday to Friday \n",
    "- 4 courses (Coletti, Fedele, Kraus, Simonelli) to accomodate in the timetable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As data structure to indicate which course is when we could use a matrix wih the 5 days as column and the 5 slots as rows, like this one\n",
    "<table align=center>\n",
    "    <tr align=center><td>Hour</td><td>Monday</td><td>Tuesday</td><td>Wednesday</td><td>Thursday</td><td>Friday</td></tr>\n",
    "    <tr align=center><td>8:00-10:00</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr>\n",
    "    <tr align=center><td>10:00-12:00</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr>\n",
    "    <tr align=center><td>12:00-14:00</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr>\n",
    "    <tr align=center><td>14:00-16:00</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr>\n",
    "    <tr align=center><td>16:00-18:00</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will obviously use a list of lists, such as TT=[ [ , , , , ] , [_, , , , ] , [ , , , , ] , [ , , , , ] , [ , , , , ] ] where each element is a day and its 5 elements are the slots.\n",
    "<br>If a list of lists confuses you, you can try with a list with 25 elements, but you will have a harder time checking for the constraints."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Inside this list we will write numbers, where 1 is Coletti, 2 is Fedele, 3 is Kraus, 4 is Simonelli... and 0 is no lesson in that hour. For example, yout timetable for the week of 2 december is:\n",
    "<br>TT=[ [0,0,0,1,2] , [0,0,0,0,0] , [0,0,0,0,0] , [0,0,0,0,0] , [0,1,0,0,0] ] <i>a hard week, isn't it?</i>\n",
    "<br>Note that if you prefer you can put the initials instead of the numbers or the full name. But comparing numbers will be easier than letters, later on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are however some constraints in the timetable. They are:\n",
    "- each course exactly 6 hours in the week (it's not true), i.e. three slots\n",
    "- no lesson on Monday morning, i.e. slots first and second must be 0;\n",
    "- no lesson on Friday afternoon, i.e. slots third, fourth and fifth must be 0\n",
    "- maximum 1 slot every day for each course\n",
    "- Coletti never lesson on two consecutive days\n",
    "- Fedele and Kraus can never meet, i.e. their lessons cannot be consecutive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The timetable is a well-known algorithmic problem which is also widely spread, you can easily imagine how often people need to build a timetable with constraints. However, there are only some heuristic algorithms which try to solve some predetermined situations. Most of the times the only way to deal with it is... brute-force, i.e. trying all the combinations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1: brute-force"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your task is to build an algorithm which calculates an acceptable timetable useing brute-force. There are clearly several solutions (or none, if we put too many constraints). Count the number of attempts your algorithm does, because I would like to know.\n",
    "\n",
    "Do not worry if after some time it is still trying to find the solution. Stop it and print TT to see at which timetable it has arrived.\n",
    "\n",
    "<font color=PURPLE>Strategy: you must build a function **check** which takes as input the timetable and returns a boolean to indicate whether it is valid or not. The function must check all the constraints one by one and return <b><font color=GREEN>False</font></b> as soon as one is not satisfied. When you have this function, you use a brute-force approach: you set up a system which tries all the combination of professors inside the timetable, even absurd ones. Every time your function will tell you whether it is ok or not. As soon as you find a good one, you stop and print it.\n",
    "    \n",
    "<p>For example, the function starts trying a timetable completely empty which obviously does not satisfy the constraint that each course does exactly 6 hours per week. Then it goes on trying 1,0,0,0..., then 2,0,0,0,..., then 3,0,0,0,..., then 4,0,0,0,..., then 0,1,0,0,..., then 1,1,0,0,..., then 2,1,0,0,...., then 3,1,0,0,...., then 4,1,0,0,...., then 0,2,0,0,...., then 1,2,0,0,...., and so on. Obviously a lot of the attempts will not be accepted, but this is brute-force and trying a huge number of possibilities is exactly the strategy of the algorithm.\n",
    "\n",
    "<p>But how do you create this sequence of numbers? Well, it's not easy at all, and for this reason I have written for you the function nextAttempt which takes as input a timetable and produces the next attempt, incrementing the professor's number.\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check(TT):\n",
    "    # no lesson on Monday morning, i.e. slots first and second must be 0;\n",
    "    if TT[0][0] != 0:\n",
    "        print(\"Attention: lesson on Monday morning\")\n",
    "        return False\n",
    "    if TT[0][1] != 0:\n",
    "        print(\"Attention: lesson on Monday morning\")\n",
    "        return False\n",
    "    \n",
    "    # no lesson on Friday afternoon, i.e. slots third, fourth and fifth must be 0\n",
    "    if TT[4][2] != 0:\n",
    "        print(\"Attention: lesson on Friday afternoon\")\n",
    "        return False\n",
    "    if TT[4][3] != 0:\n",
    "        print(\"Attention: lesson on Friday afternoon\")\n",
    "        return False\n",
    "    if TT[4][4] != 0:\n",
    "        print(\"Attention: lesson on Friday afternoon\")\n",
    "        return False\n",
    "\n",
    "    # each course exactly 3 slots in the week\n",
    "    # we have to go through the entire week and find out how many slots\n",
    "    # does each lecturer have\n",
    "    slots={ 0:0, 1:0, 2:0, 3:0, 4:0 }\n",
    "    day=0\n",
    "    while day<=4:\n",
    "        hour=0\n",
    "        while hour<=4:\n",
    "            currentProf=TT[day][hour]\n",
    "            slots[currentProf]=slots[currentProf]+1\n",
    "            hour=hour+1\n",
    "        day=day+1\n",
    "    # now inside slots I have how many slots does each prof have\n",
    "    for x in slots:\n",
    "        if x>0 and slots[x]!=3:\n",
    "            print(\"Attention! Lecturer \",x,\" has \",slots[x],\" slots\")\n",
    "            return False\n",
    "    \n",
    "    # maximum 1 slot every day for each course\n",
    "    \n",
    "    # Coletti never lesson on two consecutive days\n",
    "    \n",
    "    # Fedele and Kraus can never meet, i.e. their lessons cannot be consecutive\n",
    "    \n",
    "    \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def nextOne(TT,j,i):\n",
    "    # this function increments by 1 the timetable at day j and hour i, for profs which go from 0 to 4\n",
    "    if i>4:\n",
    "        nextOne(TT,j+1,0)\n",
    "    else:        \n",
    "        if TT[j][i]<4:\n",
    "            TT[j][i]+=1\n",
    "        else:\n",
    "            TT[j][i]=0\n",
    "            nextOne(TT,j,i+1)\n",
    "def nextAttempt(TT):\n",
    "    nextOne(TT,0,0)\n",
    "    \n",
    "\n",
    "TT=[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]\n",
    "# write here your code\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=RED>NOTE! You do not need to run it until you find  avalid solution, as it really takes too many attempts (unless you have few constraints, in particular no one on Monday morning). Just run it for a while, then stop it and print the value of TT that it has reached."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Determine the complexity in the worst case, taking as unit of measure the call of function **check**, as a function of how many slots you have in the timetable (25) and how many courses (5, including the no lesson)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Modification 2: brute-force optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For sure you have noticed that your program is doing a lot of silly attempts for nothing! If you print your attempts and inside the check function print the reason why it was rejected, you can also have an idea of the most common rejections.\n",
    "\n",
    "There are several ways to **optimize** it. It is not worthwhile to skip just a couple of attempts, but it is very worthwhile to skip a lot of useless attempts. Try to come up with at least one optimization (not the ones done in class on Monday morning or Friday afternoon) which can speed up the code, or more if you want. Explain them <u>clearly and throroughly</u> in English. Then, if you are able to implement one of them (probably it requires modifying my function and thus it might be difficult to implement it), try to do it (implementing is optional task).\n",
    "\n",
    "What you are doing is called **optimization**, a technique which makes your program go faster but usually does not reduce the category of the complexity (i.e., if it is $N^3$ it can become $N^3/2$ but definitely not $N$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Modification 3: fuzzy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of trying all the combinations in sequence, let's build a **fuzzy** algorithm. You algorithm every time fills up the 25 slots of the timetable with random numbers between 0 and 5 until you get a solution which satisfies all the constraints.\n",
    "\n",
    "To get a random integer number between 0 and 4 in Python use function randint(0,4), but at the beginning of the program you have to write \n",
    "<br>from random import randint\n",
    "<br>because the function is not available by default and needs to be taken from a package.\n",
    "\n",
    "Also here count the number of attempts because I am curious whether they are more than the number of attempts in the first execise. Ah, BTW, you can stop at 1 million attempts.... unless you are lucky to get it before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "4\n",
      "4\n",
      "4\n",
      "0\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "from random import randint\n",
    "print(randint(0,4))\n",
    "print(randint(0,4))\n",
    "print(randint(0,4))\n",
    "print(randint(0,4))\n",
    "print(randint(0,4))\n",
    "print(randint(0,4))\n",
    "print(randint(0,4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "# write here your code\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Modification 4: fuzzy optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main problem of fuzzy algorithm is that if you insert random numbers from 0 to 4 in each slot very often courses will have more than 3 slots per week. The optimized version of fuzzy algorithm that I propose completely reverses the situation. Instead of taking the slots one by one and inserting a random course there, you always start from an empty timetable, consider each course and for three times you insert that course into a random day and a random time. In this way you are sure that each course is inserted exactly three times. There is the little drawback that you might insert professor Simonelli randomly on a slot already assigned to Coletti (this is, by the way, exactly what happens in real life) and the lesson which was already there is overwritten, so sometimes the number of slots might be less than 3. Once you have set up a random timetable, check whether it satisfies the constraints. If not, repeat.\n",
    "\n",
    "\n",
    "I managed to find in 20 seconds this wonderful week. You have also a free Thursday morning and time to eat every day!\n",
    "<br>[[0, 0, 1, 0, 4], [0, 2, 0, 0, 3], [1, 2, 0, 4, 3], [0, 0, 0, 3, 4], [1, 2, 0, 0, 0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
