# Exercícios MT2

Exercícios de Prolog, com escolha múltipla, respostas guardadas neste navegador e testes de programação.

Página: https://resumos.rgo.pt/cadeiras/pfl/exercicios-mt2/

## Bases de conhecimento e relações

Nome do autor de um vídeo

Os factos dados representam utilizadores, datas de nascimento, pessoas seguidas e vídeos. Não uses `findall`, `setof`, `bagof` nem bibliotecas SICStus.

Define `video_username(?VideoID, ?Name)`. O vídeo 10 pertence a Alice; Carla tem os vídeos 13 e 14.

```prolog
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

% Define o predicado pedido.

```



### Testes

**Identificador**


```prolog
main :- findall(N, video_username(10,N), L), write_canonical(L), nl.
```


Saída esperada:

```text
['Alice']
```

**Nome**


```prolog
main :- findall(V, video_username(V,'Carla'), L), write_canonical(L), nl.
```


Saída esperada:

```text
[13,14]
```

Solução

```
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

video_username(V, N) :- video(V, U, _, _), user(U, N, _, _).
```

Relaciona os factos pelos identificadores e verifica as condições pedidas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Anos de nascimento ímpares

Os factos dados representam utilizadores, datas de nascimento, pessoas seguidas e vídeos. Não uses `findall`, `setof`, `bagof` nem bibliotecas SICStus.

Define `odd_birthyear(?UserID)`, que sucede quando o ano de nascimento é ímpar. Os resultados são 1, 3, 4 e 5.

```prolog
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

% Define o predicado pedido.

```



### Testes

**Gerar**


```prolog
main :- findall(U, odd_birthyear(U), L), write_canonical(L), nl.
```


Saída esperada:

```text
[1,3,4,5]
```

**Ano par**


```prolog
main :- findall(x, odd_birthyear(2), L), write_canonical(L), nl.
```


Saída esperada:

```text
[]
```

Solução

```
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

odd_birthyear(U) :- user(U, _, _-_-Y, _), 1 =:= Y mod 2.
```

Relaciona os factos pelos identificadores e verifica as condições pedidas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Amizade recíproca

Os factos dados representam utilizadores, datas de nascimento, pessoas seguidas e vídeos. Não uses `findall`, `setof`, `bagof` nem bibliotecas SICStus.

Define `are_friends(?UserID1, ?UserID2)`: cada utilizador segue o outro. A relação é simétrica.

```prolog
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

% Define o predicado pedido.

```



### Testes

**Pares**


```prolog
main :- findall(A-B, are_friends(A,B), L), write_canonical(L), nl.
```


Saída esperada:

```text
[-(1,2),-(1,3),-(2,1),-(3,1)]
```

**Sem reciprocidade**


```prolog
main :- findall(x, are_friends(2,4), L), write_canonical(L), nl.
```


Saída esperada:

```text
[]
```

Solução

```
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

are_friends(A, B) :- user(A, _, _, As), member(B, As), user(B, _, _, Bs), member(A, Bs).
```

Relaciona os factos pelos identificadores e verifica as condições pedidas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Personagens gémeas

Os factos `by(Character, Movie, Actor)` associam personagens, filmes ou séries e atores. Não uses `findall`, `setof`, `bagof` nem bibliotecas SICStus.

Define `plays_twins(?Actor, ?Movie)`, verdadeiro quando o ator interpreta pelo menos duas personagens diferentes no mesmo filme ou série.

```prolog
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

% Define o predicado pedido.

```



### Testes

**Encontrar**


```prolog
main :- findall(A-M, plays_twins(A,M), L), write_canonical(L), nl.
```


Saída esperada:

```text
[-(lisaKudrow,friends),-(lisaKudrow,friends)]
```

**Ausente**


```prolog
main :- findall(x, plays_twins(benAffleck,daredevil), L), write_canonical(L), nl.
```


Saída esperada:

```text
[]
```

Solução

```
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

plays_twins(A, M) :- by(C1, M, A), by(C2, M, A), C1 \= C2.
```

Relaciona os factos pelos campos pedidos, preservando as condições e os resultados distintos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#escolher-a-recolha)

Personagens interpretadas por si mesmas

Os factos `by(Character, Movie, Actor)` associam personagens, filmes ou séries e atores. Não uses `findall`, `setof`, `bagof` nem bibliotecas SICStus.

Define `changeSelf/0`, substituindo cada facto cuja personagem é igual ao ator por um facto com personagem `self`, mantendo filme e ator. Deve sempre suceder. Por exemplo, `by(stephenColbert,dailyShow,stephenColbert)` passa a `by(self,dailyShow,stephenColbert)`.

```prolog
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

% Define o predicado pedido.

```



### Testes

**Substituir**


```prolog
main :- changeSelf, findall(C, by(C,dailyShow,stephenColbert), L), write_canonical(L), nl.
```


Saída esperada:

```text
[self]
```

**Repetir**


```prolog
main :- changeSelf, changeSelf, findall(C, by(C,theColbertReport,stephenColbert), L), write_canonical(L), nl.
```


Saída esperada:

```text
[self]
```

Solução

```
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

changeSelf :- retract(by(A, M, A)), assertz(by(self, M, A)), fail.
changeSelf.
```

Relaciona os factos pelos campos pedidos, preservando as condições e os resultados distintos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#escolher-a-recolha)

Géneros de um livro

Os factos usam `author(ID, Nome, AnoNascimento, País)` e `book(Título, IDAutor, Ano, Páginas, Géneros)`.

Define `book_genre(?Title, ?Genre)`, relacionando um título com cada um dos seus géneros. Não uses `findall/3`, `setof/3`, `bagof/3` nem bibliotecas SICStus.

```prolog
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

% Define aqui o predicado pedido.
```



### Testes

**Vários géneros**


```prolog
main :- findall(G,book_genre('The Shining',G),L),write_canonical(L),nl.
```


Saída esperada:

```text
['Gothic novel','Horror','Psychological horror']
```

**Títulos por género**


```prolog
main :- findall(T,book_genre(T,'Political'),L),write_canonical(L),nl.
```


Saída esperada:

```text
['Under the Dome']
```

Solução

```
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

book_genre(T,G) :- book(T,_,_,_,Gs), member(G,Gs).
```

A pesquisa de `member` percorre os géneros por retrocesso.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Idade ao publicar

Os factos usam `author(ID, Nome, AnoNascimento, País)` e `book(Título, IDAutor, Ano, Páginas, Géneros)`.

Define `author_wrote_book_at_age(?Author, ?Title, ?Age)`. A idade é o ano de publicação menos o ano de nascimento. Por exemplo, The Client foi publicado quando John Grisham tinha 38 anos. Não uses `findall/3`, `setof/3`, `bagof/3` nem bibliotecas SICStus.

```prolog
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

% Define aqui o predicado pedido.
```



### Testes

**Idade**


```prolog
main :- findall(A,author_wrote_book_at_age('John Grisham','The Client',A),L),write_canonical(L),nl.
```


Saída esperada:

```text
[38]
```

**Autor sem livros**


```prolog
main :- findall(T,author_wrote_book_at_age('Wilbur Smith',T,_),L),write_canonical(L),nl.
```


Saída esperada:

```text
[]
```

Solução

```
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

author_wrote_book_at_age(A,T,Age) :- author(I,A,B,_), book(T,I,Y,_,_), Age is Y-B.
```

O identificador liga o autor ao livro; a subtração usa os dois anos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Retirar uma cláusula

```
predZ(R,A,C) :- T =.. [R,_,_], retract((T :- S)), E =.. [R,A,C], E, asserta((T :- S)).
```

Considera `predY/2` com várias cláusulas. O que faz uma chamada `predZ(predY,A,B)`?

Solução

Simula uma chamada a `predY/2` sem considerar a primeira cláusula.

Retira temporariamente a primeira cláusula, chama o predicado e volta a inseri-la após sucesso. Se a chamada falhar, a reinserção não é executada.

*   **Substitui os argumentos da primeira cláusula de `predY/2` pelos argumentos de `predZ/3`..** Esta alternativa não descreve o comportamento apresentado.
*   **Altera a ordem das cláusulas de `predY/2`..** Esta alternativa não descreve o comportamento apresentado.
*   **Altera a ordem dos objetivos de cada cláusula de `predY/2`..** Esta alternativa não descreve o comportamento apresentado.
*   **Simula uma chamada a `predY/2` sem considerar a primeira cláusula..** Retira temporariamente a primeira cláusula, chama o predicado e volta a inseri-la após sucesso. Se a chamada falhar, a reinserção não é executada.
*   **Nada, qualquer chamada a `predZ/3` falha sempre..** Esta alternativa não descreve o comportamento apresentado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Autores de livros

Implementa `book_author(?Title, ?Author)`, relacionando cada título com o nome do autor.

```prolog
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

% book_author(Title, Author).
```



### Testes

**Título**


```prolog
main :- findall(X, (book_author('Carrie',X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
['Stephen King']
```

**Sem livros**


