DS 2 (MP2I 2022-2023) — Planifier sa route

Devoir surveillé · MP2I · 2022-2023 · partie III du DS 2 (4 h au total)

Cours : Types inductifs

Autres parties : I–II. Correction de programmes · IV. Codeglyphes

Planifier sa route - OCaml

Pour votre route, vous devrez passer d'île en île. Afin de passer à une île suivante, il est nécessaire d'attendre une certaine durée pour que votre log2pos, une sorte de boussole, puisse vous indiquer la direction de la prochaine île.

On vous a fourni une int list contenant les temps qu'il faut attendre pour chaque île.

Question 13

Écrire une fonction de type :

temps_total : int list -> int

qui détermine le temps total qu'il faudra attendre.

Corrigé

let rec temps_total l =
  match l with
  | [] -> 0
  | t::q -> t + temps_total q

Question 14

Écrire une fonction de type :

plus_dattente : int list -> int

qui détermine l'indice dans la liste de l'île où il faudra attendre le plus longtemps.

Corrigé

Cette fonction est plutôt délicate à écrire en récursif car on a besoin de beaucoup de variables temporaires qui deviennent des paramètres de fonctions auxiliaires.

let plus_dattente l =
  let rec aux l max_courant ind_max_courant indice_actuel =
    match l with
    | [] -> ind_max_courant
    | t::q ->
      if t > max_courant
      then aux q t indice_actuel (indice_actuel+1)
      else aux q max_courant ind_max_courant (indice_actuel+1)
  in match l with
  | [] -> failwith "Vide"
  | t::q -> aux q t 0 1

Une bonne manière de programmer une telle fonction est de penser à une version impérative et à transformer l'itération en une fonction : valeurs avant \(\rightarrow\) valeurs après.

Ainsi, en Python, on aurait pu écrire :

def plus_dattente(l):
    max_courant = l[0]
    ind_max_courant = 0

    for indice_actuel in range(1, len(l)):
        t = l[indice_actuel]
        if t > max_courant:
            max_courant = t
            ind_max_courant = indice_actuel

    return ind_max_courant

Il se trouve que le temps à attendre n'est qu'une approximation grossière de votre traversée car il faut prendre en compte le trajet entre chaque île.

On considère alors le type suivant :

type donnee_nav =
    Trajet of int | Ile of int

Votre route est alors une liste alternant entre valeurs Trajet et valeurs Ile.

Question 15

Écrire une fonction de type :

alternante : donnee_nav list -> bool

qui indique si la liste alterne ainsi.

Corrigé

On peut écrire cette fonction de plusieurs manières. Avancer en regardant deux éléments est sûrement le plus simple.

let rec alternante l =
  match l with
  | [] | [_] -> true
  | Trajet _ :: Ile v :: q -> alternante (Ile v :: q)
  | Ile _ :: Trajet v :: q -> alternante (Trajet v :: q)
  | _ -> false

On pouvait aussi faire deux fonctions auxiliaires mutuellement récursives permettant de distinguer les cas où on commence avec une île ou un trajet.

let alternante l =
  let rec ile_alt l =
    match l with
    | [] -> true
    | Trajet _ :: q -> false
    | Ile _ :: q -> trajet_alt q
  and trajet_alt l =
    match l with
    | [] -> true
    | Ile _ :: q -> false
    | Trajet _ :: q -> ile_alt q
  in ile_alt l || trajet_alt l

Question 16

Écrire une fonction de type :

ile_depart_fin : donnee_nav list -> bool

qui indique si la liste commence et finit par une Ile.

Corrigé

let ile_depart_fin l =
  let rec dernier_ile l =
    match l with
    | [] -> false
    | [Ile _] -> true
    | _::q -> dernier_ile q in
  match l with
  | Ile _ :: _ -> dernier_ile l
  | _ -> false

Question 17

Écrire une fonction de type :

temps_total_nav : donnee_nav list -> int

qui détermine le temps total, trajet et attente, de la route.

Corrigé

let rec temps_total_nav l =
  match l with
  | [] -> 0
  | Trajet t :: q | Ile t :: q ->
    t + temps_total_nav q

Il se trouve que votre route n'est pas forcément linéaire : il peut y avoir des choix entre plusieurs îles.

On considère alors le type suivant :

type route =
  | Finie
  | Simple of donnee_nav * route
  | Double of (donnee_nav * route)
              * (donnee_nav * route)

