TP5

Tous les documents du cours sont autorisés. Vous avez, bien évidemment, le droit de consulter la documentation OCaml. Néanmoins, ce TP étant à faire seul-e, il est naturellement interdit d'aller sur les réseaux sociaux ou de poser des questions sur des sites d'entraide tels que developpez.com ou stackoverflow.com.

Ce TP noté évalue vos connaissances et votre compréhension d'OCaml.

Ce sujet est long pour deux heures, on ne s'attend pas à ce que vous finissiez tout (si vous y arrivez, bravo !), donc faites ce que vous pouvez et faites-le bien.

Dans tout ce sujet, lorsqu'une fonction récursive est utilisée, il sera valorisé d'utiliser de la récursion terminale : vous obtiendrez tout de même une partie des points si votre fonction est correcte sans récursion terminale, mais pas l'intégralité.

Il vous est recommandé d'utiliser l'interpréteur pour vérifier les types des fonctions que vous écrivez, ainsi que pour les tester sur des exemples. De la même manière, ils vous est recommandé d'essayer de compiler les fichiers avant le rendu, afin de vérifier qu'aucun problème syntaxe ne s'y est introduit.

Il vous est recommandé d'indiquer en commentaire dans vos fichiers .ml avant chaque question le numéro de celle à laquelle vous répondez, afin de faciliter la lecture de votre production (et ce pour vous, et pour le correcteur, qui sera ainsi dans de meilleures dispositions !).

Le TP est à rendre à la fin de la séance. Chaque exercice précise le nom du fichier .ml à rendre, veuillez nommer vos fichiers en conséquence. Vous mettrez vos fichiers sources (donc uniquement les .ml) dans un répertoire nom_prenom dans une archive au format tgz de la forme nom_prenom.tgz

Vous enverrez cette archive au chargé de TP du groupe auquel vous appartenez. Les adresses mails sont les suivantes :

1. Factorisation

Nom du fichier à rendre: factorisation.ml

On veut écrire un programme qui fournit à un entier sa décomposition en facteurs premiers.

Une première version

  1. Écrire une fonction shortestDivider : int -> int qui renvoie à un entier n>1 son plus petit diviseur supérieur ou égal à 2. Pour cela, on testera successivement si les entiers de 2 à n divisent n. Le premier diviseur est retourné, c'est au plus n. On rappelle que a mod b renvoie le reste de la division entière de a par b, par exemple 10 mod 3 = 1.

  2. Écrire une fonction reverse : 'a list -> 'a list qui renvoie à une liste l sa liste miroir, en inversant tous les éléments. Par exemple, reverse [1;2;3] = [3; 2; 1]. On notera que cette fonction existe déjà sous OCaml avec List.rev, on demande de recoder cette fonction sans utiliser List.rev.

  3. Écrire une fonction factorSlow : int -> int list qui renvoie à un entier n la liste l de ses diviseurs dans l'ordre croissant, avec leur ordre de multiplicité. Ainsi, n doit etre le produit des éléments de l, et tous les éléments de l sont des nombres premiers. Pour coder la fonction factorSlow : int -> int list , on utilisera le fait qu'une fois un diviseur trouvé d, on se ramène à factoriser n/d et que shortestDivider renvoie nécessairement un nombre premier. Par exemple:

    # factorSlow 24;;
    - : int list = [2; 2; 2; 3]

    # factorSlow 1300;;
    - : int list = [2; 2; 5; 5; 13]

    # factorSlow 100000001;;
    - : int list = [17; 5882353]

    # factorSlow 1000000001;;
    - : int list = [7; 11; 13; 19; 52579]

Version améliorée

Plusieurs améliorations permettent d'accélérer l'algorithme de factorisation précédemment décrit.

  1. Écrire une fonction shortestDividerUpper : int -> int -> int , tel que shortestDividerUpper n d renvoie à un entier n>1 son plus petit diviseur supérieur ou égal à d>1. Pour accélérer la résolution, on traitera le cas d=2 séparément, et on testera les divisions par les entiers impairs compris entre d et la racine carrée de n. Si aucun diviseur n'est trouvé sur ces tests, cela signifie que la fonction doit renvoyer n.

  2. Écrire une fonction factorFaster : int -> int list qui renvoie à un entier n la liste ordonnée l de ses diviseurs, avec leur ordre de multiplicité. Pour accélérer la résolution de factorSlow, on utilisera le fait qu'une fois un diviseur trouvé d, on se ramène à factoriser n/d et qu'on cherche alors pour la suite des diviseurs supérieurs ou égaux à d.

2. Tournois

L'histoire d'un type

Nom du fichier à rendre: tournoi.ml

