Discussion :

[Montaigne]

Bonjour, peut être savez vous que certains légumes sont de "bon voisins" et d'autres non (l'ail n'apprécie pas le voisinage du chou, mais celui de la carotte).

Je me suis dis que prolog serait parfait pour généraliser une solutions : je lui donne une liste de légume à cultiver, il me renvoi une liste de légumes ordonnée de sorte que les légumes soient tous en bon voisinage.

J'imagine le prédicat solution comme suit :

Code :

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

solution(ListeInitiale,ListeOrdonnee,Rebus)

où ListeInitiale est la liste de légume qu'on lui donne, ListeOrdonnee le résultat qu'on cherches, et Rebus une liste éventuelle de légume qu'on arrive pas à placer.

Je fais du prolog une fois tous les 5 ans, j'ai essayé de coder ça...

Code :

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

1
2
3
4
5
6
7
 
like(laitue,chou).
notlike(tomate,chou).
like(ail,carotte).
notlike(carotte,aneth).
like(oignon, carotte).
/* source http://www.gerbeaud.com/jardin/fiches/legumes-bons-voisins.php */

Ma tentative :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
solution([],[],[]).
solution([A,B],[A,B],[]) :- like(A,B).
solution([A,B],[],[A,B])    :- notlike(A,B).
 
 
solution([A,B,C], [A,B,C],[]) :- like(A,B), notlike(A,C), like(B,C).
solution([A,B,C], [], [A,B,C]) :- like(A,B), notlike(A,C), notlike(B,C).
 
solution([A,B,C], [], [A,B,C]) :- notlike(A,B), notlike(A,C).
 
solution([A,B,C], [A,C,B], []) :- like(A,C), notlike(A,B), like(B,C).

Je me disais qu'en passant à 3 paramètre, j'arriverai à généraliser, bref, faire la récurrence, mais là je sèche !

Je sais que je dois faire un truc du style Tete|Queue (comme en OCaml avec t::q ), mais je vois pas comment réordonner la liste...

[Trap D]

Bonjour

Pour mieux comprendre le problème, quel est le résultat attendu avec les données de départ :

Code :

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

1
2
3
4
5
like(laitue,chou).
notlike(tomate,chou).
like(ail,carotte).
notlike(carotte,aneth).
like(oignon, carotte).

[Montaigne]

Bonjour

Pour mieux comprendre le problème, quel est le résultat attendu avec les données de départ :

Code :

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

1
2
3
4
5
6
like(laitue,chou).
notlike(tomate,chou).
like(ail,carotte).
notlike(carotte,aneth).
like(oignon, carotte).
like(oignon,tomate).%rajout

Bonjour,

Premièrement, les relations 'like' et 'notlike' sont commutatives.

Je me suis rendu compte que c'est un peu plus compliqué :
le prédicat solution doit seulement éviter les plantes qui ne s'aiment pas. Si on a pas d'information entre deux plantes, alors elles peuvent être voisines.

Exemple sur des plante ou j'ai pas d'info like ou notlike :

Code :

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

1
2
3
4
 
?- solution([laitue,carotte,tomate],B,C).
B = [laitue, carotte, tomate],
C = []

Pour obtenir cette solution, j'ai écris :

Code :

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

solution([A,B,C], [A,B,C],[]) :- \+ notlike(A,B), \+ notlike(A,C), \+ notlike(B,C).

En gros, si l'on ne peut pas prouver que les 3 légumes ne s'aiment pas, alors ils peuvent être voisins.

Un exemple en grandeur nature de ce que je cherche à faire, ça donnerai :

Code :

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

1
2
3
?- solution([laitue , tomate, chou, carotte, oignon],Res, Rebus).
Res = [laitue, chou, carotte, oignon, tomate],
Rebus = []

Car la tomate n'aime pas le chou mais aime l'oignon. L'oignon aime la carotte. Donc on éloigne la tomate du chou et on met l'oignon entre la carotte et la tomate...

C'est plus clair comme ça ?

[Trap D]

Si j'ai bien suivi le raisonnement, il faut qu'il y ait au moins 2 légumes "neutres" entre deux légumes qui ne s'aiment pas, c'est ça ?
Dans ce cas, on peut faire comme ça, ça ne fonctionne que s'il y a au moins trois légumes qui peuvent s'entendre. Fonctionne avec SWI-Prolog

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
like(laitue,chou).
like(ail,carotte).
like(oignon, carotte).
like(oignon,tomate).%rajout
 
notlike(tomate,chou).
notlike(carotte,aneth).
 
% on introduit la commutativité
incompatibles(X, Y) :-
	notlike(X,Y); notlike(Y, X).
 
 
 