```prolog
main :- findall(X, (book_author(X,'Wilbur Smith')), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

**Autor**


```prolog
main :- findall(X, (book_author(X,'John Grisham')), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
['The Firm','The Client','The Runaway Jury','The Exchange']
```

Solução

```
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

book_author(Title, Author) :- book(Title, ID, _, _, _), author(ID, Author, _, _).
```

O identificador comum liga o livro ao facto do autor.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Contar ingredientes

Cada prato indica o preço em cêntimos e os ingredientes em gramas. Cada ingrediente surge uma vez por prato. Não uses `findall`, `setof`, `bagof` nem bibliotecas para esta questão.

Implementa `count_ingredients(?Dish, ?NumIngredients)`.

```prolog
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

% count_ingredients(Dish, NumIngredients).
```



### Testes

**Todos**


```prolog
main :- findall(X, (count_ingredients(X,3)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[ratatouille]
```

**Pizza**


```prolog
main :- findall(X, (count_ingredients(pizza,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[2]
```

**Inexistente**


```prolog
main :- findall(X, (count_ingredients(nao_existe,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

Solução

```
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

count_ingredients(Dish, N) :- dish(Dish, _, Ingredients), length(Ingredients, N).
```

O comprimento da lista dá a contagem, pois não há ingredientes repetidos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Custo de um ingrediente

Cada prato indica o preço em cêntimos e os ingredientes em gramas. Cada ingrediente surge uma vez por prato. Não uses `findall`, `setof`, `bagof` nem bibliotecas para esta questão.

Implementa `ingredient_amount_cost(?Ingredient, +Grams, ?TotalCost)` em cêntimos.

```prolog
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

% ingredient_amount_cost(Ingredient, Grams, TotalCost).
```



### Testes

**Tomate**


```prolog
main :- findall(X, (ingredient_amount_cost(tomato,350,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[700]
```

**Zero**


```prolog
main :- findall(X, (ingredient_amount_cost(cheese,0,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[0]
```

**Inexistente**


```prolog
main :- findall(X, (ingredient_amount_cost(outro,1,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

Solução

```
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

ingredient_amount_cost(I, G, Cost) :- ingredient(I, Unit), Cost is Unit * G.
```

Multiplica o custo por grama pela quantidade.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Atualizar custo unitário

Cada prato indica o preço em cêntimos e os ingredientes em gramas. Cada ingrediente surge uma vez por prato. Não uses `findall`, `setof`, `bagof` nem bibliotecas para esta questão.

Implementa `update_unit_cost(+Ingredient, +NewUnitCost)`. Atualiza o custo ou cria o ingrediente se não existir; deve ter sucesso.

```prolog
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

% update_unit_cost(Ingredient, NewUnitCost).
```



### Testes

**Existente**


```prolog
main :- update_unit_cost(cheese,8), findall(X,ingredient(cheese,X),Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[8]
```

**Novo**


```prolog
main :- update_unit_cost(flour,3), findall(X,ingredient(flour,X),Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[3]
```

Solução

```
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

update_unit_cost(I, C) :- retractall(ingredient(I,_)), assertz(ingredient(I,C)).
```

Remove os factos anteriores e insere o custo pedido.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Implicação de uma regra

O que exprime logicamente a regra `parent(X,Y) :- mother(X,Y).`?

Solução

Se `mother(X,Y)` é verdadeiro, `parent(X,Y)` é verdadeiro.

O corpo implica a cabeça, mas a regra não afirma a implicação inversa.

*   **Se `parent(X,Y)` é verdadeiro, `mother(X,Y)` tem de ser verdadeiro..** Esta opção não descreve o comportamento indicado.
*   **Define um facto novo que torna `parent` o mesmo predicado que `mother`..** Esta opção não descreve o comportamento indicado.
*   **Se `mother(X,Y)` é verdadeiro, `parent(X,Y)` é verdadeiro..** O corpo implica a cabeça, mas a regra não afirma a implicação inversa.
*   **`parent(X,Y)` e `mother(X,Y)` são sempre ambos verdadeiros ou ambos falsos..** Esta opção não descreve o comportamento indicado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

Pares de progenitores

Define `parents(?Parent1, ?Parent2, ?Person)` para os dois progenitores distintos de uma pessoa, independentemente do género. A relação é simétrica: para cameron devolve barb-merle e merle-barb; para phil, grace-frank e frank-grace.

```prolog
male(frank). male(jay). male(javier). male(merle). male(phil). male(mitchell). male(cameron). male(joe). male(manny). male(bo). male(dylan). male(luke). male(rexford). male(calhoun). male(george).
female(grace). female(dede). female(gloria). female(barb). female(claire). female(pameron). female(haley). female(alex). female(lily). female(poppy).
parent(grace,phil). parent(frank,phil). parent(dede,claire). parent(dede,mitchell). parent(jay,claire). parent(jay,mitchell). parent(jay,joe). parent(gloria,joe). parent(gloria,manny). parent(javier,manny). parent(barb,cameron). parent(barb,pameron). parent(merle,cameron). parent(merle,pameron). parent(mitchell,lily). parent(mitchell,rexford). parent(cameron,lily). parent(cameron,rexford). parent(pameron,calhoun). parent(bo,calhoun). parent(phil,haley). parent(phil,alex). parent(phil,luke). parent(claire,haley). parent(claire,alex). parent(claire,luke). parent(haley,george). parent(haley,poppy). parent(dylan,george). parent(dylan,poppy).

% Define aqui o predicado pedido.
```



### Testes

**Duas ordens**


```prolog
main :- findall(A-B,parents(A,B,cameron),L),write_canonical(L),nl.
```


Saída esperada:

```text
[-(barb,merle),-(merle,barb)]
```

**Mesmo género**


```prolog
main :- findall(A-B,parents(A,B,lily),L),write_canonical(L),nl.
```


Saída esperada:

```text
[-(mitchell,cameron),-(cameron,mitchell)]
```

Solução

```
male(frank). male(jay). male(javier). male(merle). male(phil). male(mitchell). male(cameron). male(joe). male(manny). male(bo). male(dylan). male(luke). male(rexford). male(calhoun). male(george).
female(grace). female(dede). female(gloria). female(barb). female(claire). female(pameron). female(haley). female(alex). female(lily). female(poppy).
parent(grace,phil). parent(frank,phil). parent(dede,claire). parent(dede,mitchell). parent(jay,claire). parent(jay,mitchell). parent(jay,joe). parent(gloria,joe). parent(gloria,manny). parent(javier,manny). parent(barb,cameron). parent(barb,pameron). parent(merle,cameron). parent(merle,pameron). parent(mitchell,lily). parent(mitchell,rexford). parent(cameron,lily). parent(cameron,rexford). parent(pameron,calhoun). parent(bo,calhoun). parent(phil,haley). parent(phil,alex). parent(phil,luke). parent(claire,haley). parent(claire,alex). parent(claire,luke). parent(haley,george). parent(haley,poppy). parent(dylan,george). parent(dylan,poppy).

parents(A,B,C) :- parent(A,C), parent(B,C), A \= B.
```

Procura dois factos para a mesma pessoa e exige progenitores distintos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

Filho único

Define `single_child(?Person)` para quem não tem irmãos, nem meios-irmãos. Deve ter sucesso no máximo uma vez por pessoa. As soluções são phil e calhoun.

```prolog
male(frank). male(jay). male(javier). male(merle). male(phil). male(mitchell). male(cameron). male(joe). male(manny). male(bo). male(dylan). male(luke). male(rexford). male(calhoun). male(george).
female(grace). female(dede). female(gloria). female(barb). female(claire). female(pameron). female(haley). female(alex). female(lily). female(poppy).
parent(grace,phil). parent(frank,phil). parent(dede,claire). parent(dede,mitchell). parent(jay,claire). parent(jay,mitchell). parent(jay,joe). parent(gloria,joe). parent(gloria,manny). parent(javier,manny). parent(barb,cameron). parent(barb,pameron). parent(merle,cameron). parent(merle,pameron). parent(mitchell,lily). parent(mitchell,rexford). parent(cameron,lily). parent(cameron,rexford). parent(pameron,calhoun). parent(bo,calhoun). parent(phil,haley). parent(phil,alex). parent(phil,luke). parent(claire,haley). parent(claire,alex). parent(claire,luke). parent(haley,george). parent(haley,poppy). parent(dylan,george). parent(dylan,poppy).

% Define aqui o predicado pedido.
```



### Testes

**Todos**


```prolog
main :- findall(P,single_child(P),L),sort(L,S),write_canonical(S),nl.
```


Saída esperada:

```text
[calhoun,phil]
```

**Sem duplicados**


```prolog
main :- findall(P,single_child(P),L),length(L,N),write(N),nl.
```


Saída esperada:

```text
2
```

**Meio-irmão**


```prolog
main :- (single_child(manny)->write(sim);write(nao)),nl.
```


Saída esperada:

```text
nao
```

Solução

```
male(frank). male(jay). male(javier). male(merle). male(phil). male(mitchell). male(cameron). male(joe). male(manny). male(bo). male(dylan). male(luke). male(rexford). male(calhoun). male(george).
female(grace). female(dede). female(gloria). female(barb). female(claire). female(pameron). female(haley). female(alex). female(lily). female(poppy).
parent(grace,phil). parent(frank,phil). parent(dede,claire). parent(dede,mitchell). parent(jay,claire). parent(jay,mitchell). parent(jay,joe). parent(gloria,joe). parent(gloria,manny). parent(javier,manny). parent(barb,cameron). parent(barb,pameron). parent(merle,cameron). parent(merle,pameron). parent(mitchell,lily). parent(mitchell,rexford). parent(cameron,lily). parent(cameron,rexford). parent(pameron,calhoun). parent(bo,calhoun). parent(phil,haley). parent(phil,alex). parent(phil,luke). parent(claire,haley). parent(claire,alex). parent(claire,luke). parent(haley,george). parent(haley,poppy). parent(dylan,george). parent(dylan,poppy).

single_child(P) :- setof(C,A^parent(A,C),Children), member(P,Children), \+ (parent(A,P),parent(A,S),S \= P).
```

Gera cada filho uma vez e nega a existência de outra pessoa com um progenitor em comum.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

Lista de antepassados

Define `ancestors(+Person, ?List)` com a lista de todos os antepassados. Por exemplo, `ancestors(cameron,L)` dá `[barb,merle]`.

```prolog
male(frank). male(jay). male(javier). male(merle). male(phil). male(mitchell). male(cameron). male(joe). male(manny). male(bo). male(dylan). male(luke). male(rexford). male(calhoun). male(george).
female(grace). female(dede). female(gloria). female(barb). female(claire). female(pameron). female(haley). female(alex). female(lily). female(poppy).
parent(grace,phil). parent(frank,phil). parent(dede,claire). parent(dede,mitchell). parent(jay,claire). parent(jay,mitchell). parent(jay,joe). parent(gloria,joe). parent(gloria,manny). parent(javier,manny). parent(barb,cameron). parent(barb,pameron). parent(merle,cameron). parent(merle,pameron). parent(mitchell,lily). parent(mitchell,rexford). parent(cameron,lily). parent(cameron,rexford). parent(pameron,calhoun). parent(bo,calhoun). parent(phil,haley). parent(phil,alex). parent(phil,luke). parent(claire,haley). parent(claire,alex). parent(claire,luke). parent(haley,george). parent(haley,poppy). parent(dylan,george). parent(dylan,poppy).

% Define aqui o predicado pedido.
```



### Testes

**Diretos**


```prolog
main :- ancestors(cameron,L),write_canonical(L),nl.
```


Saída esperada:

```text
[barb,merle]
```

**Sem antepassados**


```prolog
main :- ancestors(grace,L),write_canonical(L),nl.
```


Saída esperada:

```text
[]
```

Solução

```
male(frank). male(jay). male(javier). male(merle). male(phil). male(mitchell). male(cameron). male(joe). male(manny). male(bo). male(dylan). male(luke). male(rexford). male(calhoun). male(george).
female(grace). female(dede). female(gloria). female(barb). female(claire). female(pameron). female(haley). female(alex). female(lily). female(poppy).
parent(grace,phil). parent(frank,phil). parent(dede,claire). parent(dede,mitchell). parent(jay,claire). parent(jay,mitchell). parent(jay,joe). parent(gloria,joe). parent(gloria,manny). parent(javier,manny). parent(barb,cameron). parent(barb,pameron). parent(merle,cameron). parent(merle,pameron). parent(mitchell,lily). parent(mitchell,rexford). parent(cameron,lily). parent(cameron,rexford). parent(pameron,calhoun). parent(bo,calhoun). parent(phil,haley). parent(phil,alex). parent(phil,luke). parent(claire,haley). parent(claire,alex). parent(claire,luke). parent(haley,george). parent(haley,poppy). parent(dylan,george). parent(dylan,poppy).

ancestor(P,A) :- parent(A,P).
ancestor(P,A) :- parent(B,P), ancestor(B,A).
ancestors(P,L) :- findall(A,ancestor(P,A),L).
```

A relação recursiva encontra progenitores e os respetivos antepassados; findall recolhe os percursos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

## Unificação, termos e operadores

Instância comum de listas

Qual é uma instância comum de `[_,X|T]` e `[b,Y,X|_]`?

Solução

A segunda posição da primeira lista e a terceira da segunda são ambas `X`, logo têm de ser iguais.

*   **`[b,a,a,b]`.** A segunda posição da primeira lista e a terceira da segunda são ambas `X`, logo têm de ser iguais.
*   **Não existe instância comum..** Esta opção não satisfaz a condição indicada.
*   **`[b,a,b,a]`.** Esta opção não satisfaz a condição indicada.
*   **`[b,a,b,c]`.** Esta opção não satisfaz a condição indicada.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Operador follows

Para escrever `bruno follows alice` e `edgar follows bruno who follows alice who follows carla`, qual é a definição mais adequada de `follows`?

Solução

`xfy` é infixo e permite associar a cadeia à direita.

*   **`:- op(600, xfx, follows).`.** Esta opção não satisfaz a condição indicada.
*   **`:- op(600, xf, follows).`.** Esta opção não satisfaz a condição indicada.
*   **`:- op(600, xfy, follows).`.** `xfy` é infixo e permite associar a cadeia à direita.
*   **`:- op(600, fx, follows).`.** Esta opção não satisfaz a condição indicada.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Operador who

Para a cadeia `edgar follows bruno who follows alice who follows carla`, qual é a definição mais adequada de `who`?

Solução

`who` é prefixo; com prioridade 590 pode surgir como operando de `follows` com prioridade 600.

*   **`:- op(560, fy, who).`.** Esta opção não satisfaz a condição indicada.
*   **`:- op(590, fx, who).`.** `who` é prefixo; com prioridade 590 pode surgir como operando de `follows` com prioridade 600.
*   **`:- op(580, xf, who).`.** Esta opção não satisfaz a condição indicada.
*   **`:- op(570, yf, who).`.** Esta opção não satisfaz a condição indicada.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Utilidade de univ

Para qual destas tarefas `=../2` não é útil?

Solução

`=../2` relaciona um termo com a lista do functor e argumentos; não fornece concatenação em tempo constante.

*   **Verificar o nome do functor de um termo..** Esta opção não satisfaz a condição indicada.
*   **Concatenar duas listas em tempo O(1)..** `=../2` relaciona um termo com a lista do functor e argumentos; não fornece concatenação em tempo constante.
*   **Verificar a aridade de um termo..** Esta opção não satisfaz a condição indicada.
*   **Construir termos para executar em tempo de execução..** Esta opção não satisfaz a condição indicada.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Selecionar argumentos

Define `filterArgs(+Term, +Indexes, ?NewTerm)`. Os índices são inteiros positivos por ordem crescente, a contar de 1. Conserva o functor e apenas os argumentos indicados. Exemplos: `book('The Firm',1,1991,432,['Legal thriller'])` com `[1,3,5]` dá `book('The Firm',1991,['Legal thriller'])`; `author(1,'John Grisham',1955,'USA')` com `[2,3]` dá `author('John Grisham',1955)`. Não uses `findall/3`, `setof/3`, `bagof/3` nem bibliotecas SICStus.

```prolog


% Define aqui o predicado pedido.
```



### Testes

**Seleção**


```prolog
main :- filterArgs(book(a,1,1991,432,[x]),[1,3,5],R),write_canonical(R),nl.
```


Saída esperada:

```text
book(a,1991,[x])
```

**Sem argumentos**


```prolog
main :- filterArgs(f(a,b),[],R),write_canonical(R),nl.
```


Saída esperada:

```text
f
```

**Índice inválido**


```prolog
main :- (filterArgs(f(a),[2],_)->write(sim);write(nao)),nl.
```


Saída esperada:

```text
nao
```

Solução

```


filterArgs(T,Is,R) :- T =.. [F|_], args_at(Is,T,As), R =.. [F|As].
args_at([],_,[]).
args_at([I|Is],T,[A|As]) :- arg(I,T,A), args_at(Is,T,As).
```

Desmonta o termo, recolhe os argumentos por posição e reconstrói-o.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Operadores para livros

Os factos usam `author(ID, Nome, AnoNascimento, País)` e `book(Título, IDAutor, Ano, Páginas, Géneros)`.

Declara os operadores e define o código necessário para queries como `Author wrote 'The Firm' at Age`, com `wrote` acima de `at` na árvore sintática. A query devolve John Grisham e 36.

```prolog
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).
author_wrote_book_at_age(A,T,Age) :- author(I,A,B,_), book(T,I,Y,_,_), Age is Y-B.

% Define aqui o predicado pedido.
```



### Testes

**Livro**


```prolog
main :- findall(A-N, (A wrote 'The Firm' at N),L),write_canonical(L),nl.
```


Saída esperada:

```text
[-('John Grisham',36)]
```

**Idade**


```prolog
main :- findall(T, ('Stephen King' wrote T at 27),L),write_canonical(L),nl.
```


Saída esperada:

```text
['Carrie']
```

Solução

```
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).
author_wrote_book_at_age(A,T,Age) :- author(I,A,B,_), book(T,I,Y,_,_), Age is Y-B.

:- op(730,xfx,wrote).
:- op(720,xfx,at).
A wrote T at N :- author_wrote_book_at_age(A,T,N).
```

A precedência numérica maior coloca wrote na raiz; at agrupa o livro e a idade.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Livros com vários géneros

Implementa `multi_genre_book(?Title)`, que relaciona títulos com pelo menos dois géneros.

```prolog
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

% multi_genre_book(Title).
```



### Testes

**Resultados**


```prolog
main :- findall(X, (multi_genre_book(X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
['The Shining','Under the Dome','Doctor Sleep','Prey','Next']
```

**Um género**


```prolog
main :- findall(X, (multi_genre_book('Carrie'), X = sim), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

Solução

```
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

multi_genre_book(Title) :- book(Title, _, _, _, [_,_|_]).
```

Uma lista com pelo menos dois elementos unifica com `[_,_|_]`.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Unificação com um facto

Dado `likes(alice,pizza).`, como responde Prolog à query `likes(alice,X)`?

Solução

Unifica `likes(alice,X)` com factos ou regras e instancia `X`.

A unificação com o facto liga X a pizza.

*   **Falha imediatamente porque `X` não está instanciado..** Esta opção não descreve o comportamento indicado.
*   **Trata `X` como um novo facto e acrescenta-o à base..** Esta opção não descreve o comportamento indicado.
*   **Unifica `likes(alice,X)` com factos ou regras e instancia `X`..** A unificação com o facto liga X a pizza.
*   **Procura uma regra que derive `alice` a partir de `X`..** Esta opção não descreve o comportamento indicado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

Unificação de termos

Como se unifica `f(X,a)` com `f(g(Y),a)`?

Solução

Liga `X` a `g(Y)` e deixa `Y` livre.

Os funtores exteriores coincidem e o primeiro argumento impõe X = g(Y).

*   **Liga `X` a `g(Y)` e deixa `Y` livre..** Os funtores exteriores coincidem e o primeiro argumento impõe X = g(Y).
*   **Liga `Y` a `X` e substitui `f` por `g`..** Esta opção não descreve o comportamento indicado.
*   **Não são unificáveis porque `X` e `Y` são variáveis diferentes..** Esta opção não descreve o comportamento indicado.
*   **Liga `X` a `Y` e deixa `f` inalterado..** Esta opção não descreve o comportamento indicado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

Leitura de termos

Ao usar `read/1` e `write/1` em programas interativos, que condição importa?

Solução

`read/1` espera um termo Prolog seguido de ponto, pelo que as instruções e o formato de entrada devem respeitá-lo.

O ponto termina o termo lido; a apresentação deve indicar o formato.

*   **`write/1` falha se o argumento contiver variáveis não instanciadas..** Esta opção não descreve o comportamento indicado.
*   **`read/1` espera um termo Prolog seguido de ponto, pelo que as instruções e o formato de entrada devem respeitá-lo..** O ponto termina o termo lido; a apresentação deve indicar o formato.
*   **`write/1` insere automaticamente espaços e mudanças de linha..** Esta opção não descreve o comportamento indicado.
*   **`read/1` só lê números, não átomos ou termos compostos..** Esta opção não descreve o comportamento indicado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

Operadores para páginas

Que declarações permitem escrever `'The Firm' has 432 pages`?

Solução

Usa `xfx` para `has` e `xf` para `pages`.

A sintaxe exige um operador infixo e outro pós-fixo, cujo termo pode ser o operando direito de `has`.

*   **`op(700, xfx, has)` e `op(600, xf, pages)`.** `has` é infixo e `pages` é pós-fixo, com prioridade inferior.
*   **`op(700, xfx, has)` e `op(600, fx, pages)`.** `fx` é prefixo, mas `pages` aparece depois do número.
*   **`op(700, yfy, has)` e `op(600, xf, pages)`.** `yfy` não é uma especificação válida.
*   **`op(700, xfx, has)` e `op(700, xf, pages)`.** O operando direito de `xfx` exige prioridade estritamente inferior a 700.
*   **`op(700, yfy, has)` e `op(600, fx, pages)`.** `yfy` é inválido e `fx` é prefixo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/procura-jogos-simbolos/#termos-que-representam-express%C3%B5es)

Argumento de um termo

```
T =.. L, append([_,_],[X|_],L), var(X).
```

Para um termo já instanciado `T`, o que verifica a consulta?

Solução

A consulta testa se o segundo argumento é uma variável livre.

A lista produzida por `=..` começa pelo funtor. `append/3` seleciona o terceiro elemento da lista.

*   **O terceiro argumento está por instanciar..** O primeiro elemento da lista é o funtor.
*   **O segundo argumento é um átomo..** `var/1` testa uma variável livre.
*   **O segundo argumento está por instanciar..** Após o funtor e o primeiro argumento, `X` é o segundo argumento.
*   **O primeiro argumento está por instanciar..** O primeiro argumento é o segundo elemento da lista.
*   **O terceiro argumento é um átomo..** O teste é `var/1`, não `atom/1`.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/procura-jogos-simbolos/#termos-que-representam-express%C3%B5es)

Operador prefixo

Com `requires` definido como `op(590, xfx, requires)`, escolhe a definição que permite `garlic_bread requires cheese and some garlic` e impede `some some garlic`.

Solução

Usa `op(570, fx, some)`.

A forma prefixa deve ter prioridade inferior à ligação e usar `x` para proibir repetição à mesma prioridade.

*   **`op(570, xf, some)`.** É pós-fixo.
*   **`op(600, fy, some)`.** A prioridade é demasiado elevada e `fy` permite repetição.
*   **`op(600, xf, some)`.** É pós-fixo e tem prioridade demasiado elevada.
*   **`op(570, fx, some)`.** É prefixo, mais forte e não aceita outro `some` à mesma prioridade.
*   **`op(570, fy, some)`.** `fy` permite repetir o operador.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/procura-jogos-simbolos/#termos-que-representam-express%C3%B5es)

Operador de ligação

Com `requires` definido como `op(590, xfx, requires)`, escolhe a definição de `and` que permite encadear três ingredientes.

Solução

Usa `op(580, xfy, and)`.

Um operador infixo associativo e de menor prioridade pode aparecer no operando direito de `requires`.

*   **`op(580, yf, and)`.** É pós-fixo, não infixo.
*   **`op(580, xfy, and)`.** É infixo e associa à direita, permitindo encadeamento.
*   **`op(580, yxfx, and)`.** Não é uma especificação de operador válida.
*   **`op(580, xf, and)`.** É pós-fixo.
*   **`op(580, xfx, and)`.** Não permite encadear operadores da mesma prioridade sem parênteses.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/procura-jogos-simbolos/#termos-que-representam-express%C3%B5es)

Aridade de um termo

Explica numa frase o efeito de `predZ :- read(X), X =.. [_|B], length(B,N), write(N), nl.`.

Solução

Lê um termo e escreve a sua aridade, seguida de mudança de linha.

`=..` produz uma lista com o functor seguido dos argumentos; o comprimento da cauda é a aridade.

Confere a tua resposta:

*   Indiquei a leitura de um termo e a impressão da sua aridade.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

## Listas, recursão e aritmética

Número de seguidores distintos

Os factos dados representam utilizadores, datas de nascimento, pessoas seguidas e vídeos. Não uses `findall`, `setof`, `bagof` nem bibliotecas SICStus.

Define `num_followers(+UserID, ?NumFollowers)`, contando os outros utilizadores distintos que o seguem. O utilizador 1 tem três seguidores.

```prolog
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

% Define o predicado pedido.

```



### Testes

**Seguidores**


```prolog
main :- num_followers(1,N), write_canonical(N), nl.
```


Saída esperada:

```text
3
```

**Sem seguidores**


```prolog
main :- num_followers(5,N), write_canonical(N), nl.
```


Saída esperada:

```text
0
```

Solução

```
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

num_followers(U, N) :- followers(U, [], L), length(L, N).
followers(U, Seen, L) :- user(V, _, _, F), V \= U, member(U, F), \+ member(V, Seen), !, followers(U, [V|Seen], L).
followers(_, L, L).
```

Relaciona os factos pelos identificadores e verifica as condições pedidas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Visibilidade de vídeos

Os factos dados representam utilizadores, datas de nascimento, pessoas seguidas e vídeos. Não uses `findall`, `setof`, `bagof` nem bibliotecas SICStus.

Define `can_see_all_videos(+UserID, +ListOfVideoIDs)`. Uma pessoa vê os seus vídeos e os de quem segue; todos os identificadores devem existir e ser visíveis. 1 vê `[12,13,10]`, mas não `[15]`.

```prolog
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

% Define o predicado pedido.

```



### Testes

**Visíveis**


```prolog
main :- findall(x, can_see_all_videos(1,[12,13,10]), L), write_canonical(L), nl.
```


Saída esperada:

```text
[x]
```

**Inexistente**


```prolog
main :- findall(x, can_see_all_videos(1,[999]), L), write_canonical(L), nl.
```


Saída esperada:

```text
[]
```

**Não visível**


```prolog
main :- findall(x, can_see_all_videos(1,[15]), L), write_canonical(L), nl.
```


Saída esperada:

```text
[]
```

Solução

```
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

can_see_all_videos(U, Vs) :- user(U, _, _, F), visible_all(Vs, U, F).
visible_all([], _, _).
visible_all([V|Vs], U, F) :- video(V, Owner, _, _), (Owner = U ; member(Owner, F)), visible_all(Vs, U, F).
```

Relaciona os factos pelos identificadores e verifica as condições pedidas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Recursão terminal e eficiência

Considera: (1) a recursão terminal permite maior eficiência em memória e tempo; (2) só cortes verdes podem reduzir objetivos executados; (3) `append([1,2,3], [], L)` é mais eficiente do que `append([], [1,2,3], L)`. Que afirmações são verdadeiras?

Solução

Cortes vermelhos também podem reduzir a procura e a segunda chamada de `append/3` termina imediatamente. Nenhuma das combinações propostas é correta.

*   **Só (2) e (3)..** Esta opção não satisfaz a condição indicada.
*   **Nenhuma das outras opções..** Cortes vermelhos também podem reduzir a procura e a segunda chamada de `append/3` termina imediatamente. Nenhuma das combinações propostas é correta.
*   **Só (1) e (2)..** Esta opção não satisfaz a condição indicada.
*   **Só (1) e (3)..** Esta opção não satisfaz a condição indicada.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Seleção numa lista

Qual das implementações define `select(?Element, ?List, ?Residue)`?

Solução

A lista original é a concatenação de um prefixo com `X` e um sufixo; o resíduo junta o mesmo prefixo e sufixo.

*   **`select(X,Y,Z) :- append([X],Y,Z).`.** Esta opção não satisfaz a condição indicada.
*   **`select(X,Y,Z) :- append([X|A],B,Y), append(A,B,Z).`.** Esta opção não satisfaz a condição indicada.
*   **`select(X,Y,Z) :- append(_,[X|Y],Z).`.** Esta opção não satisfaz a condição indicada.
*   **`select(X,Y,Z) :- append(A,[X|B],Y), append(A,B,Z).`.** A lista original é a concatenação de um prefixo com `X` e um sufixo; o resíduo junta o mesmo prefixo e sufixo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Imprimir uma ligação

Os factos `by(Character, Movie, Actor)` associam personagens, filmes ou séries e atores.

Define `pretty_print(+ConnectionList)`, que imprime a lista alternada de atores e filmes. Por exemplo, `[lauraWard,elektra,jenniferGarner,daredevil,benAffleck,theSumOfAllFears,bridgetMoynahan]` imprime `lauraWard worked in elektra with jenniferGarner,`, depois `who worked in daredevil with benAffleck,`, e por fim `who worked in theSumOfAllFears with bridgetMoynahan.`, cada trecho numa linha.

```prolog
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

% Define o predicado pedido.

```



### Testes

**Ligação direta**


```prolog
main :- pretty_print([a,film,b]).
```


Saída esperada:

```text
a worked in film with b.
```

**Duas ligações**


```prolog
main :- pretty_print([a,film,b,other,c]).
```


Saída esperada:

```text
a worked in film with b,
 who worked in other with c.
```

Solução

```
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

pretty_print([A,M,B|T]) :- write(A), write(' worked in '), write(M), write(' with '), write(B), pretty_rest(T).
pretty_rest([]) :- write('.'), nl.
pretty_rest([M,B|T]) :- write(','), nl, write(' who worked in '), write(M), write(' with '), write(B), pretty_rest(T).
```

Relaciona os factos pelos campos pedidos, preservando as condições e os resultados distintos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#escolher-a-recolha)

Aplicação a listas

```
predX(_, [], [], []).
predX(R, [A|B], [C|D], [E|F]) :- S =.. [R,A,C,E], S, predX(R,B,D,F).
```

A que predicado de listas é equivalente `predX/4`?

Solução

`maplist/4`

A cada passo chama R com os elementos correspondentes das três listas.

*   **`select/4`.** Esta alternativa não descreve o comportamento apresentado.
*   **`scanlist/4`.** Esta alternativa não descreve o comportamento apresentado.
*   **`cumlist/4`.** Esta alternativa não descreve o comportamento apresentado.
*   **`maplist/4`.** A cada passo chama R com os elementos correspondentes das três listas.
*   **`map_product/4`.** Esta alternativa não descreve o comportamento apresentado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Rodar um disco

Não utilizes nenhuma biblioteca do Prolog, excepto a CLPFD.

Um cadeado é uma lista de discos, cada um representado por uma lista de igual comprimento. Por exemplo, cinco discos alfabéticos podem começar respetivamente em a, p, p, l e e; cada lista segue o alfabeto circular até ao elemento anterior ao inicial. Define `rotate(+List,+Position,+Rotations,?NewList)`: roda o disco na posição (a contar de 1) para a esquerda por Rotations posições. Aceita rotações negativas ou superiores ao comprimento; falha para posição inválida. Para `[[3,6,8],[5,0,7],[2,1,4]]`, rodar a posição 2 uma vez dá `[[3,6,8],[0,7,5],[2,1,4]]`, a posição 3 duas vezes dá `[[3,6,8],[5,0,7],[4,2,1]]`, a posição 1 por -1 dá `[[8,3,6],[5,0,7],[2,1,4]]` e por 4 dá `[[6,8,3],[5,0,7],[2,1,4]]`.

```prolog


% Define aqui o predicado pedido.
```



### Testes

**Negativa**


```prolog
main :- rotate([[3,6,8],[5,0,7],[2,1,4]],1,-1,R),write_canonical(R),nl.
```


Saída esperada:

```text
[[8,3,6],[5,0,7],[2,1,4]]
```

**Grande**


```prolog
main :- rotate([[3,6,8],[5,0,7]],1,4,R),write_canonical(R),nl.
```


Saída esperada:

```text
[[6,8,3],[5,0,7]]
```

**Posição inválida**


```prolog
main :- (rotate([[1,2]],2,1,_)->write(sim);write(nao)),nl.
```


Saída esperada:

```text
nao
```

Solução

```


rotate(C,I,R,N) :- nth1(I,C,D,Rest), length(D,L), L>0, K is R mod L, length(A,K), append(A,B,D), append(B,A,E), nth1(I,N,E,Rest).
```

O resto da divisão normaliza a rotação; divide o disco e troca as duas partes.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Alinhar o código

Não utilizes nenhuma biblioteca do Prolog, excepto a CLPFD.

Define `matches(+List,+Code)`: cada elemento do código deve coincidir com o primeiro elemento do disco correspondente e o número de discos deve ser igual ao comprimento do código. `[[3,6,8],[5,0,7],[2,1,4]]` coincide com `[3,5,2]`, mas não com `[6,0,1]` nem `[3,5,2,1]`.

```prolog


% Define aqui o predicado pedido.
```



### Testes

**Alinhado**


```prolog
main :- (matches([[3,6,8],[5,0,7],[2,1,4]],[3,5,2])->write(sim);write(nao)),nl.
```


Saída esperada:

```text
sim
```

**Comprimento**


```prolog
main :- (matches([[1]],[1,2])->write(sim);write(nao)),nl.
```


Saída esperada:

```text
nao
```

**Diferente**


```prolog
main :- (matches([[1,2]],[2])->write(sim);write(nao)),nl.
```


Saída esperada:

```text
nao
```

Solução

```


matches([],[]).
matches([[H|_]|Ds],[H|Ks]) :- matches(Ds,Ks).
```

Percorre as duas listas em paralelo, exigindo que terminem juntas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Movimentos do cadeado

Não utilizes nenhuma biblioteca do Prolog, excepto a CLPFD.

Define `move(+Initial,-Final)` para gerar por retrocesso todas as rotações não nulas de um único disco. Os discos têm o mesmo comprimento, que pode diferir do número de discos. Para `[[3,6,8],[5,0,7],[2,1,4]]` obtêm-se `[[6,8,3],[5,0,7],[2,1,4]]`, `[[8,3,6],[5,0,7],[2,1,4]]`, `[[3,6,8],[0,7,5],[2,1,4]]`, `[[3,6,8],[7,5,0],[2,1,4]]`, `[[3,6,8],[5,0,7],[1,4,2]]` e `[[3,6,8],[5,0,7],[4,2,1]]`.

```prolog
rotate(C,I,R,N) :- nth1(I,C,D,Rest), length(D,L), L>0, K is R mod L, length(A,K), append(A,B,D), append(B,A,E), nth1(I,N,E,Rest).

% Define aqui o predicado pedido.
```



### Testes

**Todos os movimentos**


```prolog
main :- findall(F,move([[1,2,3],[4,5,6]],F),L),write_canonical(L),nl.
```


Saída esperada:

```text
[[[2,3,1],[4,5,6]],[[3,1,2],[4,5,6]],[[1,2,3],[5,6,4]],[[1,2,3],[6,4,5]]]
```

**Disco unitário**


```prolog
main :- findall(F,move([[1]],F),L),write_canonical(L),nl.
```


Saída esperada:

```text
[]
```

Solução

```
rotate(C,I,R,N) :- nth1(I,C,D,Rest), length(D,L), L>0, K is R mod L, length(A,K), append(A,B,D), append(B,A,E), nth1(I,N,E,Rest).

move(C,N) :- nth1(I,C,D), length(D,L), Max is L-1, between(1,Max,R), rotate(C,I,R,N).
```

Para cada disco, gera rotações de 1 até ao comprimento menos um.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Coeficiente de Jaccard

Implementa `similarity(?Title1, ?Title2, ?Similarity)`: divide o número de géneros comuns pelo número de géneros distintos na união.

```prolog
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

% similarity(Title1, Title2, Similarity).
```



### Testes

**Iguais**


```prolog
main :- findall(X, (similarity('The Firm','The Client',X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[1.0]
```

**Parcial**


```prolog
main :- findall(X, (similarity('Prey','Next',X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[0.4]
```

**Disjuntos**


```prolog
main :- findall(X, (similarity('Carrie','The Firm',X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[0.0]
```

Solução

```
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

similarity(T1,T2,S) :-
    book(T1,_,_,_,G1), book(T2,_,_,_,G2),
    sort(G1,A), sort(G2,B), append(A,B,All), sort(All,Union),
    findall(G, (member(G,A), memberchk(G,B)), Common),
    length(Common,I), length(Union,U), U > 0, S is 1.0*I/U.
```

Ordenar e eliminar duplicados dá a união de conjuntos; o quociente usa os tamanhos da interseção e da união.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Lucro de um prato

Cada prato indica o preço em cêntimos e os ingredientes em gramas. Cada ingrediente surge uma vez por prato. Não uses `findall`, `setof`, `bagof` nem bibliotecas para esta questão.

Implementa `dish_profit(?Dish, ?Profit)`, subtraindo ao preço a soma dos custos dos ingredientes.

```prolog
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

% dish_profit(Dish, Profit).
```



### Testes

**Pizza**


```prolog
main :- findall(X, (dish_profit(pizza,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[300]
```

**Todos**


```prolog
main :- findall(X, (dish_profit(X,710)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[ratatouille]
```

**Desconhecido**


```prolog
main :- findall(X, (dish_profit(outro,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

Solução

```
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

ingredients_cost([], 0).
ingredients_cost([I-G|Rest], Cost) :- ingredient(I, Unit), ingredients_cost(Rest, Tail), Cost is G*Unit+Tail.
dish_profit(Dish, Profit) :- dish(Dish, Price, Ingredients), ingredients_cost(Ingredients, Cost), Profit is Price-Cost.
```

Calcula recursivamente o custo de cada ingrediente e subtrai a soma ao preço.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Consumir ingredientes

Cada prato indica o preço em cêntimos e os ingredientes em gramas. Cada ingrediente surge uma vez por prato. Não uses `findall`, `setof`, `bagof` nem bibliotecas para esta questão.

Implementa `consume_ingredient(+IngredientStocks, +Ingredient, +Grams, ?NewIngredientStocks)`. Reduz a quantidade indicada, preservando a ordem; falha se o ingrediente não existir ou não houver stock suficiente. Não uses recursão.

```prolog
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

% consume_ingredient(Stocks, Ingredient, Grams, NewStocks).
```



### Testes

**Suficiente**


```prolog
main :- findall(X, (consume_ingredient([garlic-600,tomato-800,cheese-750],tomato,150,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[[-(garlic,600),-(tomato,650),-(cheese,750)]]
```

**Insuficiente**


```prolog
main :- findall(X, (consume_ingredient([tomato-800],tomato,1000,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

**Ausente**


```prolog
main :- findall(X, (consume_ingredient([],tomato,1,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

Solução

```
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

consume_ingredient(Stocks,I,G,New) :-
    append(Before,[I-Amount|After],Stocks), Amount >= G,
    Remaining is Amount-G, append(Before,[I-Remaining|After],New).
```

Divide a lista em prefixo, par escolhido e sufixo; recompõe-a após verificar a quantidade.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Listar ingredientes dos pratos

Cada facto `dish/3` contém um preço e pares ingrediente-gramas.

Implementa `list_dishes(?DishIngredients)`, uma lista de pares prato-lista de nomes de ingredientes, na ordem dos factos.

```prolog
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

% list_dishes(DishIngredients).
```



### Testes

**Todos**


```prolog
main :- findall(X, (list_dishes(X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[[-(pizza,[cheese,tomato]),-(ratatouille,[tomato,eggplant,garlic]),-(garlic_bread,[cheese,garlic])]]
```

**Primeiro prato**


```prolog
main :- list_dishes([X|_]), write_canonical(X), nl.
```


Saída esperada:

```text
-(pizza,[cheese,tomato])
```

Solução

```
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

ingredient_names([],[]).
ingredient_names([I-_|Rest],[I|Names]) :- ingredient_names(Rest,Names).
list_dishes(List) :- findall(D-Names,(dish(D,_,Ingredients),ingredient_names(Ingredients,Names)),List).
```

Transforma cada lista de pares em nomes e recolhe os resultados na ordem dos factos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Ordenar pratos por lucro

Cada facto `dish/3` contém um preço e pares ingrediente-gramas.

Implementa `most_lucrative_dishes(?Dishes)` por ordem decrescente de lucro; em empates aceita-se qualquer ordem.

```prolog
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

% most_lucrative_dishes(Dishes).
```



### Testes

**Ordem**


```prolog
main :- findall(X, (most_lucrative_dishes(X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[[ratatouille,pizza,garlic_bread]]
```

**Último prato**


```prolog
main :- most_lucrative_dishes(L), last(L,X), write_canonical(X), nl.
```


Saída esperada:

```text
garlic_bread
```

Solução

```
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

ingredients_cost([],0).
ingredients_cost([I-G|Rest],Cost) :- ingredient(I,U), ingredients_cost(Rest,T), Cost is G*U+T.
most_lucrative_dishes(Dishes) :- findall(Key-D,(dish(D,P,Is),ingredients_cost(Is,C),Key is C-P),Pairs), keysort(Pairs,Sorted), pairs_values(Sorted,Dishes).
```

Ordena pelo simétrico do lucro, conservando todos os pratos mesmo quando há empate.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Pontuar um código

No Mastermind, cada código tem quatro dígitos entre 1 e 9, com repetições permitidas. `score(+Guess,+Key,?CC,?CE)` conta dígitos na posição certa e dígitos certos na posição errada. Define `right_position/3` e `any_position/3` usados por score. Conta ocorrências repetidas no máximo uma vez cada. Exemplos: `[1,2,3,4]` contra `[4,3,2,1]` dá 0 e 4; `[5,6,7,8]` dá 0 e 0; `[4,2,3,5]` dá 1 e 2.

```prolog
score(Guess,Key,CC,CE) :- right_position(Guess,Key,CC), any_position(Guess,Key,CA), CE is CA-CC.

% Define aqui o predicado pedido.
```



### Testes

**Invertido**


```prolog
main :- score([1,2,3,4],[4,3,2,1],A,B),write_canonical(A-B),nl.
```


Saída esperada:

```text
-(0,4)
```

**Repetições**


```prolog
main :- score([1,1,1,2],[1,2,2,2],A,B),write_canonical(A-B),nl.
```


Saída esperada:

```text
-(2,0)
```

**Misto**


```prolog
main :- score([4,2,3,5],[4,3,2,1],A,B),write_canonical(A-B),nl.
```


Saída esperada:

```text
-(1,2)
```

Solução

```
score(Guess,Key,CC,CE) :- right_position(Guess,Key,CC), any_position(Guess,Key,CA), CE is CA-CC.

right_position([],[],0).
right_position([X|Xs],[Y|Ys],N) :- right_position(Xs,Ys,M), (X=Y -> N is M+1 ; N=M).
any_position([],_,0).
any_position([X|Xs],Ys,N) :- (select(X,Ys,Zs) -> any_position(Xs,Zs,M), N is M+1 ; any_position(Xs,Ys,N)).
```

Conta posições iguais e remove cada dígito encontrado da chave antes de procurar o seguinte.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

Recursão de cauda

Qual das afirmações sobre recursão de cauda está correta?

Solução

Um argumento acumulador pode tornar alguns predicados recursivos de cauda.

O acumulador permite passar trabalho por fazer para a chamada seguinte, deixando-a como último objetivo.

*   **Ocorre também em factos..** Um facto não tem chamada recursiva.
*   **Um argumento adicional permite transformar certos predicados em recursão de cauda..** Um acumulador pode guardar trabalho pendente.
*   **Um corte torna qualquer chamada recursiva uma chamada de cauda..** A posição da chamada, não o corte, determina se é de cauda.
*   **Um predicado sem chamada recursiva usa recursão de cauda..** É necessária uma chamada recursiva.
*   **Todas as outras afirmações estão erradas..** A opção do acumulador está correta.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#acumuladores-e-termina%C3%A7%C3%A3o)

Listas de diferença

Considera A: `[a,b|T]\T` representa `[a,b]`; B: as listas de diferença dão acesso O(1) a um prefixo não instanciado; C: permitem calcular o comprimento do prefixo em O(1). Que afirmações são corretas?

Solução

Só A está correta.

A cauda partilhada delimita o segmento, mas não guarda o seu comprimento.

*   **A, B e C.** O comprimento não está guardado na representação.
*   **A e C.** Contar o prefixo exige percorrê-lo.
*   **Só A.** O segmento entre a lista e a cauda partilhada é `[a,b]`.
*   **Só C.** O comprimento não é obtido em tempo constante.
*   **B e C.** Nem a consulta arbitrária do prefixo nem o seu comprimento são constantes.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Contar pratos com ingrediente

Implementa `count_dishes_with_ingredient(+Ingredient, ?N)`. Conta os pratos que usam o ingrediente, sem `findall`, `bagof`, `setof` nem bibliotecas. Cada ingrediente ocorre no máximo uma vez por prato.

```prolog
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).

% count_dishes_with_ingredient(Ingredient, N).
```



### Testes

**Tomate**


```prolog
main :- count_dishes_with_ingredient(tomato,N), writeln(N).
```


Saída esperada:

```text
2
```

**Ausente**


```prolog
main :- count_dishes_with_ingredient(rice,N), writeln(N).
```


Saída esperada:

```text
0
```

**Valor dado**


```prolog
main :- (count_dishes_with_ingredient(garlic,2) -> writeln(sim); writeln(nao)).
```


Saída esperada:

```text
sim
```

Solução

```
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient_counter/1.
count_dishes_with_ingredient(I,N) :-
    retractall(ingredient_counter(_)), assertz(ingredient_counter(0)),
    (dish(_,_,Items), has_ingredient(I,Items),
     retract(ingredient_counter(A)), B is A+1, assertz(ingredient_counter(B)), fail
    ; retract(ingredient_counter(Result)), N=Result).
has_ingredient(I,[I-_|_]) :- !.
has_ingredient(I,[_|Rest]) :- has_ingredient(I,Rest).
```

Percorre as cláusulas da base e acumula uma unidade por prato com o ingrediente.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Consumir para um prato

```
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).

predX(S,D,NewS) :- dish(D,_,L), predY(L,S,NewS).
predY([],L,L).
predY([I-Gr|Is],S,NewS) :- !, consume_ingredient(S,I,Gr,S1), predY(Is,S1,NewS).
```

Explica os argumentos e o efeito de `predX/3`, incluindo o caso de stock insuficiente. `consume_ingredient/4` retira a quantidade pedida e falha se não houver stock suficiente.

Solução

Recebe os pares ingrediente-quantidade e o nome de um prato, devolvendo o stock após consumir os ingredientes. Falha se algum for insuficiente.

`predY/3` percorre os ingredientes do prato e passa o stock atualizado à chamada seguinte.

Confere a tua resposta:

*   Identifiquei a lista de stocks, o prato e a lista resultante.
*   Expliquei a falha quando algum ingrediente é insuficiente.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Representação binária

Implementa `dec2bin(+Dec, -BinList, +N)`: representa um inteiro não negativo em exatamente `N` bits, com zeros à esquerda. Falha se não couber.

```prolog
% dec2bin(Dec, BinList, N).
```



### Testes

**Sete**


```prolog
main :- findall(X, (dec2bin(7,X,8)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[[0,0,0,0,0,1,1,1]]
```

**Não cabe**


```prolog
main :- findall(X, (dec2bin(1234,X,8)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

**Zero bits**


```prolog
main :- findall(X, (dec2bin(0,X,0)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[[]]
```

**Negativo**


```prolog
main :- findall(X, (dec2bin(-1,X,8)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

Solução

```
dec2bin(Dec, Bits, N) :- integer(Dec), integer(N), Dec >= 0, N >= 0, binary_digits(Dec,N,[],Bits).
binary_digits(0,0,Bits,Bits).
binary_digits(Dec,N,Acc,Bits) :- N > 0, Bit is Dec mod 2, Next is Dec div 2, N1 is N-1, binary_digits(Next,N1,[Bit|Acc],Bits).
```

Divide sucessivamente por dois e acumula os restos; ao fim de N posições o quociente tem de ser zero.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Preparar geração

Implementa `initialize(+DecNumber, +Bits, +Padding, -List)`: converte o número em `Bits` bits e coloca `Padding` zeros em cada lado.

```prolog
dec2bin(Dec, Bits, N) :- integer(Dec), integer(N), Dec >= 0, N >= 0, binary_digits(Dec,N,[],Bits).
binary_digits(0,0,Bits,Bits).
binary_digits(Dec,N,Acc,Bits) :- N > 0, Bit is Dec mod 2, Next is Dec div 2, N1 is N-1, binary_digits(Next,N1,[Bit|Acc],Bits).

% initialize(DecNumber, Bits, Padding, List).
```



### Testes

**Exemplo**


```prolog
main :- findall(X, (initialize(12,4,2,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[[0,0,1,1,0,0,0,0]]
```

**Sem margem**


```prolog
main :- findall(X, (initialize(3,2,0,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[[1,1]]
```

**Não cabe**


```prolog
main :- findall(X, (initialize(4,2,1,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

Solução

```
dec2bin(Dec, Bits, N) :- integer(Dec), integer(N), Dec >= 0, N >= 0, binary_digits(Dec,N,[],Bits).
binary_digits(0,0,Bits,Bits).
binary_digits(Dec,N,Acc,Bits) :- N > 0, Bit is Dec mod 2, Next is Dec div 2, N1 is N-1, binary_digits(Next,N1,[Bit|Acc],Bits).

initialize(D,B,P,L) :- dec2bin(D,Middle,B), integer(P), P >= 0, length(Side,P), maplist(=(0),Side), append([Side,Middle,Side],L).
```

Cria duas margens iguais e concatena-as com a representação binária.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Imprimir uma geração

Implementa `print_generation(+List)`: escreve `.` para 0, `M` para 1 e `|` no início e após cada grupo completo de oito bits. Termina com mudança de linha.

```prolog
% print_generation(List).
```



### Testes

**Byte**


```prolog
main :- print_generation([0,0,0,0,1,0,1,0]).
```


Saída esperada:

```text
|....M.M.|
```

**Parcial**


```prolog
main :- print_generation([0,0,0,0,1,0,1,0,0,0,1,1]).
```


Saída esperada:

```text
|....M.M.|..MM
```

**Vazia**


```prolog
main :- print_generation([]).
```


Saída esperada:

```text
|
```

Solução

```
print_generation(Bits) :- write('|'), print_bits(Bits,0), nl.
print_bits([], _).
print_bits([B|Bs], N) :- (B = 0 -> write('.') ; B = 1, write('M')), N1 is N+1, (N1 mod 8 =:= 0 -> write('|') ; true), print_bits(Bs,N1).
```

Conta os bits impressos e coloca uma barra após cada oitavo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Atualizar regra celular

Implementa `update_rule(+Rule)` para um inteiro entre 0 e 255. Substitui os factos `rule(Left-Self-Right, State)` pelas oito combinações. O bit menos significativo corresponde a `0-0-0` e o mais significativo a `1-1-1`. Um valor fora do intervalo falha sem alterar as regras.

```prolog
:- dynamic rule/2.

% update_rule(Rule).
```



### Testes

**Regra 10**


```prolog
main :- update_rule(10), findall(B,rule(_,B),Bs), write_canonical(Bs), nl.
```


Saída esperada:

```text
[0,1,0,1,0,0,0,0]
```

**Limite**


```prolog
main :- update_rule(255), findall(B,rule(_,B),Bs), write_canonical(Bs), nl.
```


Saída esperada:

```text
[1,1,1,1,1,1,1,1]
```

**Inválida**


```prolog
main :- findall(X, (update_rule(256), X=sim), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

Solução

```
:- dynamic rule/2.

update_rule(R) :- integer(R), between(0,255,R), retractall(rule(_,_)), forall(between(0,7,I), (L is I div 4, S is (I div 2) mod 2, Right is I mod 2, Bit is (R >> I) /\ 1, assertz(rule(L-S-Right,Bit)))).
```

O índice binário dos três vizinhos seleciona o bit correspondente do número.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Calcular a geração seguinte

Implementa `next_gen(+Previous, -Next)` aplicando `rule/2` a cada célula. Os vizinhos em falta nas extremidades são zero.

```prolog
:- dynamic rule/2.
rule(0-0-0,0). rule(0-0-1,1). rule(0-1-0,0). rule(0-1-1,0).
rule(1-0-0,1). rule(1-0-1,0). rule(1-1-0,1). rule(1-1-1,1).

% next_gen(Previous, Next).
```



### Testes

**Exemplo**


```prolog
main :- findall(X, (next_gen([0,0,1,0,0,0,1,0],X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[[0,1,0,1,0,1,0,1]]
```

**Vazia**


```prolog
main :- findall(X, (next_gen([],X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[[]]
```

**Uma célula**


```prolog
main :- findall(X, (next_gen([1],X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[[0]]
```

Solução

```
:- dynamic rule/2.
rule(0-0-0,0). rule(0-0-1,1). rule(0-1-0,0). rule(0-1-1,0).
rule(1-0-0,1). rule(1-0-1,0). rule(1-1-0,1). rule(1-1-1,1).

next_gen(Previous,Next) :- next_cells(0,Previous,Next).
next_cells(_,[],[]).
next_cells(Left,[Self],[New]) :- rule(Left-Self-0,New).
next_cells(Left,[Self,Right|Rest],[New|Tail]) :- rule(Left-Self-Right,New), next_cells(Self,[Right|Rest],Tail).
```

Passa a célula anterior como vizinho esquerdo e usa zero ao terminar.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

## Corte, negação e falha

Imprimir vídeos por género

Os factos dados representam utilizadores, datas de nascimento, pessoas seguidas e vídeos. Não uses `findall`, `setof`, `bagof` nem bibliotecas SICStus.

Define `print_genre_videos(+Genre)`. Imprime todos os títulos e nomes dos autores como `Title by Name`, um por linha, em qualquer ordem; deve sempre suceder. Não uses recursão.

```prolog
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

% Define o predicado pedido.

```



### Testes

**Um vídeo**


```prolog
main :- print_genre_videos(vlog).
```


Saída esperada:

```text
Daily Coding Vlog by Bruno
```

**Género ausente**


```prolog
main :- print_genre_videos(none), write(ok), nl.
```


Saída esperada:

```text
ok
```

**Todos os vídeos**


```prolog
main :- with_output_to(atom(A), print_genre_videos(education)), atomic_list_concat(Lines, '\n', A), msort(Lines, Sorted), write_canonical(Sorted), nl.
```


Saída esperada:

```text
['','Advanced Prolog Tricks by Edgar','Logic Puzzles Explained by Alice','Prolog for Beginners by Alice']
```

Solução

```
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

print_genre_videos(G) :- video(_, U, T, G), user(U, N, _, _), write(T), write(' by '), write(N), nl, fail.
print_genre_videos(_).
```

Relaciona os factos pelos identificadores e verifica as condições pedidas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Cortes na comparação de datas

```
predX(_-_-Y1, _-_-Y2) :- Y1 < Y2, !.
predX(_-M1-Y, _-M2-Y) :- M1 =< M2, !.
predX(D1-M-Y, D2-M-Y) :- D1 < D2.
```

Quais dos cortes são verdes?

Solução

O primeiro corte elimina alternativas incompatíveis com anos diferentes. O segundo impede a terceira regra quando os meses são iguais, alterando as soluções.

*   **Só o corte da primeira regra..** O primeiro corte elimina alternativas incompatíveis com anos diferentes. O segundo impede a terceira regra quando os meses são iguais, alterando as soluções.
*   **Só o corte da segunda regra..** Esta opção não satisfaz a condição indicada.
*   **Nenhum dos cortes..** Esta opção não satisfaz a condição indicada.
*   **Ambos os cortes..** Esta opção não satisfaz a condição indicada.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Filmes distintos por ator

Os factos `by(Character, Movie, Actor)` associam personagens, filmes ou séries e atores. Não uses `findall`, `setof`, `bagof` nem bibliotecas SICStus.

Define `actor_movies(+Actor, -Movies)`, a lista de filmes e séries distintos em que o ator participa. A ordem não é relevante.

```prolog
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

% Define o predicado pedido.

```



### Testes

**Sem duplicados**


```prolog
main :- actor_movies(lisaKudrow,L), msort(L,S), write_canonical(S), nl.
```


Saída esperada:

```text
[friends]
```

**Ator ausente**


```prolog
main :- actor_movies(nobody,L), write_canonical(L), nl.
```


Saída esperada:

```text
[]
```

Solução

```
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

actor_movies(A, L) :- actor_movies_acc(A, [], L).
actor_movies_acc(A, Seen, L) :- by(_, M, A), \+ member(M, Seen), !, actor_movies_acc(A, [M|Seen], L).
actor_movies_acc(_, L, L).
```

Relaciona os factos pelos campos pedidos, preservando as condições e os resultados distintos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#escolher-a-recolha)

Autor mais jovem

Os factos usam `author(ID, Nome, AnoNascimento, País)` e `book(Título, IDAutor, Ano, Páginas, Géneros)`.

Define `youngest_author(?Author)`, que relaciona cada autor que publicou o primeiro livro na menor idade. Devolve empates por retrocesso. Neste conjunto, o resultado é Stephen King. Não uses `findall/3`, `setof/3`, `bagof/3` nem bibliotecas SICStus.

```prolog
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).
author_wrote_book_at_age(A,T,Age) :- author(I,A,B,_), book(T,I,Y,_,_), Age is Y-B.

% Define aqui o predicado pedido.
```



### Testes

**Autores**


```prolog
main :- findall(A,youngest_author(A),L),write_canonical(L),nl.
```


Saída esperada:

```text
['Stephen King']
```

**Outro autor**


```prolog
main :- (youngest_author('John Grisham')->write(sim);write(nao)),nl.
```


Saída esperada:

```text
nao
```

Solução

```
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).
author_wrote_book_at_age(A,T,Age) :- author(I,A,B,_), book(T,I,Y,_,_), Age is Y-B.

youngest_author(A) :- author_wrote_book_at_age(A,_,N), \+ (author_wrote_book_at_age(_,_,M), M < N).
```

Escolhe uma idade para a qual não existe publicação mais precoce.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Imprimir géneros

Os factos usam `author(ID, Nome, AnoNascimento, País)` e `book(Título, IDAutor, Ano, Páginas, Géneros)`.

Define `genres(+Title)` sem recursão. Imprime os géneros do livro, um por linha e pela ordem dos factos; deve sempre ter sucesso, mesmo para um título ausente. The Firm imprime Legal thriller; The Shining imprime Gothic novel, Horror e Psychological horror. Não uses `findall/3`, `setof/3`, `bagof/3` nem bibliotecas SICStus.

```prolog
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

% Define aqui o predicado pedido.
```



### Testes

**Ordem**


```prolog
main :- genres('The Shining').
```


Saída esperada:

```text
Gothic novel
Horror
Psychological horror
```

**Ausente**


```prolog
main :- genres('Missing'),write(ok),nl.
```


Saída esperada:

```text
ok
```

Solução

```
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

genres(T) :- book(T,_,_,_,Gs), member(G,Gs), write(G), nl, fail.
genres(_).
```

A falha força o próximo género; a segunda cláusula termina com sucesso.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Corte na comparação

```
most_similar(Book,C1,C2,C1) :- similarity(Book,C1,S1), similarity(Book,C2,S2), S1 >= S2, !.
most_similar(Book,C1,C2,C2) :- similarity(Book,C1,S1), similarity(Book,C2,S2), S2 >= S1.
```

`similarity(+Title1,+Title2,?Similarity)` dá um valor entre 0 e 1, maior para livros mais semelhantes. O predicado abaixo escolhe entre C1 e C2 o mais semelhante a Book. Que afirmação sobre o corte é verdadeira?

Solução

O corte é vermelho porque removê-lo altera os resultados de `most_similar/4`.

Num empate, sem corte ambas as cláusulas podem produzir resultados distintos.

*   **É necessário conhecer a implementação de `similarity/3` para classificar o corte..** Esta alternativa não descreve o comportamento apresentado.
*   **O corte pode ser vermelho ou verde consoante os resultados de `similarity/3`..** Esta alternativa não descreve o comportamento apresentado.
*   **O corte não é vermelho nem verde e pode ser retirado sem efeitos..** Esta alternativa não descreve o comportamento apresentado.
*   **O corte é vermelho porque removê-lo altera os resultados de `most_similar/4`..** Num empate, sem corte ambas as cláusulas podem produzir resultados distintos.
*   **O corte é verde porque removê-lo só afeta o desempenho..** Esta alternativa não descreve o comportamento apresentado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Pratos mais caros

Cada prato indica o preço em cêntimos e os ingredientes em gramas. Cada ingrediente surge uma vez por prato. Não uses `findall`, `setof`, `bagof` nem bibliotecas para esta questão.

Implementa `most_expensive_dish(?Dish, ?Price)`, devolvendo por retrocesso todos os pratos empatados no preço máximo.

```prolog
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

% most_expensive_dish(Dish, Price).
```



### Testes

**Empate**


```prolog
main :- findall(X, (most_expensive_dish(X,2200)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[pizza,ratatouille]
```

**Não máximo**


```prolog
main :- findall(X, (most_expensive_dish(garlic_bread,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

Solução

```
dish(pizza,2200,[cheese-300,tomato-350]).
dish(ratatouille,2200,[tomato-70,eggplant-150,garlic-50]).
dish(garlic_bread,1600,[cheese-50,garlic-200]).
:- dynamic ingredient/2.
ingredient(cheese,4).
ingredient(tomato,2).
ingredient(eggplant,7).
ingredient(garlic,6).

most_expensive_dish(Dish,Price) :- dish(Dish,Price,_), \+ (dish(_,Other,_), Other > Price).
```

Um prato é máximo se não existir outro de preço superior.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Efeito do corte

Qual é o principal efeito de inserir `!` no meio do corpo de uma regra?

Solução

Impede o retrocesso para além desse ponto na regra atual.

O corte descarta os pontos de escolha anteriores da chamada atual.

*   **Impede a regra de voltar a ser usada..** Esta opção não descreve o comportamento indicado.
*   **Converte a regra num facto..** Esta opção não descreve o comportamento indicado.
*   **Aborta toda a query e sai..** Esta opção não descreve o comportamento indicado.
*   **Impede o retrocesso para além desse ponto na regra atual..** O corte descarta os pontos de escolha anteriores da chamada atual.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

Corte após uma escolha

Na cláusula `p(X) :- q(X), !, r(X).`, o que acontece quando `q(X)` tem várias soluções?

Solução

Só se usa a primeira solução de `q(X)`; o retrocesso não tenta alternativas de `q(X)`.

Depois do primeiro sucesso de q, o corte elimina as suas alternativas.

*   **Nenhuma solução de `q(X)` é considerada; o corte passa diretamente a `r(X)`..** Esta opção não descreve o comportamento indicado.
*   **Só se usa a primeira solução de `q(X)`; o retrocesso não tenta alternativas de `q(X)`..** Depois do primeiro sucesso de q, o corte elimina as suas alternativas.
*   **Todas as soluções de `q(X)` são consideradas e `r(X)` é verificado para cada uma..** Esta opção não descreve o comportamento indicado.
*   **A cláusula comporta-se como se não tivesse corte, pois cortes só afetam factos..** Esta opção não descreve o comportamento indicado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

Corte numa consulta

```
member(X,[a,b,c,d,e]), !, member(Y,[1,2,3,4]).
```

O corte nesta consulta é verde?

Solução

É um corte vermelho.

O corte fixa a primeira solução de `member/2`; removê-lo altera o conjunto de respostas.

*   **Verdadeiro.** Sem o corte surgem soluções com outros valores de `X`.
*   **Falso.** O corte elimina soluções, por exemplo `X = b`.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Mover um corte

```
member(X,[a,b,c,d,e]), !, member(Y,[1,2,3,4]).
```

Mover o corte para o início da consulta diminui o número de unificações feitas ao pedir todas as soluções?

Solução

Não. O corte inicial não elimina as alternativas de `member(X, ...)`.

Um corte elimina escolhas anteriores, não as que são criadas depois de o executar.

*   **Verdadeiro.** O corte inicial deixa todas as escolhas de `X` disponíveis.
*   **Falso.** O corte inicial não poda as alternativas criadas depois dele.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Corte na recursão

Considera `predY([],L,L).` e `predY([I-Gr|Is],S,N) :- !, consume_ingredient(S,I,Gr,S1), predY(Is,S1,N).` O corte é verde?

Solução

Verdadeiro

As cabeças distinguem lista vazia de lista não vazia. Com uma lista própria de entrada, o corte não elimina soluções; apenas evita alternativas incompatíveis.

*   **Verdadeiro.** As cabeças distinguem lista vazia de lista não vazia. Com uma lista própria de entrada, o corte não elimina soluções; apenas evita alternativas incompatíveis.
*   **Falso.** Esta opção não corresponde ao comportamento descrito.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

## Recolha de soluções

Média de pessoas seguidas

Os factos dados representam utilizadores, datas de nascimento, pessoas seguidas e vídeos.

Define `avg_num_following_by_year(+Year, ?Avg)`, a média em vírgula flutuante do número de pessoas seguidas por quem nasceu no ano. Falha se não houver utilizadores nesse ano. Para 1999 dá 3.0 e para 1997 dá 0.5.

```prolog
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

% Define o predicado pedido.

```



### Testes

**Média**


```prolog
main :- avg_num_following_by_year(1997,A), write_canonical(A), nl.
```


Saída esperada:

```text
0.5
```

**Ano ausente**


```prolog
main :- findall(A, avg_num_following_by_year(1920,A), L), write_canonical(L), nl.
```


Saída esperada:

```text
[]
```

**Outro ano**


```prolog
main :- avg_num_following_by_year(1999,A), write_canonical(A), nl.
```


Saída esperada:

```text
3.0
```

Solução

```
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

avg_num_following_by_year(Y, Avg) :- findall(N, (user(_, _, _-_-Y, F), length(F, N)), Ns), length(Ns, Count), Count > 0, sum_list(Ns, Sum), Avg is float(Sum) / Count.
```

Relaciona os factos pelos identificadores e verifica as condições pedidas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Aniversários de pessoas seguidas

Os factos dados representam utilizadores, datas de nascimento, pessoas seguidas e vídeos.

Define `get_following_birthdays(?UserID, +Month, ?BirthDayUserIDList)`. Devolve os identificadores seguidos com aniversário no mês, ordenados por dia crescente. Para 2 e mês 1 o resultado é `[3,4]`; para 4 e mês 12 é `[]`.

```prolog
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

% Define o predicado pedido.

```



### Testes

**Ordenar**


```prolog
main :- get_following_birthdays(2,1,L), write_canonical(L), nl.
```


Saída esperada:

```text
[3,4]
```

**Gerar utilizadores**


```prolog
main :- findall(U-L, get_following_birthdays(U,1,L), R), write_canonical(R), nl.
```


Saída esperada:

```text
[-(1,[3]),-(2,[3,4]),-(3,[]),-(4,[]),-(5,[3,4])]
```

Solução

```
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

get_following_birthdays(U, M, IDs) :- user(U, _, _, F), findall(D-V, (member(V, F), user(V, _, D-M-_, _)), Pairs), keysort(Pairs, Sorted), birthday_ids(Sorted, IDs).
birthday_ids([], []).
birthday_ids([_-V|Rest], [V|IDs]) :- birthday_ids(Rest, IDs).
```

Relaciona os factos pelos identificadores e verifica as condições pedidas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Agrupar vídeos por género

Os factos dados representam utilizadores, datas de nascimento, pessoas seguidas e vídeos.

Define `group_videos_by_genre(+UserID, -ListOfPairs)`, com pares `Genre-VideoIDs` sem duplicados. A ordem dos pares e dos identificadores é livre. Para 1, um resultado é `[education-[10,11]]`; para 6 é `[]`.

```prolog
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

% Define o predicado pedido.

```



### Testes

**Grupo**


```prolog
main :- group_videos_by_genre(1,L), msort(L,S), write_canonical(S), nl.
```


Saída esperada:

```text
[-(education,[10,11])]
```

**Sem vídeos**


```prolog
main :- group_videos_by_genre(6,L), write_canonical(L), nl.
```


Saída esperada:

```text
[]
```

Solução

```
% user(UserID, Name, BirthDate, FollowingList).
user(1, 'Alice', 12-05-1999, [2,3]).
user(2, 'Bruno', 23-11-2000, [1,3,4]).
user(3, 'Carla', 01-01-1997, [1]).
user(4, 'Diana', 30-01-1997, []).
user(5, 'Edgar', 15-03-1999, [1,2,3,4]).
% video(VideoID, UserID, Title, Genre).
video(10, 1, 'Prolog for Beginners', education).
video(11, 1, 'Logic Puzzles Explained', education).
video(12, 2, 'Daily Coding Vlog', vlog).
video(13, 3, 'Functional vs Logic', tech).
video(14, 3, 'Cooking with Recursion', cooking).
video(15, 4, 'Travel in Portugal', travel).
video(16, 5, 'Advanced Prolog Tricks', education).

group_videos_by_genre(U, Pairs) :- findall(G, video(_, U, _, G), Gs), sort(Gs, Genres), genre_pairs(Genres, U, Pairs).
genre_pairs([], _, []).
genre_pairs([G|Gs], U, [G-IDs|Pairs]) :- findall(V, video(V, U, _, G), Vs), sort(Vs, IDs), genre_pairs(Gs, U, Pairs).
```

Relaciona os factos pelos identificadores e verifica as condições pedidas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#corte-e-findall)

Atores e filmes de uma personagem

Os factos `by(Character, Movie, Actor)` associam personagens, filmes ou séries e atores.

Define `playedBy(+Character, -List)`, uma lista de pares `Actor-Movies` com os atores que interpretaram a personagem e os seus filmes ou séries. A ordem é livre. Para `jackRyan`, inclui `benAffleck-[theSumOfAllFears]`, `alecBaldwin-[theHuntForRedOctober]` e `harrisonFord-[patriotGames,clearAndPresentDanger]`.

```prolog
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

% Define o predicado pedido.

```



### Testes

**Um ator**


```prolog
main :- playedBy(president,L), write_canonical(L), nl.
```


Saída esperada:

```text
[-(harrisonFord,[airForceOne])]
```

**Ausente**


```prolog
main :- playedBy(nobody,L), write_canonical(L), nl.
```


Saída esperada:

```text
[]
```

Solução

```
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

playedBy(C, L) :- findall(A, by(C, _, A), As), sort(As, Actors), findall(A-Ms, (member(A, Actors), findall(M, by(C, M, A), Ms)), L).
```

Relaciona os factos pelos campos pedidos, preservando as condições e os resultados distintos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#escolher-a-recolha)

Atores com mais filmes

Os factos `by(Character, Movie, Actor)` associam personagens, filmes ou séries e atores.

Define `most_popular(+Exclude, -List, -NMovies)`. Devolve todos os atores não excluídos com o maior número de filmes ou séries distintos, e esse número. A ordem em caso de empate é livre. Com `[]` são `harrisonFord` e `jenniferGarner`, com 3; excluindo o primeiro fica só a segunda, e excluindo ambos há seis atores com 2.

```prolog
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

% Define o predicado pedido.

```



### Testes

**Empate**


```prolog
main :- most_popular([],L,N), msort(L,S), write_canonical(S-N), nl.
```


Saída esperada:

```text
-([harrisonFord,jenniferGarner],3)
```

**Exclusão**


```prolog
main :- most_popular([harrisonFord],L,N), write_canonical(L-N), nl.
```


Saída esperada:

```text
-([jenniferGarner],3)
```

Solução

```
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

most_popular(Exclude, List, N) :- setof(A, C^M^(by(C,M,A), \+ member(A,Exclude)), Actors), findall(Count-A, (member(A,Actors), setof(M,C^by(C,M,A),Movies), length(Movies,Count)), Pairs), keysort(Pairs,Sorted), last(Sorted,N-_), findall(A,member(N-A,Sorted),List).
```

Relaciona os factos pelos campos pedidos, preservando as condições e os resultados distintos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#escolher-a-recolha)

Livros com mais géneros

Os factos usam `author(ID, Nome, AnoNascimento, País)` e `book(Título, IDAutor, Ano, Páginas, Géneros)`.

Define `diverse_books(-Books)` com todos os títulos que têm o maior número de géneros; qualquer ordem é aceite. Neste conjunto, o resultado é `['Prey']`.

```prolog
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

% Define aqui o predicado pedido.
```



### Testes

**Máximo**


```prolog
main :- diverse_books(L),sort(L,S),write_canonical(S),nl.
```


Saída esperada:

```text
['Prey']
```

**Uma solução**


```prolog
main :- findall(L,diverse_books(L),Ls),length(Ls,N),write(N),nl.
```


Saída esperada:

```text
1
```

Solução

```
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

diverse_books(Bs) :- findall(T,(book(T,_,_,_,Gs),length(Gs,N),\+ (book(_,_,_,_,Hs),length(Hs,M),M>N)),Bs).
```

Recolhe os livros para os quais não há outro com mais géneros.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Autores por país

Os factos usam `author(ID, Nome, AnoNascimento, País)` e `book(Título, IDAutor, Ano, Páginas, Géneros)`.

Define `country_authors(?Country, ?Authors)`, relacionando cada país de nascimento com a lista de todos os seus autores. Para USA são John Grisham, Stephen King e Michael Crichton; para Zambia, Wilbur Smith.

```prolog
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

% Define aqui o predicado pedido.
```



### Testes

**Países**


```prolog
main :- findall(C-As,country_authors(C,As),L),sort(L,S),write_canonical(S),nl.
```


Saída esperada:

```text
[-('USA',['John Grisham','Stephen King','Michael Crichton']),-('Zambia',['Wilbur Smith'])]
```

**Ausente**


```prolog
main :- findall(A,country_authors('Portugal',A),L),write_canonical(L),nl.
```


Saída esperada:

```text
[]
```

Solução

```
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

country_authors(C,As) :- bagof(A,I^Y^author(I,A,Y,C),As).
```

`bagof` agrupa por país e as variáveis existenciais não criam grupos separados.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Livros populares

Os factos usam `author(ID, Nome, AnoNascimento, País)` e `book(Título, IDAutor, Ano, Páginas, Géneros)`.

Um livro é popular quando pelo menos 75% dos membros do clube o leram. Define `popular(?Title)`. The Client falha e The Firm é popular.

```prolog
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).
read_book(bernardete,'The Firm').
read_book(bernardete,'The Client').
read_book(clarice,'The Firm').
read_book(clarice,'Carrie').
read_book(deirdre,'The Firm').
read_book(deirdre,'Next').

% Define aqui o predicado pedido.
```



### Testes

**Todos**


```prolog
main :- findall(T,popular(T),L),write_canonical(L),nl.
```


Saída esperada:

```text
['The Firm']
```

**Não popular**


```prolog
main :- (popular('The Client')->write(sim);write(nao)),nl.
```


Saída esperada:

```text
nao
```

Solução

```
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).
read_book(bernardete,'The Firm').
read_book(bernardete,'The Client').
read_book(clarice,'The Firm').
read_book(clarice,'Carrie').
read_book(deirdre,'The Firm').
read_book(deirdre,'Next').

popular(T) :- setof(P,B^read_book(P,B),All), length(All,N), setof(P,read_book(P,T),Readers), length(Readers,K), 4*K >= 3*N.
```

Conta pessoas distintas no clube e para cada título, comparando a proporção sem arredondar.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Géneros comuns

Implementa `shared_genres(?Title1, ?Title2, -CommonGenres)`. Devolve os géneros comuns aos dois livros, em qualquer ordem.

```prolog
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

% shared_genres(Title1, Title2, CommonGenres).
```



### Testes

**Interseção**


```prolog
main :- findall(S, (shared_genres('Prey','Next',L), sort(L,S)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[['Science fiction','Techno-thriller']]
```

**Sem interseção**


```prolog
main :- findall(X, (shared_genres('Carrie','The Firm',X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[[]]
```

**Título inexistente**


```prolog
main :- findall(X, (shared_genres('Carrie',inexistente,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

Solução

```
author(1,'John Grisham',1955,'USA').
author(2,'Wilbur Smith',1933,'Zambia').
author(3,'Stephen King',1947,'USA').
author(4,'Michael Crichton',1942,'USA').
book('The Firm',1,1991,432,['Legal thriller']).
book('The Client',1,1993,422,['Legal thriller']).
book('The Runaway Jury',1,1996,414,['Legal thriller']).
book('The Exchange',1,2023,338,['Legal thriller']).
book('Carrie',3,1974,199,['Horror']).
book('The Shining',3,1977,447,['Gothic novel','Horror','Psychological horror']).
book('Under the Dome',3,2009,1074,['Science fiction','Political']).
book('Doctor Sleep',3,2013,531,['Horror','Gothic','Dark fantasy']).
book('Jurassic Park',4,1990,399,['Science fiction']).
book('Prey',4,2002,502,['Science fiction','Techno-thriller','Horror','Nanopunk']).
book('Next',4,2006,528,['Science fiction','Techno-thriller','Satire']).

shared_genres(T1,T2,Common) :-
    book(T1,_,_,_,G1), book(T2,_,_,_,G2),
    findall(G, (member(G,G1), memberchk(G,G2)), Common).
```

Percorre os géneros do primeiro livro e conserva os que também pertencem ao segundo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

findall e setof

Qual é uma diferença entre `findall/3` e `setof/3`?

Solução

`setof/3` ordena, remove duplicados e pode agrupar por variáveis livres; `findall/3` recolhe todas numa lista.

`findall` devolve uma lista vazia quando não há soluções; `setof` falha.

*   **`findall/3` remove duplicados automaticamente e `setof/3` conserva-os..** Esta opção não descreve o comportamento indicado.
*   **`findall/3` devolve só a primeira solução e `setof/3` devolve todas..** Esta opção não descreve o comportamento indicado.
*   **`setof/3` ordena, remove duplicados e pode agrupar por variáveis livres; `findall/3` recolhe todas numa lista..** `findall` devolve uma lista vazia quando não há soluções; `setof` falha.
*   **`setof/3` falha sem soluções e `findall/3` lança um erro..** Esta opção não descreve o comportamento indicado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

Recolher soluções

Para `predX/3`, considera A: `findall(X,predX(1,X,_),L)`, B: `setof(X,predX(1,X,_),L)`, C: `setof(X,Y^predX(1,X,Y),L)`, D: `bagof(X,predX(1,X,_),L)` e E: `bagof(X,Y^predX(1,X,Y),L)`. Qual par recolhe a mesma lista quando existe pelo menos uma solução?

Solução

Só A e E

A e E preservam ordem e repetidos sem agrupar pela terceira variável. Sem soluções, `findall` devolve `[]`, enquanto `bagof` falha, pelo que não são equivalentes nesse caso.

*   **Só A e E.** A e E preservam ordem e repetidos sem agrupar pela terceira variável. Sem soluções, `findall` devolve `[]`, enquanto `bagof` falha, pelo que não são equivalentes nesse caso.
*   **Só C e E.** Esta opção não corresponde ao comportamento descrito.
*   **Só B e D.** Esta opção não corresponde ao comportamento descrito.
*   **A, B e D.** Esta opção não corresponde ao comportamento descrito.
*   **Só A e C.** Esta opção não corresponde ao comportamento descrito.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

## Árvores SLD e execução

Folha de falha SLD

Numa árvore de execução SLD, o que representa uma folha de falha?

Solução

Um ponto em que é necessário retroceder porque nenhuma cabeça de cláusula unificou com o objetivo atual.

Sem cláusula aplicável a esse objetivo, esse ramo falha.

*   **Uma prova com sucesso de todos os objetivos da query..** Esta opção não descreve o comportamento indicado.
*   **Um ponto em que é necessário retroceder porque nenhuma cabeça de cláusula unificou com o objetivo atual..** Sem cláusula aplicável a esse objetivo, esse ramo falha.
*   **Um erro de sintaxe que interrompe toda a pesquisa..** Esta opção não descreve o comportamento indicado.
*   **Um ponto em que Prolog evita o retrocesso e fixa o ramo atual..** Esta opção não descreve o comportamento indicado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

Escolher a árvore SLD de append

```
append([], L, L).
append([H|T], L, [H|T2]) :- append(T, L, T2).
```

Qual das quatro árvores SLD corresponde a `append(X,Y,[1,2])` para as cláusulas apresentadas? Considere a seleção de objetivos à esquerda e a ordem das cláusulas.

a)

![Árvore a: ramo recursivo à direita, com objetivo seguinte append(T,Y,[2]). As folhas dão três substituições.](https://resumos.rgo.pt/cadeiras/pfl/exercicios-mt2/figura-1.svg)

b)

![Árvore b: ramo recursivo à esquerda, com objetivo seguinte append(T,Y,[2]). As folhas dão três substituições.](https://resumos.rgo.pt/cadeiras/pfl/exercicios-mt2/figura-2.svg)

c)

![Árvore c: ramo recursivo à direita, com objetivo seguinte append(X,T,[2]). As folhas dão três substituições.](https://resumos.rgo.pt/cadeiras/pfl/exercicios-mt2/figura-3.svg)

d)

![Árvore d: ramo recursivo à esquerda, com objetivo seguinte append(X,T,[2]). As folhas dão três substituições.](https://resumos.rgo.pt/cadeiras/pfl/exercicios-mt2/figura-4.svg)

Solução

?- append(X,Y,\[1,2\]). X = \[\], Y = \[1,2\] ; X = \[1\], Y = \[2\] ; X = \[1,2\], Y = \[\].

A alternativa a conserva a ordem das cláusulas e as substituições. As três respostas correspondem aos três pontos de corte da lista. No último nó só a cláusula base unifica com a terceira lista vazia.

*   **a. Árvore a..** A primeira cláusula produz a resposta imediata à esquerda; a segunda retira a cabeça do primeiro argumento e recorre sobre a cauda.
*   **b. Árvore b..** Os ramos estão trocados: a cláusula recursiva é visitada antes da cláusula base.
*   **c. Árvore c..** O objetivo intermédio deve ser append(T,Y,\[2\]), pois a recursão retira a cabeça do primeiro argumento.
*   **d. Árvore d..** A árvore troca a ordem dos ramos e recorre sobre o segundo argumento em vez do primeiro.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#resolu%C3%A7%C3%A3o-sld-passo-a-passo)

Ramos da pesquisa

Na consulta `member(X,[a,b,c,d,e]), !, member(Y,[1,2,3,4])`, quantos filhos sobrevivem na raiz da árvore de pesquisa após aplicar o corte?

Solução

1

Após o corte só sobrevive o ramo em que `X=a`. Antes de podar, o número de ramos depende da representação da árvore e da definição de `member/2`.

*   **3.** Esta opção não corresponde ao comportamento descrito.
*   **1.** Após o corte só sobrevive o ramo em que `X=a`. Antes de podar, o número de ramos depende da representação da árvore e da definição de `member/2`.
*   **5.** Esta opção não corresponde ao comportamento descrito.
*   **2.** Esta opção não corresponde ao comportamento descrito.
*   **0.** Esta opção não corresponde ao comportamento descrito.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Unificações e corte

Na consulta `member(X,[a,b,c,d,e]), !, member(Y,[1,2,3,4])`, quantas unificações de `X` e `Y` com elementos das listas ocorrem ao pedir todas as soluções?

Solução

5

O corte fixa `X=a`; depois `Y` unifica com os quatro elementos, num total de cinco unificações de valores.

*   **1.** Esta opção não corresponde ao comportamento descrito.
*   **9.** Esta opção não corresponde ao comportamento descrito.
*   **4.** Esta opção não corresponde ao comportamento descrito.
*   **20.** Esta opção não corresponde ao comportamento descrito.
*   **5.** O corte fixa `X=a`; depois `Y` unifica com os quatro elementos, num total de cinco unificações de valores.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

## Procura, grafos e simulação

Ligação entre atores

Os factos `by(Character, Movie, Actor)` associam personagens, filmes ou séries e atores.

Define `connection_link(+Actor1, +Actor2, -ConnectionList)` com uma ligação possível como lista alternada de atores e filmes em que trabalharam juntos. Falha quando não existe ligação. Exemplos: `[jenniferAniston,friends,courteneyCox]` e `[jenniferGarner,daredevil,benAffleck,theSumOfAllFears,bridgetMoynahan]`.

```prolog
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

% Define o predicado pedido.

```



### Testes

**Direta**


```prolog
main :- once(connection_link(jenniferAniston,courteneyCox,L)), write_canonical(L), nl.
```


Saída esperada:

```text
[jenniferAniston,friends,courteneyCox]
```

**Sem ligação**


```prolog
main :- findall(L, connection_link(jenniferAniston,benAffleck,L), R), write_canonical(R), nl.
```


Saída esperada:

```text
[]
```

Solução

```
:- dynamic by/3.
% by(Character, Movie, Actor).
by(jackRyan, theSumOfAllFears, benAffleck).
by(cathyMuller, theSumOfAllFears, bridgetMoynahan).
by(jackRyan, theHuntForRedOctober, alecBaldwin).
by(jackRyan, patriotGames, harrisonFord).
by(cathyMuller, patriotGames, anneArcher).
by(jackRyan, clearAndPresentDanger, harrisonFord).
by(cathyMuller, clearAndPresentDanger, anneArcher).
by(president, airForceOne, harrisonFord).
by(frasierCrane, cheers, kelseyGrammer).
by(frasierCrane, frasier, kelseyGrammer).
by(rachelGreen, friends, jenniferAniston).
by(monicaGeller, friends, courteneyCox).
by(phoebeBuffay, friends, lisaKudrow).
by(ursulaBuffay, friends, lisaKudrow).
by(joeyTribbiani, friends, mattLeBlanc).
by(joeyTribbiani, joey, mattLeBlanc).
by(alexGarrett, joey, andreaAnders).
by(stephenColbert, dailyShow, stephenColbert).
by(stephenColbert, theColbertReport, stephenColbert).
by(addisonMontgomery, privatePractice, kateWalsh).
by(addisonMontgomery, greysAnatomy, kateWalsh).
by(mattMurdock, daredevil, benAffleck).
by(elektraNatchios, daredevil, jenniferGarner).
by(elektraNatchios, elektra, jenniferGarner).
by(elektraNatchios, elektra, lauraWard).
by(sydneyBristow, alias, jenniferGarner).

connection_link(A, B, L) :- connection_path(A, B, [A], L).
connection_path(A, B, Seen, [A,M,B]) :- by(_, M, A), by(_, M, B), A \= B, \+ member(B, Seen).
connection_path(A, B, Seen, [A,M|Rest]) :- by(_, M, A), by(_, M, Next), A \= Next, Next \= B, \+ member(Next, Seen), connection_path(Next, B, [Next|Seen], Rest).
```

Relaciona os factos pelos campos pedidos, preservando as condições e os resultados distintos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#escolher-a-recolha)

Resolver o cadeado

Não utilizes nenhuma biblioteca do Prolog, excepto a CLPFD.

Define `solve(+Code,+Key,-States)`, com o estado inicial, estados intermédios e final, sem repetições. Key contém o primeiro elemento pretendido de cada disco. Privilegia caminhos curtos. Para `[6,0,4]`, um caminho é `[[[3,6,8],[5,0,7],[2,1,4]],[[6,8,3],[5,0,7],[2,1,4]],[[6,8,3],[0,7,5],[2,1,4]],[[6,8,3],[0,7,5],[4,2,1]]]`. Por exemplo, para `[[3,6,8],[5,0,7],[2,1,4]]` e `[6,5,1]`, um caminho passa por `[[6,8,3],[5,0,7],[2,1,4]]` antes de chegar a `[[6,8,3],[5,0,7],[1,4,2]]`.

```prolog
rotate(C,I,R,N) :- nth1(I,C,D,Rest), length(D,L), L>0, K is R mod L, length(A,K), append(A,B,D), append(B,A,E), nth1(I,N,E,Rest).
matches([],[]).
matches([[H|_]|Ds],[H|Ks]) :- matches(Ds,Ks).
move(C,N) :- nth1(I,C,D), length(D,L), Max is L-1, between(1,Max,R), rotate(C,I,R,N).

% Define aqui o predicado pedido.
```



### Testes

**Já alinhado**


```prolog
main :- solve([[1,2]],[1],S),write_canonical(S),nl.
```


Saída esperada:

```text
[[[1,2]]]
```

**Um movimento**


```prolog
main :- solve([[1,2]],[2],S),write_canonical(S),nl.
```


Saída esperada:

```text
[[[1,2]],[[2,1]]]
```

**Impossível**


```prolog
main :- (solve([[1,2]],[3],_)->write(sim);write(nao)),nl.
```


Saída esperada:

```text
nao
```

Solução

```
rotate(C,I,R,N) :- nth1(I,C,D,Rest), length(D,L), L>0, K is R mod L, length(A,K), append(A,B,D), append(B,A,E), nth1(I,N,E,Rest).
matches([],[]).
matches([[H|_]|Ds],[H|Ks]) :- matches(Ds,Ks).
move(C,N) :- nth1(I,C,D), length(D,L), Max is L-1, between(1,Max,R), rotate(C,I,R,N).

solve(C,K,States) :- bfs([[C]],K,States).
bfs([[C|Path]|_],K,States) :- matches(C,K), !, reverse([C|Path],States).
bfs([[C|Path]|Queue],K,States) :- findall([N,C|Path],(move(C,N), \+ member(N,[C|Path])),Next), append(Queue,Next,Q), bfs(Q,K,States).
```

A pesquisa em largura explora primeiro caminhos mais curtos e impede ciclos em cada caminho.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Encontrar códigos consistentes

Define `solve(+Scores, ?Key)`, gerando por retrocesso todas as chaves de quatro dígitos de 1 a 9, com repetição permitida, consistentes com cada `score(Guess,CC,CE)`. Para `[score([1,2,3,4],2,2)]` as chaves são `[1,2,4,3]`, `[1,3,2,4]`, `[1,4,3,2]`, `[2,1,3,4]`, `[3,2,1,4]` e `[4,2,3,1]`.

```prolog
score(Guess,Key,CC,CE) :- right_position(Guess,Key,CC), any_position(Guess,Key,CA), CE is CA-CC.
right_position([],[],0).
right_position([X|Xs],[Y|Ys],N) :- right_position(Xs,Ys,M), (X=Y -> N is M+1 ; N=M).
any_position([],_,0).
any_position([X|Xs],Ys,N) :- (select(X,Ys,Zs) -> any_position(Xs,Zs,M), N is M+1 ; any_position(Xs,Ys,N)).

% Define aqui o predicado pedido.
```



### Testes

**Exemplo**


```prolog
main :- findall(K,solve([score([1,2,3,4],2,2)],K),L),sort(L,S),write_canonical(S),nl.
```


Saída esperada:

```text
[[1,2,4,3],[1,3,2,4],[1,4,3,2],[2,1,3,4],[3,2,1,4],[4,2,3,1]]
```

**Repetição**


```prolog
main :- findall(K,solve([score([1,1,1,1],4,0)],K),L),write_canonical(L),nl.
```


Saída esperada:

```text
[[1,1,1,1]]
```

**Incompatível**


```prolog
main :- findall(K,solve([score([1,1,1,1],4,0),score([1,1,1,1],0,0)],K),L),write_canonical(L),nl.
```


Saída esperada:

```text
[]
```

Solução

```
score(Guess,Key,CC,CE) :- right_position(Guess,Key,CC), any_position(Guess,Key,CA), CE is CA-CC.
right_position([],[],0).
right_position([X|Xs],[Y|Ys],N) :- right_position(Xs,Ys,M), (X=Y -> N is M+1 ; N=M).
any_position([],_,0).
any_position([X|Xs],Ys,N) :- (select(X,Ys,Zs) -> any_position(Xs,Zs,M), N is M+1 ; any_position(Xs,Ys,N)).

solve(Scores,Key) :- length(Key,4), maplist(digit,Key), consistent(Scores,Key).
digit(X) :- between(1,9,X).
consistent([],_).
consistent([score(G,C,E)|Ss],K) :- score(G,K,C,E), consistent(Ss,K).
```

Gera os quatro dígitos e verifica cada resultado com score.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/logica-unificacao-prolog/#factos-regras-e-queries)

Arestas comuns

Implementa `common_edges(+G1,+G2,?L)` para grafos não dirigidos. Cada facto `edge(G,A,B)` representa uma aresta; aceita-se qualquer ordem e orientação. Para `g1` e `g2` há seis arestas comuns.

```prolog
edge(g1,br,o). edge(g1,br,ni). edge(g1,o,ni). edge(g1,o,c). edge(g1,o,h). edge(g1,h,c). edge(g1,h,n). edge(g1,n,he). edge(g1,c,he).
edge(g2,br,h). edge(g2,br,ni). edge(g2,h,ni). edge(g2,h,o). edge(g2,h,c). edge(g2,o,c). edge(g2,o,n). edge(g2,n,he). edge(g2,c,he). edge(g2,cl,he).

% common_edges(G1,G2,L).
```



### Testes

**Interseção**


```prolog
main :- common_edges(g1,g2,L), length(L,N), writeln(N).
```


Saída esperada:

```text
6
```

**Mesmo grafo**


```prolog
main :- common_edges(g1,g1,L), length(L,N), writeln(N).
```


Saída esperada:

```text
9
```

**Sem arestas**


```prolog
main :- common_edges(g1,inexistente,L), writeln(L).
```


Saída esperada:

```text
[]
```

Solução

```
edge(g1,br,o). edge(g1,br,ni). edge(g1,o,ni). edge(g1,o,c). edge(g1,o,h). edge(g1,h,c). edge(g1,h,n). edge(g1,n,he). edge(g1,c,he).
edge(g2,br,h). edge(g2,br,ni). edge(g2,h,ni). edge(g2,h,o). edge(g2,h,c). edge(g2,o,c). edge(g2,o,n). edge(g2,n,he). edge(g2,c,he). edge(g2,cl,he).
undirected(G,A,B) :- edge(G,A,B); edge(G,B,A).
common_edges(G,H,L) :- findall(A-B,(edge(G,X,Y),undirected(H,X,Y),sort([X,Y],[A,B])),Pairs), sort(Pairs,L).
```

Normaliza cada par de extremos antes de eliminar duplicados. A consulta inversa reconhece arestas guardadas na orientação oposta.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Componentes comuns

Implementa `common_subgraphs(+G1,+G2,?Subgraphs)`: devolve as componentes conexas formadas pelas arestas comuns dos grafos não dirigidos. Qualquer ordem é aceite. No exemplo são `[[br,ni],[c,h,he,n,o]]`.

```prolog
edge(g1,br,o). edge(g1,br,ni). edge(g1,o,ni). edge(g1,o,c). edge(g1,o,h). edge(g1,h,c). edge(g1,h,n). edge(g1,n,he). edge(g1,c,he).
edge(g2,br,h). edge(g2,br,ni). edge(g2,h,ni). edge(g2,h,o). edge(g2,h,c). edge(g2,o,c). edge(g2,o,n). edge(g2,n,he). edge(g2,c,he). edge(g2,cl,he).

% common_subgraphs(G1,G2,Subgraphs).
```



### Testes

**Componentes**


```prolog
main :- common_subgraphs(g1,g2,C), writeln(C).
```


Saída esperada:

```text
[[br,ni],[c,h,he,n,o]]
```

**Sem arestas comuns**


```prolog
main :- common_subgraphs(g1,nenhum,C), writeln(C).
```


Saída esperada:

```text
[]
```

**Mesmo grafo**


```prolog
main :- common_subgraphs(g1,g1,C), writeln(C).
```


Saída esperada:

```text
[[br,c,h,he,n,ni,o]]
```

Solução

```
edge(g1,br,o). edge(g1,br,ni). edge(g1,o,ni). edge(g1,o,c). edge(g1,o,h). edge(g1,h,c). edge(g1,h,n). edge(g1,n,he). edge(g1,c,he).
edge(g2,br,h). edge(g2,br,ni). edge(g2,h,ni). edge(g2,h,o). edge(g2,h,c). edge(g2,o,c). edge(g2,o,n). edge(g2,n,he). edge(g2,c,he). edge(g2,cl,he).
common_edge(G,H,A,B) :- edge(G,X,Y), (edge(H,X,Y);edge(H,Y,X)), (A=X,B=Y;A=Y,B=X).
reach(G,H,X,Seen,Out) :- findall(Y,(member(Z,Seen),common_edge(G,H,Z,Y),\+ memberchk(Y,Seen)),Ys), append(Seen,Ys,All), sort(All,Next), (Next=Seen -> Out=Seen ; reach(G,H,X,Next,Out)).
components(_,_,[],[]).
components(G,H,[X|Xs],[C|Cs]) :- reach(G,H,X,[X],C), subtract(Xs,C,Rest), components(G,H,Rest,Cs).
common_subgraphs(G,H,Cs) :- findall(X,common_edge(G,H,X,_),Vs), sort(Vs,Sorted), components(G,H,Sorted,Cs).
```

Forma o grafo das arestas comuns e percorre cada componente uma só vez.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Simular gerações

Implementa `play(+DecNumber, +Bits, +Padding, +Rule, +N)`. Inicializa o estado e as regras, depois imprime as primeiras `N` gerações; para `N = 1`, imprime apenas a inicial.

```prolog
dec2bin(Dec, Bits, N) :- integer(Dec), integer(N), Dec >= 0, N >= 0, binary_digits(Dec,N,[],Bits).
binary_digits(0,0,Bits,Bits).
binary_digits(Dec,N,Acc,Bits) :- N > 0, Bit is Dec mod 2, Next is Dec div 2, N1 is N-1, binary_digits(Next,N1,[Bit|Acc],Bits).
:- dynamic rule/2.
update_rule(R) :- integer(R), between(0,255,R), retractall(rule(_,_)), forall(between(0,7,I), (L is I div 4, S is (I div 2) mod 2, Right is I mod 2, Bit is (R >> I) /\ 1, assertz(rule(L-S-Right,Bit)))).
next_gen(Previous,Next) :- next_cells(0,Previous,Next).
next_cells(_,[],[]).
next_cells(Left,[Self],[New]) :- rule(Left-Self-0,New).
next_cells(Left,[Self,Right|Rest],[New|Tail]) :- rule(Left-Self-Right,New), next_cells(Self,[Right|Rest],Tail).
print_generation(Bits) :- write('|'), print_bits(Bits,0), nl.
print_bits([], _).
print_bits([B|Bs], N) :- (B = 0 -> write('.') ; B = 1, write('M')), N1 is N+1, (N1 mod 8 =:= 0 -> write('|') ; true), print_bits(Bs,N1).
initialize(D,B,P,L) :- dec2bin(D,M,B), integer(P), P>=0, length(S,P), maplist(=(0),S), append([S,M,S],L).

% play(DecNumber, Bits, Padding, Rule, N).
```



### Testes

**Uma**


```prolog
main :- play(2,4,0,210,1).
```


Saída esperada:

```text
|..M.
```

**Duas**


```prolog
main :- play(2,4,0,210,2).
```


Saída esperada:

```text
|..M.
|.M.M
```

**Zero**


```prolog
main :- play(2,4,0,210,0).
```


Saída esperada:

```text

```

Solução

```
dec2bin(Dec, Bits, N) :- integer(Dec), integer(N), Dec >= 0, N >= 0, binary_digits(Dec,N,[],Bits).
binary_digits(0,0,Bits,Bits).
binary_digits(Dec,N,Acc,Bits) :- N > 0, Bit is Dec mod 2, Next is Dec div 2, N1 is N-1, binary_digits(Next,N1,[Bit|Acc],Bits).
:- dynamic rule/2.
update_rule(R) :- integer(R), between(0,255,R), retractall(rule(_,_)), forall(between(0,7,I), (L is I div 4, S is (I div 2) mod 2, Right is I mod 2, Bit is (R >> I) /\ 1, assertz(rule(L-S-Right,Bit)))).
next_gen(Previous,Next) :- next_cells(0,Previous,Next).
next_cells(_,[],[]).
next_cells(Left,[Self],[New]) :- rule(Left-Self-0,New).
next_cells(Left,[Self,Right|Rest],[New|Tail]) :- rule(Left-Self-Right,New), next_cells(Self,[Right|Rest],Tail).
print_generation(Bits) :- write('|'), print_bits(Bits,0), nl.
print_bits([], _).
print_bits([B|Bs], N) :- (B = 0 -> write('.') ; B = 1, write('M')), N1 is N+1, (N1 mod 8 =:= 0 -> write('|') ; true), print_bits(Bs,N1).
initialize(D,B,P,L) :- dec2bin(D,M,B), integer(P), P>=0, length(S,P), maplist(=(0),S), append([S,M,S],L).

play(D,B,P,R,N) :- integer(N), N>=0, initialize(D,B,P,Initial), update_rule(R), play_generations(N,Initial).
play_generations(0,_).
play_generations(N,State) :- N>0, print_generation(State), N1 is N-1, (N1=:=0 -> true ; next_gen(State,Next), play_generations(N1,Next)).
```

Imprime o estado inicial e aplica as regras entre gerações sucessivas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Tamanho de um círculo

Cada pessoa oferece um livro ao destinatário indicado; cada ciclo fecha ao voltar à pessoa inicial.

Implementa `circle_size(+Person, ?Size)`, o número de pessoas no ciclo de ofertas que contém a pessoa.

```prolog
gives_gift_to(bernardete,'The Exchange',celestina).
gives_gift_to(celestina,'The Brethren',eleuterio).
gives_gift_to(eleuterio,'The Summons',felismina).
gives_gift_to(felismina,'River God',juvenaldo).
gives_gift_to(juvenaldo,'Seventh Scroll',leonilde).
gives_gift_to(leonilde,'Sunbird',bernardete).
gives_gift_to(marciliano,'Those in Peril',nivaldo).
gives_gift_to(nivaldo,'Vicious Circle',sandrino).
gives_gift_to(sandrino,'Predator',marciliano).

% circle_size(Person, Size).
```



### Testes

**Primeiro**


```prolog
main :- findall(X, (circle_size(bernardete,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[6]
```

**Segundo**


```prolog
main :- findall(X, (circle_size(marciliano,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[3]
```

**Desconhecida**


```prolog
main :- findall(X, (circle_size(outra,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[]
```

Solução

```
gives_gift_to(bernardete,'The Exchange',celestina).
gives_gift_to(celestina,'The Brethren',eleuterio).
gives_gift_to(eleuterio,'The Summons',felismina).
gives_gift_to(felismina,'River God',juvenaldo).
gives_gift_to(juvenaldo,'Seventh Scroll',leonilde).
gives_gift_to(leonilde,'Sunbird',bernardete).
gives_gift_to(marciliano,'Those in Peril',nivaldo).
gives_gift_to(nivaldo,'Vicious Circle',sandrino).
gives_gift_to(sandrino,'Predator',marciliano).

circle(Person,People) :- gives_gift_to(Person,_,Next), circle_follow(Next,Person,[Person],People).
circle_follow(Start,Start,Acc,Acc).
circle_follow(P,Start,Acc,People) :- P \= Start, \+ memberchk(P,Acc), gives_gift_to(P,_,Next), circle_follow(Next,Start,[P|Acc],People).
circle_size(Person,Size) :- circle(Person,People), length(People,Size).
```

Segue cada destinatário até regressar ao ponto de partida e conta as pessoas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Maior círculo de ofertas

Cada pessoa oferece um livro ao destinatário indicado; cada ciclo fecha ao voltar à pessoa inicial.

Implementa `largest_circle(?People)`. Devolve cada círculo de tamanho máximo uma vez por retrocesso. A ordem das pessoas e dos círculos não importa.

```prolog
gives_gift_to(bernardete,'The Exchange',celestina).
gives_gift_to(celestina,'The Brethren',eleuterio).
gives_gift_to(eleuterio,'The Summons',felismina).
gives_gift_to(felismina,'River God',juvenaldo).
gives_gift_to(juvenaldo,'Seventh Scroll',leonilde).
gives_gift_to(leonilde,'Sunbird',bernardete).
gives_gift_to(marciliano,'Those in Peril',nivaldo).
gives_gift_to(nivaldo,'Vicious Circle',sandrino).
gives_gift_to(sandrino,'Predator',marciliano).

% largest_circle(People).
```



### Testes

**Maior**


```prolog
main :- findall(S,(largest_circle(P),sort(P,S)),Xs), sort(Xs,R), write_canonical(R), nl.
```


Saída esperada:

```text
[[bernardete,celestina,eleuterio,felismina,juvenaldo,leonilde]]
```

**Tamanho**


```prolog
main :- findall(X, (largest_circle(P), length(P,X)), Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[6]
```

Solução

```
gives_gift_to(bernardete,'The Exchange',celestina).
gives_gift_to(celestina,'The Brethren',eleuterio).
gives_gift_to(eleuterio,'The Summons',felismina).
gives_gift_to(felismina,'River God',juvenaldo).
gives_gift_to(juvenaldo,'Seventh Scroll',leonilde).
gives_gift_to(leonilde,'Sunbird',bernardete).
gives_gift_to(marciliano,'Those in Peril',nivaldo).
gives_gift_to(nivaldo,'Vicious Circle',sandrino).
gives_gift_to(sandrino,'Predator',marciliano).

circle(Person,People) :- gives_gift_to(Person,_,Next), circle_follow(Next,Person,[Person],People).
circle_follow(Start,Start,Acc,Acc).
circle_follow(P,Start,Acc,People) :- P \= Start, \+ memberchk(P,Acc), gives_gift_to(P,_,Next), circle_follow(Next,Start,[P|Acc],People).
largest_circle(People) :- setof(Size-Sorted, P^C^Gift^Recipient^(gives_gift_to(P,Gift,Recipient),circle(P,C),sort(C,Sorted),length(Sorted,Size)),Pairs), last(Pairs,Max-_), member(Max-People,Pairs).
```

Ordena cada ciclo para eliminar rotações, encontra o tamanho máximo e devolve todos os ciclos desse tamanho.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

## CLP(FD): domínios e propagação

Erro na restrição de produto

```
:- use_module(library(clpfd)).
restricao_produto([], _, 1).
restricao_produto([Pos|Ps], Nums, Prod) :- nth1(Pos, Nums, Num), Prod #= Prod1 * Num, restricao_produto(Ps, Nums, Prod1).
fatores(Nums, Prod, NPosicoes, NPares, Posicoes) :- length(Posicoes,NPosicoes), all_distinct(Posicoes), restricao_produto(Posicoes,Nums,Prod), restricao_pares(Posicoes,Nums,NPares), restricao_remover_simetrias(Posicoes), labeling([],Posicoes).
```

Em que fase está o erro do programa? A seleção de posições é feita antes de as etiquetar.

Solução

Definição das restrições

`nth1/3` enumera posições em vez de impor a relação de domínio finito entre posição e valor.

*   **Definição do domínio das variáveis de decisão.** Esta opção não satisfaz as condições indicadas.
*   **Definição da pesquisa no espaço de estados (`labeling`).** Esta opção não satisfaz as condições indicadas.
*   **Definição do número de variáveis de decisão.** Esta opção não satisfaz as condições indicadas.
*   **Definição das restrições.** `nth1/3` enumera posições em vez de impor a relação de domínio finito entre posição e valor.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Contar fatores pares

Implementa `restricao_pares(+Posicoes,+Nums,?NPares)` com restrições, contando os valores pares nas posições selecionadas.

```prolog
:- use_module(library(clpfd)).

% restricao_pares(Posicoes,Nums,NPares).
```



### Testes

**Pares**


```prolog
main :- restricao_pares([1,3],[2,3,4],N), writeln(N).
```


Saída esperada:

```text
2
```

**Vazio**


```prolog
main :- restricao_pares([],[],N), writeln(N).
```


Saída esperada:

```text
0
```

**Escolha**


```prolog
main :- findall(P,(restricao_pares([P],[2,3],1),labeling([],[P])),L), writeln(L).
```


Saída esperada:

```text
[1]
```

Solução

```
:- use_module(library(clpfd)).
restricao_pares([],_,0).
restricao_pares([P|Ps],Nums,N) :- element(P,Nums,X), B #<==> (X mod 2 #= 0), N #= B+R, restricao_pares(Ps,Nums,R).
```

Uma variável booleana reifica a paridade de cada elemento; a soma conta os pares.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Consistência de um grafo

Domínios: A = {-1,0,1,3}, B = {2,4,6}, C = {4,6,8}, D = {4,6,8}. Restrições unárias: B > 1, C >= 3, D <= 8. Arestas: A < B, A < C, B < C e C ≠ D.

Classifica o grafo de restrições.

Grafo de restrições

![A tem domínio {-1,0,1,3}; B, {2,4,6}; C e D, {4,6,8}. A<B, A<C, B<C, C diferente de D; B>1, C>=3 e D<=8.](https://resumos.rgo.pt/cadeiras/pfl/exercicios-mt2/figura-5.svg)

Solução

1-consistente e 2-consistente, mas não 3-consistente

Todos os valores satisfazem as restrições unárias e têm suporte nas arestas. Porém, A=3 e C=4 não se estendem a B, pois teria de estar entre 3 e 4.

*   **1-consistente, 2-consistente e 3-consistente.** Esta opção não satisfaz as condições indicadas.
*   **1-consistente e 2-consistente, mas não 3-consistente.** Todos os valores satisfazem as restrições unárias e têm suporte nas arestas. Porém, A=3 e C=4 não se estendem a B, pois teria de estar entre 3 e 4.
*   **1-consistente, mas não 2-consistente ou 3-consistente.** Esta opção não satisfaz as condições indicadas.
*   **Nem 1-consistente, nem 2-consistente, nem 3-consistente.** Esta opção não satisfaz as condições indicadas.
*   **1-consistente e 3-consistente, mas não 2-consistente.** Esta opção não satisfaz as condições indicadas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Primeira etiqueta

Domínios: A = {-1,0,1,3}, B = {2,4,6}, C = {4,6,8}, D = {4,6,8}. Restrições unárias: B > 1, C >= 3, D <= 8. Arestas: A < B, A < C, B < C e C ≠ D.

Com `labeling([ff, step, down], [A,B,C,D])` em SICStus, qual é a primeira etiqueta parcial?

Grafo de restrições

![A tem domínio {-1,0,1,3}; B, {2,4,6}; C e D, {4,6,8}. A<B, A<C, B<C, C diferente de D; B>1, C>=3 e D<=8.](https://resumos.rgo.pt/cadeiras/pfl/exercicios-mt2/figura-6.svg)

Solução

{B - 6}

`ff` escolhe o primeiro domínio de tamanho mínimo, B; `down` tenta primeiro o maior valor, 6.

*   **{C - 8}.** Esta opção não satisfaz as condições indicadas.
*   **{A - 3}.** Esta opção não satisfaz as condições indicadas.
*   **{C - 4}.** Esta opção não satisfaz as condições indicadas.
*   **{D - 8}.** Esta opção não satisfaz as condições indicadas.
*   **{B - 6}.** `ff` escolhe o primeiro domínio de tamanho mínimo, B; `down` tenta primeiro o maior valor, 6.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Opções de pesquisa

Qual ação não é possível com a biblioteca CLP(FD) de SICStus?

Solução

Definir o número de variáveis de decisão como uma variável de domínio.

A estrutura e o número das variáveis têm de estar definidos ao construir o modelo; os seus valores podem ter domínios.

*   **Escolher aleatoriamente a próxima variável a etiquetar..** Esta opção não satisfaz as condições indicadas.
*   **Definir duas estratégias de pesquisa distintas para cada metade das variáveis de decisão..** Esta opção não satisfaz as condições indicadas.
*   **Definir um tempo máximo para a fase de pesquisa..** Esta opção não satisfaz as condições indicadas.
*   **Escolher aleatoriamente o valor da próxima variável a etiquetar..** Esta opção não satisfaz as condições indicadas.
*   **Definir o número de variáveis de decisão como uma variável de domínio..** A estrutura e o número das variáveis têm de estar definidos ao construir o modelo; os seus valores podem ter domínios.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Propriedades da programação por restrições

Qual afirmação está correta?

Solução

Todas as restantes afirmações estão erradas.

Não há garantia universal de desempenho, soluções distintas não têm de ser simétricas, `circuit` impõe mais do que distinção e restrições também existem fora da programação em lógica.

*   **Constraint & Generate tem sempre desempenho temporal igual ou superior a Generate & Test..** Esta opção não satisfaz as condições indicadas.
*   **Todas as restantes afirmações estão erradas..** Não há garantia universal de desempenho, soluções distintas não têm de ser simétricas, `circuit` impõe mais do que distinção e restrições também existem fora da programação em lógica.
*   **Múltiplas soluções implicam simetria..** Esta opção não satisfaz as condições indicadas.
*   **`all_distinct/1` é mais restritiva do que `circuit/1`..** Esta opção não satisfaz as condições indicadas.
*   **Os sistemas de programação baseados em restrições seguem um paradigma de programação em lógica..** Esta opção não satisfaz as condições indicadas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Permutações em ziguezague

```
p1(L1,L2) :- gen(L1,L2), test(L2).
gen([],[]).
gen(L1,[X|L2]) :- select(X,L1,L3), gen(L3,L2).
test([_,_]).
test([X1,X2,X3|Xs]) :-
    (X1 < X2, X2 > X3 ; X1 > X2, X2 < X3),
    test([X2,X3|Xs]).
```

Explique o que faz o programa e comente a sua eficiência.

Solução

`gen/2` enumera permutações da lista. `test/1` exige que cada triplo consecutivo tenha o elemento do meio estritamente maior ou estritamente menor do que os vizinhos. Para N elementos distintos podem ser geradas N! permutações, com verificação linear de cada uma. A abordagem gera muitas candidatas que só depois rejeita.

Confere a tua resposta:

*   Identifica a permutação e a alternância entre máximos e mínimos locais.
*   Explica o custo de gerar antes de verificar.
*   Reconhece que o caso base aceita listas com dois elementos, não listas vazias ou singulares.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Gerar listas com somas adjacentes

```
prog1(N,M,L1,L2) :-
    length(L1,N), N1 is N-1, length(L2,N1),
    findall(E,between(1,M,E),LE), fill(L1,LE,LE1), fill(L2,LE1,_), check(L1,L2).
fill([],LE,LE).
fill([X|Xs],LE,Rest) :- select(X,LE,LE1), fill(Xs,LE1,Rest).
check([_],[]).
check([A,B|Rest],[X|Xs]) :- A+B =:= X, check([B|Rest],Xs).
```

Explique o programa para N positivo. `between(+Inf,+Sup,-X)` enumera os inteiros do intervalo fechado.

Solução

`fill/3` escolhe sem reposição os elementos das duas listas a partir do mesmo conjunto `1..M`. `L2` contém, pela ordem, as somas de pares consecutivos de `L1`. Essas somas também têm de estar em `1..M` e ser distintas de todos os outros valores escolhidos.

Confere a tua resposta:

*   Identifica os comprimentos N e N−1 e o domínio 1..M.
*   Explica que as duas listas não partilham nem repetem valores.
*   Relaciona cada valor de L2 com uma soma adjacente de L1.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Contar atribuições de domínio

```
prog1(N,M,L1,L2) :-
    length(L1,N), N1 is N-1, length(L2,N1),
    findall(E,between(1,M,E),LE), fill(L1,LE,LE1), fill(L2,LE1,_), check(L1,L2).
fill([],LE,LE).
fill([X|Xs],LE,Rest) :- select(X,LE,LE1), fill(Xs,LE1,Rest).
check([_],[]).
check([A,B|Rest],[X|Xs]) :- A+B =:= X, check([B|Rest],Xs).
```

No problema das duas listas, `L1` tem N variáveis e `L2` tem N−1, cada uma no domínio `1..M`. Qual é a dimensão do produto cartesiano dos domínios antes de aplicar as restrições?

Solução

Multiplica M uma vez por variável, em vez de somar os espaços de cada lista.

*   **a. $2MN$.** Esta opção não corresponde ao modelo pedido. Há 2N−1 variáveis e M escolhas por variável. Esta contagem antecede as restrições de valores distintos e de somas; não é a contagem das permutações que `fill/3` consegue gerar.
*   **b. $M^{L1}+M^{L2}$.** Esta opção não corresponde ao modelo pedido. Há 2N−1 variáveis e M escolhas por variável. Esta contagem antecede as restrições de valores distintos e de somas; não é a contagem das permutações que `fill/3` consegue gerar.
*   **c. $NM$.** Esta opção não corresponde ao modelo pedido. Há 2N−1 variáveis e M escolhas por variável. Esta contagem antecede as restrições de valores distintos e de somas; não é a contagem das permutações que `fill/3` consegue gerar.
*   **d. $(2N-1)^M$.** Esta opção não corresponde ao modelo pedido. Há 2N−1 variáveis e M escolhas por variável. Esta contagem antecede as restrições de valores distintos e de somas; não é a contagem das permutações que `fill/3` consegue gerar.
*   **e. \[Não Responder\].** Esta opção não corresponde ao modelo pedido. Há 2N−1 variáveis e M escolhas por variável. Esta contagem antecede as restrições de valores distintos e de somas; não é a contagem das permutações que `fill/3` consegue gerar.
*   **f. $M^{2N-1}$.** Há 2N−1 variáveis e M escolhas por variável. Esta contagem antecede as restrições de valores distintos e de somas; não é a contagem das permutações que `fill/3` consegue gerar.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Espaço de atribuições binárias

Existem N presentes para distribuir por K pessoas. Uma pessoa pode receber vários presentes ou nenhum. Se usar N×K variáveis binárias para a matriz de atribuição, qual é o tamanho do espaço de procura antes de impor restrições?

Solução

Contam-se atribuições às variáveis da modelação, não apenas soluções válidas.

*   **a. $2^{NK}$.** Cada uma das NK variáveis binárias tem duas possibilidades. A exclusividade de atribuição de cada presente é uma restrição posterior.
*   **b. $N^K$.** Esta opção não corresponde ao modelo pedido. Cada uma das NK variáveis binárias tem duas possibilidades. A exclusividade de atribuição de cada presente é uma restrição posterior.
*   **c. $NK$.** Esta opção não corresponde ao modelo pedido. Cada uma das NK variáveis binárias tem duas possibilidades. A exclusividade de atribuição de cada presente é uma restrição posterior.
*   **d. $K^N$.** Esta opção não corresponde ao modelo pedido. Cada uma das NK variáveis binárias tem duas possibilidades. A exclusividade de atribuição de cada presente é uma restrição posterior.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Uma variável por presente

Existem N presentes e K pessoas, sem limitar quantos presentes cada pessoa recebe. Usando uma variável por presente, cujo domínio são os índices das pessoas, qual é o tamanho do espaço de procura?

Solução

Mudar a representação muda o número de variáveis e os seus domínios.

*   **a. $NK$.** Esta opção não corresponde ao modelo pedido. Há N variáveis e K escolhas independentes para cada uma. Cada atribuição já escolhe uma pessoa por presente.
*   **b. $2^{NK}$.** Esta opção não corresponde ao modelo pedido. Há N variáveis e K escolhas independentes para cada uma. Cada atribuição já escolhe uma pessoa por presente.
*   **c. $K^N$.** Há N variáveis e K escolhas independentes para cada uma. Cada atribuição já escolhe uma pessoa por presente.
*   **d. $N^K$.** Esta opção não corresponde ao modelo pedido. Há N variáveis e K escolhas independentes para cada uma. Cada atribuição já escolhe uma pessoa por presente.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Atribuir presentes com paridade oposta

```
:- use_module(library(clpfd)).
pres(N,K,Vars) :-
    length(Vars,N), domain(Vars,1,K), indices(1,Vars), labeling([],Vars).
indices(I,[V|Vs]) :- V mod 2 #\= I mod 2, J is I+1, indices(J,Vs).
indices(_,[]).
% Compatibilidade com a notação domain/3.
domain(Vars,Lo,Hi) :- Vars ins Lo..Hi.
```

Explique as soluções que `pres/3` obtém. A variável de índice I representa o destinatário do presente I.

Solução

O presente de índice ímpar só pode ir para uma pessoa de índice par; o presente de índice par só pode ir para uma pessoa de índice ímpar. Não há `all_distinct/1` nem uma restrição sobre quantos presentes cada pessoa recebe.

Confere a tua resposta:

*   Identifica uma pessoa em 1..K para cada presente.
*   Relaciona a paridade do presente com a paridade da pessoa.
*   Reconhece que uma pessoa pode receber vários presentes.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Propagação antes de labeling

```
:- use_module(library(clpfd)).
pres(N,K,Vars) :-
    length(Vars,N), domain(Vars,1,K), indices(1,Vars), labeling([],Vars).
indices(I,[V|Vs]) :- V mod 2 #\= I mod 2, J is I+1, indices(J,Vs).
indices(_,[]).
% Compatibilidade com a notação domain/3.
domain(Vars,Lo,Hi) :- Vars ins Lo..Hi.
```

Considere a restrição de paridade do programa. Com propagação por intervalos, a sua colocação altera os domínios antes da pesquisa?

Solução

A propagação reduz os domínios, mas não deve ser confundida com a enumeração das soluções. O efeito concreto depende do domínio e do propagador.

*   **a. Não..** Esta opção não corresponde ao modelo pedido. O propagador pode ajustar os extremos do intervalo sem remover todos os valores interiores incompatíveis. Por exemplo, `X in 1..10` e `X mod 2 #\= 1` deixam um intervalo `2..10`; nem todos os ímpares interiores são eliminados antes de `labeling`.
*   **b. O limite inferior ou superior do domínio das variáveis é alterado..** O propagador pode ajustar os extremos do intervalo sem remover todos os valores interiores incompatíveis. Por exemplo, `X in 1..10` e `X mod 2 #\= 1` deixam um intervalo `2..10`; nem todos os ímpares interiores são eliminados antes de `labeling`.
*   **c. Todos os valores redundantes são removidos dos domínios das variáveis..** Esta opção não corresponde ao modelo pedido. O propagador pode ajustar os extremos do intervalo sem remover todos os valores interiores incompatíveis. Por exemplo, `X in 1..10` e `X mod 2 #\= 1` deixam um intervalo `2..10`; nem todos os ímpares interiores são eliminados antes de `labeling`.
*   **d. Sim, mas apenas em algumas das variáveis..** Esta opção não corresponde ao modelo pedido. O propagador pode ajustar os extremos do intervalo sem remover todos os valores interiores incompatíveis. Por exemplo, `X in 1..10` e `X mod 2 #\= 1` deixam um intervalo `2..10`; nem todos os ímpares interiores são eliminados antes de `labeling`.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Construir uma linha binária

```
constroi_binarias(I,K,Vars,[LBin|LBins]) :-
    I =< K, !, constroi_bins(I,Vars,LBin),
    J is I+1, constroi_binarias(J,K,Vars,LBins).
constroi_binarias(_,_,_,[]).
```

Implemente `constroi_bins(+I,+Vars,-LBin)` usando materializações. Para cada variável V de `Vars`, o bit correspondente deve valer 1 se e só se `V=I`, mantendo a restrição nos dois sentidos. É a linha da pessoa I numa matriz de presentes. O auxiliar `constroi_binarias/4` aplica este predicado a cada pessoa de 1 a K.

```prolog
:- use_module(library(clpfd)).
% Define constroi_bins/3.
```



### Testes

**Valores conhecidos**


```prolog
main :- constroi_bins(2,[2,1,2],B), write_canonical(B), nl.
```


Saída esperada:

```text
[1,0,1]
```

**Do bit ao destinatário**


```prolog
main :- constroi_bins(2,[X],[1]), write_canonical(X), nl.
```


Saída esperada:

```text
2
```

**Excluir um destinatário**


```prolog
main :- X in 1..3, constroi_bins(2,[X],[0]), findall(X,labeling([],[X]),Xs), write_canonical(Xs), nl.
```


Saída esperada:

```text
[1,3]
```

**Sem presentes**


```prolog
main :- constroi_bins(1,[],B), write_canonical(B), nl.
```


Saída esperada:

```text
[]
```

Solução

```
:- use_module(library(clpfd)).
constroi_bins(_,[],[]).
constroi_bins(I,[V|Vs],[B|Bs]) :-
    B #<==> (V #= I), constroi_bins(I,Vs,Bs).
```

A equivalência reificada `B #<==> (V #= I)` permite deduzir o bit a partir do destinatário e restringir o destinatário a partir do bit.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

## CLP(FD): modelos e otimização

Corrigir seleção por posição

Corrige uma linha de `restricao_produto/3` para relacionar uma posição de domínio finito com o elemento da lista. Mantém as restantes linhas.

```prolog
:- use_module(library(clpfd)).
restricao_produto([], _, 1).
restricao_produto([Pos|Ps], Nums, Prod) :- nth1(Pos, Nums, Num), Prod #= Prod1 * Num, restricao_produto(Ps, Nums, Prod1).
fatores(Nums, Prod, NPosicoes, NPares, Posicoes) :- length(Posicoes,NPosicoes), all_distinct(Posicoes), restricao_produto(Posicoes,Nums,Prod), restricao_pares(Posicoes,Nums,NPares), restricao_remover_simetrias(Posicoes), labeling([],Posicoes).
```



### Testes

**Produto**


```prolog
main :- restricao_produto([P],[2,3],3), labeling([],[P]), writeln(P).
```


Saída esperada:

```text
2
```

**Vazio**


```prolog
main :- restricao_produto([],[],P), writeln(P).
```


Saída esperada:

```text
1
```

**Impossível**


```prolog
main :- (restricao_produto([_],[2,3],5) -> writeln(sim); writeln(nao)).
```


Saída esperada:

```text
nao
```

Solução

```
:- use_module(library(clpfd)).
restricao_produto([], _, 1).
restricao_produto([Pos|Ps], Nums, Prod) :- element(Pos, Nums, Num), Prod #= Prod1 * Num, restricao_produto(Ps, Nums, Prod1).
fatores(Nums, Prod, NPosicoes, NPares, Posicoes) :- length(Posicoes,NPosicoes), all_distinct(Posicoes), restricao_produto(Posicoes,Nums,Prod), restricao_pares(Posicoes,Nums,NPares), restricao_remover_simetrias(Posicoes), labeling([],Posicoes).
restricao_pares([],_,0).
restricao_pares([P|Ps],Nums,N) :- element(P,Nums,X), B #<==> (X mod 2 #= 0), N #= B+R, restricao_pares(Ps,Nums,R).
restricao_remover_simetrias([]).
restricao_remover_simetrias([_]).
restricao_remover_simetrias([A,B|Xs]) :- A #< B, restricao_remover_simetrias([B|Xs]).
```

`element/3` restringe a posição e o valor sem os etiquetar previamente.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Eliminar permutações

Implementa `restricao_remover_simetrias(+Posicoes)` impondo ordem crescente às posições para evitar permutações da mesma seleção.

```prolog
:- use_module(library(clpfd)).

% restricao_remover_simetrias(Posicoes).
```



### Testes

**Ordenado**


```prolog
main :- (restricao_remover_simetrias([1,2,3])->writeln(sim);writeln(nao)).
```


Saída esperada:

```text
sim
```

**Permutação**


```prolog
main :- (restricao_remover_simetrias([2,1])->writeln(sim);writeln(nao)).
```


Saída esperada:

```text
nao
```

**Vazio**


```prolog
main :- (restricao_remover_simetrias([])->writeln(sim);writeln(nao)).
```


Saída esperada:

```text
sim
```

Solução

```
:- use_module(library(clpfd)).
restricao_remover_simetrias([]).
restricao_remover_simetrias([_]).
restricao_remover_simetrias([A,B|Xs]) :- A #< B, restricao_remover_simetrias([B|Xs]).
```

A ordem estrita deixa uma representação para cada conjunto de posições.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Quantidades de pratos

Implementa `pratos(+PrecosUnitarios,+Total,+QuantidadeMaxima,-Quantidades)`. As quantidades são não negativas, têm máximo exatamente igual a `QuantidadeMaxima` e os valores positivos são distintos. Para `[10,22,9,8]`, total 132 e máximo 9, as soluções são `[6,0,0,9]` e `[9,0,2,3]`.

```prolog
:- use_module(library(clpfd)).

% pratos(Precos,Total,Max,Quantidades).
```



### Testes

**Exemplo**


```prolog
main :- findall(Q,pratos([10,22,9,8],132,9,Q),L), writeln(L).
```


Saída esperada:

```text
[[6,0,0,9],[9,0,2,3]]
```

**Impossível**


```prolog
main :- (pratos([2],3,2,_)->writeln(sim);writeln(nao)).
```


Saída esperada:

```text
nao
```

**Zeros**


```prolog
main :- pratos([1,2],0,0,Q), writeln(Q).
```


Saída esperada:

```text
[0,0]
```

Solução

```
:- use_module(library(clpfd)).
distintos([]).
distintos([X|Xs]) :- maplist(diferente(X),Xs), distintos(Xs).
diferente(X,Y) :- (X #= 0)  #\/ (Y #= 0)  #\/ (X  #\= Y).
pratos(P,T,M,Q) :- same_length(P,Q), Q ins 0..M, distintos(Q), sum_max(Q,M), scalar_product(P,Q,#=,T), labeling([],Q).
sum_max(Q,M) :- maplist(igual(M),Q,Bs), sum(Bs,#>=,1).
igual(M,X,B) :- B #<==> (X #= M).
```

A soma ponderada fixa o total; a disjunção permite repetir zero e impede iguais positivos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Distribuir grupos por autocarros

Implementa `autocarros(+Grupos,+Autocarros,-IDsAutocarros,-NAutocarrosUsados)`. Cada grupo fica inteiro num autocarro identificado pela posição, as capacidades são respeitadas e o número usado é mínimo. Para `[3,5,7,4,3]` e `[11,14,10,20]`, o mínimo é 2.

```prolog
:- use_module(library(clpfd)).

% autocarros(Grupos,Autocarros,IDs,N).
```



### Testes

**Mínimo**


```prolog
main :- autocarros([3,5,7,4,3],[11,14,10,20],_,N), writeln(N).
```


Saída esperada:

```text
2
```

**Sem capacidade**


```prolog
main :- (autocarros([5],[4],_,_)->writeln(sim);writeln(nao)).
```


Saída esperada:

```text
nao
```

**Sem grupos**


```prolog
main :- autocarros([],[],IDs,N), write_canonical(result(IDs,N)), nl.
```


Saída esperada:

```text
result([],0)
```

Solução

```
:- use_module(library(clpfd)).
autocarros([],_,[],0).
autocarros(Grupos, Caps, IDs, N) :- Grupos=[_|_], same_length(Grupos,IDs), length(Caps,K), K>0, IDs ins 1..K, capacidades(Caps,1,Grupos,IDs,Usados), sum(Usados,#=,N), once(labeling([min(N)],IDs)).
capacidades([],_,_,_,[]).
capacidades([Cap|Cs],I,G,IDs,[U|Us]) :- maplist(no_bus(I),IDs,Bs), scalar_product(G,Bs,#=<,Cap), sum(Bs,#=,Count), U #<==> (Count #> 0), J is I+1, capacidades(Cs,J,G,IDs,Us).
no_bus(I,X,B) :- B #<==> (X #= I).
```

Cada indicador associa um grupo a um autocarro; a soma ponderada limita a carga e a etiquetagem minimiza o número usado.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Colocar restrições antes da pesquisa

```
:- use_module(library(clpfd)).
p2(L1,L2) :-
    length(L1,N), length(L2,N),
    pos(L1,L2,Is), all_distinct(Is),
    labeling([],Is), test(L2).
pos([],_,[]).
pos([X|Xs],L2,[I|Is]) :- nth1(I,L2,X), pos(Xs,L2,Is).
test([_,_]).
test([X1,X2,X3|Xs]) :-
    (X1 < X2, X2 > X3 ; X1 > X2, X2 < X3),
    test([X2,X3|Xs]).
```

Porque é que p2/2 não constitui uma modelação correta em programação em lógica com restrições?

Solução

É preciso representar a escolha das posições por variáveis de domínio e publicar a alternância antes de `labeling/2`.

*   **a. As variáveis de domínio estão a ser instanciadas antes da fase de pesquisa..** Esta opção não corresponde ao modelo pedido. nth1/3 enumera posições concretas antes de `labeling/2`. Além disso, `test/1` usa comparações aritméticas depois da pesquisa, em vez de publicar restrições antecipadamente. Não faltam domínios a índices que já ficaram instanciados.
*   **b. \[Não Responder\].** Esta opção não corresponde ao modelo pedido. nth1/3 enumera posições concretas antes de `labeling/2`. Além disso, `test/1` usa comparações aritméticas depois da pesquisa, em vez de publicar restrições antecipadamente. Não faltam domínios a índices que já ficaram instanciados.
*   **c. Nem todas as restrições foram colocadas antes da fase da pesquisa..** Esta opção não corresponde ao modelo pedido. nth1/3 enumera posições concretas antes de `labeling/2`. Além disso, `test/1` usa comparações aritméticas depois da pesquisa, em vez de publicar restrições antecipadamente. Não faltam domínios a índices que já ficaram instanciados.
*   **d. Não é possível etiquetar `Is`, pois estas variáveis não têm domínio definido, e nem todas as restrições foram colocadas antes da fase da pesquisa..** Esta opção não corresponde ao modelo pedido. nth1/3 enumera posições concretas antes de `labeling/2`. Além disso, `test/1` usa comparações aritméticas depois da pesquisa, em vez de publicar restrições antecipadamente. Não faltam domínios a índices que já ficaram instanciados.
*   **e. As variáveis de domínio estão a ser instanciadas antes da fase da pesquisa e nem todas as restrições foram colocadas antes da fase da pesquisa..** nth1/3 enumera posições concretas antes de `labeling/2`. Além disso, `test/1` usa comparações aritméticas depois da pesquisa, em vez de publicar restrições antecipadamente. Não faltam domínios a índices que já ficaram instanciados.
*   **f. Não é possível etiquetar `Is`, pois estas variáveis não têm domínio definido..** Esta opção não corresponde ao modelo pedido. nth1/3 enumera posições concretas antes de `labeling/2`. Além disso, `test/1` usa comparações aritméticas depois da pesquisa, em vez de publicar restrições antecipadamente. Não faltam domínios a índices que já ficaram instanciados.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Modelar o ziguezague com CLP(FD)

```
:- use_module(library(clpfd)).
p2(L1,L2) :-
    length(L1,N), length(L2,N),
    pos(L1,L2,Is), all_distinct(Is),
    labeling([],Is), test(L2).
pos([],_,[]).
pos([X|Xs],L2,[I|Is]) :- nth1(I,L2,X), pos(Xs,L2,Is).
test([_,_]).
test([X1,X2,X3|Xs]) :-
    (X1 < X2, X2 > X3 ; X1 > X2, X2 < X3),
    test([X2,X3|Xs]).
```

Corrija `p2(+L1,-L2)` para gerar as mesmas permutações em ziguezague, usando restrições antes da pesquisa. Considere uma lista de inteiros com pelo menos dois elementos; os valores podem repetir-se.

```prolog
:- use_module(library(clpfd)).
% Define p2/2 e os auxiliares necessários.
```



### Testes

**Três valores**


```prolog
main :- findall(L,p2([1,2,3],L),Ls), sort(Ls,S), write_canonical(S), nl.
```


Saída esperada:

```text
[[1,3,2],[2,1,3],[2,3,1],[3,1,2]]
```

**Dois valores**


```prolog
main :- findall(L,p2([1,2],L),Ls), sort(Ls,S), write_canonical(S), nl.
```


Saída esperada:

```text
[[1,2],[2,1]]
```

**Valores repetidos**


```prolog
main :- findall(L,p2([1,1,2],L),Ls), sort(Ls,S), write_canonical(S), nl.
```


Saída esperada:

```text
[[1,2,1]]
```

Solução

```
:- use_module(library(clpfd)).
p2(L1,L2) :-
    length(L1,N), N >= 2, length(L2,N),
    length(Is,N), Is ins 1..N, all_distinct(Is),
    positions(Is,L1,L2), zigzag_fd(L2), labeling([],Is).
positions([],_,[]).
positions([I|Is],Source,[X|Xs]) :-
    element(I,Source,X), positions(Is,Source,Xs).
zigzag_fd([_,_]).
zigzag_fd([A,B,C|Rest]) :-
    ((A #< B) #/\ (B #> C)) #\/ ((A #> B) #/\ (B #< C)),
    zigzag_fd([B,C|Rest]).
```

As posições são distintas, mas os valores não precisam de o ser. `element/3` liga as posições aos valores; as comparações reificadas impõem a alternância antes de etiquetar.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Escolher quatro receitas

Implemente `receitas(+NOvos,+TempoMax,+OvosPorReceita,+TempoPorReceita,-OvosUsados,-Receitas)` com CLP(FD). Escolha quatro receitas diferentes que respeitem os ovos disponíveis e o tempo total, maximizando os ovos usados. `Receitas` contém índices, a partir de 1. Para ovos `[6,4,12,20,6]` e tempos `[20,50,10,20,15]`, com 30 ovos e 100 minutos, a escolha é `[1,2,3,5]`, usando 28 ovos; com 50 ovos, é `[1,3,4,5]`, usando 44.

```prolog
:- use_module(library(clpfd)).
% Define receitas/6.
```



### Testes

**Limite de ovos**


```prolog
main :- receitas(30,100,[6,4,12,20,6],[20,50,10,20,15],U,R), sort(R,S), write_canonical(result(U,S)), nl.
```


Saída esperada:

```text
result(28,[1,2,3,5])
```

**Melhor combinação**


```prolog
main :- receitas(50,100,[6,4,12,20,6],[20,50,10,20,15],U,R), sort(R,S), write_canonical(result(U,S)), nl.
```


Saída esperada:

```text
result(44,[1,3,4,5])
```

**Receitas insuficientes**


```prolog
main :- (receitas(10,10,[1,2,3],[1,1,1],_,_) -> write(true) ; write(false)), nl.
```


Saída esperada:

```text
false
```

Solução

```
:- use_module(library(clpfd)).
receitas(NOvos,TempoMax,Ovos,Tempos,Usados,Receitas) :-
    same_length(Ovos,Tempos), length(Ovos,N), N >= 4,
    length(Receitas,4), Receitas ins 1..N, chain(Receitas,#<),
    elements(Receitas,Ovos,Escolhidos), elements(Receitas,Tempos,Duracoes),
    sum(Escolhidos,#=,Usados), Usados #=< NOvos,
    sum(Duracoes,#=<,TempoMax), once(labeling([max(Usados)],Receitas)).
elements([],_,[]).
elements([I|Is],Xs,[X|Rest]) :- element(I,Xs,X), elements(Is,Xs,Rest).
```

Os quatro índices crescentes eliminam permutações da mesma escolha. `element/3` obtém os recursos, `sum/3` impõe os limites e a pesquisa maximiza os ovos usados.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Distribuir cortes por pranchas

Implemente `corta(+Pranchas,+Prateleiras,-PranchasSelecionadas)` com CLP(FD). Cada lista contém comprimentos; cada prateleira deve caber inteira numa única prancha e a soma dos cortes numa prancha não pode exceder o seu comprimento. A lista de saída indica a prancha de cada prateleira. Para `[100,45,70]` e `[12,50,14,8,10,90,24]`, as soluções são `[2,3,3,2,1,1,2]` e `[3,3,2,3,1,1,2]`.

```prolog
:- use_module(library(clpfd)).
% Define corta/3.
```



### Testes

**Todas as distribuições**


```prolog
main :- findall(S,corta([100,45,70],[12,50,14,8,10,90,24],S),Ss), sort(Ss,R), write_canonical(R), nl.
```


Saída esperada:

```text
[[2,3,3,2,1,1,2],[3,3,2,3,1,1,2]]
```

**Separar duas peças**


```prolog
main :- findall(S,corta([5,5],[3,3],S),Ss), sort(Ss,R), write_canonical(R), nl.
```


Saída esperada:

```text
[[1,2],[2,1]]
```

**Sem peças**


```prolog
main :- corta([5],[],S), write_canonical(S), nl.
```


Saída esperada:

```text
[]
```

Solução

```
:- use_module(library(clpfd)).
corta(Pranchas,Prateleiras,Selecionadas) :-
    length(Pranchas,N), same_length(Prateleiras,Selecionadas),
    Selecionadas ins 1..N,
    board_limits(Pranchas,1,Prateleiras,Selecionadas),
    labeling([],Selecionadas).
board_limits([],_,_,_).
board_limits([Cap|Caps],I,Sizes,Vars) :-
    maplist(on_board(I),Vars,Bits), scalar_product(Sizes,Bits,#=<,Cap),
    J is I+1, board_limits(Caps,J,Sizes,Vars).
on_board(I,V,B) :- B #<==> (V #= I).
```

Uma variável por prateleira escolhe a prancha. Para cada prancha, materializam-se as igualdades entre índices e usa-se um produto escalar para somar os comprimentos atribuídos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Corrigir restrições e eliminar reflexões

```
prog1(N,M,L1,L2) :-
    length(L1,N), N1 is N-1, length(L2,N1),
    findall(E,between(1,M,E),LE), fill(L1,LE,LE1), fill(L2,LE1,_), check(L1,L2).
fill([],LE,LE).
fill([X|Xs],LE,Rest) :- select(X,LE,LE1), fill(Xs,LE1,Rest).
check([_],[]).
check([A,B|Rest],[X|Xs]) :- A+B =:= X, check([B|Rest],Xs).
```

Implemente `prog2(+N,+M,-L1,-L2)` em CLP(FD), equivalente ao programa apresentado. Corrija a comparação aritmética sobre variáveis, impeça valores repetidos nas duas listas e elimine a simetria de inverter ambas. Para `N > 1`, conserve o representante com o primeiro valor de `L1` menor que o último; para `N = 1`, conserve todos os valores.

```prolog
:- use_module(library(clpfd)).
% Define prog2/4.
```



### Testes

**Duas variáveis e uma soma**


```prolog
main :- findall(result(A,B),prog2(2,5,A,B),Rs), sort(Rs,S), write_canonical(S), nl.
```


Saída esperada:

```text
[result([1,2],[3]),result([1,3],[4]),result([1,4],[5]),result([2,3],[5])]
```

**Um elemento**


```prolog
main :- findall(result(A,B),prog2(1,3,A,B),Rs), sort(Rs,S), write_canonical(S), nl.
```


Saída esperada:

```text
[result([1],[]),result([2],[]),result([3],[])]
```

**Domínio insuficiente**


```prolog
main :- (prog2(2,2,_,_) -> write(true) ; write(false)), nl.
```


Saída esperada:

```text
false
```

Solução

```
:- use_module(library(clpfd)).
prog2(N,M,L1,L2) :-
    N >= 1, length(L1,N), N1 is N-1, length(L2,N1),
    L1 ins 1..M, L2 ins 1..M, append(L1,L2,All), all_distinct(All),
    sums(L1,L2),
    (N > 1 -> L1=[First|_], last(L1,Last), First #< Last ; true),
    labeling([],L1).
sums([_],[]).
sums([A,B|Rest],[S|Ss]) :- A+B #= S, sums([B|Rest],Ss).
```

Usa `#=` para as somas antes da pesquisa e `all_distinct/1` sobre a concatenação das listas. Etiquetar `L1` determina `L2` através das somas. A comparação entre os extremos conserva uma orientação de cada reflexão.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Emparelhar todas as pessoas

Implemente `gym_pairs(+MenHeights,+WomenHeights,+Delta,-Pairs)` em CLP(FD). As listas têm o mesmo tamanho. Cada pessoa aparece num par, o homem não pode ser mais baixo e a diferença tem de ser estritamente inferior a `Delta`. Use índices a partir de 1 e evite permutações da mesma lista de pares. Exemplos: `[95,78,67,84]` com `[65,83,75,80]` e `Delta=10` não tem solução; com `[65,83,75,86]` obtém `[1-4,2-3,3-1,4-2]`; com `[65,77,75,86]` há também `[1-4,2-2,3-1,4-3]`.

```prolog
:- use_module(library(clpfd)).
% Define gym_pairs/4.
```



### Testes

**Impossível**


```prolog
main :- (gym_pairs([95,78,67,84],[65,83,75,80],10,_) -> write(true) ; write(false)), nl.
```


Saída esperada:

```text
false
```

**Solução única**


```prolog
main :- findall(S,(gym_pairs([95,78,67,84],[65,83,75,86],10,P),sort(P,S)),Ss), msort(Ss,R), write_canonical(R), nl.
```


Saída esperada:

```text
[[-(1,4),-(2,3),-(3,1),-(4,2)]]
```

**Duas combinações**


```prolog
main :- findall(S,(gym_pairs([95,78,67,84],[65,77,75,86],10,P),sort(P,S)),Ss), msort(Ss,R), write_canonical(R), nl.
```


Saída esperada:

```text
[[-(1,4),-(2,2),-(3,1),-(4,3)],[-(1,4),-(2,3),-(3,1),-(4,2)]]
```

Solução

```
:- use_module(library(clpfd)).
gym_pairs(Men,Women,Delta,Pairs) :-
    same_length(Men,Women), length(Women,N), same_length(Men,Vars),
    Vars ins 1..N, all_distinct(Vars),
    gym_heights(Men,Women,Delta,Vars), labeling([],Vars), indexed_pairs(Vars,1,Pairs).
gym_heights([],_,_,[]).
gym_heights([H|Hs],Women,D,[I|Is]) :-
    element(I,Women,W), H #>= W, H-W #< D, gym_heights(Hs,Women,D,Is).
indexed_pairs([],_,[]).
indexed_pairs([W|Ws],M,[M-W|Ps]) :- M1 is M+1, indexed_pairs(Ws,M1,Ps).
```

Fixa a ordem dos homens e escolhe uma permutação dos índices das mulheres. `element/3` obtém a altura e as restrições rejeitam pares incompatíveis antes da pesquisa.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Maximizar pares possíveis

Implemente `optimal_skating_pairs(+MenHeights,+WomenHeights,+Delta,-Pairs)` em CLP(FD). As listas podem ter tamanhos diferentes e algumas pessoas podem ficar sem par. Maximize o número de pares, sem repetir pessoas: o homem não pode ser mais baixo e a diferença deve ser inferior a `Delta`. Para `[95,78,67,84]`, `[65,83,75,80]` e 10, uma solução ótima é `[2-3,3-1,4-2]`. Para `[95,78,67,84,65,90,77]` e a mesma lista de mulheres, há quatro pares, por exemplo `[4-4,5-1,6-2,7-3]`. Trocando as listas, há quatro, por exemplo `[1-5,2-2,3-3,4-7]`. Se a primeira mulher tiver altura 55, o ótimo passa a três: `[4-4,6-2,7-3]`; no caso trocado `[2-2,3-3,4-7]`. Qualquer emparelhamento ótimo válido é aceite.

```prolog
:- use_module(library(clpfd)).
% Define optimal_skating_pairs/4.
```



### Testes

**Três pares**


```prolog
valid_pairs(Men,Women,D,Ps) :-
    findall(I,member(I-_,Ps),Is), sort(Is,SI), same_length(Is,SI),
    findall(J,member(_-J,Ps),Js), sort(Js,SJ), same_length(Js,SJ),
    forall(member(I-J,Ps),(nth1(I,Men,H),nth1(J,Women,W),H>=W,H-W<D)).
main :- optimal_skating_pairs([95,78,67,84],[65,83,75,80],10,P), (length(P,3),valid_pairs([95,78,67,84],[65,83,75,80],10,P) -> write_canonical(valid(3)) ; write_canonical(invalid(P))), nl.
```


Saída esperada:

```text
valid(3)
```

**Listas de tamanhos diferentes**


```prolog
valid_pairs(Men,Women,D,Ps) :-
    findall(I,member(I-_,Ps),Is), sort(Is,SI), same_length(Is,SI),
    findall(J,member(_-J,Ps),Js), sort(Js,SJ), same_length(Js,SJ),
    forall(member(I-J,Ps),(nth1(I,Men,H),nth1(J,Women,W),H>=W,H-W<D)).
main :- optimal_skating_pairs([95,78,67,84,65,90,77],[65,83,75,80],10,P), (length(P,4),valid_pairs([95,78,67,84,65,90,77],[65,83,75,80],10,P) -> write_canonical(valid(4)) ; write_canonical(invalid(P))), nl.
```


Saída esperada:

```text
valid(4)
```

**Sem candidatos**


```prolog
main :- optimal_skating_pairs([60],[80],10,P), write_canonical(P), nl.
```


Saída esperada:

```text
[]
```

Solução

```
:- use_module(library(clpfd)).
optimal_skating_pairs(Men,Women,Delta,Pairs) :-
    length(Women,N), same_length(Men,Vars), Vars ins 0..N,
    skating_heights(Men,[0|Women],Delta,Vars), distinct_nonzero(Vars),
    maplist(matched,Vars,Bs), sum(Bs,#=,Count),
    once(labeling([max(Count)],Vars)), selected_pairs(Vars,1,Pairs).
skating_heights([],_,_,[]).
skating_heights([H|Hs],Women,D,[V|Vs]) :-
    I #= V+1, element(I,Women,W),
    (V #> 0) #==> ((H #>= W) #/\ (H-W #< D)),
    skating_heights(Hs,Women,D,Vs).
distinct_nonzero([]).
distinct_nonzero([V|Vs]) :- maplist(compatible(V),Vs), distinct_nonzero(Vs).
compatible(X,Y) :- (X #= 0) #\/ (Y #= 0) #\/ (X #\= Y).
matched(V,B) :- B #<==> (V #> 0).
selected_pairs([],_,[]).
selected_pairs([0|Vs],I,Ps) :- !, J is I+1, selected_pairs(Vs,J,Ps).
selected_pairs([W|Vs],I,[I-W|Ps]) :- J is I+1, selected_pairs(Vs,J,Ps).
```

O índice zero representa um homem sem par. Só os índices não nulos têm de ser distintos. Materializa-se a presença de cada par e maximiza-se a soma dessas presenças antes de apresentar uma solução ótima.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Distribuir objetos pelo armário

Há N objetos maleáveis, com peso em gramas e volume em cm³, para distribuir por compartimentos de um armário matricial. Cada compartimento tem uma capacidade volumétrica. O peso total num compartimento não pode ser superior ao do compartimento imediatamente abaixo na mesma coluna. Numere os compartimentos por linhas, da esquerda para a direita e de cima para baixo.

Implemente `prat(+Prateleiras,+Objetos,-Vars)` em CLP(FD). `Prateleiras` é a matriz de capacidades e `Objetos` contém pares `Peso-Volume`. `Vars` indica o compartimento de cada objeto. No exemplo pequeno `prat([[30,6],[75,15]],[176-40,396-24,474-35,250-8,149-5,479-5],Vars)`, as soluções são `[3,1,3,4,1,4]` e `[3,1,3,4,2,4]`. Os factos do exemplo maior estão no código inicial; uma resposta parcial é `Vars=[12,13,9,14,20,8,20,10,16,18|...]`.

```prolog
:- use_module(library(clpfd)).
armario([[20,30,6,50],[50,75,15,125],[60,90,18,150],[30,45,9,75],[40,60,12,100]]).
objetos([114-54,305-30,295-53,376-39,468-84,114-48,337-11,259-80,473-28,386-55,258-39,391-37,365-76,251-18,144-42,399-94,463-48,473-9,132-56,367-81]).
% Define prat/3.
```



### Testes

**Todas as distribuições pequenas**


```prolog
main :- findall(V,prat([[30,6],[75,15]],[176-40,396-24,474-35,250-8,149-5,479-5],V),Vs), sort(Vs,S), write_canonical(S), nl.
```


Saída esperada:

```text
[[3,1,3,4,1,4],[3,1,3,4,2,4]]
```

**Só cabe em baixo**


```prolog
main :- prat([[1],[3]],[2-2],V), write_canonical(V), nl.
```


Saída esperada:

```text
[2]
```

**Volume excessivo**


```prolog
main :- (prat([[1],[1]],[2-2],_) -> write(true) ; write(false)), nl.
```


Saída esperada:

```text
false
```

Solução

```
:- use_module(library(clpfd)).
armario([[20,30,6,50],[50,75,15,125],[60,90,18,150],[30,45,9,75],[40,60,12,100]]).
objetos([114-54,305-30,295-53,376-39,468-84,114-48,337-11,259-80,473-28,386-55,258-39,391-37,365-76,251-18,144-42,399-94,463-48,473-9,132-56,367-81]).
prat(Rows,Objects,Vars) :-
    Rows=[First|_], length(First,Cols), maplist(same_length(First),Rows),
    append(Rows,Caps), length(Caps,K), same_length(Objects,Vars), Vars ins 1..K,
    object_data(Objects,Weights,Volumes),
    compartment_loads(Caps,1,Vars,Weights,Volumes,Loads),
    Last is K-Cols, numlist(1,Last,Upper), maplist(not_heavier(Loads,Cols),Upper),
    labeling([],Vars).
object_data([],[],[]).
object_data([W-V|Os],[W|Ws],[V|Vs]) :- object_data(Os,Ws,Vs).
compartment_loads([],_,_,_,_,[]).
compartment_loads([Cap|Caps],I,Vars,Weights,Volumes,[Load|Loads]) :-
    maplist(in_slot(I),Vars,Bits), scalar_product(Volumes,Bits,#=<,Cap),
    scalar_product(Weights,Bits,#=,Load),
    J is I+1, compartment_loads(Caps,J,Vars,Weights,Volumes,Loads).
in_slot(I,V,B) :- B #<==> (V #= I).
not_heavier(Loads,Cols,I) :-
    J is I+Cols, nth1(I,Loads,Upper), nth1(J,Loads,Lower), Upper #=< Lower.
```

Materializa-se a atribuição de cada objeto a cada compartimento. Produtos escalares somam volumes e pesos; a capacidade limita o volume e uma comparação por coluna limita o peso superior.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Escolher as variáveis do armário

Há N objetos maleáveis, com peso em gramas e volume em cm³, para distribuir por compartimentos de um armário matricial. Cada compartimento tem uma capacidade volumétrica. O peso total num compartimento não pode ser superior ao do compartimento imediatamente abaixo na mesma coluna. Numere os compartimentos por linhas, da esquerda para a direita e de cima para baixo.

```
armario([[20,30,6,50],[50,75,15,125],[60,90,18,150],[30,45,9,75],[40,60,12,100]]).
objetos([114-54,305-30,295-53,376-39,468-84,114-48,337-11,259-80,473-28,386-55,258-39,391-37,365-76,251-18,144-42,399-94,463-48,473-9,132-56,367-81]).
```

Descreva a modelação do armário: variáveis de decisão, domínios e significado. `Prateleiras` contém a matriz de capacidades e cada objeto é um par `Peso-Volume`.

Solução

Use X\_i em `1..K` para o compartimento do objeto i. Para cada compartimento j, B\_ij equivale a X\_i=j. A soma Volume\_i×B\_ij não excede a capacidade j; a soma Peso\_i×B\_ij é o peso j. Para cada posição que tenha uma posição inferior na mesma coluna, imponha Peso\_j ≤ Peso\_inferior. A pesquisa etiqueta os X\_i.

Confere a tua resposta:

*   Uma variável por objeto com domínio dos índices dos compartimentos.
*   Materializa cada atribuição para calcular volumes e pesos.
*   Impõe a capacidade de cada compartimento e a ordem vertical dos pesos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Planear o transporte de mobília

Existem quatro trabalhadores e, no máximo, 60 minutos. Transportar um piano exige três trabalhadores durante 30 minutos; uma cadeira, um durante 10; uma cama, três durante 15; uma mesa, dois durante 15. As tarefas não podem ser interrompidas. Pretende-se concluir tudo no menor tempo possível. O programa tem de funcionar também com outros objetos, números de trabalhadores e limites de tempo.

Construa a programação em CLP(FD), minimizando o instante de conclusão e respeitando o máximo. Para testar sem impor um formato de impressão, implemente `furniture(-Schedule,-Total)`: `Schedule` contém `task(Nome,Inicio,Fim)`, uma vez por objeto. Os factos `objeto/3`, `homens/1` e `tempo_max/1` são fornecidos. O predicado de apresentação `furniture/0` é opcional. Uma programação ótima é piano 0–30, cadeira 0–10, cama 30–45 e mesa 45–60, com `Total=60`; qualquer programação ótima válida é aceite.

```prolog
:- use_module(library(clpfd)).
:- dynamic objeto/3, homens/1, tempo_max/1.
objeto(piano,3,30).
objeto(cadeira,1,10).
objeto(cama,3,15).
objeto(mesa,2,15).
homens(4).
tempo_max(60).
% Define furniture/2.
```



### Testes

**Quatro trabalhadores**


```prolog
valid_schedule(Plan,Total) :-
    findall(N,objeto(N,_,_),Names), findall(N,member(task(N,_,_),Plan),Got),
    msort(Names,Sorted), msort(Got,Sorted),
    forall(member(task(N,S,E),Plan),(objeto(N,_,D),integer(S),integer(E),S>=0,E-S=:=D,E=<Total)),
    findall(E,member(task(_,_,E),Plan),Ends), max_list(Ends,Total),
    homens(Limit), tempo_max(Max), Total=<Max, Last is Total-1,
    forall(between(0,Last,T),(findall(R,(member(task(N,S,E),Plan),S=<T,T<E,objeto(N,R,_)),Rs),sum_list(Rs,Load),Load=<Limit)).
main :- furniture(P,T), (valid_schedule(P,T) -> V=true ; V=false), write_canonical(result(T,V)), nl.
```


Saída esperada:

```text
result(60,true)
```

**Outros objetos e limites**


```prolog
valid_schedule(Plan,Total) :-
    findall(N,objeto(N,_,_),Names), findall(N,member(task(N,_,_),Plan),Got),
    msort(Names,Sorted), msort(Got,Sorted),
    forall(member(task(N,S,E),Plan),(objeto(N,_,D),integer(S),integer(E),S>=0,E-S=:=D,E=<Total)),
    findall(E,member(task(_,_,E),Plan),Ends), max_list(Ends,Total),
    homens(Limit), tempo_max(Max), Total=<Max, Last is Total-1,
    forall(between(0,Last,T),(findall(R,(member(task(N,S,E),Plan),S=<T,T<E,objeto(N,R,_)),Rs),sum_list(Rs,Load),Load=<Limit)).
main :- retractall(objeto(_,_,_)),retractall(homens(_)),retractall(tempo_max(_)),assertz(objeto(a,1,3)),assertz(objeto(b,1,2)),assertz(homens(2)),assertz(tempo_max(10)),furniture(P,T),(valid_schedule(P,T) -> V=true ; V=false),write_canonical(result(T,V)),nl.
```


Saída esperada:

```text
result(3,true)
```

**Recursos insuficientes**


```prolog
main :- retractall(homens(_)),assertz(homens(2)),(furniture(_,_) -> write(true) ; write(false)),nl.
```


Saída esperada:

```text
false
```

Solução

```
:- use_module(library(clpfd)).
:- dynamic objeto/3, homens/1, tempo_max/1.
objeto(piano,3,30).
objeto(cadeira,1,10).
objeto(cama,3,15).
objeto(mesa,2,15).
homens(4).
tempo_max(60).
furniture(Schedule,Total) :-
    findall(obj(N,R,D),objeto(N,R,D),Objs), homens(Limit), tempo_max(Max),
    same_length(Objs,Starts), same_length(Objs,Ends),
    Starts ins 0..Max, Ends ins 0..Max,
    build_jobs(Objs,Starts,Ends,Tasks,Schedule),
    cumulative(Tasks,[limit(Limit)]), max_end(Ends,Total),
    once(labeling([min(Total),ffc,bisect],Starts)).
build_jobs([],[],[],[],[]).
build_jobs([obj(N,R,D)|Os],[S|Ss],[E|Es],[task(S,D,E,R,N)|Ts],[task(N,S,E)|Ps]) :-
    E #= S+D, build_jobs(Os,Ss,Es,Ts,Ps).
max_end([],0).
max_end([E|Es],M) :- max_end(Es,Rest), M #= max(E,Rest).
```

Uma variável indica o início de cada tarefa. O fim é início mais duração. `cumulative/2` limita trabalhadores simultâneos, o máximo dos fins dá o tempo total e a pesquisa minimiza esse total.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)

Escolher as variáveis do horário

Existem quatro trabalhadores e, no máximo, 60 minutos. Transportar um piano exige três trabalhadores durante 30 minutos; uma cadeira, um durante 10; uma cama, três durante 15; uma mesa, dois durante 15. As tarefas não podem ser interrompidas. Pretende-se concluir tudo no menor tempo possível. O programa tem de funcionar também com outros objetos, números de trabalhadores e limites de tempo.

```
:- dynamic objeto/3, homens/1, tempo_max/1.
objeto(piano,3,30).
objeto(cadeira,1,10).
objeto(cama,3,15).
objeto(mesa,2,15).
homens(4).
tempo_max(60).
```

Descreva a modelação do transporte de mobília, as variáveis de decisão, os seus domínios e significado.

Solução

Use um início S\_i em `0..TempoMax` por objeto e um fim E\_i=S\_i+Duração\_i, também limitado por `TempoMax`. Cada tarefa consome o número de trabalhadores indicado no seu facto durante \[S\_i,E\_i). `cumulative/2` limita o consumo agregado ao total de homens. `Total` é o máximo dos E\_i e deve ser minimizado na pesquisa.

Confere a tua resposta:

*   Define início e fim de cada tarefa e o tempo total.
*   Relaciona início, duração e fim.
*   Impõe os recursos simultâneos, o limite de tempo e a minimização.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/prolog-recursao-procura/#listas-e-aritm%C3%A9tica)