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.
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.
// ceci est du code Java 9 et pas Python !
// On a besoin des dépendances suivantes :
import java.util.Calendar; // pour Calendar.FEBRUARY, .YEAR, .MONDAY
import java.util.GregorianCalendar; // pour
import java.util.stream.IntStream; // pour cet IntStream
// ceci est du code Java 9 et pas Python !
IntStream.rangeClosed(1994, 2077)
//.parallel() // ce .parallel() est inutile, il y a trop peu de valeurs
.mapToObj(i -> new GregorianCalendar(i, Calendar.FEBRUARY, 1))
.filter(calendar -> !calendar.isLeapYear(calendar.get(Calendar.YEAR)))
.filter(calendar -> calendar.get(Calendar.DAY_OF_WEEK) == Calendar.MONDAY)
.count();
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.
System.out.println("Test d'une cellule en Java dans un notebook déclaré comme Java");
// ==> ça marche !
Test d'une cellule en Java dans un notebook déclaré comme Java
%%java
System.out.println("Test d'une cellule en Java dans un notebook déclaré comme Python");
// cela ne marche pas !
--------------------------------------------------------------------------- io.github.spencerpark.jupyter.kernel.magic.registry.UndefinedMagicException: Undefined cell magic 'java' at io.github.spencerpark.jupyter.kernel.magic.registry.Magics.applyCellMagic(Magics.java:34) at io.github.spencerpark.ijava.runtime.Magics.cellMagic(Magics.java:31) at .(#14:1)
# On peut aussi écrire une cellule Python qui fait appel à une commande Bash
!echo 'System.out.println("\nTest d\'une ligne de Java dans un notebook déclaré comme Python");' | jshell -q
| # On peut aussi écrire une cellule Python qui fait appel à une commande Bash illegal character: '#' | # On peut aussi écrire une cellule Python qui fait appel à une commande Bash ';' expected
%%bash
# voir une commande Bash directement !
# mais uniquement depuis un notebook Python
echo 'System.out.println("\nok");' | jshell -q
--------------------------------------------------------------------------- io.github.spencerpark.jupyter.kernel.magic.registry.UndefinedMagicException: Undefined cell magic 'bash' at io.github.spencerpark.jupyter.kernel.magic.registry.Magics.applyCellMagic(Magics.java:34) at io.github.spencerpark.ijava.runtime.Magics.cellMagic(Magics.java:31) at .(#19:1)
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 !
%%bash
ncal February 2021
Février 2021 lu 1 8 15 22 ma 2 9 16 23 me 3 10 17 24 je 4 11 18 25 ve 5 12 19 26 sa 6 13 20 27 di 7 14 21 28
En recherchant exactement cette chaîne "lu 1 8 15 22" et en excluant 29 des lignes trouvées, on obtient la réponse :
%%bash
time for ((annee=1994; annee<=2077; annee+=1)); do
ncal February $annee \
| grep 'lu 1 8 15 22' \
| grep -v 29;
done \
| wc -l
9
real 0,102 user 0,195 sys 0,048 pcpu 239,02
%%bash
for ((annee=1994; annee<=2077; annee+=1)); do ncal February $annee | grep 'lu 1 8 15 22' | grep -v 29; done | wc -l
9
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 !
import calendar
def filter_annee(annee):
return (
set(calendar.Calendar(annee).itermonthdays2(annee, 2))
& {(1,0), (28, 6), (29, 0)}
) == {(1, 0), (28, 6)}
filter_annee(2020), filter_annee(2021), filter_annee(2022)
(False, True, False)
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 :
%%time
len(list(filter(filter_annee, ( annee
for annee in range(1994, 2077 + 1)
# if not calendar.isleap(annee) # en fait c'est inutile
)
)))
CPU times: user 1.51 ms, sys: 1.62 ms, total: 3.13 ms Wall time: 3.02 ms
9
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.
(* cette cellule est en OCaml *)
(* avec la solution en Bash et Sys.command... *)
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\"";;
(* mais ça ne compte pas ! *)
9
- : int = 0
On pourrait faire en calculant manuellement les quantièmes du 01/01/YYYY pour YYYY entre 1994 et 2077.
type day = int
and dayofweek = int
and month = int
and year = int
;;
type date = { d: day; q: dayofweek; m: month; y: year };;
type day = int and dayofweek = int and month = int and year = int
type date = { d : day; q : dayofweek; m : month; y : year; }
let is_not_bissextil (y: year) : bool =
(y mod 4 != 0) || (y mod 100 == 0 && y mod 400 != 0)
;;
val is_not_bissextil : year -> bool = <fun>
is_not_bissextil 2019;;
is_not_bissextil 2020;;
is_not_bissextil 2021;;
- : bool = true
- : bool = false
- : bool = true
(* Ce Warning:8 est volontaire ! *)
let length_of_month (m: month) (y: year) : int =
match m with
| 4 | 6 | 9 | 11 -> 30
| 1 | 3 | 5 | 7 | 8 | 10 | 12 -> 31
| 2 -> if is_not_bissextil(y) then 28 else 29
;;
File "[7]", line 3, characters 4-133: Warning 8: this pattern-matching is not exhaustive. Here is an example of a case that is not matched: 0
val length_of_month : month -> year -> int = <fun>
length_of_month 2 2019;; (* 28 *)
length_of_month 2 2020;; (* 29 *)
length_of_month 2 2021;; (* 28 *)
- : int = 28
- : int = 29
- : int = 28
let next_dayofweek (q: dayofweek) =
1 + (q mod 7)
;;
val next_dayofweek : dayofweek -> int = <fun>
next_dayofweek 1;; (* Monday => Tuesday *)
next_dayofweek 2;; (* Tuesday => Wednesday *)
next_dayofweek 3;; (* Wednesday => Thursday *)
next_dayofweek 4;; (* Thursday => Friday *)
next_dayofweek 5;; (* Friday => Saturday *)
next_dayofweek 6;; (* Saturday => Sunday *)
next_dayofweek 7;; (* Sunday => Monday *)
- : int = 2
- : int = 3
- : int = 4
- : int = 5
- : int = 6
- : int = 7
- : int = 1
let next_day { d; q; m; y } =
let l_o_m = length_of_month m y in
if (d = 31 && m = 12) then
{ d=1; q=next_dayofweek q; m=1; y=y+1 }
else begin
if (d = l_o_m) then
{ d=1; q=next_dayofweek q; m=m+1; y=y }
else
{ d=d+1; q=next_dayofweek q; m=m; y=y }
end
;;
val next_day : date -> date = <fun>
let rec iterate (n: int) (f: 'a -> 'a) (x: 'a): 'a =
match n with
| 0 -> x (* identité *)
| 1 -> f(x)
| n -> iterate (n-1) f (f(x))
;;
val iterate : int -> ('a -> 'a) -> 'a -> 'a = <fun>
let start_of_next_month { d; q; m; y } =
let l_o_m = length_of_month m y in
let nb_nextday = l_o_m - d + 1 in
if (m = 12) then
{ d=1; q=iterate nb_nextday next_dayofweek q; m=1; y=y+1 }
else
{ d=1; q=iterate nb_nextday next_dayofweek q; m=m+1; y=y }
;;
val start_of_next_month : date -> date = <fun>
Je vais tricher un peu et utiliser la connaissance que le 01/01/1994 est un samedi :
Sys.command "ncal Jan 1994 | grep ' 1'";
sa 1 8 15 22 29
- : int = 0
let start_date = {d=1; q=6; m=1; y=1994};; (* 01/01/1994 était un samedi, q=6 *)
(* let start_date = {d=1; q=3; m=1; y=2020};; (* 01/01/2020 était un mercredi, q=3 *) *)
let end_date = {d=31; q=0; m=1; y=2077};; (* on se fiche du quantième ici ! *)
(* let end_date = {d=31; q=0; m=1; y=2021};; (* on se fiche du quantième ici ! *) *)
let aujourdhui = ref start_date;; (* les champs sont pas mutables, go reference *)
let nb_bon_mois_fevrier = ref 0;;
let aujourdhuis = ref [];;
let solutions = ref [];;
while (!aujourdhui.y <= end_date.y || !aujourdhui.y <= end_date.y || !aujourdhui.y <= end_date.y) do
if (!aujourdhui.d = 1 && !aujourdhui.m = 2) then begin
(* on a un début de février, est-ce qu'il vérifie les critères ? *)
let date_suivante = iterate 27 next_day !aujourdhui in
let date_suivante_p1 = next_day date_suivante in
if (
date_suivante.d = 28 && date_suivante.m = 2
&& date_suivante_p1.d != 29 (* année pas bisextile *)
&& !aujourdhui.q = 1 (* mois février commence par lundi *)
) then begin
solutions := !aujourdhui :: !solutions;
incr nb_bon_mois_fevrier;
end;
end;
(* on a un jour quelconque, on avance d'un mois *)
aujourdhui := start_of_next_month !aujourdhui;
aujourdhuis := !aujourdhui :: !aujourdhuis;
done;;
!nb_bon_mois_fevrier;;
val start_date : date = {d = 1; q = 6; m = 1; y = 1994}
val end_date : date = {d = 31; q = 0; m = 1; y = 2077}
val aujourdhui : date ref = {contents = {d = 1; q = 6; m = 1; y = 1994}}
val nb_bon_mois_fevrier : int ref = {contents = 0}
val aujourdhuis : '_a list ref = {contents = []}
val solutions : '_a list ref = {contents = []}
- : unit = ()
- : int = 9
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).
!solutions
- : date list =
[{d = 1; q = 1; m = 2; y = 2077}; {d = 1; q = 1; m = 2; y = 2066};
{d = 1; q = 1; m = 2; y = 2055}; {d = 1; q = 1; m = 2; y = 2049};
{d = 1; q = 1; m = 2; y = 2038}; {d = 1; q = 1; m = 2; y = 2027};
{d = 1; q = 1; m = 2; y = 2021}; {d = 1; q = 1; m = 2; y = 2010};
{d = 1; q = 1; m = 2; y = 1999}]
(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...)
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 :
chrono (je ne suis pas encore très familier avec Rust).:dep chrono = "0.4"
use chrono::TimeZone;
use chrono::Datelike;
fn main() {
let n = (1994..=2077)
.filter(|n| chrono::Utc.ymd_opt(*n, 2, 29) == chrono::LocalResult::None)
.map(|n| chrono::Utc.ymd(n, 2, 1))
.filter(|t| t.weekday() == chrono::Weekday::Mon)
.count();
println!("{}", n);
}
main()
9
()
On trouve la même réponse que les autres langages, parfait.
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...
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.
- 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.