Discussion :

[sirius911]

Bonjour à tous,
Je vous donne une énigme et je souhaiterai trouver la solution avec prolog :

C'est un mot de 5 lettres qui a une lettre commune, dans la même position, avec
CREPI, et deux lettres communes, dans la même position, avec TROIS. Il y a une lettre commune et dans la même position, avec FERME, mais aucune avec ECROU et une seule, dans la même position, avec SOMME.
Quel est ce mot ?

Bon évidement on ne va pas rechercher un mot existant, ce qui nécessiterait d'avoir une base de données de mots, mais plutôt une liste de mots possibles prenant en compte toutes les contraintes énoncées dans l'énigme

Bon étant débutante, je ne sais pas trop par quoi commencer, j'ai enregistré une base comme ceci :

Code :

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

1
2
3
4
5
6
7
mot_mystere([A,B,C,D,E]).
 
mots([c,r,é,p,i],1).    % mots/2    mot et nombre de lettres communes avec le
mots([t,r,o,i,s],2).     %  le mot mystère.
mots([f,e,r,m,e],1).
mots([é,c,r,o,u],0).
mots([s,o,m,m,e],1).

j'ai ensuite fait un prédicat pour donner le nombre de lettres communes à deux mots:

Code :

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

1
2
3
let_comm([],[],[]):-!.
let_comm([X|L],[X|M],[X|N]):-!,let_comm(L,M,N).
let_comm([_|L],[_|M],R):-let_comm(L,M,R).

ça donne

Code :

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

1
2
3
 ?- let_comm([a,b,c,d],[a,a,h,d],R).
 
R = [a, d]

s'il y a des gens partants pour m'aider avec plaisir...

[Trap D]

Bonjour

Moi, j'ai toujours un problème avec ce genre de jeu :
Quand tu dis "le mot cherché n'a aucune lettre commune avec ECROU", celà veut-il dire qu'il n'y a ni E, ni C, ni R, ni O, ni U dans le mot à n'impoerte quelle place, ou il peut y avoir E mais pas en 1, un C mais pas en 2 ...?

[sirius911]

Ben connaissant la réponse il n'y a aucune lettre du mot ÉCROU mais attention
Il faut bien faire la différence entre les é è et e ce qui ne facilite pas la tâche !!

[Trap D]

J'ai trouvé 'temps', j'ai bon ?

12 ?- mot_mystere.
[c, e, m, i, s]
[f, o, e, i, s]
[f, o, o, i, i]
[f, o, o, p, s]
[s, e, e, i, s]
[s, e, o, i, i]
[s, e, o, p, s]
[t, e, m, i, i]
[t, e, m, p, s]
true.

[sirius911]

bravo
respect ...
mais comment tu as fait exactement ?

[Trap D]

Le principe :
J'ai collecté toutes les possibilites pour chaque lettre du mot.
J'ai ensuite défini ce qu'était un mot :
formé de lettres parmi les possibles
respectant les conditions énoncées.
J'ai demandé enfin à Prolog de me donner toutes les solutions possibles.

Je te donne une piste, cherche dans cette voie.

[sirius911]

c'est chaud
pour l'instant j'ai fait un prédicats pour

J'ai collecté toutes les possibilités pour chaque lettre du mot.

Code :

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

1
2
3
possibilites(0,_,[]).
possibilites(N,[X|T],[X|Comb]):-N>0,N1 is N-1,possibilites(N1,T,Comb).
possibilites(N,[_|T],Comb):-N>0,possibilites(N,T,Comb).

Code :

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

1
2
3
4
5
6
7
8
9
 possibilites(3,[a,b,d,e],R).
 
R = [a, b, d] ;
 
R = [a, b, e] ;
 
R = [a, d, e] ;
 
R = [b, d, e] ;

évidemment si je fais
?- possibilites (5,[c,r,e,p,i,t,r,o,i,s,f,e,r,m,e,e,c,r,o,u,s,o,m,m,e],R). j'ai le mot
... dans deux ans
il faut utiliser des prédicats spéciaux ?? maplist sublist ??
je ne suis que débutante et là je sèche...

[Trap D]

Non, tu es sur une mauvaise voie :
J'ai collecté les lettres possibles pour la première lettre du mot mystère :
[c, f, s, t]
les lettres possibles pour la deuxième lettre du mot mystère :
[e, o, r]
.........
etc

