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 :

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 : 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
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 : 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
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.