(* ----------------------------------------------------------------------- inf201-ZBIRI-EDDAHBI-ZENG.ml : cr Projet "Dames Chinoises" Nael ZBIRI <[email protected]> \ Ayman EDDAHBI <[email protected]> \ Anthony Zeng <[email protected]> / ----------------------------------------------------------------------- *) (* --------------------- Question Ecrite -------------------- *) (*Q1 1 - Ce seront les cases situées sur la branche en bas du plateau. 2 - Ce seront les cases situées sur la branche en haut du plateau. 3 - Ce seront les cases situées sur la branche en haut à gauche du plateau. 4 - Ce sera la case tout en haut du plateau. 5 - Cases en dehors en dessous du plateau. 6 - Les cases qui ne sont pas dans les trois branches inférieures. *) (* ------------------- Fin Question Ecrite ------------------ *) (* ------------------------ Debut code ------------------------ *) type dimension = int;; (*restreint aux entiers strictement positifs*) type case = int * int * int;; (*restreint au triplet tels (i,j,k) tels que i+j+k=0*) type vecteur = int * int * int;; (*restreint au triplet tels (i,j,k) tels que i+j+k=0*) type couleur = Vert | Jaune | Rouge | Noir | Bleu | Marron (*Les couleurs des joueurs*) | Libre | Code of string (*une chaine restreinte a 3 caracteres*);; type case_coloree = case * couleur;; type configuration = case_coloree list * couleur list * dimension;; (*sans case libre*) type coup = Du of case * case | Sm of case list;; (* SPÉCIFICATIONS DE indice_valide Profil indice_valide : int -> dimension -> bool Sémantique indice_valide x dim renvoie vrai si l'indice x est valide dans le contexte de la dimension dim. *) let indice_valide (x:int) (dim:dimension) : bool = x >= -2*dim && x<= 2*dim;; (* SPÉCIFICATIONS DE est_case Profil est_case : case -> bool Sémantiques est_case (i,j,k) renvoie vrai si le triplet (i,j,k) correspond à une case valide, c'est-à-dire telle que i + j + k = 0. *) let est_case ((i,j,k):case):bool= (i+j+k=0);; (*Q2*) (* SPÉCIFICATIONS DE est_dans_losange Profil est_dans_losange : case -> dimension -> bool Sémantiques est_dans_losange (c, dim) renvoie vrai si la case c est à l'intérieur du losange défini par la dimension dim. *) let est_dans_losange ((i, j, k) : case) (dim:dimension): bool = indice_valide i dim && (j>= -dim && j<=dim) && (k>= -dim && k<=dim) && est_case (i,j,k) ;; (*Q3*) (* SPÉCIFICATIONS DE est_dans_etoile Profil est_dans_etoile : case -> dimension -> bool Sémantiques est_dans_etoile (c, dim) renvoie vrai si la case c est à l'intérieur de l'étoile définie par la dimension dim. *) let est_dans_etoile ((i, j, k) : case) (dim:dimension) : bool = (*Si la case est dans le triangle de la pointe haute, pointe bas gauche et pointe bas droite*) (((i>= -dim && i<=0) && (j>= -dim && j<=2*dim) && (k>= -dim && k<=2*dim)) || ((i> 0 && i<=2*dim) && (j>= -dim && j<=dim) && (k>= -dim && k<=dim))) (*Si la case est dans le triangle de la pointe bas, pointe haute gauche et pointe haute droite*) || ((((i>= -2*dim && i<=0) && (j>= -dim && j<=dim) && (k>= -dim && k<=dim))) || ((i>0 && i<=dim) && (j>= -2*dim && j<=dim) && (k>= -2*dim && k<=dim))) ;; (*Q4*) (* SPÉCIFICATIONS DE tourner_case Profil tourner_case : int -> case -> case Sémantiques tourner_case m c effectue une rotation de la case c d'un nombre de 60 degrés équivalent à m sixièmes de tour. *) let rec tourner_case(m:int)((i, j, k):case):case = match m with | 1 -> (-k), (-i), (-j) (* répeter tant qu'il y a des sixièmes de tours restants *) | m -> let c1 = (-k, -i, -j) in tourner_case (m-1) c1 ;; (*Q5*) (* SPÉCIFICATIONS DE translate Profil translate : case -> vecteur -> case Sémantiques translate c v effectue une translation de la case c par le vecteur v. *) let translate((c1, c2, c3):case)((v1, v2, v3):vecteur):case = (* Application de l'algorithme d'une translation de vecteurs *) (c1 + v1), (c2 + v2), (c3 + v3) ;; (*Q6*) (* SPÉCIFICATIONS DE diff_case Profil diff_case : case -> case -> vecteur Sémantiques diff_case c1 c2 renvoie le vecteur différence entre les cases c1 et c2. *) let diff_case((i1, j1, k1):case)((i2, j2, k2):case):vecteur = (* Algorithme *) (i1 - i2), (j1 - j2), (k1 - k2) ;; (*Q7*) (* SPÉCIFICATIONS DE sont_cases_voisines Profil sont_cases_voisines : case -> case -> bool Sémantiques sont_cases_voisines c1 c2 renvoie vrai si les cases c1 et c2 sont voisines. *) let sont_cases_voisines (c1:case)(c2:case):bool = ((diff_case c1 c2) = (-1, 1, 0)) || ((diff_case c1 c2) = (-1, 0, 1)) || ((diff_case c1 c2) = (0, -1, 1)) || ((diff_case c1 c2) = (1, -1, 0)) || ((diff_case c1 c2) = (1, 0, -1)) || ((diff_case c1 c2) = (0, 1, -1)) ;; (*Q8*) (* SPÉCIFICATIONS DE calcul_pivot Profil calcul_pivot : case -> case -> case option Sémantiques calcul_pivot c1 c2 renvoie le point médian entre les cases c1 et c2 si elles sont alignées horizontalement, verticalement ou diagonalement ; sinon, renvoie None. *) let calcul_pivot((i1, j1, k1):case)((i2, j2, k2):case):case option = if i1 = i2 then (* cas : si les deux cases sont sur la même ligne *) let i3 = i1 and j3 = if j1 < j2 then j1 + (j2 - j1) / 2 else j1 - (j1 - j2) / 2 and k3 = if k1 < k2 then k1 + (k2 - k1) / 2 else k1 - (k1 - k2) / 2 in Some (i3, j3, k3) else if j1 = j2 then (* cas : si les deux cases sont sur la même diagonale d'indice j*) let i3 = if i1 < i2 then i1 + (i2 - i1) / 2 else i1 - (i1 - i2) /2 and j3 = j2 and k3 = if k1 < k2 then k1 + (k2 - k1) / 2 else 1 - (k1 - k2) / 2 in Some (i3, j3, k3) (* case : si les deux cases sont sur la même diagonale d'indice i *) else if k1 = k2 then let i3 = if i1 < i2 then i1 + (i2 - i1) / 2 else i1 - (i1 - i2) /2 and j3 = if j1 < j2 then j1 + (j2 - j1) / 2 else j1 - (j1 - j2) / 2 and k3 = k1 in Some (i3, j3, k3) (* None sera retournée si il n'y a pas possibilité d'un pivot *) else None ;; (*Q9*) (* SPÉCIFICATIONS DE vec_et_dist Profil vec_et_dist : case -> case -> vecteur * int Sémantiques vec_et_dist c1 c2 renvoie le vecteur direction et la distance entre les cases c1 et c2. *) let vec_et_dist((i1, j1, k1):case)((i2, j2, k2):case):vecteur*int = let sign (a:int)(b:int):int = if a = b then 0 else if a < b then -1 else 1 (* fonction locale calculant la valeur absolue d'un entier *) and abs (a:int) = if a>0 then a else -a (* la distance *) in let distance = if i1 = i2 then abs (j2 - j1) else if j2 = j1 || k2 = k1 then abs (i2 - i1) else -1 (* cas d'erreur *) in ((sign i1 i2), (sign j1 j2), (sign k1 k2)), distance ;; (*Q10*) (* SPÉCIFICATIONS DE tourner_liste Profil tourner_liste : 'a list -> 'a list Sémantique tourner_liste liste effectue une rotation circulaire vers la gauche de la liste passée en paramètre. *) let rec tourner_liste (liste: 'a list): 'a list = match liste with | [] -> [] | deb :: fin -> fin @ [deb] ;; let rec der_liste (liste: 'a list) : 'a list = match liste with | [] -> [] | [fin] -> [fin] | _ :: fin -> der_liste fin ;; (*Q11*) (* SPÉCIFICATIONS DE remplir_segment Profil remplir_segment : int -> case -> case list Sémantique remplir_segment a c génère une liste de a cases consécutives suivant la direction verticale descendant à partir de la case c. *) let rec remplir_segment (a:int) (c:case) : case list = match a with | 0 -> [] | 1 -> [c] | _ -> let i, j, k = c in (i, j, k) :: remplir_segment (a-1) (i, j+1, k-1) ;; (*Q12*) (* SPÉCIFICATIONS DE remplir_triangle_bas Profil remplir_triangle_bas : int -> case -> case list Sémantique remplir_triangle_bas a c génère une liste de cases formant un triangle descendant avec a niveaux à partir de la case c. *) let rec remplir_triangle_bas(a:int)(c:case):case list = match a with | 0 -> [] | 1 -> [c] | _ -> let i, j, k = c in (remplir_segment (a)(i,j,k))@(remplir_triangle_bas (a-1) (i-1,j+1,k)) ;; (*Q13*) (* SPÉCIFICATIONS DE remplir_triangle_haut Profil remplir_triangle_haut : int -> case -> case list Sémantique remplir_triangle_haut a c génère une liste de cases formant un triangle ascendant avec a niveaux à partir de la case c. *) let rec remplir_triangle_haut(a:int)(c:case) :case list = match a with | 0 -> [] | 1 -> [c] | _ -> let i, j, k = c in (remplir_segment (a)(i,j,k))@(remplir_triangle_haut (a-1) (i+1,j,k-1)) ;; (*Q14*) (* SPÉCIFICATIONS DE colorie Profil colorie : couleur -> case list -> case_coloree list Sémantique colorie couleur lc colore chaque case dans la liste lc avec la couleur spécifiée, produisant une liste de cases colorées. *) let rec colorie (coul:couleur)(lc: case list): case_coloree list= match lc with | [] -> [] | [solo] -> [(solo,coul)] | pr::fin -> (pr,coul)::colorie coul fin ;; (*Q15*) (* SPÉCIFICATIONS DE tourner_config Profil tourner_config : configuration -> configuration Sémantique tourner_config (cl, coul, dim) effectue une rotation des cases de la configuration cl en fonction du nombre de joueurs spécifié par coul. *) let rec tourner_config (cl, coul, dim : configuration) : configuration = match List.length coul with | 1 -> let cl_tourne1 = List.fold_left (fun acc x -> let (c,color) = x in ((tourner_case 6 c),color)::acc) [] cl in (cl_tourne1,tourner_liste coul, dim) | 2 -> let cl_tourne2 = List.fold_left (fun acc x -> let (c,color) = x in ((tourner_case 3 c),color)::acc) [] cl in (cl_tourne2,tourner_liste coul, dim) | 3 -> let cl_tourne3 = List.fold_left (fun acc x -> let (c,color) = x in ((tourner_case 2 c),color)::acc) [] cl in (cl_tourne3,tourner_liste coul, dim) | 6 -> let cl_tourne6 = List.fold_left (fun acc x -> let (c,color) = x in ((tourner_case 1 c),color)::acc) [] cl in (cl_tourne6,tourner_liste coul, dim) | _ -> (cl, coul, dim) ;; (*Q16*) (* SPÉCIFICATIONS DE remplir_init Profil remplir_init : couleur list -> dimension -> configuration Sémantique remplir_init liste_joueurs dim génère une configuration initiale en remplissant le plateau selon les règles du jeu, avec les joueurs de la liste_joueurs et la dimension dim. *) let remplir_init (liste_joueurs : couleur list) (dim : dimension) : configuration = let plateau_vide = ([], liste_joueurs, dim) in let rec remplir_par_joueur (config : configuration) (joueurs : couleur list) : configuration = match joueurs with | [] -> config | joueur::reste_joueurs -> let cases_a_colorier = remplir_triangle_haut dim (0,0,0) in let cases_coloriees = colorie joueur cases_a_colorier in let (cl, _, _) = config in let nouvelle_config = (cl @ cases_coloriees, liste_joueurs, dim) in let config_tournee = tourner_config nouvelle_config in remplir_par_joueur config_tournee reste_joueurs in remplir_par_joueur plateau_vide liste_joueurs ;; (*Q17*) (* SPÉCIFICATIONS DE quelle_couleur Profil quelle_couleur : case -> configuration -> couleur Sémantique quelle_couleur cl config renvoie la couleur associée à la case cl dans la configuration spécifiée, ou Libre si la case est vide. *) let associe (a:'a) (l:('a*'b) list) (defaut:'b):'b = defaut;; let quelle_couleur(cl:case)(config:configuration):couleur= let a,b,c = config in associe cl a Libre ;; (*Q18*) (* SPÉCIFICATIONS DE supprime_dans_config Profil supprime_dans_config : configuration -> case -> configuration Sémantique supprime_dans_config (cl, coul, dim) c supprime la case c de la configuration spécifiée, renvoyant la configuration résultante. *) let rec supprime_dans_config (cl, coul, dim : configuration) (c : case) : configuration = match cl with | [] -> [], coul, dim | (case1,color1) :: fin -> if case1 = c then supprime_dans_config (fin, coul, dim) c else let (reste,coul1,dim1) = supprime_dans_config (fin,coul,dim) c in (case1,color1) :: reste,coul1,dim1 ;; (*Q19*) (* SPÉCIFICATIONS DE est_voisine Profil est_voisine : case -> case -> bool Sémantique est_voisine c1 c2 renvoie vrai si les cases c1 et c2 sont voisines, c'est-à-dire si elles diffèrent d'au plus une unité dans chaque coordonnée. *) let est_voisine (c1 : case) (c2 : case) : bool = let i1, j1, k1 = c1 in let i2, j2, k2 = c2 in abs(i1 - i2) <= 1 && abs(j1 - j2) <= 1 && abs(k1 - k2) <= 1 (* SPÉCIFICATIONS DE est_present_dans_liste Profil est_present_dans_liste : case -> case_coloree list -> bool Sémantique est_present_dans_liste c liste renvoie vrai si la case c est présente dans la liste de cases colorées. *) let rec est_present_dans_liste (c : case) (liste : case_coloree list) : bool = match liste with | [] -> false | (case, _) :: reste -> case = c || est_present_dans_liste c reste (* SPÉCIFICATIONS DE est_coup_valide Profil est_coup_valide : configuration -> coup -> bool Sémantique est_coup_valide conf coup renvoie vrai si le coup est valide dans la configuration spécifiée, c'est-à-dire si les cases du coup sont présentes dans la configuration, sont voisines et la case d'arrivée est libre. *) let est_coup_valide (conf:configuration) (coup:coup) : bool = let cl, _, _ = conf in match coup with | Du (c1, c2) -> let presente_c1 = est_present_dans_liste c1 cl in let presente_c2 = est_present_dans_liste c2 cl in let voisines = est_voisine c1 c2 in let libre_c2 = not presente_c2 in presente_c1 && presente_c2 && voisines && libre_c2 | _ -> failwith "saut multiple non implémenter" ;; (*Q20*) (* SPÉCIFICATIONS DE appliquer_coup Profil appliquer_coup : configuration -> coup -> configuration Sémantique appliquer_coup conf cp applique le coup cp à la configuration conf, renvoyant la configuration résultante. *) let appliquer_coup (conf:configuration)(cp:coup):configuration = let cl, coul, dim = conf in match cp with | Du (c1, c2) -> let nouvelle_cl, _, _ = supprime_dans_config (cl, coul, dim) c1 in (c2, Libre) :: nouvelle_cl, coul, dim | _ -> failwith "Coup non valide" ;; (*Q21*) (* SPÉCIFICATIONS DE mettre_a_jour_configuration Profil mettre_a_jour_configuration : configuration -> coup -> configuration Sémantique mettre_a_jour_configuration conf cp met à jour la configuration conf en appliquant le coup cp, renvoyant la configuration résultante. Si le coup n'est pas valide, une exception est levée. *) let mettre_a_jour_configuration(conf:configuration)(cp:coup):configuration= if est_coup_valide conf cp then appliquer_coup conf cp else failwith "Coup non valide" ;; (*Q22*) (* SPÉCIFICATIONS DE est_libre_seg Profil est-libre-seg : case -> case -> configuration-> bool Sémantique (est-libre-seg c1 c2 conf) retourne true si toutes les cases entre c1 et c2 sont libres, c1 et c2 sont supposées alignées *) let rec est_libre_seg (c1:case)(c2:case)(conf:configuration):bool= match c1,c2 with | (i1,j1,k1),(i2,j2,k2) when (i1,j1,k1) = (i2,j2,k2) -> true | (i1,j1,k1),(i2,j2,k2) -> let (i,j,k) = c1 in if (quelle_couleur (i,j,k) conf) = Libre then est_libre_seg (translate (i,j,k) (diff_case (i,j,k) (i2,j2,k2))) (c2) conf else false ;; (*Q23*) (* SPÉCIFICATIONS DE est_saut Profil est_saut : case -> case -> configuration-> bool Sémantique (est_saut c1 c2) conf retourne true si si le déplacement de c1 à c2 est un saut valide. *) let est_saut (c1:case)(c2:case)(conf:configuration):bool= let (i1,j1,k1) = c1 and (i2,j2,k2) = c2 in if (quelle_couleur (i1,j1,k1) conf) = Libre then false else if (quelle_couleur (i2,j2,k2) conf) <> Libre then false else if not (sont_cases_voisines c1 c2) then false else if (est_libre_seg c1 c2 conf) then false else true ;; (*Q24*) (* SPÉCIFICATIONS DE est_saut_multiple Profil est_saut_multiple : case list -> configuration -> bool Sémantique (est_saut cl conf) retourne true si le déplacement de la première case à la dernière de cl est un saut multiple valide passant par toutes les cases intermédiaires. *) let rec est_saut_multiple (cl:case list)(conf:configuration):bool= match cl with | [] -> false | [c] -> false | [c1;c2] -> est_saut c1 c2 conf | c1::c2::c3 -> if est_saut c1 c2 conf then est_saut_multiple (c2::c3) conf else false ;; (*Q25 à faire*) (*Q26*) (* SPÉCIFICATIONS DE score Profil score: configuration -> int Sémantique (score conf) est le score du joueur protagoniste dans la configuration conf. *) let score (conf:configuration):int= let (cl, coul, dim) = conf in let rec score_aux (cl:case_coloree list)(coul:couleur):int= match cl with | [] -> 0 | (c,couleur)::fin -> if couleur = coul then 1 + score_aux fin coul else score_aux fin coul in let (_,coul1) = List.hd cl in score_aux cl coul1 ;; (* SPÉCIFICATIONS DE score_gagnant Profil score_gagnant: dimension -> int Sémantique (score_gagnant d) score de la configuration gagnante pour le protagoniste dans une configuration de dimension d, c’est à dire quand tous ses pions sont dans le camp Nord *) let score_gagnant (d:dimension):int= let rec score_gagnant_aux (d:dimension)(i:int)(j:int)(k:int):int= match d with | 0 -> 0 | _ -> if i = 0 then 1 + score_gagnant_aux (d-1) (i-1) (j+1) (k) else 1 + score_gagnant_aux (d-1) (i) (j+1) (k-1) in score_gagnant_aux d 0 0 0 ;; (*Q27*) (* SPÉCIFICATIONS DE gagne Profil gagne : configuration -> bool Sémantique (gagne conf) retourne true si conf est gagnante pour le protagoniste *) let gagne (conf:configuration):bool= let (_,coul,_) = conf in let score_actuel = score conf in let score_max = score_gagnant (List.length coul) in score_actuel = score_max ;; (*Q28*) (* SPÉCIFICATIONS DE est_partie Profil est_partie : configuration -> coup list -> couleur Sémantique (est_partie conf cl) est la couleur du gagnant ou Libre si la partie est nulle *) let est_partie (conf:configuration)(cl:coup list):couleur= let rec est_partie_aux (conf:configuration)(cl:coup list)(coul:couleur):couleur= match cl with | [] -> Libre | coup::fin -> let nouvelle_conf = mettre_a_jour_configuration conf coup in if gagne nouvelle_conf then coul else let (cl1,coul1,dim1) = tourner_config nouvelle_conf in est_partie_aux (cl1,coul1,dim1) fin (List.hd coul1) in let (cl1,coul1,dim1) = tourner_config conf in est_partie_aux (cl1,coul1,dim1) cl (List.hd coul1) ;; (*Q29*) (* SPÉCIFICATIONS DE coup_possibles Profil coup_possibles : configuration -> case -> (case*coup) list Sémantique (coup_possibles conf c) est la liste des couples (c',cp) tels que 𝑐′ est accessible depuis 𝑐 en effectuant le coup 𝑐𝑝. *) let coup_possibles (conf:configuration)(c:case):(case*coup) list= let (cl,_,_) = conf in let rec coup_possibles_aux (cl:case_coloree list)(c:case):(case*coup) list= match cl with | [] -> [] | (c1,coul)::fin -> if est_saut c c1 conf then (c1,Du(c,c1))::coup_possibles_aux fin c else coup_possibles_aux fin c in coup_possibles_aux cl c ;; (*Q30 à faire*) (*AFFICHAGE (fonctionne si les fonctions au dessus sont remplies)*) (*transfo transforme des coordonnees cartesiennes (x,y) en coordonnees de case (i,j,k)*) let transfo x y = (y, (x-y)/2,(-x-y)/2);; let couleur2string (coul:couleur):string = match coul with | Libre -> " . " | Code s -> s | Vert -> " V " | Jaune -> " J " | Rouge -> " R " | Noir -> " N " | Bleu -> " B " | Marron -> " M " ;; let rec affiche_ligne (n:int) (m:int) (config:configuration) : string = let (lcc,_,dim)=config in if m = (4 * dim) + 1 then " " (*fin de ligne*) else let c = transfo m n in if not ((n+m) mod 2 = 0) || not (est_dans_etoile c dim) then (*ceci est une inter-case (case inutile d'un damier) ou hors de l'etoile*) " "^ affiche_ligne n (m + 1) config else (*ceci est une case ou bien en dehors du plateau*) (couleur2string (associe c lcc Libre)) ^ affiche_ligne n (m + 1) config ;; let affiche (config:configuration):unit = let (_,_,dim)=config in let rec affiche_aux n = if n = - 2 * dim - 1 then () else begin print_endline (affiche_ligne n (-4*dim-1) config); print_endline "\n"; affiche_aux (n - 1) end in affiche_aux (2*dim+1) ;; let conf_1=([((0,0,0),Jaune)],[Jaune],2);; affiche conf_1;; let conf_reggae=([((0,-1,1),Vert);((0,0,0),Jaune);((0,1,-1),Rouge)],[Vert;Jaune;Rouge],3);; affiche conf_reggae;; let conf_vide=([],[],2);; affiche conf_vide;; (*A essayer apres avoir fait remplir_init affiche (remplir_init [Code "Ali";Code "Bob";Code "Jim"] 3);; *)
Write, Run & Share OCaml code online using OneCompiler's OCaml online compiler for free. It's one of the robust, feature-rich online compilers for OCaml language, running on the latest version 4. Getting started with the OneCompiler's OCaml compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as OCaml
. OneCompiler also has reference programs, where you can look for the sampleprograms and start coding.
OCaml is general purpose programming language with more importance to safety and expressiveness. With it's advanced type system, it helps to catch the mistakes in an efficient way. Hence this is used to develop applications/environments where a single mistake can cost millions and speed matters. It has good community support and rich set of development tools and libraries.
Classification | Data types |
---|---|
Basic data types | integers, floating point numbers, booleans, characters, strings |
Sophisticated data types | tuples, arrays, lists, sets, hash tables, queues, stacks, data streams |
OCaml allows users to define new data types.
Variable is a name given to the storage area in order to manipulate them in our programs.
let varible-names = value
If is performed when you need to choose expression based on a boolean-condition.
if boolean-condition then (* code if condition is true *)
if boolean-condition then (* code if condition is true*) else (* code if condition is false*)
While is used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while boolean-condition do
(* code *)
done
For loop is used to iterate a set of statements for specific number of items.
for var = start-value to end-value do
(* code *)
done
for var = start-value downto end-value do
(* code *)
done