Organiser un tour de garde

21 juillet 2004

Ce programme fournit une liste aléatoire de personnes qui devront assurer chaque jour une garde (que l'on pense à des médecins, des pharmaciens etc.).

Cette liste doit respecter les contraintes suivantes :
- une même personne ne peut pas être de garde deux jours de suite, sauf le week-end ;
- la même personne assure la garde le samedi et le dimanche qui suit ;
- une même personne ne peut pas être de garde un même jour de la semaine deux semaines de suite.

Pour paramétrer le programme, il faut choisir  l’année considérée et indiquer la liste des partenaires. La liste doit être saisie sous le format suivant :

Le nombre des partenaires doit être supérieur à quatre. Le millésime de l'année doit être supérieur à 1999.

Le résultat est édité sous la forme d'une liste comportant une ligne par jour :

Pour conserver et utiliser ce résultat, faire un copier-coller vers Word ou vers Excel.

Le programme fournit aussi le décompte des jours de garde par personne pour chaque semestre :

Le tirage étant réalisé sans remise, le nombre des jours de garde dans un semestre est à peu près le même pour chaque partenaire, les écarts étant dus à un effet d'arrondi.

Chaque exécution du programme fournit une liste différente. Si nécessaire, on peut ainsi choisir entre plusieurs listes.

*  *

La première partie du programme concerne le traitement du calendrier : elle distingue les années bissextiles et attribue un jour de semaine à chaque date. Excel fait cela automatiquement ... programmer soi-même ce que sait déjà faire un progiciel, c'est un bon exercice.

Pour réaliser le tirage sans remise, j'ai dû écrire ma première fonction "tail-recursive" : cela m'a donné pas mal de tintouin, mais j'y ai beaucoup appris. La fonction tirage n'est en effet pas des plus simples :

(define tirage
 (lambda (nombre-à-tirer sac cumul sac-)
  (cond ((= nombre-à-tirer 0) cumul)
        ((= (length sac-) 0) (tirage (length dates) sac-1er-semestre '() sac-1er-semestre))
        (else (let* ( (numero (random (length sac-)))
                      (individu (cond ((and (< nombre-à-tirer (length dates))(eq? (joursemaine nombre-à-tirer) 'samedi)) (car cumul))
                                (else (list-ref sac- numero))))
                      (newsac (cond ((= nombre-à-tirer (- semestre1 1)) (append sac-2nd-semestre (remove individu sac)))
                              (else (remove individu sac))))
                      (newsac- (cond ((> (length cumul) 7) (removeall (caddr (cdddr cumul)) (removeall individu newsac)))
                               (else (removeall individu newsac)))) )
      (tirage (- nombre-à-tirer 1) newsac (cons individu cumul) newsac-))))))

Voici le commentaire détaillé de cette fonction :

(define tirage
    (lambda (n sac cumul sac-)

1) nombre-à-tirer est le nombre de tirages à effectuer, soit ici le nombre de jours de l'année (length dates). Après un premier tirage, on itèrera sur (- nombre-à-tirer 1).

2) sac est le "sac" dans lequel on fait le tirage sans remise : après chaque tirage, l'individu tiré est ôté du sac. Cela donne newsac, sur lequel on itérera.

3) cumul est l'empilage "tail-récursif" des résultats des tirages. Au début il est vide et il se remplit progressivement. On va donc commencer par '(), puis itérer par (cons individu cumul).

4) sac- est le sac dans lequel on tire effectivement : c'est newsac dont on a ôté les individus qui, pour respecter les contraintes ci-dessus, ne doivent pas être tirés.

(cond ((= nombre-à-tirer 0) cumul)

Lorsque l'on a tiré n fois, cumul est complet. C'est lui qui sera le résultat de la fonction.

((= (length sac-) 0) (tirage (length dates) sac-1er-semestre '() sac-1er-semestre))

Il se peut que (= (length sac-) 0) avant que (= nombre-à-tirer 0), c'est-à-dire avant que le tirage ne soit fini : l'empilage des conditions n'est pas toujours tenable ! Cette instruction relance le tirage jusqu'à ce que l'on ait une solution.

(else (let* ( (numero (random (length sac-)))

On tire au sort un rang dans le sac où doit se faire le tirage

(individu (cond ((and (< nombre-à-tirer (length dates))(eq? (joursemaine nombre-à-tirer) 'samedi)) (car cumul))

Si le jour de semaine est un samedi, il faut que l'on tire le même individu que le jour précédent (qui était un dimanche, l'empilage se faisant selon l'ordre inverse de la chronologie).

(else (list-ref z- x))))

Si le jour de semaine n'est pas un samedi, on tire l'individu dont le rang a été au sort précédemment.

(newsac (cond ((= nombre-à-tirer (- semestre1 1)) (append sac-2nd-semestre (remove individu sac)))

A la fin du premier semestre, ou ajoute le sac du second semestre au reste du sac du premier semestre.

(else (remove individu sac))))

On ôte du sac le dernier individu tiré.

(newsac- (cond ((> (length cumul) 7) (removeall (caddr (cdddr cumul)) (removeall individu newsac)))
               (else (removeall individu newsac)))) )

On ôte de newsac tous les individus qui, en raison des contraintes, ne doivent pas être tirés. Il faut tenir compte du fait que l'on ne peut ôter l'individu tiré sept jours avant que si l'on a déjà parcouru une semaine !

(tirage (- nombre-à-tirer 1) newsac (cons individu cumul) newsac-))))))

On itère la fonction : il reste à tirer (- n 1) fois ; le nouveau sac est newsac, dont les individus tirés ont été ôtés ; le résultat du tirage précédent s'empile par (cons y c) ; enfin, ôter de newsac les individus à éviter donne newsac- dans lequel est réalisé le tirage effectif.