Février 2021 un mini challenge arithmético-algorithmique.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Février-2021-un-mini-challenge-arithmético-algorithmique\" data-toc-modified-id=\"Février-2021-un-mini-challenge-arithmético-algorithmique-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Février 2021 un mini challenge arithmético-algorithmique</a></span><ul class=\"toc-item\"><li><span><a href=\"#Challenge-:\" data-toc-modified-id=\"Challenge-:-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Challenge :</a></span></li><li><span><a href=\"#Réponse-en-Java-(par-un-de-mes-élèves-de-L3-SIF)\" data-toc-modified-id=\"Réponse-en-Java-(par-un-de-mes-élèves-de-L3-SIF)-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Réponse en Java (par <a href=\"http://www.dit.ens-rennes.fr/\" target=\"_blank\">un de mes élèves de L3 SIF</a>)</a></span></li><li><span><a href=\"#Réponse-en-Bash-(par-Lilian-Besson)-?\" data-toc-modified-id=\"Réponse-en-Bash-(par-Lilian-Besson)-?-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Réponse en Bash (par <a href=\"https://perso.crans.org/besson/\" target=\"_blank\">Lilian Besson</a>) ?</a></span></li><li><span><a href=\"#Réponse-en-Python-(par-Lilian-Besson)\" data-toc-modified-id=\"Réponse-en-Python-(par-Lilian-Besson)-1.4\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Réponse en Python (par <a href=\"https://perso.crans.org/besson/\" target=\"_blank\">Lilian Besson</a>)</a></span></li><li><span><a href=\"#Réponse-en-OCaml-(par-Lilian-Besson)\" data-toc-modified-id=\"Réponse-en-OCaml-(par-Lilian-Besson)-1.5\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Réponse en OCaml (par <a href=\"https://perso.crans.org/besson/\" target=\"_blank\">Lilian Besson</a>)</a></span></li><li><span><a href=\"#Réponse-en-Rust-(par-un-de-mes-élèves-(Théo-Degioanni))\" data-toc-modified-id=\"Réponse-en-Rust-(par-un-de-mes-élèves-(Théo-Degioanni))-1.6\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Réponse en Rust (par <a href=\"https://github.com/Moxinilian\" target=\"_blank\">un de mes élèves (Théo Degioanni)</a>)</a></span></li><li><span><a href=\"#Conclusion\" data-toc-modified-id=\"Conclusion-1.7\"><span class=\"toc-item-num\">1.7&nbsp;&nbsp;</span>Conclusion</a></span></li><li><span><a href=\"#Challenge-(pour-les-futurs-agrégs-maths)\" data-toc-modified-id=\"Challenge-(pour-les-futurs-agrégs-maths)-1.8\"><span class=\"toc-item-num\">1.8&nbsp;&nbsp;</span>Challenge (pour les futurs agrégs maths)</a></span><ul class=\"toc-item\"><li><span><a href=\"#Une-première-réponse\" data-toc-modified-id=\"Une-première-réponse-1.8.1\"><span class=\"toc-item-num\">1.8.1&nbsp;&nbsp;</span>Une première réponse</a></span></li></ul></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Février 2021 un mini challenge arithmético-algorithmique\n",
    "## Challenge :\n",
    "Le lundi 01 février 2021, j'ai donné à mes élèves de L3 et M1 du département informatique de l'ENS Rennes le challenge suivant :\n",
    "\n",
    "> Mini challenge algorithmique pour les passionnés en manque de petits exercices de code : (optionnel)\n",
    "Vous avez dû observer que ce mois de février est spécial parce que le 1er février est un lundi, et qu'il a exactement 4 lundis, 4 mardis, 4 mercredis, 4 jeudis, 4 vendredis, 4 samedis et 4 dimanches.\n",
    "\n",
    "> **Question** : Comptez le nombre de mois de février répondant à ce critère (je n'ai pas trouvé de nom précis), depuis l'année de création de l'ENS Rennes (1994, enfin pour Cachan antenne Bretagne) jusqu'à 2077 (1994 et 2077 inclus)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Auteur : [Lilian Besson](https://perso.crans.org/besson/)\n",
    "- License : [MIT](https://lbesson.mit-license.org/)\n",
    "- Date : 01/02/2021\n",
    "- Cours : [ALGO2](http://people.irisa.fr/Francois.Schwarzentruber/algo2/) @ [ENS Rennes](http://www.dit.ens-rennes.fr/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red;\">Attention : ce notebook est déclaré avec le kernel Python, mais certaines sections (Java, OCaml et Rust) ont été exécutées avec le kernel correspondant. La coloration syntaxique multi-langage n'est pas (encore?) supportée, désolé d'avance.</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Réponse en Java (par [un de mes élèves de L3 SIF](http://www.dit.ens-rennes.fr/))\n",
    "\n",
    "> Oui, on peut utiliser Java dans des notebooks ! Voir [ce poste de blogue](https://blog.frankel.ch/teaching-java-jupyter-notebooks/), et [ce kernel IJava](https://github.com/SpencerPark/IJava).\n",
    "Moi je trouve ça chouette, [et je m'en suis servi en INF1 au semestre dernier](https://perso.crans.org/besson/teach/INF1_L1_Rennes1_2020-21/)\n",
    "\n",
    "Il en avait trouvé 9.\n",
    "\n",
    "- Date et heure : lundi 01 février, 20h32."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-01T20:08+0000",
     "start_time": "2021-02-01T20:08:43.628Z"
    }
   },
   "outputs": [],
   "source": [
    "// ceci est du code Java 9 et pas Python !\n",
    "// On a besoin des dépendances suivantes :\n",
    "import java.util.Calendar;           // pour Calendar.FEBRUARY, .YEAR, .MONDAY\n",
    "import java.util.GregorianCalendar;  // pour \n",
    "import java.util.stream.IntStream;   // pour cet IntStream"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-01T20:08+0000",
     "start_time": "2021-02-01T20:08:46.379Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// ceci est du code Java 9 et pas Python !\n",
    "IntStream.rangeClosed(1994, 2077)\n",
    "         //.parallel()  // ce .parallel() est inutile, il y a trop peu de valeurs\n",
    "         .mapToObj(i -> new GregorianCalendar(i, Calendar.FEBRUARY, 1))\n",
    "         .filter(calendar -> !calendar.isLeapYear(calendar.get(Calendar.YEAR)))\n",
    "         .filter(calendar -> calendar.get(Calendar.DAY_OF_WEEK) == Calendar.MONDAY)\n",
    "         .count();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si les cellules précédentes ne s'exécute pas, a priori c'est normal : ce notebook est déclaré en Python !\n",
    "Il faudrait utiliser une des astuces suivantes, mais flemme."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-01T20:01+0000",
     "start_time": "2021-02-01T20:01:50.312Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test d'une cellule en Java dans un notebook déclaré comme Java\n"
     ]
    }
   ],
   "source": [
    "System.out.println(\"Test d'une cellule en Java dans un notebook déclaré comme Java\");\n",
    "// ==> ça marche !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-01T20:01+0000",
     "start_time": "2021-02-01T20:01:41.000Z"
    }
   },
   "outputs": [
    {
     "ename": "EvalException",
     "evalue": "Undefined cell magic 'java'",
     "output_type": "error",
     "traceback": [
      "\u001b[1m\u001b[31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1m\u001b[31mio.github.spencerpark.jupyter.kernel.magic.registry.UndefinedMagicException: Undefined cell magic 'java'\u001b[0m",
      "\u001b[1m\u001b[31m\tat io.github.spencerpark.jupyter.kernel.magic.registry.Magics.applyCellMagic(Magics.java:34)\u001b[0m",
      "\u001b[1m\u001b[31m\tat io.github.spencerpark.ijava.runtime.Magics.cellMagic(Magics.java:31)\u001b[0m",
      "\u001b[1m\u001b[31m\tat .(#14:1)\u001b[0m"
     ]
    }
   ],
   "source": [
    "%%java\n",
    "System.out.println(\"Test d'une cellule en Java dans un notebook déclaré comme Python\");\n",
    "// cela ne marche pas !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-01T20:02+0000",
     "start_time": "2021-02-01T20:02:06.642Z"
    }
   },
   "outputs": [
    {
     "ename": "CompilationException",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1m\u001b[30m|   \u001b[1m\u001b[30m\u001b[0m\u001b[1m\u001b[30m\u001b[41m\u001b[0m\u001b[1m\u001b[30m# On peut aussi écrire une cellule Python qui fait appel à une commande Bash\u001b[0m",
      "\u001b[1m\u001b[31millegal character: '#'\u001b[0m",
      "",
      "\u001b[1m\u001b[30m|   \u001b[1m\u001b[30m# On peut aussi\u001b[0m\u001b[1m\u001b[30m\u001b[41m\u001b[0m\u001b[1m\u001b[30m écrire une cellule Python qui fait appel à une commande Bash\u001b[0m",
      "\u001b[1m\u001b[31m';' expected\u001b[0m",
      ""
     ]
    }
   ],
   "source": [
    "# On peut aussi écrire une cellule Python qui fait appel à une commande Bash\n",
    "!echo 'System.out.println(\"\\nTest d\\'une ligne de Java dans un notebook déclaré comme Python\");' | jshell -q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-01T20:02+0000",
     "start_time": "2021-02-01T20:02:29.874Z"
    }
   },
   "outputs": [
    {
     "ename": "EvalException",
     "evalue": "Undefined cell magic 'bash'",
     "output_type": "error",
     "traceback": [
      "\u001b[1m\u001b[31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1m\u001b[31mio.github.spencerpark.jupyter.kernel.magic.registry.UndefinedMagicException: Undefined cell magic 'bash'\u001b[0m",
      "\u001b[1m\u001b[31m\tat io.github.spencerpark.jupyter.kernel.magic.registry.Magics.applyCellMagic(Magics.java:34)\u001b[0m",
      "\u001b[1m\u001b[31m\tat io.github.spencerpark.ijava.runtime.Magics.cellMagic(Magics.java:31)\u001b[0m",
      "\u001b[1m\u001b[31m\tat .(#19:1)\u001b[0m"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "# voir une commande Bash directement !\n",
    "# mais uniquement depuis un notebook Python\n",
    "echo 'System.out.println(\"\\nok\");' | jshell -q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Réponse en Bash (par [Lilian Besson](https://perso.crans.org/besson/)) ?\n",
    "\n",
    "En bidouillant avec des programmes en lignes de commandes tels que `cal` et des grep on devrait pouvoir s'en sortir facilement. Ça tient même en une ligne !\n",
    "\n",
    "- Date et heure : 01/02/2021, 21h16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:27.276606Z",
     "start_time": "2021-02-02T22:32:27.229076Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    Février 2021      \n",
      "lu  1  8 15 22      \n",
      "ma  2  9 16 23      \n",
      "me  3 10 17 24      \n",
      "je  4 11 18 25      \n",
      "ve  5 12 19 26      \n",
      "sa  6 13 20 27      \n",
      "di  7 14 21 28      \n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "ncal February 2021"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En recherchant exactement cette chaîne \"lu  1  8 15 22\" et en excluant 29 des lignes trouvées, on obtient la réponse :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:28.868027Z",
     "start_time": "2021-02-02T22:32:28.747959Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n",
      "real 0,102\tuser 0,195\tsys 0,048\tpcpu 239,02\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "time for ((annee=1994; annee<=2077; annee+=1)); do\n",
    "    ncal February $annee \\\n",
    "    | grep 'lu  1  8 15 22' \\\n",
    "    | grep -v 29;\n",
    "done \\\n",
    "| wc -l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:30.559177Z",
     "start_time": "2021-02-02T22:32:30.439738Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "for ((annee=1994; annee<=2077; annee+=1)); do ncal February $annee | grep 'lu  1  8 15 22' | grep -v 29; done | wc -l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Réponse en Python (par [Lilian Besson](https://perso.crans.org/besson/))\n",
    "\n",
    "Avec le module [calendar](https://www.geeksforgeeks.org/python-calendar-module/) on pourrait faire comme en Bash : imprimer les calendriers, et rechercher des chaînes particulières... mais ce n'est pas très propre.\n",
    "Essayons avec ce même module mais en écrivant une solution fonctionnelle !\n",
    "\n",
    "- Date et heure : lundi 01 février, 21h40."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:18.978229Z",
     "start_time": "2021-02-02T22:32:18.971900Z"
    }
   },
   "outputs": [],
   "source": [
    "import calendar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:19.758451Z",
     "start_time": "2021-02-02T22:32:19.753637Z"
    }
   },
   "outputs": [],
   "source": [
    "def filter_annee(annee):\n",
    "    return (\n",
    "        set(calendar.Calendar(annee).itermonthdays2(annee, 2))\n",
    "        & {(1,0), (28, 6), (29, 0)}\n",
    "    ) == {(1, 0), (28, 6)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:20.362363Z",
     "start_time": "2021-02-02T22:32:20.338630Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, True, False)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "filter_annee(2020), filter_annee(2021), filter_annee(2022)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et donc on a juste à compter les années, de 1994 à 2077 inclus, qui ne sont pas des années bissextiles et qui satisfont le filtre :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:21.191296Z",
     "start_time": "2021-02-02T22:32:21.177816Z"
    },
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.51 ms, sys: 1.62 ms, total: 3.13 ms\n",
      "Wall time: 3.02 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "len(list(filter(filter_annee, ( annee\n",
    "        for annee in range(1994, 2077 + 1)\n",
    "        # if not calendar.isleap(annee) # en fait c'est inutile\n",
    "    )\n",
    ")))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Réponse en OCaml (par [Lilian Besson](https://perso.crans.org/besson/))\n",
    "\n",
    "En installant et utilisant [ocaml-calendar](https://github.com/ocaml-community/calendar) cela ne doit pas être trop compliqué. On peut s'inspirer du code Java ci-dessus, qui a une approche purement fonctionnelle.\n",
    "\n",
    "- Date et heure : ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:31:31.700200Z",
     "start_time": "2021-02-02T22:31:31.565Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : int = 0\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* cette cellule est en OCaml *)\n",
    "(* avec la solution en Bash et Sys.command... *)\n",
    "Sys.command \"bash -c \\\"for ((annee=1994; annee<=2077; annee+=1)); do ncal February \\\\$annee | grep 'lu  1  8 15 22' | grep -v 29; done | wc -l\\\"\";;\n",
    "(* mais ça ne compte pas ! *)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On pourrait faire en calculant manuellement les quantièmes du 01/01/YYYY pour YYYY entre 1994 et 2077."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:31:33.287000Z",
     "start_time": "2021-02-02T22:31:33.278Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type day = int\n",
       "and dayofweek = int\n",
       "and month = int\n",
       "and year = int\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type date = { d : day; q : dayofweek; m : month; y : year; }\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type day = int\n",
    "and  dayofweek = int\n",
    "and  month = int\n",
    "and  year = int\n",
    ";;\n",
    "type date = { d: day; q: dayofweek; m: month; y: year };;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:31:34.399900Z",
     "start_time": "2021-02-02T22:31:34.386Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_not_bissextil : year -> bool = <fun>\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let is_not_bissextil (y: year) : bool =\n",
    "    (y mod 4 != 0) || (y mod 100 == 0 && y mod 400 != 0)\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:31:35.323200Z",
     "start_time": "2021-02-02T22:31:35.312Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : bool = true\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : bool = false\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : bool = true\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_not_bissextil 2019;;\n",
    "is_not_bissextil 2020;;\n",
    "is_not_bissextil 2021;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:31:56.506500Z",
     "start_time": "2021-02-02T22:31:56.494Z"
    }
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "File \"[7]\", line 3, characters 4-133:\n",
      "Warning 8: this pattern-matching is not exhaustive.\n",
      "Here is an example of a case that is not matched:\n",
      "0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "val length_of_month : month -> year -> int = <fun>\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* Ce Warning:8 est volontaire ! *)\n",
    "let length_of_month (m: month) (y: year) : int =\n",
    "    match m with\n",
    "    | 4 | 6 | 9 | 11 -> 30\n",
    "    | 1 | 3 | 5 | 7 | 8 | 10 | 12 -> 31\n",
    "    | 2 -> if is_not_bissextil(y) then 28 else 29\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:31:58.046800Z",
     "start_time": "2021-02-02T22:31:58.036Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 28\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 29\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 28\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length_of_month 2 2019;; (* 28 *)\n",
    "length_of_month 2 2020;; (* 29 *)\n",
    "length_of_month 2 2021;; (* 28 *)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:31:59.615800Z",
     "start_time": "2021-02-02T22:31:59.607Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val next_dayofweek : dayofweek -> int = <fun>\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let next_dayofweek (q: dayofweek) =\n",
    "    1 + (q mod 7)\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:00.417800Z",
     "start_time": "2021-02-02T22:32:00.403Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 2\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 3\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 4\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 5\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 6\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 7\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 1\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next_dayofweek 1;; (* Monday => Tuesday *)\n",
    "next_dayofweek 2;; (* Tuesday => Wednesday *)\n",
    "next_dayofweek 3;; (* Wednesday => Thursday *)\n",
    "next_dayofweek 4;; (* Thursday => Friday *)\n",
    "next_dayofweek 5;; (* Friday => Saturday *)\n",
    "next_dayofweek 6;; (* Saturday => Sunday *)\n",
    "next_dayofweek 7;; (* Sunday => Monday *)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:01.877900Z",
     "start_time": "2021-02-02T22:32:01.861Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val next_day : date -> date = <fun>\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let next_day { d; q; m; y } =\n",
    "    let l_o_m = length_of_month m y in\n",
    "    if (d = 31 && m = 12) then\n",
    "        { d=1; q=next_dayofweek q; m=1; y=y+1 }\n",
    "    else begin\n",
    "        if (d = l_o_m) then\n",
    "            { d=1; q=next_dayofweek q; m=m+1; y=y }\n",
    "        else\n",
    "            { d=d+1; q=next_dayofweek q; m=m; y=y }\n",
    "    end\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:03.159400Z",
     "start_time": "2021-02-02T22:32:03.145Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val iterate : int -> ('a -> 'a) -> 'a -> 'a = <fun>\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec iterate (n: int) (f: 'a -> 'a) (x: 'a): 'a =\n",
    "    match n with\n",
    "    | 0 -> x (* identité *)\n",
    "    | 1 -> f(x)\n",
    "    | n -> iterate (n-1) f (f(x))\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:04.186700Z",
     "start_time": "2021-02-02T22:32:04.170Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val start_of_next_month : date -> date = <fun>\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let start_of_next_month { d; q; m; y } =\n",
    "    let l_o_m = length_of_month m y in\n",
    "    let nb_nextday = l_o_m - d + 1 in\n",
    "    if (m = 12) then\n",
    "        { d=1; q=iterate nb_nextday next_dayofweek q; m=1; y=y+1 }\n",
    "    else\n",
    "        { d=1; q=iterate nb_nextday next_dayofweek q; m=m+1; y=y }\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Je vais tricher un peu et utiliser la connaissance que le 01/01/1994 est un samedi :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:05.419100Z",
     "start_time": "2021-02-02T22:32:05.413Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sa  1  8 15 22 29   \n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : int = 0\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sys.command \"ncal Jan 1994 | grep '  1'\";"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:06.197100Z",
     "start_time": "2021-02-02T22:32:06.161Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val start_date : date = {d = 1; q = 6; m = 1; y = 1994}\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val end_date : date = {d = 31; q = 0; m = 1; y = 2077}\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val aujourdhui : date ref = {contents = {d = 1; q = 6; m = 1; y = 1994}}\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val nb_bon_mois_fevrier : int ref = {contents = 0}\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val aujourdhuis : '_a list ref = {contents = []}\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val solutions : '_a list ref = {contents = []}\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 9\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let start_date = {d=1; q=6; m=1; y=1994};; (* 01/01/1994 était un samedi, q=6 *)\n",
    "(* let start_date = {d=1; q=3; m=1; y=2020};; (* 01/01/2020 était un mercredi, q=3 *) *)\n",
    "\n",
    "let end_date   = {d=31; q=0; m=1; y=2077};; (* on se fiche du quantième ici ! *)\n",
    "(* let end_date   = {d=31; q=0; m=1; y=2021};; (* on se fiche du quantième ici ! *) *)\n",
    "\n",
    "let aujourdhui = ref start_date;; (* les champs sont pas mutables, go reference *)\n",
    "let nb_bon_mois_fevrier = ref 0;;\n",
    "let aujourdhuis = ref [];;\n",
    "let solutions = ref [];;\n",
    "\n",
    "while (!aujourdhui.y <= end_date.y || !aujourdhui.y <= end_date.y || !aujourdhui.y <= end_date.y) do\n",
    "    if (!aujourdhui.d = 1 && !aujourdhui.m = 2) then begin\n",
    "        (* on a un début de février, est-ce qu'il vérifie les critères ? *)\n",
    "        let date_suivante    = iterate 27 next_day !aujourdhui in\n",
    "        let date_suivante_p1 = next_day date_suivante in\n",
    "        if (\n",
    "               date_suivante.d = 28 && date_suivante.m = 2\n",
    "            && date_suivante_p1.d != 29 (* année pas bisextile *)\n",
    "            && !aujourdhui.q = 1        (* mois février commence par lundi *)\n",
    "        ) then begin\n",
    "            solutions := !aujourdhui :: !solutions;\n",
    "            incr nb_bon_mois_fevrier;\n",
    "        end;\n",
    "    end;\n",
    "    (* on a un jour quelconque, on avance d'un mois *)\n",
    "    aujourdhui := start_of_next_month !aujourdhui;\n",
    "    aujourdhuis := !aujourdhui :: !aujourdhuis;\n",
    "done;;\n",
    "\n",
    "!nb_bon_mois_fevrier;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut même facilement vérifier les années qui ont été trouvées, et donc vérifier que 2021 est dedans.\n",
    "\n",
    "J'ai aussi eu la chance d'observer ce phénomène en 1999 (mais je ne me souviens pas l'avoir remarqué, j'avais 6 ans !) et en 2010 (et je me *souviens* l'avoir remarqué, normal j'étais en MP* et on adore ce genre de coïncidences)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:32:08.028200Z",
     "start_time": "2021-02-02T22:32:08.008Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : date list =\n",
       "[{d = 1; q = 1; m = 2; y = 2077}; {d = 1; q = 1; m = 2; y = 2066};\n",
       " {d = 1; q = 1; m = 2; y = 2055}; {d = 1; q = 1; m = 2; y = 2049};\n",
       " {d = 1; q = 1; m = 2; y = 2038}; {d = 1; q = 1; m = 2; y = 2027};\n",
       " {d = 1; q = 1; m = 2; y = 2021}; {d = 1; q = 1; m = 2; y = 2010};\n",
       " {d = 1; q = 1; m = 2; y = 1999}]\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "!solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(le kernel [ocaml-jupyter](https://github.com/akabe/ocaml-jupyter/) est génial, mais [plante un peu](https://github.com/akabe/ocaml-jupyter/issues/160), j'ai galéré à écrire cette douzaine de cellules sans devoir relancer Jupyter plusieurs fois... bug signalé, résolution en cours...)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Réponse en Rust (par [un de mes élèves (Théo Degioanni)](https://github.com/Moxinilian))\n",
    "\n",
    "Le code Rust proposé peut être executé depuis le [bac à sable Rust]() :\n",
    "https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2ab9c57e9d114a344363e21f9493bf22\n",
    "\n",
    "Mais on peut aussi utiliser [le kernel Jupyter proposé par le projet evcxr de Google](https://github.com/google/evcxr/blob/master/evcxr_jupyter/README.md) :\n",
    "\n",
    "1. il faut installer Rust, je n'avais jamais fait j'ai donc suivi [rustup.rs](https://rustup.rs/) le site officiel de présentation de l'installation de Rust ;\n",
    "2. puis j'ai suivi les explications pour installer le kernel [sur GitHub @google/evcxr](https://github.com/google/evcxr/blob/master/evcxr_jupyter/README.md) ;\n",
    "3. puis j'ai écrit cette cellule ci-dessous, j'ai changé le Noyau en Rust, et j'ai exécuté la cellule ;\n",
    "4. notez qu'avec l'extension [jupyter nbextension ExecuteTime](https://jupyter-contrib-nbextensions.readthedocs.io/en/latest/nbextensions/execute_time/readme.html), j'ai vu que la première cellule avait pris quasiment 10 secondes... mais je pense qu'il s'agit du temps d'installer et de compilation du module `chrono` (je ne suis pas encore très familier avec Rust).\n",
    "   - Les exécutions suivantes prennent environ 300ms pour la définition (y a-t-il recompilation même si le texte ne change pas ?) de la fonction ;\n",
    "   - Et environ 700ms pour l'exécution. C'est bien plus lent que les 35 ms de mon code naïf en OCaml (qui est juste interprété et pas compilé), que les 10 ms de Python, ou les 100 ms de Bash. Mais pas grave !\n",
    "\n",
    "- Date et heure : lundi 01/02/2021, 21h20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:38:05.810898875+00:00",
     "start_time": "2021-02-02T22:38:05.492Z"
    }
   },
   "outputs": [],
   "source": [
    ":dep chrono = \"0.4\"\n",
    "use chrono::TimeZone;\n",
    "use chrono::Datelike;\n",
    "\n",
    "fn main() {\n",
    "    let n = (1994..=2077)\n",
    "        .filter(|n| chrono::Utc.ymd_opt(*n, 2, 29) == chrono::LocalResult::None)\n",
    "        .map(|n| chrono::Utc.ymd(n, 2, 1))\n",
    "        .filter(|t| t.weekday() == chrono::Weekday::Mon)\n",
    "        .count();\n",
    "        \n",
    "    println!(\"{}\", n);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-02T22:38:07.564614803+00:00",
     "start_time": "2021-02-02T22:38:06.871Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "()"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On trouve la même réponse que les autres langages, parfait."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Conclusion\n",
    "\n",
    "En utilisant bien la librairie standard de votre langage favori, ce n'est pas très difficile.\n",
    "\n",
    "Curieux de plus ? Voir [cet article](https://www.truthorfiction.com/february-2017-4-day-first-time-823-years/) et [celui là](https://www.tecatips.com/february-happens-every-823-years/) qui expliquent que ce n'est pas si rare (comme vous venez de le calculer), contrairement à une rumeur qui semble circuler régulièrement sur les réseaux sociaux. La rumeur dirait que ces mois de février n'arrivent qu'une fois tous les 823 ans...\n",
    "\n",
    "## Challenge (pour les futurs agrégs maths)\n",
    "\n",
    "**Bonus spécial** : si quelqu'un trouve un calcul de maths qui permette de trouver la réponse \"à la main\", ou en tous cas sans un programme informatique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Une première réponse\n",
    "\n",
    "- Date : lundi 01/02/2021, 22h32\n",
    "\n",
    "> - Sur 28 ans, chaque année on décale d'un jour, sauf les bissextiles où c'est de 2 (car 365%7 = 1).\n",
    "> - Donc il y a 7 années bissextiles et comme 7 et 4 sont premiers entre eux, autant de chacun des jours, donc 3 cas (une des commençant lundi ayant 5 lundis).\n",
    "> - Aucunes années non bissextiles en 4 entre 94 et 77\n",
    "> - On a donc 83 années = 3x28-1.\n",
    "> - 2020-28 = 1992 donc 1993 (l'année manquante pour tomber rond) n'était pas un cas de lundi.\n",
    "> - Le nombre de cas semblable est donc de 3x3 = **9** (réponse correcte)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> C'est tout pour ce notebook, [allez voir ce projet](https://github.com/Naereen/notebooks/) pour d'autres notebooks."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "287.183px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}