On veut écrire un programme qui permet de calculer les points d'un tournoi un peu particulier : le tournoi est composé d'un certain nombre d'épreuves prises parmi les épreuves du pentathlon moderne: la course, le tir, l'équitation, la natation et l'escrime.

  1. Écrire le type constructeur epreuve correspondant aux cinq possibilités d'épreuve: Course, Tir, Equitation, Natation et Escrime.
  2. Pour chaque épreuve de ce tournoi, un score entier est donné à chaque joueur en premier lieu, puis sera ensuite pondéré lors du calcul final.

  3. Donnez un type epreuve_score formant la paire epreuve et score entier
  4. Puis, donnez le type enregistrement joueur comportant le champ id correspondant au numéro de dossard, et le champ competition contenant une liste d' epreuve_score.
  5. enfin, donnez le type ponderation , un tuple comprenant un int pour chacune des épreuves possibles.

Les points

On a maintenant les ingrédients pour pouvoir faire notre comptage des points, mais dans un premier temps, il faut enregistrer ces points:

  1. Créez une fonction qui, étant donnée un identifiant de joueur et une épreuve, demande a la console le nombre de points qu'a fait le joueur de l'identifiant a cette épreuve particulière: points_epreuve : epreuve -> int -> int (On rappelle que la fonction read_int: unit -> int permet de récupérer un nombre dans la console)
  2. Créez une fonction new_competition : epreuve list -> int -> epreuve_score list prenant en argument une liste d'épreuve et un identifiant et retournant la liste des épreuves assortie des points fait par le joueur correspondant à l'identifiant
  3. Créez une fonction new_joueur : epreuve list -> int -> joueur créant un nouveau joueur.
  4. Donnez une fonction new_ponderation : unit -> ponderation demandant la pondération de chacune des épreuves possibles et retournant le tuple correspondant. Maintenant que les points peuvent être rentrés, on va calculer la somme:
  5. Donnez la fonction score_pondere : epreuve_score -> ponderation -> int qui prend une épreuve et la pondération de chaque épreuve, et renvoie le score pondéré
  6. Donnez la fonction points_comp : list epreuve_score -> ponderation -> int qui, prend une liste d'épreuve d'un joueur et la pondération et renvoie la somme des points. (Rappel : n'oubliez pas que la récursion terminale est valorisée !)

Le tournois

On veut maintenant pouvoir retourner automatiquement le gagnant entre deux joueurs.

  1. Donnez la fonction match_2 : joueur -> joueur -> ponderation -> unit qui prend deux compétiteurs en entrée, ainsi que la pondération des épreuves, et écrit sur la console le numéro du gagnant (celui qui a le plus de points) avec son score.
  2. On veut maintenant créer un tournoi avec plus de personnes, mais avec des éliminations de certains participant avant la fin du tournoi :

  3. Créez une fonction resultat_partiel : epreuve_score list -> ponderation -> int qui fait la somme des scores pondérés jusqu'à la fin de la liste ou jusqu'à l'épreuve qui arrive à la position max. (Rappel : n'oubliez pas que la récursion terminale est valorisée !)
  4. Enfin, donnez la fonction tournoi_a_4 : epreuve list -> unit qui en prenant une liste d'épreuves, demande la pondération, créez 4 joueurs en demandant leur score et dans un premier temps regarde lequel des deux premiers joueurs est devant après deux épreuves, puis regarde lequel des deux autres joueurs est devant après le même nombre d'épreuves, et enfin regarde parmi ces deux finalistes lequel gagne le match sur toutes les épreuves

3. Palindrome

Nom du fichier à rendre: palindrome.ml

Un palindrome désigne un texte ou une suite d’éléments dont l’ordre reste le même qu’on le lise de gauche à droite ou de droite à gauche, comme dans les listes «"de" "la" "sa" "la" "de" » ou encore « 1 2 3 2 1» (ref).

Une première version

Une technique pour vérifier qu’une liste est un palindrome est de vérifier que l’élément de tête est de queue sont identiques, puis de supprimer l’élément de tête et de queue et de vérifier que la liste résultante est un palindrome.

  1. Implémentez une fonction get_last de type 'a list -> 'a option qui renvoie le dernier élément d’une liste (None si la liste est vide).
  2. Implémentez une fonction remove_last de type 'a list -> 'a list qui prend en paramètre une liste et renvoie la même liste avec le dernier élément retirer.
  3. Implémentez une fonction is_palindrome_1 de type 'a list -> bool qui renvoie true si la liste en paramètre est un palindrome (false sinon) et utilise les fonctions get_last et remove_last.
  4. Testez votre fonction sur les listes «"de" "la" "sa" "la" "de"» et «1 2 3 2 3». Conclure sur le bon fonctionnement de la fonctions (une réponse en commentaire).

Une seconde version

L’implémentation précédente utilise deux fonctions get_last et remove_last. Il peut être intéressant de fusionner ces deux fonctions en une seule fonction get_remove_last de type 'a list -> 'a option * 'a list qui renvoie le dernier élément d’une liste et la liste sans son dernier élément.

  1. Implémentez la fonction get_remove_last.
  2. Implémentez une fonction is_palindrome_2 de type 'a list -> bool qui renvoie true si la liste en paramètre est un palindrome (false sinon) et utilise la fonction get_remove_last.
  3. Testez votre fonction sur les listes «"de" "la" "sa" "la" "de" » et « 1 2 3 2 3». Conclure sur le bon fonctionnement de la fonctions (une réponse en commentaire).

