Merci pythamede pour ta réponse
Citation :
je ne vois pas comment on pourrait contourner ça,...
Justement je cherche un moyen de tester tous les coloriages de plus de 6 éléments parmi 23 (voir plus) possibles, quitte à changer l'algorithme.
Citation :
Cela dit, quelqu'un qui connaît bien CAML peut peut-être t'aider à condition que tu lui donnes ton code !
Déjà posté pour l'Enigmo 126 - Triancey
Enigmo 126 : Triancey, je le remet ici :
Citation :
(*couleur = bool vect | tableau des triangles coloriés
associes =(int vect) vect | tableau des tableau des triangles associés au triangle i.*)
(*exemple*)
(*Représentation : On représente un triancey par un tableau de tableaux de 3 éléments correspondant au triangle commun au triangle i+1.
Par exemple triancey.(0) renvoie le tableau des indices des triangles commun au triangle 1.
Un coloriage sera représenté par un tableau de booléens tel que coloriage.(i) renvoie true si le triangle i+1 est colorié, false sinon
*)
let triancey = [|[|2; 10; 9|]; [|1; 3; 18|]; [|2; 4; 12|]; [|3; 5; 20|]; [|4; 6; 14|];
[|5; 7; 22|]; [|6; 8; 16|]; [|7; 9; 23|]; [|1; 8; 17|]; [|1; 11; 17|];
[|10; 12; 19|]; [|3; 11; 13|]; [|12; 14; 21|]; [|5; 13; 15|]; [|14; 16; 22|];
[|7; 15; 23|]; [|9; 10; 24|]; [|2; 19; 24|]; [|11; 18; 20|]; [|4; 19; 21|];
[|13; 20; 22|]; [|6; 15; 21|]; [|8; 16; 24|]; [|17; 23; 18|]|]
;;
(*Procédé : pour un entier n donné, on va colorier toute les partie de n triangle dans les N triangles totaux. De la, on voit si tout est colorié.*)
(*====================================================== Fonctions préliminaires - Combinatoire (inspiré ESIM 99) ======================================*)
let prem ens = match ens with
| [] -> failwith "Erreur dans prem"
| t :: q -> t;;
let sp ens = match ens with
| [] -> failwith "Erreur dans sp"
| t :: q -> q;;
let rec siem i ens = match ens with
| [] -> failwith "Erreur"
| t :: q -> if i = 1 then q else t :: (siem (i - 1) q);;
let rec ieme i ens = match ens with
| [] -> failwith "Erreur dans ieme"
| t :: q -> if i = 1 then t else ieme (i - 1) q;;
let rec ajout e lst_ens = match lst_ens with
| [] -> []
| t :: q -> (e :: t) :: (ajout e q);;
(* Determinations d'ensembles *)
let rec parties e =
if e = [] then [[]]
else let x = prem e and e_1 = sp e
in let part = parties e_1
in part @ (ajout x part);;
let rec combinaisons p e =
if p > list_length e then []
else if p = 0 then [[]]
else let x = prem e and e_1 = sp e in
combinaisons p e_1 @ (ajout x (combinaisons (p - 1) e_1))
;;
let construire_tableau p e =
vect_of_list (combinaisons p e)
;;
combinaisons 3 [1;2;3;4];;
(*Quelques fonctions de calcul*)
let rec facto n = match n with
| 1 -> 1
| x -> x * facto (x - 1)
;;
facto 5;;
let comb (i: int) (n: int) =
(facto n) / ((facto i) * (facto (n - i)))
;;
comb 3 10;;
(*====================================================== Fonctions de création des coloriages ========================================================*)
let lister n = let l = ref [] in
for i = 1 to n do l:=i::!l done;
rev !l;;
(* _ Créer la liste des parties de i élément sur les n totaux*)
let partiesDeTriangles (i:int) (n:int) = construire_tableau i (lister n);;
partiesDeTriangles 2 6;;
(*Fonctions de coloriage*)
(*Colorie les parties sélectionnées*)
let coloriageParties (i: int) (j: int) (n: int) = (*colorie la jeme partie calculée parmi les parties a i éléments de l'ensemble total a n éléments*)
let parties = partiesDeTriangles i n in let partiesj = parties.(j) in let v = ref (make_vect n false) in
let rec aux (ll: int list) =
match ll with
| [] -> ()
| [x] -> !v.(x - 1) <- true
| t :: q -> !v.(t - 1) <- true; aux q
in aux partiesj; !v
;;
(*====================================================== Fonctions de coloriage automatique ========================================================*)
let couleur (i: int) (v: bool vect) = v.(i);;
let nombre_associes (i: int) (v: bool vect) (l: int vect vect) = (*Determine le nombre de triangles coloriés en contact avec le triangle i*)
let ll = l.(i) in let k = ref 0 in
for j = 0 to 2 do
if couleur (ll.(j) - 1) v then incr k
done;
!k
;;
let coloriageAuto (v: bool vect) (l: (int vect) vect) = let n = vect_length v in let vv = (make_vect n false) in
for i = 0 to n - 1 do if ((nombre_associes i v l) >= 2 || couleur i v) then vv.(i) <- true done; vv
;;
let coloriageComplet (coloriage: bool vect) (triancey: int vect vect) = let n = vect_length triancey in let vtest = ref coloriage in
while !vtest <> (coloriageAuto !vtest triancey) do
vtest := coloriageAuto !vtest triancey done; !vtest;;
let coloriageComplet2 (coloriage: bool vect) (triancey: int vect vect) = let v = ref (make_vect 24 false) in
for i = 0 to (vect_length triancey) do v := coloriageComplet coloriage triancey done; !v;;
(*====================================================== Fonctions de test des coloriages ========================================================*)
(*Teste si le coloriage pris en argument permet de couvrir tout le triancey*)
let test_final (v: bool vect) = let ans = ref true and n = vect_length v in
for i = 0 to n - 1 do if v.(i) = false then ans := false done; !ans;;
(*====================================================== Fonctions de conversions ========================================================*)
let int_of_bool (b: bool) = if b then 1 else 0;;
let imprimerColoriage (coloriage: bool vect) =
let n = vect_length coloriage in
for i = 0 to n - 1 do print_int (int_of_bool coloriage.(i)) done;;
let valeurColoriage (coloriage: bool vect) = (*Determine le nombre de triangle coloriés dans un coloriage*)
let n = vect_length coloriage and entier = ref 0 in
for i = 0 to n - 1 do entier := !entier + (int_of_bool coloriage.(i)) done; !entier;;
(*ConstruireColoriage : convertir un code "binaire" en coloriage 1 = colorié, 0= non colorié*)
let construireColoriage (code: string) = let n = string_length code in let v = make_vect n false in
for i = 0 to n - 1 do if (int_of_string (sub_string code i 1)) = 1 then v.(i) <- true done;
v
;;
(*====================================================== Fonctions de recherche et vérification ========================================================*)
let test = construireColoriage "001010010100000100001001";; (*Une solution au problème*)
coloriageComplet test triancey;;
coloriageComplet2 test triancey;;
(*======================================== Fonction de recherche par parties | Exhaustif, mais ne marche par pour toutes les valeurs (exn memoire)=======*)
exception stop of int;;
let trouveCombinaisonEtAffiche max = (*ne marche pas pour toutes le valeurs de max (exception memoire)*)
try for i = 0 to 134595 do
let c = coloriageParties max i 24 in if valeurColoriage (coloriageComplet c triancey) = 24 then raise (stop i) done;
with
| stop i -> print_string "Partie "; print_int i;
;;
trouveCombinaisonEtAffiche 6;;
comb 3 24;;
(*======================================== Fonction de recherche au Hasard| non exhaustif, mais ne fait pas d'exn memoire ==============================*)
(*Génère un coloriage de max triangle au hasard*)
#open "random";;
let coloriageAuPif (max: int) (n: int) = (*On créer un coloriage aléatoire que l'on teste*)
let t = [|true; false|] in
let v = make_vect n false in
while valeurColoriage v <> max do
for i = 0 to (n - 1) do if (valeurColoriage v < max) then v.(i) <- t.(int 2) done;
done;
(*De la, on procede au coloriage automatique*)
v
;;
init 0;;
coloriageAuPif 6 24;;
(*On teste m coloriage générés aléatoirement *)
exception stop of bool vect;;
let recherche max n m =
try
for i = 0 to m - 1 do
let c = coloriageAuPif max n in let cc = coloriageComplet c triancey in
if valeurColoriage cc = 24 then raise (stop c); done;
with
| stop c -> print_string "Le coloriage "; imprimerColoriage c; print_string " convient !";
print_string "Rien trouvé"
;;
recherche 7 24 1000;;
let coloriageTest = coloriageAuPif 7 24;;
let solution = construireColoriage "001010010100000100001001";; (*Une solution au problème, en 7 coups*)
coloriageComplet solution triancey;;