Programme mot-à-mot

Version imprimable

Programme mot-à-mot

Bonjour à tous,

j'ai reçu un petit problème à résoudre en pascal, connu sous le nom 'mot à mot'.
Le voici en détails :

Citation:

Etant donnés deux mots de même longueur, trouver une suite de mots commençant par le premier et se terminant par le deuxième, et telle que chaque mot de la suite, existe dans le dictionnaire, et ne diffère du précédent que par une seule lettre.

Donc j'ai à ma disposition un fichier Dico.txt qui contient tous les mots du dictionnaire en minuscules et sans caractères accentués, mais ceci est sans importance.

Et bien je ne sais vraiment pas quoi faire !
En tapant certaines paires de mots (par ex 'debut, aimer') ça marche, et d'autres (par ex 'debut, arret') qui ont pourtant bien un chemin, ça ne marche pas !!! (ex : 'aimer, debut' ne marche pas ...)

Je ne comprends pas ce qui cloche.

Merci à vous de jeter un oeil à mon code et me dire ce qui cloche !

Code:

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
program motamot;
 
uses sysutils, uliste;
 
procedure loaddictionnary(var dic : array of string; var lg : integer; const fil : textfile);
var	w : string;
begin
	lg := 0;
	while not eof(fil) do begin
		readln(fil,w);
		dic[lg] := w;
		lg := lg+1;
	end;
end;
 
function exists(const dic : array of string; indmin,indmax : integer; const w : string):boolean;
var	indmid : integer;
begin
	result := false;
	while (indmin <= indmax) and not result do begin
		indmid := (indmin+indmax) div 2;
		if dic[indmid] < w then indmin := indmid+1
		else if dic[indmid]>w then indmax := indmid-1
		else {dic[indmid]=w then} result := true;
	end;
end;
 
function way(const dic : array of string; const lg : integer; const w1,w2 : string;l : liste):boolean;
var 	w : string;
	c : char;
	i : integer;
begin
	result := false;
	insererliste(w1,l);
	if w1=w2 then begin
		result := true;
		afficherliste(l);
	end
	else begin
		if length(w1)=length(w2) then begin
			for i:=0 to length(w1) do begin
				for c:='a' to 'z' do begin
					w := w1;
					w[i]:=c;	
					if exists(dic,0,lg,w) then begin
						if not dansliste(w,l) then begin
							if way(dic,lg,w,w2,l) then begin
								result := true;
								exit;
							end;
						end;
					end;
				end;
			end;
		end;
	end;			
end;
 
var	word1,word2 : string;
	lg : integer;
	dic : array[0..109000] of string;
	fil : textfile;
	l : liste;
 
const	filename : string = 'Dico.txt';
 
