Discussion :

[Rigaux]

Bonjour à tous ,

Je lance cette discussion car j'aurais besoin d'aide pour réaliser une operation en OCAML.
Je vais tout d'abord vous expliquer le problème pour vous mettre dans le contexte.

J'ai un fichier à lire avec des déclarations de fonctions du style : abc=(d,f) ou ab=() ou encore abg=(dsa) etc.
Une fonction est sur une ligne.
Et donc je dois trouver pour une certaine liste de fonctions si cette liste est correcte ou pas vis a vis des declarations. Par exemple :

Code :

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

1
2
3
abc=f(a,b)
a=()
b=()

est correcte car toutes les variables sont définies

Cependant si on a :

Code :

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

1
2
abc=f(a,b)
a=()

ceci est faux car b n'est pas définie

et dernierement si on a :

Code :

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

1
2
a=f(b)
b=f(a)

cela est egalement faux

Pour coder ceci j'ai choisis de créer trois listes : une avec les fonctions qui sont bien déclarés (fb), une autre avec le couple (nom_fonctions,[liste_vars]) où on mets les fonctions qui ne sont pas encore bien définies car ces variables ne sont pas définies (fa) et une derniere pour les variables qui ne sont pas encore définis (va).

Donc dans ma logique j'ai fais ainsi :
On lis une fonction ainsi : nom_fonct=x([liste_vars]) (Ici on n'a pas besoin de x)

1. Si nom_fonct=(), on ajoute nom_fonct directement a la liste fb
2. Si touts les elements de [liste_vars] sont dans fb alors mettre nom_fonct dans fb
3. Si un ou plusieurs elements de [liste_vars] ne sont pas dans fb alors on ajoute [liste_vars] dans va, mais ne faisant un test pour savoir si certaines de ces variables y sont deja pour ne pas en avoir en 2 fois. Et par la suite ajouter dans la liste fa (nom_fonct,[liste_vars]
4. Apres avoir lu chaque fonction de la liste, faire une operation qui permet de comparer les deux listes et voir si il n'y a pas des elements dans fb qui sont dans va et ainsi le supprimer dans va, et faire la meme opération dans la liste fa pour les variables des couples et au fur et à mesure vider les deux liste fa et va et remplir celle de fb.
5. Finalement, apres avoir lu toute la liste des fonctions, si la liste va n'est pas vide alors cette sequence de fonctions n'est pas bonne, sinon elle est bonne.

J'ai commence a coder ceci mais je suis bloqué au niveau de l'ajout dans les liste fa et va avec le non-rajout de deux fois le meme élément

Je vous mets mon code ci-dessous :

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
let rec supprime l a = match l with
	[]-> []
	|x::r when x = a -> List.tl l
	|x::r -> supprime r a;;
 
let rec ajoutefin a l = match l with
	[] -> [a]
	|x::r -> x::ajoutefin a r;;
 
let rec jamLoop n fich i  lb la va =
	let indiceEgal s = String.index s '=' in
	let indice1Par s = String.index s '(' in
	let ssv s j = String.sub s j+1 ((String.length s)-j-2) in (*Sortie du string des variables*)
	let ssn s i = String.sub s 0 i in (*Sortie du nom de la fonction en string*)
	let listVar s = if String.contains s ',' then Str.split (Str.regexp ",") s else Str.split (Str.regexp "") s i (*Si les variables comportent des virgules, les separer avec la virgule comme séparateur sinon juste mettre le string sous forme d'un element de la liste*)
	let lecVarDir s fb = match s with
		s when String.sub s (String.length s - 3) 3 = "=()" -> ajoutefin (String.sub s 0 (String.length s - 3)) fb (*Direct mettre dans FB si aucune variable*)
		|_ -> s in
	let ligne = input_line fich in
 
	let rec verifVar fb l fa va s = match l with 
		[] -> ajoutefin s fb
		|x::r when List.mem x fb -> verifVar fb l fa va s (*Si variable dans la liste fb faire appelle reecursif et verifie autres elements de la liste*)
		|_ -> let rec ajoutDiffLis fa va l s = match l with (*Ajout dans les differentes listes*)
			x::r when List.mem x va -> ajoutDiffLis fa va r s (*Vérifie si une variable est dans la liste des fb si oui il fait le test avec touts les autres variables*)
			|x::r -> ajoutefin x va;ajoutefin () (*C'est ici qu'il faut vérifier si les variables sont deja dans la liste VA si oui on passe à la prochaine sinon on ajoute dans la liste et à la fin il faut ajouter le couple (fonct,[vars]) dans la liste FA*)
 
 
	if i = n then
		if la = [] then "GOOD" else "BAD"
	else jamLoop n fich (i+1) lb la;;
 
let jamEval a =
	let fb = [] in
	let fa = [] in
	let va = [] in
	let fich = open_in "C-small-practice.in" in
	let n = int_of_string (input_line fich) in
	jamLoop n fich 0 fb fa va;;

C'est seulement après avoir trouvé une seule variable qui n'est pas dans fb qu'on fais l'ajout aux différentes listes

J'espère que vous comprenez le problème que je rencontre. Sinon je vous mets le liens du problème en question : https://code.google.com/codejam/cont...dashboard#s=p2

Merci d'avance.

Cordialement
Rigaux

[james-mi]

Bonjour,

je n'ai pas vraiment les compétences pour rentrer dans le corps de ton code, mais par contre quelques remarques qui peuvent éventuellement te permettre d'y voir plus clair :
1) tu recodes des fonctions qui sont assez facilement accessibles de façon "native" :
1.1 par exemple supprime s’exprime très facilement avec List.filter (cf ici : http://caml.inria.fr/pub/docs/manual...bref/List.html)
1.2 De même, ajouteFin est facile à écrire comme ajout et 2 List.rev (pas forcément le plus efficace bien sûr)
2) le fait même que tu aies besoin de ajouteFin est bizarre : tu ne peux pas plus simplement faire un ajout à ta liste, puis faire un List.rev à la fin ?
3) enfin, puisque tu as supprime, pourquoi hésites-tu à ajouter ? tu pourrais très bien tolérer les doublons temporairement, et les en ôter à la fin, juste avant de renvoyer le résultat, non ? Si oui, je crois que ton problème est (presque ...) résolu.
4) jette aussi un coup d'oeil, dans le manuel du module List (celui dont j'ai donné le lien plus haut), sur la section "List associations", parce qu'il y a des fonctions qui peuvent t'aider.


