###### tags: `prolog`

# TP Prolog - s06 - ISC IL 3a
## Baudin Valentin et Braillard Simon

## Exercice 1
### Etudier le programme Hanoi ci-dessous. Les appels solve1 et solve2 seront-ils traités
#### (i) correctement ?
`solve1` et `solve2` sont traités correctement.
#### (ii) efficacement ?
`solve2` est efficace, mais pas `solve1`, car `solve1` n'utilise pas les `asserta` et `retract`. Par conséquent, la programmation dynamique n'est pas utilisée.

## Exercice 2
### Expliquer clairement ce que réalise le prédicat organize/2 et comment fonctionne tout ce programme, p. ex. en spécifiant chaque prédicat.

`elt/1` : Le prédicat utilisé pour stocker une valeur.

`convert/2` : Converti une valeur sour la forme `elt/1`.

`enrich/1` : Ajoute une variable dans les variables glopbales avec le `asserta`.

`wrap/1` : Récupère les éléments stockés

`add` : Compare l'élement reçu avec les éléments stockés :
- Si aucun élément est actuellement stocké, stocke l'élément reçu `X`.
- Si l'élément stocké `Y` est plus petit que l'élément reçu `X`, `Y` est enlevé des variables globales et `X` est ajouté dans `Gs` qui est la liste des éléments plus petit que `X`. Le cut permet d'arrêter de vérifer lorsque `Y` est plus grand ou égal à `X`.
- Si l'élément stocké `Y` n'est pas plus petit que l'élément reçu `X`, stocke `X` dans les variables globales.

`organize` : Stocke les éléments de la liste reçue. Lorsque la liste est vide, retourne une liste triée avec les éléments stockés.

## Exercice 3
### a)

fol([], _, A, Res) :- Res is A.
fol([E|Ls], Op, Crt, Res) :-
    Crt1 =.. [Op, Crt, E],
    fol(Ls, Op, Crt1, Res).

Ce prédicat prend 3 paramètres en entrée et 1 en sortie. Les 3 entrées sont, dans l'ordre, un tableau, un operateur, un nombre et retourne un nombre. Ce prédicat permet d'effectuer une opération sur toutes les valeurs d'un tableau et sur une valeur entrée hors du tableau. Par exemple, la question `fol([1, 2, 3, 4], +, 0, A).` fera la somme des valeurs des tableau à laquelle elle ajoute 0 au début. On obtient donc 10. La question `fol([1, 2, 3, 4], *, 1, A).` multiplie 1 et la première valeur du tableau puis multiplie le résultat à chaque autre valeur du tableau et retourne donc 24.

### b)
Le seul moyen que nous avons trouvé pour ajouter un `is` dans ce prédicat est de supprimer le `is` du cas de base et d'en ajouter un autre dans le cas générique.

fol([], _, A, A).
fol([E|Ls], Op, Crt, Res) :-
    Crt1 =.. [Op, Crt, E],
    Crt2 is Crt1,
    fol(Ls, Op, Crt2, Res).

## Exercice 4

%--- fromAdjacencyMatrix(+Gr). Gr = graph(GraphName, AdjMatrix) 
fromAdjacencyMatrix(Gr) :-
     Gr = graph(Nanme, Matrix),
     length(Matrix, Length),
     asserta(graphOrder(Name, Length)),
     findall(X, anEdge(Gr), _).

%--- anEdge(Gr): an edge is asserted as a fact.
anEdge(Gr):-
    Gr = graph(Name, Matrix),
    nth(From, Matrix, Es),
    nth(To, Es, Weight),
    nonvar(Weight),
    asserta(edge(Name, From, To, Weight)).

### Output

| ?- > fromAdjMatrixDemo.


yes
| ?- > listing.

% file: /Users/simonbraillard/development/intelliJ_workspace/tp-prolog/tp-prolog/src/s06/dyn.pl

hanoiDyn(1, _, _, _, 1.0).
hanoiDyn(A, B, C, D, E) :-
	A > 1,
	F is A - 1,
	hanoiDyn(F, B, D, C, G),
	asserta((hanoiDyn(F, B, D, C, G) :- !)),
	hanoiDyn(F, D, C, B, H),
	retract((hanoiDyn(F, B, D, C, _) :- !)),
	E is G + H + 1.

solve1(A, B) :-
	[C, D, E] = [a, b, c],
	hanoiDyn(A, C, D, E, B).

solve2(A, B) :-
	hanoiDyn(A, C, D, E, B),
	[C, D, E] = [a, b, c].

organize([A|B], C) :-
	add(A, []),
	organize(B, C).
organize([], A) :-
	wrap(A).

wrap([A|B]) :-
	elt(A),
	convert(A, C),
	retract(C), !,
	wrap(B).
wrap([]).

add(A, B) :-
	elt(C),
	C < A,
	convert(C, D),
	retract(D), !,
	add(A, [D|B]).
add(A, B) :-
	convert(A, C),
	enrich([C|B]).

enrich([]).
enrich([A|B]) :-
	asserta(A),
	enrich(B).


convert(A, elt(A)).

fol([], _, A, A).
fol([A|B], C, D, E) :-
	F =.. [C, D, A],
	G is F,
	fol(B, C, G, E).

edge(g1, 4, 2, 7).
edge(g1, 3, 4, 8).
edge(g1, 3, 1, 1).
edge(g1, 2, 3, 5).
edge(g1, 1, 4, 2).
edge(g1, 1, 3, 3).
edge(g1, 4, 2, 7).
edge(g1, 3, 4, 8).
edge(g1, 3, 1, 1).
edge(g1, 2, 3, 5).
edge(g1, 1, 4, 2).
edge(g1, 1, 3, 3).

graphOrder(_, 4).
graphOrder(_, 4).

fromAdjacencyMatrix(A) :-
	A = graph(_, B),
	length(B, C),
	asserta(graphOrder(_, C)),
	findall(_, anEdge(A), _).

anEdge(A) :-
	A = graph(B, C),
	nth(D, C, E),
	nth(F, E, G),
	nonvar(G),
	asserta(edge(B, D, F, G)).

fromAdjMatrixDemo :-
	A = [[_, _, 3, 2], [_, _, 5, _], [1, _, _, 8], [_, 7, _, _]],
	fromAdjacencyMatrix(graph(g1, A)).

yes
| ?-