Discussion :

[Rigaux]

Bonjour,

Je viens vers vous pour vous demander de l'aide car j'ai du mal à coder une partie d'un programme.
J'ai réussi à coder ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
let extract_param (a,b,c) =
	let ssli s = Str.split (Str.regexp " ") s in
	let strToInt l = List.map int_of_string l in
	let rec listeCoupList l = match l with
		x::y::tl -> (x,y)::(listeCoupList tl)
		|_ -> failwith "Erreur" in
	(listeCoupList (strToInt (ssli b)),listeCoupList (strToInt (ssli c)));;

Qui doit prendre un triplet de string a,b et c, qui sont composé d'entiers séparés d'un espace. Je n'ai besoin que des strings b et c dans la suite du programme.

Je créer ensuite une liste de couples.

Bref, je suis maintenant bloqués ici.
Il faut savoir que b et c sont de formes : "123 4 543 2 554 4 123 6 134 2 2314 6". La fonction renvoie donc : [(123,4);(543,2);(554,4);(123,6);(134,2);(2314,6)]
Donc de couple (x,y) et ce que je veux faire dorénavant, c'est ressortir une liste avec la somme des couples quand les y sont égaux.
C'est-à-dire : [(677,4);(677,2);(2448,6)]. Mais je ne sais pas quelles fonctions utilisés pour faire ainsi....

De plus après avoir fait ceci à b et c je voudrais comparer les deux listes et pour tout y données prendre le minimum de x entre les deux listes et faire une somme entre toutes ces valeurs.

Exemple :
On a :
[(677,4);(677,2);(2448,6)] et [(7634,3);(4432,4);(54,6);(134,2);(45436,99)], cela doit me renvoyer : [(677,4);(134,2);(54,6)] et je veux finalement faire : 677+134+54 = 865.

Je voulais donc savoir si vous aviez des recommendations pour résoudre mon problème.
J'ai déjà codé la fonction pour déterminer le minimum entre les deux valeurs :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

let min x y = if x < y then x else y;;

Mais j'ai du mal à utiliser les listes en programmation fonctionnelle. Je suis plus habitué à du procédurale.

Merci d'avance !

Cordialement Rigaux.

[TchoubiTchoub]

Bonjour,

Ce que je ferais, dans ce cas, ce serait la chose suivante :

1. Trier mes deux listes selon le deuxième élément du couple
2. Parcourir chaque liste et pour chaque élément vérifier si l'élément suivant est égal ou non
   
   • Si oui, j'additionne et je continue
   • Sinon, je passe à la suite
3. Une fois que j'ai fait toutes les sommes nécessaires je peux facilement récupérer les min de chaque liste

Donc, en OCaml ça donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
let sort l = List.fast_sort (fun (_, y1) (_, y2) -> compare y1 y2) l;;
 
let sum_equals l =
  let rec sr l acc  = match l, acc with
    | [], _ -> List.rev acc
    | (x1, y1) :: tl1, (x2, y2) :: tl2 when y1 = y2 ->
      sr tl1 ((x1 + x2, y1) :: tl2)
    | hd :: tl, _ -> sr tl (hd :: acc)
  in sr l [];;
 
let get_min l1 l2 =
   let rec gr l1 l2 acc = match l1, l2 with
     | [], _ | _, [] -> List.rev acc
     | (x1, y1) :: tl1, (x2, y2) :: tl2 when y1 = y2 ->
       gr tl1 tl2 ((min x1 x2, y1) :: acc)
     | (x1, y1) :: tl1, (x2, y2) :: tl2 when y1 < y2 ->
       gr tl1 l2 acc
     | (x1, y1) :: tl1, (x2, y2) :: tl2 ->
       gr l1 tl2 acc
   in gr l1 l2 [];;
 
let sum_all m = List.fold_left (fun acc (x, _) -> x + acc) 0 m;;
 
let l1 = sort  [(123,4);(543,2);(554,4);(123,6);(134,2);(2314,6)];;
 
let l1s = sum_equals l;;
 
let l2s = sort [(7634,3);(4432,4);(54,6);(134,2);(45436,99)];;
 
let m = get_min l1s l2s;;
 
# let s = sum_all m;;
val s : int = 865

Voilà

Sinon, comme ça m'embête de faire ça avec les listes, j'aurais plutôt fait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
module IMap = Map.Make (
  struct
    type t = int
    let compare = compare
  end
)
 
let b = "123 4 543 2 554 4 123 6 134 2 2314 6"
let c = "7634 3 4432 4 54 6 134 2 45436 99"
 