Ensuite j'ai dit qu'un mot possible était constitué de lettres tirées parmi les lettres possibles, ce mot étant testé par rapport aux conditions fournies (j'ai repris sans vergogne ton code llet_comm/3 ).

PS : J'ai trouvé ton problème sur la liste SWI-Prolog résolu par Markus Triska lui-même , avec l'utilisation de sa librairie des contraintes, c'est très instructif comme méthode !

[sirius911]

oulaa je galère
j'ai mes 5 lettres possibles pour le mots mais avec ça !!

lettre1(R):-findall(X,mots([X|_]),R).
lettre2(R):-findall(X,mots([_,X|_]),R).
lettre3(R):-findall(X,mots([_,_,X|_]),R).
lettre4(R):-findall(X,mots([_,_,_,X|_]),R).
lettre5(R):-findall(X,mots([_,_,_,_,X|_]),R).

je n'arrive pas à trouver une récusivité
à chaque fois il reste sur le même mots

[Trap D]

Maintenant que tu as toutes tes lettres (tu pourrais faire un test dans ton findall, pour éviter les lettres de écrou), explique à Prolog ce qu'est le mot recherché.

• Sa première lettre est dans Lettre1
• Sa deuxième lettre est dans Lettre2
• ....
• Le mot n'a aucune lettre commune avec "écrou"

Il n'y a pas de récursivité, tu as tout pour trouver le mot !

[sirius911]

je ne sais pas mettre de test dans findall !!
sinon pour faire le mot : voilà...

J'ai vraiment l'impression de dire des grossiertés avec mon code !!

Code :

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

1
2
3
4
5
mystere([A,B,C,D,E]):-	lettre1(Lettre1),permut(Lettre1,[A|_]),
			lettre2(Lettre2),permut(Lettre2,[B|_]),
			lettre3(Lettre3),permut(Lettre3,[C|_]),
			lettre4(Lettre4),permut(Lettre4,[D|_]),
			lettre5(Lettre5),permut(Lettre5,[E|_]).

avec

Code :

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

1
2
permut([],[]).
permut(L,[X|Q1]):-enlever(X,L,Q),permut(Q,Q1).

Bien évidemment ça me donne une quantité énorme de solution...

[Trap D]

Non, tu galères, je réitère :
Maintenant que tu as toutes tes lettres , explique à Prolog ce qu'est le mot recherché.

* Sa première lettre est dans Lettre1
* Sa deuxième lettre est dans Lettre2
* ....

Code :

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

1
2
3
4
5
6
member(C1, Lettre1),
member(C2, Lettre2),
member(C3, Lettre3),
member(C4, Lettre4),
member(C5, Lettre5),
mot = [C1,C2,C3,C4,C5],

et maintenant, tu testes que ton mot répond aux critères donnés avec le prédicat let_communes !

[sirius911]

bon j'ai :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
construit_mystere([A,B,C,D,E]):-
	lettre1(Lettre1),
	lettre2(Lettre2),
	lettre3(Lettre3),
	lettre4(Lettre4),
	lettre5(Lettre5),
	member(A,Lettre1),
	member(B,Lettre2),
	member(C,Lettre3),
	member(D,Lettre4),
	member(E,Lettre5).

puis

Code :

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

1
2
3
go(Mot):-construit_mystere(R),
	mots(Mots,I),
	nb_comm(R,Mots,Nb) , nb = I.

avec
nb_comm(Mot1,Mot2,Nb) qui donne le nombre de lettre commune :

Code :

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

1
2
3
4
nb_comm([],[],0).
nb_comm([X],[X],Nb):- Nb is 1.
nb_comm([X|L],[X|M],Nb):-!,nb_comm(L,M,Nbs),Nb is Nbs +1.
nb_comm([_|L],[_|M],Nb):-nb_comm(L,M,Nb).

mais ça me rend rien

[Trap D]

Ben tu y es presque :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
construit_mystere([A,B,C,D,E]):-
	lettre1(Lettre1),
	lettre2(Lettre2),
	lettre3(Lettre3),
	lettre4(Lettre4),
	lettre5(Lettre5),
	member(A,Lettre1),
	member(B,Lettre2),
	member(C,Lettre3),
	member(D,Lettre4),
	member(E,Lettre5),
	% tu dois maintenant tester ton mot par rapport aux contraintes
        forall(mots(L, Nb), (let_comm(Mot, L, L1), .............)).
.

C'est pratiquement fini

[sirius911]

Hourra
j'étais entrain d'écrire un mot de découragement me traitant de nulle etc quand d'un seul coup j'ai repéré que dans le dernier prédicat j'avais omis une majuscule...
ça marche avec

Code :

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

1
2
go(MotMystere):-construit_mystere(MotMystere),
	forall(mots(Mots,Nb),(nb_comm(MotMystere,Mots,Nb_Commun),Nb = Nb_commun)).

par contre j'ai triché car pour les prédicats lettrei(R) je n'ai pas mis le mot "interdit" :

Code :

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

lettre1(R):-findall(X,mots([X|_]),R).

mots/1

mots([c,r,e,p,i]).
mots([t,r,o,i,s]).
mots([f,e,r,m,e]).
%mots([e,c,r,o,u]).
mots([s,o,m,m,e]).

par contre pour nb_comm :

Code :

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

1
2
3
4
nb_comm([],[],0).
nb_comm([X],[X],Nb):- Nb is 1.
nb_comm([X|L],[X|M],Nb):-!,nb_comm(L,M,Nbs),Nb is Nbs +1.
nb_comm([_|L],[_|M],Nb):-nb_comm(L,M,Nb).

j'ai ma base avec le mot interdit : mots/2

Code :

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

1
2
3
4
5
mots([c,r,e,p,i],1).
mots([t,r,o,i,s],2).
mots([f,e,r,m,e],1).
mots([e,c,r,o,u],0).
mots([s,o,m,m,e],1).

comment j'aurais pu mettre le mots interdit dans les prédicats lettrei(R)??

sinon ça marche (je venge les blondes !!)
j'ai moins de mots que toi ?!?!

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
?- go(Mot).

Mot = [c, e, m, i, s] ;

Mot = [t, e, m, p, s] ;

Mot = [t, e, m, i, i] ;

Mot = [f, o, e, i, s] ;

Mot = [f, o, o, p, s] ;

Mot = [f, o, o, i, i] ;

Mot = [s, e, e, i, s] ;

Mot = [s, e, o, p, s] ;

Mot = [s, e, o, i, i] ;

[Trap D]

pour le findall :

Code :

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

lettre1(R):-findall(X,(mots([X|_],Nb), Nb > 0),R).

Celà t'assurait que tu n'avais que les bonnes lettres.

Pour ma part, je l'ai fait comme ceci :

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
mot_mystere(M) :-
	%mots(L, _),
	%length(L, NbL),
	%NbL1 is NbL-1,
	%lettres_possibles(NbL1, [], L1),
	lettres_possibles(4, [], L),
	mot_possible(L, M).
 
mot_possible(LC, M) :-
	maplist(member, M, LC),
	test(M).
 
test(M) :-
	forall(mots(L, Nb), let_comm(M, L, Nb)).
 
 
let_comm([],[],0).
 
let_comm([X|L],[X|M],N1):-
	!,
	let_comm(L,M,N),
	N1 is N + 1.
 
let_comm([_|L],[_|M],R):-
	let_comm(L,M,R).
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
lettres_possibles( -1, L, L):- !.
 
lettres_possibles(N, L, L1):-
	collect(N, H),
	N1 is N - 1,
	lettres_possibles(N1, [H | L], L1).
 
 
get_lettre(N, L) :-
	mots(LL, Nb),
	Nb > 0,
	nth0(N, LL, L),
	mots(LL1, 0),
	forall(member(L1, LL1), L1\= L).
 
collect(N, H) :-
	setof(L, get_lettre(N, L), H).

Pour la petite histoire, je te donnes le code de Markus Triska que je te conseille d'étudier, il utilise sa librairie de contraintes :

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
:- use_module(library(clpfd)).
triska :-
	time((mot(Ms, Bs), maplist(label,Bs), format(Ms), nl, false)).
 
 
communes(Xs, Ys, N, Bs) :-
           maplist(commune, Xs, Ys, Bs),
           sum(Bs, #=, N).
 
commune(X, Y, B) :- X #= Y #<==> B.
 
mot(Ms, Bs) :-
           length(Ms, 5),
           Ms ins 0'a..0'z,
           maplist(communes(Ms), ["crépi","trois","ferme", "somme"],
                                 [   1,      2,      1,       1],
                                 Bs),
           maplist(all_neq(Ms), "écrou").
 
all_neq(Ms, L) :- maplist(#\=(L), Ms).

Enfin, un autre code très compact, du à Bart Deomen :

Code :

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

1
2
3
4
5
6
7
8
9
10
bart(L) :-
        length(L,5),
        maplist(same(L),[1,2,1,1],
                [[c,r,é,p,i],[t,r,o,i,s],[f,e,r,m,é],[s,o,m,m,e]]),
        \+((member(X,L),member(Y,[é,c,r,o,u]),X==Y)).
 
 
same([],N,[]) :- N == 0.
same([X|R],N,[X|S]) :- M is N - 1, same(R,M,S).
same([_|R],N,[_|S]) :- same(R,N,S).

Je te cite :

s'il y a des gens partants pour m'aider avec plaisir..

[sirius911]

Merci beaucoup Trap D
Ca m'a fait progressé ...
j'ai commencé à regarder le code de Markus Triska mais c'est super compliqué ...
j'ai pas encore bien compris les maplist, tant qu'aux librairies de contraintes ...
n'oublie pas que je suis blonde !!
biz
merci encore

[Trap D]

Avant de commencer les contraintes, regarde bien l'utilisation des maplist, c'est important.

n'oublie pas que je suis blonde !!

Avec des gros ...