begin
	if paramcount <> 2 then begin
		writeln('usage: motamot mo1 mot2');
	end
	else begin 	
		word1 := ParamStr(1);
		word2 := ParamStr(2);
		nouvelleliste(l);
		if FileExists(filename) then begin
			assignfile(fil,filename);
			reset(fil);
			loaddictionnary(dic,lg,fil);
			if exists(dic,0,lg,word1) and exists(dic,0,lg,word2) then begin
				writeln('ok, these words are in the dictionnary');
				writeln('now, lets see if there is a way from ''' + word1 + ''' to ''' + word2 + ''' ...');
				if way(dic,lg,word1,word2,l) then writeln('ihaaa! a way has been found! here it is...')
				else writeln('too bad, no way has been found...try with other words!');
			end
			else begin
				writeln('one of these words is not in the dictionnary');
			end;
		end
		else begin
			writeln('error while opening dictionnary file');
		end;
	end;
end.

et voici le code de l'unité 'UListe' utilisée dans ce programme :

Code:

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
76
77
78
79
80
81
unit Uliste;
 
INTERFACE
 
type    Liste =^cellule;
	cellule = 	record
				info:string;
				svt:Liste;
			end;
 
procedure   NouvelleListe(var l:liste);
function  ListeVide(l:liste):boolean;
function  DansListe(e:string;l:liste):boolean;
function  InsererListe(E:string;var L:Liste):boolean;
procedure Afficherliste(L:liste);
 
IMPLEMENTATION
procedure   NouvelleListe(var l:liste);
begin
	l := nil;
end;
 
function  ListeVide(l:liste):boolean;
begin
	if (l = nil) then result := true
	else result := false;
end;
 
function  DansListe(e:string;l:liste):boolean;
var	cell : liste;
begin
	result := false;
	if not ListeVide(l) then
	begin
		cell := l;
		while (cell <> nil) do
		begin
			if (cell^.info=e) then
			begin
				result := true;
				break;
			end;
			cell := cell^.svt;
		end;
	end
end;
 
function  InsererListe(E:string;var L:Liste):boolean;
var 	cell : liste;
begin
	result := false;
	if not DansListe(e,l) then
	begin
		result := true;
		new(cell);
		cell^.info := e;
		cell^.svt := l;
		l := cell;
	end
end;
 
procedure Afficherliste(L:liste);
var	cell : liste;
begin
	if ListeVide(l) then 
	begin
		writeln('Liste Vide');
	end
	else 
	begin
		cell := l;
		while (cell <> nil) do
		begin
			write(cell^.info:10);
			cell := cell^.svt;
		end;
		writeln;
	end;
end;
 
end.

Je l'ai fait en java, et là aucun problème, il me trouve bien un chemin quand il en existe un !

Voici le code :

Code:

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import java.util.*;
import java.io.*;
 
public class MotAMot{
 
	public static String[] monDico = new String[108996];
 
	public static void main(String[] Args) throws IOException {
		final String dico = "Dico.txt";
		if (Args.length != 2) {
			System.out.println("Il faut 2 arguments !");
			return;
		}
		loadDico(monDico,dico);
		if (exists(monDico, Args[0])){
			if (exists(monDico, Args[1])){
				System.out.println("ces mots sont dans le dictionnaire");
				System.out.println("voyons si il existe un chemin entre les deux");
				Liste l = new Liste();
				if (chemin(monDico, Args[0], Args[1], l)){
					System.out.println("il existe un chemin, le voici :");
					l.afficher();
				}
				else{
					System.out.println("il n'existe pas de chemin");
				}
			}
			else{
				System.out.println("le mot "+Args[1]+" n'est pas dans le dictionnaire");
			}
		}
		else{
			System.out.println("le mot "+Args[0]+" n'est pas dans le dictionnaire");
		}
	}
 
	private static void loadDico(String[] monDico,String dico) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(dico));
		String mot;
		int i = 0;
		while((mot=in.readLine()) != null) {
			monDico[i] = mot;
			++i;
		}
		return;
	} 
 
	private static boolean exists(String[] monDico, String mot){
		int indmin, indmax, indmid;
		indmin = 0;
		indmax = monDico.length-1;
		while (indmin <= indmax){
			indmid = (indmin+indmax)/2;
			if (monDico[indmid].compareTo(mot) < 0){
				indmin = indmid+1;
			}
			else if (monDico[indmid].compareTo(mot) > 0){
				indmax = indmid-1;
			}
			else{
				return true;
			}
		}
		return false;
	}
 
	private static boolean chemin(String[] monDico, String mot1, String mot2, Liste l){
		l.ajouter(mot1);
		if (mot1.compareTo(mot2) == 0){
			return true;
		}
		else{
			for(int i=0; i< mot1.length(); i++){
				for(char c='a'; c<='z'; c++){
					String mot = ((mot1.substring(0,i)).concat(Character.toString(c))).concat(mot1.substring(i+1,mot1.length()));
					if (exists(monDico, mot)){
						if (! l.contient(mot)){
							if (chemin(monDico, mot, mot2, l)){
								return true;
							}
						}
					}
				}
			}
			return false;
		}
	}
 
}

et ma classe 'Liste' :

Code:

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
import java.util.*;
 
public class Liste{
 
	private String[] liste = new String[108996];;
	private int lg;
 
	public Liste(){
		lg = 0;
	}
 
	public void afficher(){
		for (int i=0; i<lg; i++){
			System.out.println(liste[i]);
		}
	}
 
	public void ajouter(String mot){
		liste[lg] = mot;
		++lg;	
	}
 
	public boolean contient(String mot){
		for (int i=0; i<lg; i++){
			if (liste[i].compareTo(mot) == 0){
				return true;
			}
		}
		return false;
	}
 
}

Alors, une idée d'où vient le problème en pascal ?

Oui, il y plusieurs problèmes

D'abord sur l'unité : la variable "result" n'état pas déclarée donc l'unité n'était pas compilable.
D'autre part, il y a un problème sur test fonctions, relis la syntaxe Pascal. En Pascal une fonction est une VRAIE fonction (pas comme en java, C, C++ etc, tous les langages à effets de bord). Donc la valeur retournée doit être explicite. Ex

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
program test_fonction;
 
Var 
 
   val1, val2 : integer;
 
Function somme(x,y :integer) : integer;
 
begin
  somme:= x+y;
end;
 
 
Begin
 
 writeln(' valeur du premier nombre ?');
 readln(val1);
 writeln('valeur du deuxieme nombre ?');
 readln(val2);
 Writeln(' la somme est : ',  somme(val1,val2));
 readln;
end.

Code:

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
76
77
78
79
80
81
82
83
84
85
unit Uliste;
 
INTERFACE
 
type    Liste =^cellule;
	cellule = 	record
				info:string;
				svt:Liste;
			end;
 
Var
 
   result : boolean;
 
procedure   NouvelleListe(var l:liste);
function  ListeVide(l:liste):boolean;
function  DansListe(e:string;l:liste):boolean;
function  InsererListe(E:string;var L:Liste):boolean;
procedure Afficherliste(L:liste);
 
IMPLEMENTATION
procedure   NouvelleListe(var l:liste);
begin
	l := nil;
end;
 
function  ListeVide(l:liste):boolean;
begin
	if (l = nil) then result := true
	else result := false;
end;
 
function  DansListe(e:string;l:liste):boolean;
var	cell : liste;
begin
	result := false;
	if not ListeVide(l) then
	begin
		cell := l;
		while (cell <> nil) do
		begin
			if (cell^.info=e) then
			begin
				result := true;
				break;
			end;
			cell := cell^.svt;
		end;
	end
end;
 
function  InsererListe(E:string;var L:Liste):boolean;
var 	cell : liste;
begin
	result := false;
	if not DansListe(e,l) then
	begin
		result := true;
		new(cell);
		cell^.info := e;
		cell^.svt := l;
		l := cell;
	end
end;
 
procedure Afficherliste(L:liste);
var	cell : liste;
begin
	if ListeVide(l) then 
	begin
		writeln('Liste Vide');
	end
	else 
	begin
		cell := l;
		while (cell <> nil) do
		begin
			write(cell^.info:10);
			cell := cell^.svt;
		end;
		writeln;
	end;
end;
 
end.

Il y a aussi des problème sur ton programme principal. Corrige d'abord ton unité.

... D'autre part je suis comme une truie qui doute (comme dirait C. Duneton) : comment as-tu fait pour tester un programme ... non compilé (puisque non compilable) ? :calim2: