Discussion :

[cLaSic]

Bonjour,
Je voudrai écrire un programme en prolog qui retourne le meilleur coup.

En entrée : +une liste de nombres de 1 à 12
+un nombre de 1 à 12
En sortie : -une liste de nombres de 1 à 12

Je m'explique:
on a en entrée une liste de nombres de 1 à 12 qu'on appellera L, et un nombre lui aussi de 1 à 12 qu'on appellera X,
le but c'est de déterminer le plus grand enchainement commençant par le nombre X et choisissant après les nombre de la liste L.
on peut enchainer B par nombre A s'il suit B (par exemple si le nombre B=3 alors on peut l'enchainer par 2 ou 4. si B=12 on peut l'enchainer par 11 ou 1 ... etc).

si on a en entrée une liste L=[3,9,8,1,4,2] et un nombre X=2 alors les enchainements possibles à partir du nombre X sont :
2 3 4 ou
2 3 2 1 ou
2 1 2 3 4.

et le programme doit nous retourner le plus long enchainement (dans notre cas : 2 1 2 3 4)
----------------------- voila ce que j'ai fais --------------------

Code :

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

1
2
3
4
5
6
7
8
 
test([A|L],E,M):-
    E+1=\=A,
    E-1=\=A,
    test(L,E,M).
test([A|L],E,[E,A|G]):-
    (E+1=:=A;E-1=:=A),
    test(L,A,G).

------------------ Mais ca ne marche pas car je ne suis pas pro en prolog

All hints are welcome

[Trap D]

Ça ne serait pas plus pratique si la liste d'entrée était triée ?

[Trap D]

Je viens de regarder un peu ton problème, d'après moi, si j'ai bien compris ..., la plus longue liste serait 2 3 4 3 2 1, y a-til un ordre pour balayer la liste fournie en entrée, ou ne doit-on utiliser qu'une seule fois les nombres de la liste ?

[Trap D]

J'ai pu extraire la sous liste de nombres consécutifs avec ce principe:
je trie la liste d'entrée en y insérant le nombre en entrée
j'extrait la sous liste de nombres consécutifs contenant le nombre en entrée
je fais deux recherches supplémentaires pour tenir compte de la contrainte de continuité entre 12 et 1.
Je te laisse réfléchir à cette méthode.

[cLaSic]

Je viens de regarder un peu ton problème, d'après moi, si j'ai bien compris ..., la plus longue liste serait 2 3 4 3 2 1, y a-til un ordre pour balayer la liste fournie en entrée, ou ne doit-on utiliser qu'une seule fois les nombres de la liste ?

Au fait on doit utiliser qu'une seule fois les nombres de la liste, et la plus longue liste est 2 1 2 3 4.

[cLaSic]

J'ai pensé à une autre méthode mais je ne sais pas si elle est meilleur que la tienne :
-je sélectionne un elem E de la liste L et je regarde s'il suit l'elem X c-à-d si X+1==E OU X-1==E, et je le rajoute à une liste résultat ...

Code :

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

1
2
3
4
5
6
 
test(L,E,M):-
   select(X,L,N),
   (E+1=:=X;E-1=:=X),
   M=[E,X|R],
   test(N,X,R).

27 ?- test([3,9,8,1,4,2],2,M).

No

Grrrrrr

Mais comme d'hab il me manque un coup de pouce

[Trap D]

Je pense que tu dois décomposer ta recherche en deux parties, les nombres plus grands et les nombres plus petits.
Le petit "coup de pouce":

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
test(L,E, M):-
        % la liste résultat contient forcément le nombre recherché
	recherche_plus_grand(L, E, [E], M1),
	recherche_plus_petit(......).
 
% arg1 : la liste de recherche des nombres 
% arg 2 : le nombre dont on cherche les successeurs
% arg 3 : la liste des nombres consécutifs en construction
% arg 4 : la liste résultat
recherche_plus_grand(L, E, M, N) :-
   E2 is E + 1,
   % Si on atteint 13 il faur repartir à 1
   (   E2 = 13 -> E1 = 1; E1 = E2),
   % le nombre est-il dans la liste ?
   member(E1,L), !,
   % si oui on ajoute à la liste dejà formée le nouveau nombre
   % et on continue
   recherche_plus_grand(L,E1,[E1 | M], N).
 
% on n'a plus de nombre, donc on identifie la liste
% en construction à la liste finale
recherche_plus_grand(_, _, M,M).

[cLaSic]

J'ai complété mais il y a un problème quand on dépasse les bornes (12 ou 1):

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
 
test(L,E, M):-
        % la liste résultat contient forcément le nombre recherché
  recherche_plus_grand(L, E, [E], M1),
  recherche_plus_petit(L, E, [E], M2),
  append(M1,M2,M).
 
 
recherche_plus_grand(L, E, M, N) :-
   E2 is E + 1,
   (   E2 = 13 -> E1 = 1; E1 = E2),
   member(E1,L), !,
   recherche_plus_grand(L,E1,[E1 | M], N).
 
recherche_plus_grand(_, _, M,M).
 
recherche_plus_petit(L, E, M, N) :-
   E2 is E - 1,
   (   E2 = 0 -> E1 = 12; E1 = E2),
   member(E1,L), !,
   recherche_plus_petit(L,E1,[E1 | M], N).
 
recherche_plus_petit(_, _, M,M).

12 ?- test([3,4,1,5,4,2,12,1,2],2,M).