solution(L, Rebut) :-
	% constitution de la liste des légumes
	bagof([X,Y], like(X,Y), L1),
	bagof([X,Y], notlike(X,Y), L2),
	flatten([L1|L2], LF),
	% cree une liste sans doublons
	sort(LF, Lst),
	cree_liste(Lst, L, Rebut).
 
% on initialise la liste avec deux éléments non incompatibles
cree_liste(Lst, L, Rebut) :-
	select(Elem1, Lst, Lst1),
	select(Elem2, Lst1, Lst2),
	\+incompatibles(Elem1,Elem2),
	cree_liste(Lst2, [Elem1, Elem2], L, Rebut).
 
% derniers elements de la liste des légumes
cree_liste([X, Y], [H | T], L, Rebut) :-
	(   (\+incompatibles(X,H), \+incompatibles(Y, H), \+incompatibles(X,Y))
	->  L = [X, Y, H | T], Rebut = []
	;   L = [H | T], Rebut = [X, Y]).
 
% on parcourt la liste des legumes, et on apparie
cree_liste(Lst, [H1, H2 | T], L, Rebut) :-
	select(Elem, Lst, Lst1),
	\+incompatibles(Elem,H1),\+incompatibles(Elem,H2),
	(   cree_liste(Lst1, [Elem, H1, H2 | T], L_, Rebut_)
	->  L = L_, Rebut = Rebut_
	;   L = [H1, H2 | T], Rebut = Lst).

Je ne m'interesse qu'aux impossibilités entre légumes, si on veut privilégier les "like" on peut créer un prédicat possible/2.

Pour avoir toutes les solutions sans rebut on peut faire

Code :

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

 setof(L, solution(L,[]), Solution), maplist(writeln, Solution).

Pour les solutions avec rebut

Code :

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

setof([L,Y], (solution(L,Y), Y \= []), Solution), maplist(writeln, Solution).

[Montaigne]

Si j'ai bien suivi le raisonnement, il faut qu'il y ait au moins 2 légumes "neutres" entre deux légumes qui ne s'aiment pas, c'est ça ?

En fait, un seul neutre suffit (je me suis mal exprimé)

Dans ce cas, on peut faire comme ça, ça ne fonctionne que s'il y a au moins trois légumes qui peuvent s'entendre. Fonctionne avec SWI-Prolog

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
like(laitue,chou).
like(ail,carotte).
like(oignon, carotte).
like(oignon,tomate).%rajout
 
notlike(tomate,chou).
notlike(carotte,aneth).
 
% on introduit la commutativité
incompatibles(X, Y) :-
	notlike(X,Y); notlike(Y, X).
 
 
 
solution(L, Rebut) :-
	% constitution de la liste des légumes
	bagof([X,Y], like(X,Y), L1),
	bagof([X,Y], notlike(X,Y), L2),
	flatten([L1|L2], LF),
	% cree une liste sans doublons
	sort(LF, Lst),
	cree_liste(Lst, L, Rebut).
 
% on initialise la liste avec deux éléments non incompatibles
cree_liste(Lst, L, Rebut) :-
	select(Elem1, Lst, Lst1),
	select(Elem2, Lst1, Lst2),
	\+incompatibles(Elem1,Elem2),
	cree_liste(Lst2, [Elem1, Elem2], L, Rebut).
 
% derniers elements de la liste des légumes
cree_liste([X, Y], [H | T], L, Rebut) :-
	(   (\+incompatibles(X,H), \+incompatibles(Y, H), \+incompatibles(X,Y))
	->  L = [X, Y, H | T], Rebut = []
	;   L = [H | T], Rebut = [X, Y]).
 
% on parcourt la liste des legumes, et on apparie
cree_liste(Lst, [H1, H2 | T], L, Rebut) :-
	select(Elem, Lst, Lst1),
	\+incompatibles(Elem,H1),\+incompatibles(Elem,H2),
	(   cree_liste(Lst1, [Elem, H1, H2 | T], L_, Rebut_)
	->  L = L_, Rebut = Rebut_
	;   L = [H1, H2 | T], Rebut = Lst).

Je ne m'interesse qu'aux impossibilités entre légumes, si on veut privilégier les "like" on peut créer un prédicat possible/2.

Pour avoir toutes les solutions sans rebut on peut faire

Code :

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

 setof(L, solution(L,[]), Solution), maplist(writeln, Solution).

Pour les solutions avec rebut

Code :

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

setof([L,Y], (solution(L,Y), Y \= []), Solution), maplist(writeln, Solution).

J'aurai clairement pas été capable de faire ça, je vais patiemment analyser ce code, merci !