Un couple du type donnee_nav * route représente ainsi un bout du parcours, soit d'une île, soit d'un trajet, et on continue la route. On a alors une route qui est soit finie, soit simple quand il n'y a pas de choix, soit double quand on a le choix entre deux parcours.

Par exemple, la valeur :

Simple(Ile 3,
  Double(
    (Trajet 3,
      Simple(Ile 2,
        Double((Trajet 2, Simple(Ile 1, Finie)),
          (Trajet 3, Simple(Ile 2, Finie))))),
    (Trajet 1, Simple(Ile 5, Finie))))

représente la route suivante :

La route représentée : îles dans les cercles, numéros de trajet sur les arêtes.

Question 18

Écrire une fonction de type

temps_total_route : route -> int

qui renvoie la somme des temps de l'ensemble de la route.

Corrigé

let rec temps_total_route l =
  match l with
  | Finie -> 0
  | Simple(Trajet t, q)
  | Simple(Ile t, q) ->
    t + temps_total_route q
  | Double(r1,r2) ->
    let aux c =
      match c with
      | (Ile t, r)
      | (Trajet t, r) -> t + temps_total_route r
    in aux r1 + aux r2

Question 19

Écrire une fonction de type

alternant_route : route -> bool

qui détermine si une route alterne toujours comme sur l'exemple, entre île et trajet.

Corrigé

Ici, la version avec récursivité croisée semble plus intéressante.

let alternant_route l =
  let rec alt_ile l =
    match l with
    | Finie -> true
    | Simple(Ile _, r) -> alt_trajet r
    | Double( (Ile _, r1), (Ile _, r2) ) ->
      alt_trajet r1 && alt_trajet r2
    | _ -> false
  and alt_trajet l =
    match l with
    | Finie -> true
    | Simple(Trajet _, r) -> alt_ile r
    | Double( (Trajet _, r1), (Trajet _, r2) ) ->
      alt_ile r1 && alt_ile r2
    | _ -> false
  in alt_ile l || alt_trajet l

Question 20

Écrire une fonction de type

temps_min_route : route -> int

qui renvoie le temps du chemin le plus court dans cette route.

Indication : sur l'exemple, on constate que le chemin le plus court est donné par le chemin du bas Ile 3 - Trajet 1 - Ile 5 pour une durée de 9.

Corrigé

let rec temps_min_route l =
  match l with
  | Finie -> 0
  | Simple(Trajet t, q)
  | Simple(Ile t, q) ->
    t + temps_min_route q
  | Double(r1,r2) ->
    let aux c =
      match c with
      | (Ile t, r)
      | (Trajet t, r) -> t + temps_min_route r
    in min (aux r1) (aux r2)

Question 21

Écrire une fonction de type

est_chemin : route -> donnee_nav list -> bool

qui vérifie qu'un chemin donné sous la forme d'une liste de données de navigation est dans la route en partant du départ et en finissant complètement.

Indication : dans la route précédente, on peut constater que [Ile 3; Trajet 3; Ile 2; Trajet 2; Ile 1] est un chemin de la route, mais pas [Ile 3; Trajet 1] (pas finie) ou [Ile 3; Trajet 4] (données non présentes).

Corrigé

let rec est_chemin r l =
  match r, l with
  | Finie, [] -> true
  | Simple(Ile a, r'), Ile b::q when a = b
    -> est_chemin r' q
  | Simple(Trajet a, r'), Trajet b::q when a = b
    -> est_chemin r' q
  | Double((d1, r1), (d2, r2)), d::q ->
    (d1 = d && est_chemin r1 q) || (d2 = d && est_chemin r2 q)
  | _ -> false

Note : dans le cas Double, il faut bien essayer les deux branches (avec un ||) : si elles commencent par la même donnée, le chemin peut se trouver dans la seconde.

Question 22

Écrire une fonction de type

chemins : route -> donnee_nav list list

qui renvoie la liste de tous les chemins présents dans la route.

Indication : pour l'exemple, cette fonction va renvoyer :

[[Ile 3; Trajet 3; Ile 2; Trajet 2; Ile 1];
 [Ile 3; Trajet 3; Ile 2; Trajet 3; Ile 2];
 [Ile 3; Trajet 1; Ile 5]]

Corrigé

let rec ajoute x l =
  match l with
  | [] -> []
  | t::q -> (x::t) :: ajoute x q

let rec chemins r =
  match r with
  | Finie -> [ [] ]
  | Simple(v,r') -> ajoute v (chemins r')
  | Double((v1,r1),(v2,r2)) ->
    ajoute v1 (chemins r1)
    @ ajoute v2 (chemins r2)