---
# System prepended metadata

title: TP Prolog - s07 - ISC IL 3a
tags: [prolog]

---

###### tags: `prolog`

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

## Exercice 1
```prolog=
transition(jugs(contents(_,Vb), C, T), empty(a), 
    jugs(contents(0, Vb),C, T)).
transition(jugs(contents(Va,_), C, T), empty(b), 
    jugs(contents(Va, 0),C, T)).
transition(jugs(contents(_, Vb), capacity(A, B), T), fill(a), 
    jugs(contents(A, Vb), capacity(A, B), T)).
transition(jugs(contents(Va, _), capacity(A, B), T), fill(b), 
    jugs(contents(Va, B), capacity(A, B), T)).

transition(jugs(contents(Va, Vb), capacity(Ca, Cb), T), 
    transfer(a, b), jugs(contents(A, B), capacity(Ca, Cb), T)) :-
        RemainingCapacity is Cb - Vb,
        A is max(Va - RemainingCapacity, 0),
        B is min(Va + Vb, Cb).

transition(jugs(contents(Va, Vb), capacity(Ca, Cb), T), 
    transfert(b, a), jugs(contents(A, B), capacity(Ca, Cb), T)) :-
        RemainingCapacity is Ca - Va,
        B is max(Vb - RemainingCapacity, 0),
        A is min(Va + Vb, Ca).
```

### Output : 
La première solution est correcte mais n'est pas optimale étant donné qu'on remplis a pour le vider juste après.
```!
| ?- > go(M).
solveStateProblem(jugs(8,5,7),_279)

M = [fill(a), fill(b), empty(a), transfert(b,a), fill(b), transfert(b,a), empty(a), transfert(b,a), fill(b), transfert(b,a)] ? 
```

## Exercice 2
```prolog=
initialState(cannibals(N, Cap), cannib(left, left(N,N), right(0,0), 
        capacity(Cap))).

finalState(cannib(right, left(0,0), _,_)).

% M should not be less than C on a bank
legalStateBank(0, _).
legalStateBank(M, C) :-
    M >= C .

legalState(cannib(_, left(LM, LC), right(RM, RC), _)) :-
    legalStateBank(LM, LC),
    legalStateBank(RM, RC).

% Move left to right
transition(cannib(left, left(LM, LC), right(RM, RC),capacity(Cap)), 
        move(NM, NC),
        cannib(right, left(LM1, LC1), right(RM1, RC1), capacity(Cap))) :-
    nbBetween(0, LM, NM),
    NM =< Cap,
    nbBetween(0, LC, NC),
    NC =< Cap - NM,
    (NM + NC) > 0,
    LM1 is LM - NM,
    LC1 is LC - NC,
    RM1 is RM + NM,
    RC1 is RC + NC.

% Move right to left
transition(cannib(right, left(LM, LC), right(RM, RC),capacity(Cap)), 
        move(NM, NC),
        cannib(left, left(LM1, LC1), right(RM1, RC1), capacity(Cap))) :-
    nbBetween(0, RM, NM),
    NM =< Cap,
    nbBetween(0, RC, NC),
    NC =< Cap - NM,
    (NM + NC) > 0,
    LM1 is LM + NM,
    LC1 is LC + NC,
    RM1 is RM - NM,
    RC1 is RC - NC.
```

### Output : 
```!
| ?- > go(M).
solveStateProblem(cannibals(3,2),_279)

M = [move(0,2),move(0,1),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(0,1),move(0,2)] ? > a
a

M = [move(0,2),move(0,1),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(0,1),move(0,2)]

M = [move(0,2),move(0,1),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(1,0),move(1,1)]

M = [move(0,2),move(0,1),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(1,0),move(1,1)]

M = [move(1,1),move(1,0),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(0,1),move(0,2)]

M = [move(1,1),move(1,0),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(0,1),move(0,2)]

M = [move(1,1),move(1,0),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(1,0),move(1,1)]

M = [move(1,1),move(1,0),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(1,0),move(1,1)]

(1 ms) no
```

## Exercice 3

```prolog=
bfs(n(S,Ms), Queue, History, Moves) :-   
    findall(n(S1,[M|Ms]), transition(S,M,S1), Ls),
    enqueueRelevantNodes(Ls, History, Queue, Queue1), 
    fifo_apply(Queue1, dequeue(NextNode), Queue2),
    bfs(NextNode, Queue2, [S|History], Moves).

enqueueRelevantNodes([], _, Queue, Queue).

enqueueRelevantNodes([Node|Ls], History, Queue, Queue2) :- 
    Node = n(S,_Ms),
    legalState(S),
    \+ member(S, History),
    !,
    fifo_apply(Queue, enqueue(Node), Queue1), 
    enqueueRelevantNodes(Ls, History, Queue1, Queue2).

```

### Output ex1
Si on relance maintenant l'exercice 1 en ajoutant le prédicat goBfs ainsi pour utiliser ce qui a été fait dans l'exercice 3 : 
```prolog=
goBfs(M) :-
    Goal=solveBfs(jugs(8,5,7), M),
    write(Goal), nl,
    Goal.
```

On obtient : 
```!
| ?- > goBfs(M).
solveBfs(jugs(8,5,7),_279)

M = [fill(b), transfert(b,a), fill(b), transfert(b,a), empty(a), transfert(b,a), fill(b), transfert(b,a)] ?
```
Ce qui est bien plus court que l'output de l'exercice 1.

### Output ex2
Si on relance maintenant l'exercice 2 en ajoutant le prédicat goBfs ainsi pour utiliser ce qui a été fait dans l'exercice 3 : 
```prolog=
goBfs(M) :-
    Goal=solveBfs(cannibals(3, 2), M),
    write(Goal), nl,
    Goal.
```

On obtient : 
```!
| ?- > goBfs(M).
solveBfs(cannibals(3,2),_279)

M = [move(0,2),move(0,1),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(0,1),move(0,2)] ? > a
a

M = [move(0,2),move(0,1),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(1,0),move(1,1)]

M = [move(1,1),move(1,0),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(0,1),move(0,2)]

M = [move(1,1),move(1,0),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(1,0),move(1,1)]

(1 ms) no
```
On peut voir qu'il n'y a plus de doublon.