Table of Contents

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

Challenge :

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 :

Mini challenge algorithmique pour les passionnés en manque de petits exercices de code : (optionnel) 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.

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).

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.


Réponse en Java (par un de mes élèves de L3 SIF)

Oui, on peut utiliser Java dans des notebooks ! Voir ce poste de blogue, et ce kernel IJava. Moi je trouve ça chouette, et je m'en suis servi en INF1 au semestre dernier

Il en avait trouvé 9.

Si les cellules précédentes ne s'exécute pas, a priori c'est normal : ce notebook est déclaré en Python ! Il faudrait utiliser une des astuces suivantes, mais flemme.


Réponse en Bash (par Lilian Besson) ?

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 !

En recherchant exactement cette chaîne "lu 1 8 15 22" et en excluant 29 des lignes trouvées, on obtient la réponse :


Réponse en Python (par Lilian Besson)

Avec le module calendar on pourrait faire comme en Bash : imprimer les calendriers, et rechercher des chaînes particulières... mais ce n'est pas très propre. Essayons avec ce même module mais en écrivant une solution fonctionnelle !

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 :


Réponse en OCaml (par Lilian Besson)

En installant et utilisant ocaml-calendar cela ne doit pas être trop compliqué. On peut s'inspirer du code Java ci-dessus, qui a une approche purement fonctionnelle.

On pourrait faire en calculant manuellement les quantièmes du 01/01/YYYY pour YYYY entre 1994 et 2077.

Je vais tricher un peu et utiliser la connaissance que le 01/01/1994 est un samedi :

On peut même facilement vérifier les années qui ont été trouvées, et donc vérifier que 2021 est dedans.

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).

(le kernel ocaml-jupyter est génial, mais plante un peu, j'ai galéré à écrire cette douzaine de cellules sans devoir relancer Jupyter plusieurs fois... bug signalé, résolution en cours...)


Réponse en Rust (par un de mes élèves (Théo Degioanni))

Le code Rust proposé peut être executé depuis le bac à sable Rust : https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2ab9c57e9d114a344363e21f9493bf22

Mais on peut aussi utiliser le kernel Jupyter proposé par le projet evcxr de Google :

  1. il faut installer Rust, je n'avais jamais fait j'ai donc suivi rustup.rs le site officiel de présentation de l'installation de Rust ;
  2. puis j'ai suivi les explications pour installer le kernel sur GitHub @google/evcxr ;
  3. puis j'ai écrit cette cellule ci-dessous, j'ai changé le Noyau en Rust, et j'ai exécuté la cellule ;
  4. notez qu'avec l'extension jupyter nbextension ExecuteTime, 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).
    • 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 ;
    • 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 !

On trouve la même réponse que les autres langages, parfait.


Conclusion

En utilisant bien la librairie standard de votre langage favori, ce n'est pas très difficile.

Curieux de plus ? Voir cet article et celui là 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...

Challenge (pour les futurs agrégs maths)

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.

Une première réponse

  • Sur 28 ans, chaque année on décale d'un jour, sauf les bissextiles où c'est de 2 (car 365%7 = 1).
  • 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).
  • Aucunes années non bissextiles en 4 entre 94 et 77
  • On a donc 83 années = 3x28-1.
  • 2020-28 = 1992 donc 1993 (l'année manquante pour tomber rond) n'était pas un cas de lundi.
  • Le nombre de cas semblable est donc de 3x3 = 9 (réponse correcte).

C'est tout pour ce notebook, allez voir ce projet pour d'autres notebooks.