let extract_param (a,b,c) =
  let ssli s = Str.split (Str.regexp " ") s in
  let strToInt l = List.map int_of_string l in
  let rec maplist map = function
    | [] -> map
    | x::y::tl ->
      let i = try IMap.find y map
        with Not_found -> 0 in
      maplist (IMap.add y (x + i) map) tl
    | _ -> failwith "Erreur" in
  maplist IMap.empty (strToInt (ssli b)),
  maplist IMap.empty (strToInt (ssli c));;
 
let get_min m1 m2 =
  IMap.fold (fun k v1 acc ->
    try let v2 = IMap.find k m2 in
        IMap.add k (min v1 v2) acc
    with Not_found -> acc
  ) m1 IMap.empty
 
let sum_all m = IMap.fold (fun _ v acc -> v + acc) m 0
 
let () =
  let m1, m2 = extract_param (1, b, c) in
  let m = get_min m1 m2 in
  let res = sum_all m in
  Printf.printf "Res : %d\n" res

Au fait, une petite erreur dans votre fonction extract_param, vous n'avez pas pris en compte le cas où la liste est vide (ce qui est le cas où on renvoie l'accumulateur).

[Rigaux]

Merci beaucoup TchoubiTchoub,

Mais pourrais tu m'expliquer ce que tu as fais avec le module ? C'est quoi ? J'arrive pas à bien comprendre ...

[TchoubiTchoub]

L'intérêt de ce module c'est que c'est un dictionnaire qui associe donc à chaque clé une unique valeur.

Pas à pas :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
module IMap = Map.Make (
  struct
    type t = int
    let compare = compare
  end
)