M = [5, 4, 3, 2, 12, 1, 2]

[Trap D]

ben j'ai sans doute mal compris ce que tu voulais, je croyais qu'il devait y avoir continuité entre 1 et 12.
Maintenant, il te reste à extraire la plus longue sous liste avec ces données en partant de 2.

[cLaSic]

ben j'ai sans doute mal compris ce que tu voulais, je croyais qu'il devait y avoir continuité entre 1 et 12.
Maintenant, il te reste à extraire la plus longue sous liste avec ces données en partant de 2.

Effectivement il doit y avoir continuité entre 1 et 12 mais pas entre 12 et 2.

Code :

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

1
2
3
12 ?- test([3,4,1,5,4,2,12,1,2],2,M).
 
M = [5, 4, 3, 2, 12, 1, 2]

Dans ce cas je doit obtenir comme résultat final : [2 1 12 1 2 3 4 5] comme la plus langue liste.

[Trap D]

Décidément, je ne comprends rien, car d'après ta liste en entrée
[3,4,1,5,4,2,12,1,2], triée elle donne [1,1,2,2,3,4,4,5,12]
Si on commence par 2, on peut faire
2, 1, 12, 1, 2, 3, 4, 5, 4

J'ai aussi une question, le nombre choisi pour débuter (le deuxième argument du prédicat), est-il ajouté à la liste ?
Car sinon, avec ces entrées L=[3,9,8,1,4,2] et un nombre X=2 , la plus longue suite est 2 3 4 car 2 ne figure pas 2 fois dans la liste.

Il faudrait que tu donnes en détails les conditions à respecter pour l'obtention de la suite.

[cLaSic]

Décidément, je ne comprends rien, car d'après ta liste en entrée
[3,4,1,5,4,2,12,1,2], triée elle donne [1,1,2,2,3,4,4,5,12]
Si on commence par 2, on peut faire
2, 1, 12, 1, 2, 3, 4, 5, 4

J'ai aussi une question, le nombre choisi pour débuter (le deuxième argument du prédicat), est-il ajouté à la liste ?
Car sinon, avec ces entrées L=[3,9,8,1,4,2] et un nombre X=2 , la plus longue suite est 2 3 4 car 2 ne figure pas 2 fois dans la liste.

Il faudrait que tu donnes en détails les conditions à respecter pour l'obtention de la suite.

Oui effectivement la plus langue liste est 2, 1, 12, 1, 2, 3, 4, 5, 4 , j'ai oublié le dernier 4
sinon pour ta deuxième question la réponse est oui, on ajoute le deuxième argument à la liste en entrée.
Et avec ces entrées L=[3,9,8,1,4,2] et un nombre X=2 , la plus longue suite est 2,1,2,3,4

[Trap D]

Voilà un bout de code qui fait ce que j'ai compris de ce que tu cherches

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
 
test(L,E, R):-
	exploration_haut(L, E, [E], M4),
	exploration_bas(L, E, [E], M5),
	length(M4, N4),
	length(M5, N5),
	(   N4 > N5 -> reverse(M4, R); reverse(M5, R)).
 
exploration_haut(M, E, LT, L) :-
	E2 is E + 1,
	(E2 = 13 -> E1 = 1; E1 = E2),   
	select(E1, M, M1), !,
	exploration_haut(M1, E1, [E1 | LT], L).
 
exploration_haut(M, E, LT, L) :-
	E2 is  E - 1,
	(   E2 = 0 -> E1 = 12; E1 = E2),
	member(E1, M), !,
	exploration_bas(M, E, LT, L).
 
exploration_haut(_M, _E, L, L).
 
exploration_bas(M, E, LT, L) :-
	E2 is E - 1,
	(E2 = 0 -> E1 = 12; E1 = E2),   
	select(E1, M, M1), !,
	exploration_bas(M1, E1, [E1 | LT], L).
 
 
exploration_bas(M, E, LT, L) :-
	E2 is E + 1,
	(   E2 = 13 -> E1 = 1; E1 = E2),
	member(E1, M), !,
	exploration_haut(M, E, LT, L).
 
exploration_bas(_M, _E, L, L).
 
 
essai :-
	test([3,9,8,1,4,2, 11, 12], 2, X3),
	format('Entrée ~w ~w  Sortie ~w~n', [[3,9,8,1,4,2, 11, 12], 2, X3]),
	writeln('*********************************'),
	test([3,4,1,5,4,2,12,1,2],2,M),
	format('Entrée ~w ~w  Sortie ~w~n', [[3,4,1,5,4,2,12,1,2], 2, M])
	.

Sortie

44 ?- essai.
Entrée [3, 9, 8, 1, 4, 2, 11, 12] 2 Sortie [2, 1, 12, 11]
*********************************
Entrée [3, 4, 1, 5, 4, 2, 12, 1, 2] 2 Sortie [2, 1, 12, 1, 2, 3, 4, 5, 4]

Le code est balancé sans commentaire, donc n'hésite pas à poser des questions si tu ne comprends pas.

[cLaSic]

WaW. ça répond parfaitement à ma question ... je regarde le code et je te dirai si j'ai pas compris quelque chose ...
Merci je rêve du jour où je serai pro comme toi.
Franchement prolog est Génial

[Trap D]

Franchement prolog est Génial

Ça je suis parfaitement d'accord avec toi !

[cLaSic]

Et avec quelques lignes de code, tu peut créer un miracle . ah oui la récursivité fait le boulot.