En attendant des réponses plus autorisées que la mienne ...

[TchoubiTchoub]

Bonjour,

Votre solution est un peu complexe et je vous avoue que j'ai du mal à la lire (il y a, notamment, des erreurs de syntaxe qui n'aident pas ) Je vous invite à suivre les conseils avisés de james-mi et, surtout, à trouver le cas minimal qui vous pose problème.

En réalité, ce problème est un problème très intéressant d'algorithmique, c'est celui de l'existence ou non d'un cycle dans un graphe orienté.

Par exemple, si on a

Code :

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

1
2
a = f(c)
b = f(c)

On peut représenter ça comme le graphe

a -> c
b -> c

Idem, si on a

Code :

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

1
2
a = f(b)
b = f(a)

On peut représenter ça comme le graphe

a -> b
b -> a

On a le cycle a <-> b, ce qui veut dire que a dépend de b et b de a.

Donc, la solution du problème c'est de vérifier que le graphe représenté par chacune des lignes du fichier ne contient pas de cycle.

C'est un peu ce que vous essayez de faire avec vos multiples listes (même si je vous invite à réécrire ce code pour voir exactement ce qui cloche) et je n'ai pas pu m'empêcher de faire ma solution avec des beaux modules (en gros, on fait un DFS dans le graphe créé) :

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
module SS = Set.Make (String)
module Graph = Map.Make (String)
 
type color = White | Gray | Black
 
type value = {args : SS.t; mutable color : color}
 
let read_testcase n file =
  let ltrs = "[a-z]+" in
  let params = "(\\(\\(" ^ ltrs ^ ",\\)*" ^ ltrs ^ "\\)?)" in
  let re_assign =
    Str.regexp ("^\\(" ^ ltrs ^ "\\)=\\(" ^ ltrs ^ "\\)" ^ params ^ "$") in
  let comma = Str.regexp "," in
  let rec aux i graph =
    if i > n then graph
    else
      let line = input_line file in
      if Str.string_match re_assign line 0 then
        let var = Str.matched_group 1 line in
        let args =
          try
            let args = Str.matched_group 3 line in
            let args = Str.split comma args in
            SS.of_list args
          with Not_found -> SS.empty in
        let graph = Graph.add var {args; color = White} graph in
        aux (i + 1) graph
      else assert false
  in aux 1 Graph.empty
 
let get_starts graph =
  let nodes, children =
    Graph.fold (fun key {args} (nodes, children) ->
      SS.add key nodes, SS.union children args
    ) graph (SS.empty, SS.empty) in
  SS.diff nodes children
 
let is_acyclic_dfs graph starts =
  let rec aux key =
    try
      let value = Graph.find key graph in
      match value.color with
      | White -> 
        value.color <- Gray;
        SS.iter (fun node -> aux node) value.args;
        value.color <- Black
      | Gray -> raise Exit
      | Black -> ()
    with Not_found -> raise Exit
  in
  try
    SS.iter (fun node -> aux node) starts;
    true
  with Exit -> false
 
let is_acyclic graph starts =
  not (SS.is_empty starts) && is_acyclic_dfs graph starts
 
let file_loop n file =
  let rec aux i =
    if i > n then close_in file
    else
      let nl = int_of_string (input_line file) in
      let graph = read_testcase nl file in
      let starts = get_starts graph in
      let res = is_acyclic graph starts in
      let res = if res then "GOOD" else "BAD" in
      Format.eprintf "Case #%d: %s@." i res;
      aux (i + 1)
  in aux 1
 
let () =
  let file = open_in Sys.argv.(1) in
  let n = int_of_string (input_line file) in
  file_loop n file

Bon courage pour comprendre mais quand vous aurez compris vous serez une nouvelle personne !