Création d'un module dont les clés sont des entiers qu'on compare avec la fonction compare du module Pervasives (le module standard, le seul qu'on n'a pas besoin d'ouvrir)

En effet, le foncteur (c'est une espèce de fonction qui crée des modules) Map.Make prend un module dont la signature est

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
sig 
  type t
  val compare : t -> t -> int 
end

En gros, une map OCaml est un AVL (un arbre binaire de recherche équilibré) donc il a besoin de pouvoir comparer les clés pour les placer.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let b = "123 4 543 2 554 4 123 6 134 2 2314 6"
let c = "7634 3 4432 4 54 6 134 2 45436 99"
 
let extract_param (a,b,c) =
  let ssli s = Str.split (Str.regexp " ") s in
  let strToInt l = List.map int_of_string l in
  let rec maplist map = function
    | [] -> map
    | x::y::tl ->
      let i = try IMap.find y map
        with Not_found -> 0 in
      maplist (IMap.add y (x + i) map) tl
    | _ -> failwith "Erreur" in
  maplist IMap.empty (strToInt (ssli b)),
  maplist IMap.empty (strToInt (ssli c));;

Ici, plutôt que de remplir une liste, à chaque fois que je trouve un couple x :: y, je récupère, dans la map que je suis en train de construire, la dernière valeur associée à y avec IMap.find y map et si je ne la trouve pas (l'exception Not_found) je renvoie 0 et j'ajoute dans la map (donc, en fait, je remplace la dernière valeur associée) la somme x + i associée à la clé y.

Si on regarde ce qui se passe pour la liste b, au début notre map est vide puis :

• je vois 123 :: 4 :: [543 2 554 4 123 6 134 2 2314 6] donc j'ajoute dans ma map 4 associé à 123 + 0 (car 4 n'est associé à rien dans la map, vu qu'elle est vide) et je me rappelle récursivement sur le reste de la liste et la map [4 -> 123]
• je vois 543 :: 2 :: [554 4 123 6 134 2 2314 6], donc, idem, je me rappelle récursivement sur le reste de la liste et la map [4 -> 123, 2 -> 543]
• je vois 554 :: 4 :: [123 6 134 2 2314 6], cette fois je récupère dans i la valeur 123 et je me rappelle récursivement sur le reste de la liste et la map [4 -> 123 + 554 = 677, 2 -> 542]
• etc jusqu'à la fin où ma liste est vide et ma map est de la forme suivante [4 -> 677, 2 -> 677, 6 -> 2448]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let get_min m1 m2 =
  IMap.fold (fun k v1 acc ->
    try let v2 = IMap.find k m2 in
        IMap.add k (min v1 v2) acc
    with Not_found -> acc
  ) m1 IMap.empty

Ici j'utilise un itérateur sur la map, en gros, je parcoure toute la map et je mets à jour un accumulateur. Le principe c'est que pour chaque clé que je parcoure de m1 (car, comme on le voit, j'itère sur m1), si elle est aussi dans m2 alors j'associe à cette clé le minimum entre les deux valeurs associées dans m1 et m2, sinon je n'ajoute pas la clé dans mon accumulateur (donc, oui, mon accumulateur est aussi une map qui est initialement vide).

Pas à pas :

• Je vois l'association 2 -> 677 dans m1, je regarde si une valeur est associée à 2 dans m2, c'est le cas, je mets donc dans mon accumulateur 2 associé au minimum entre 677 (valeur associée à 2 dans m1) et 134 (valeur associée à 2 dans m2) donc mon accumulateur est de la forme [2 -> 123]
• Idem pour 4, mon accumulateur est de la forme [2 -> 123, 4 -> 677]
• Idem pour 6, mon accumulateur est de la forme [2 -> 123, 4 -> 677, 6 -> 54]
• Plus d'élément à regarder, j'ai fini d'itérer

A l'issue de cette fonction j'ai donc bien une map qui ne contient que des clés qui sont présentes dans les deux maps précédentes et qui à chacune de ces clés associe la valeur minimale à laquelle elle était associée.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

let sum_all m = IMap.fold (fun _ v acc -> v + acc) m 0

La beauté d'OCaml, en une ligne je somme chacune des valeurs à un accumulateur initialement nul (sans prendre en compte les clés, d'où le _)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let () =
  let m1, m2 = extract_param (1, b, c) in
  let m = get_min m1 m2 in
  let res = sum_all m in
  Printf.printf "Res : %d\n" res

Le programme principal avec le calcul des maps, de la map min et de la somme résultante.

En gros, une fois qu'on a compris les modules et les itérateurs, mon code est très clair. Je vous conseille donc de lire la doc du module Map.Make pour bien comprendre la fonction fold.

[Rigaux]

D'accord !

Merci j'ai compris le fonctionnement de ton algorithme ! Et un peu plus du Module, mais je vais devoir y travailler un peu plus sur ça.

Par contre, j'ai un petit problème l'algorithme me donne 45 pour ces strings :
"10 1 20 2 25 3"
"10 2 30 3 20 1"
Alors que je suis censé avoir 35 ... Mais je ne semble pas trouver l'erreur ...

[TchoubiTchoub]

Par contre, j'ai un petit problème l'algorithme me donne 45 pour ces strings :
"10 1 20 2 25 3"
"10 2 30 3 20 1"
Alors que je suis censé avoir 35 ... Mais je ne semble pas trouver l'erreur ...

Ah non, je compte bien 10 + 10 + 25 = 45

[Rigaux]

En fait, j'ai mal expliqué ce que je devais faire ...

Et maintenant j'ai du mal à comprendre ce que je devais faire.

En gros le problème est le suivant : https://code.google.com/codejam/cont...board#s=p2&a=3

Donc si tu arrives à comprendre un truc, je te prie de me le dire parce que je t'avoue que je galère...

Merci d'avance

[TchoubiTchoub]

Ah, mais ce n'est pas vraiment le même problème

En effet, pour ce problème, les listes sont les meilleures structures de données car que faut-il faire ?

On a deux listes, une de boîtes et une deux jouets. Chacune a la même forme : (quantité, type) :: reste_de_la_liste

Donc, par exemple, si on a la liste [(10, 2); (20, 1)] et [(20, 2); (10, 1)], on peut consommer parallèlement les 10 premières boîtes de type 2 avec 10 jouets de type 2, il nous reste donc [(20, 1)] [(10, 2); (10, 1)], là on jette les 10 jouets de type 2 car on ne peut pas les associer aux boîtes de type 1 donc il nous reste [(20, 1)] [(10, 1)], on peut donc consommer les 10 jouets de type 1 avec 10 boîtes de type 1 et il nous reste donc 10 boîtes de type 1 mais plus aucun jouet donc on a fini. On a donc pu créer 20 assemblages en tout.

Le principe est donc le suivant, j'ai une première liste de type [(v1, t1); (v2, t2); (v3, t3); ...] et une deuxième de type [(v'1, t'1); (v'2, t'2); (v'3, t'3); ...]

Que dois-je faire ?

• Si t1 = t'1 alors on garde le minimum entre v1 et v'1
• Si t1 != t'1, on a un problème, on jette le couple (v1, t1) ou le couple (v'1, t'1) ? En fait on va tester les deux solutions et garder la meilleure.

Ca donne un code différent :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
let assemble l1 l2 =
  let rec ar acc l1 l2 = match l1, l2 with
    | [], _ | _, [] -> acc
    | (v1, t1) :: tl1, (v2, t2) :: tl2 when t1 = t2 ->
      (* Si t1 = t2, on ajoute à l'accumulateur le nombre maximum
         d'assemblages qu'on peut faire, donc le minimum entre v1 et v2 
      
         Par contre, attention, il faut qu'on garde le reste parce qu'on
         peut toujours s'en resservir.*)
      let acc, l1, l2 = if v1 = v2 then acc + v1, tl1, tl2
        else if v1 > v2 then acc + v2, (v1 - v2, t1) :: tl1, tl2
        else acc + v1, tl1, (v2 - v1, t2) :: tl2
      in ar acc l1 l2
    | (v1, t1) :: tl1, (v2, t2) :: tl2 ->
      (* Dans ce cas, on doit tester, soit on jette les boîtes
         soit on jette les jouets et on regarde ce qui nous renvoie le 
         résultat maximal *)
      (* On jette le couple (v1, t1) *)
      let r1 = ar acc tl1 l2 in
      (* On jette le couple (v2, t2) *)
      let r2 = ar acc l1 tl2 in
      max r1 r2
  in ar 0 l1 l2

Et voilà ce que ça donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
# let l1 = [(123,4);(543,2);(554,4);(123,6);(134,2);(2314,6)];;
val l1 : (int * int) list =[(123, 4); (543, 2); (554, 4); (123, 6); (134, 2); (2314, 6)]
# let l2 = [(7634,3);(4432,4);(54,6);(134,2);(45436,99)];;
val l2 : (int * int) list =[(7634, 3); (4432, 4); (54, 6); (134, 2); (45436, 99)]
# let r1 = assemble l1 l2;;
val r1 : int = 865
# let l1', l2' = extract_param "10 1 20 2 25 3" "10 2 30 3 20 1";;
val l1' : (int * int) list = [(10, 1); (20, 2); (25, 3)]
val l2' : (int * int) list = [(10, 2); (30, 3); (20, 1)]
# let r2 = assemble l1' l2';;
val r2 : int = 35

[Rigaux]

Ah parfait !!

Je comprends beaucoup mieux le problème.

Par contre je me permets de te demander un petits truc, j'essaye d'intégrer ton bout de code dans mon programme mais ça me ressors une erreur.
L'erreur n'a rien à voir avec ton code mais je ne comprends pas car la fonction marchait avant mais plus maintenant. Je te mets mon programme complet ici, et le fichier .in est le fichier sur le liens que j'ai mis précédemment.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
let rec jam_rec flec algolec algopb nblignes total = match nblignes with
 0 -> ""
|n -> let line = (algolec flec) in
	"Case #"^(string_of_int(total-nblignes+1))^": "^(algopb line)^"\n"^(jam_rec flec algolec algopb (nblignes-1) total) ;;
 
let jam fin fout algolec algopb =
	let fecr = open_out fout in
	let flec = open_in fin in
	let nb = (int_of_string(input_line flec)) in
	begin
		output_string fecr (jam_rec flec algolec algopb nb nb);
		close_in flec;
		close_out fecr;
	end;;
 
let lecture f =
	let a = input_line f in
	let b = input_line f in
	let c = input_line f in
	(b,c);;
 
#load "str.cma";;
 
let extract_param (b,c) =
	let ssli s = Str.split (Str.regexp " ") s in
	let strToInt l = List.map int_of_string l in
	let rec listeCoupList l = match l with
		x::y::tl -> (x,y)::(listeCoupList tl)
		|_ -> failwith "Erreur" in
	(listeCoupList (strToInt (ssli b)),listeCoupList (strToInt (ssli c)));;
 
 
let assemble l1 l2 =
	let rec ar acc l1 l2 = match l1, l2 with
		| [], _ | _, [] -> acc
		| (v1, t1) :: tl1, (v2, t2) :: tl2 when t1 = t2 ->
			let acc, l1, l2 = if v1 = v2 then acc + v1, tl1, tl2
				else if v1 > v2 then acc + v2, (v1 - v2, t1) :: tl1, tl2
				else acc + v1, tl1, (v2 - v1, t2) :: tl2 in
			ar acc l1 l2
		| (v1, t1) :: tl1, (v2, t2) :: tl2 ->  let r1 = ar acc tl1 l2 in
	                                                          let r2 = ar acc l1 tl2 in
	            max r1 r2 in
		ar 0 l1 l2;;
 
let jamC (b,c) =
	let (l1,l2) = extract_param (b,c) in
	string_of_int (assemble l1 l2);;
 
 
(* Exemple d'utilisation *)
(* jam "C-large-practice.in" "toto.out" lecture jamC;;*)

L'erreur ce produit au niveau de la fonction extract_param et m'affiche :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
# jam "C-large-practice.in" "toto.out" lecture jamC;;
Exception: Failure "Erreur".

Je ne semble pas trouver l'erreur n'y était pas précédemment...

Merci d'avance

[TchoubiTchoub]

J'avais écrit ça dans ma première réponse : Au fait, une petite erreur dans votre fonction extract_param, vous n'avez pas pris en compte le cas où la liste est vide (ce qui est le cas où on renvoie l'accumulateur).

N'est-ce pas là le problème ?

[Rigaux]

Oui en effet, il s'agissait de cette erreur !

Autant pour moi.

Merci beaucoup en tout cas, ce programme marche parfaitement

Cordialement Rigaux.