Une troisième version

Une alternative pour vérifier qu’une liste est un palindrome est de vérifier qu’elle est identique à son inverse (la liste renversée).

  1. Implémentez une fonction list_equal de type 'a list -> 'a list -> bool qui vérifie que deux listes sont identiques.
  2. En utilisant la fonction List.rev (pour renverser une liste), implémentez une fonction is_palindrome_3 de type 'a list -> bool qui renvoie true si la liste en paramètre est un palindrome et utilise la fonction list_equal.
  3. Testez votre fonction sur les listes «"de" "la" "sa" "la" "de" » et « 1 2 3 2 3». Conclure sur le bon fonctionnement de la fonctions (une réponse en commentaire).

4. Tours de Hanoï

Nom du fichier à rendre: hanoi.ml

Les tours de Hanoï sont un jeu de réflexion consistant à déplacer des disques de diamètres différents d'une tour de « départ » à une tour d'« arrivée » en passant par une tour « intermédiaire », et ceci en un minimum de coups, tout en respectant les règles suivantes :

On suppose que cette dernière règle est également respectée dans la configuration de départ.

Dans cet exercice, on se propose de calculer une séquence de coups optimale permettant de déplacer les disques de la tour de départ à la tour d'arrivée. Chaque tour est représentée par une liste d'entier, la valeur d'un entier représentant la taille d'un disque.

Préliminaires

  1. Définir un type enregistrement hanoi à trois champs t1, t2 et t3, tous trois de type int list, représentant les trois tours du jeu.

  2. Écrire une fonction check : int list -> bool, qui renvoie un booléen indiquant si la liste passée en paramètre représente un tour valide. Les entiers de la liste représentant les tailles des disques, il faut s'assurer que pour deux entiers consécutifs de la liste, le premier est strictement plus petit que le second.

  3. En utilisant la fonction check précédemment définie et la fonction de la bibliothèque standard assert : bool -> unit permettant de s'assurer de la validité d'une assertion, écrire une fonction make : int list -> int list -> int list -> hanoi telle que make t1 t2 t3 vérifie que t1, t2 et t3 sont bien des tours valides, et renvoie le jeu composé de celles-ci.

Affichage

  1. En utilisant la fonction hd_tl_opt : 'a list -> 'a option * 'a list donnée ci-dessous et la fonction de la bibliothèque standard List.rev : 'a list -> 'a list permettant de retourner une liste, écrire une fonction combine : int list -> int list -> int list -> (int option * int option * int option) list telle que:

    On pourra passer par une fonction auxiliaire et/ou un accumulateur.

    let hd_tl_opt ls = match ls with [] -> None, [] | x :: ls -> Some x, ls

  2. En utilisant la fonction print_option : int option -> unit donnée ci-dessous, écrire une fonction print_list : (int option * int option * int option) list -> unit telle que print_list [(None, None, Some 3); (Some 1, None, Some 5); (Some 4, Some 2, Some 6)] affiche:

               3
       1       5
       4   2   6

    let print_option opt = match opt with None -> Printf.printf "    " | Some i -> Printf.printf "%4i" i

  3. En utilisant les fonctions combine et print_list précédemment définies, écrire une fonction print_hanoi : hanoi -> unit telle que print_hanoi { t1 = [1; 4]; t2 = [2]; t3 = [3; 5; 6] } affiche:

               3
       1       5
       4   2   6
    ============

Résolution

  1. En utilisant la fonction move : 'a list -> 'a list -> 'a list * 'a list définie ci-dessous et la fonction make précédemment définie, écrire une fonction play : hanoi -> int -> int telle que play hanoi src dst renvoie le jeu hanoi dans lequel le disque au sommet de la tour src a été déplacé au sommet de la tour dst. Si src ou dst ne sont pas des indices de tour valides, le jeu est renvoyé inchangé.

    let move t1 t2 = match t1 with [] -> t1, t2 | x :: t1 -> t1, x :: t2

  2. En utilisant la fonction play précédemment définie, écrire une fonction compute : int -> int -> int -> int -> hanoi list telle que compute n src dst aux renvoie la liste des séquences de jeu de Hanoi permettant de déplacer une tour de n disque de la position src à la position dst en passant par la position intermédiaire aux. On passera par une fonction auxiliaire faisant intervenir un accumulateur, et on pourra utiliser la fonction de la bibliothèque standard List.hd : 'a list -> 'a pour récupérer la tête de la liste des séquences de jeu de Hanoï.

    Pour ce faire, on remarquera que déplacer une tour de n disques de src vers dst en passant par aux c'est:

    1. déplacer les n-1 premiers disques de src vers aux
    2. déplacer le disque restant de src vers dst
    3. déplacer les n-1 disques de aux vers dst

  3. Utiliser les fonctions précédemment définies pour afficher les séquences de jeu permettant de passer de { t1 = [1; 2; 3; 4]; t2 = []; t3 = [] } à { t1 = []; t2 = []; t3 = [1; 2; 3; 4] }.