Exercícios MT2 · Programação Funcional e em Lógica

Bases de conhecimento e relações

Código

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.

% 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Identificador

Código do teste

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

Esperado:

['Alice']

Nome

Código do teste

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

Esperado:

[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

Código

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.

% 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Gerar

Código do teste

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

Esperado:

[1,3,4,5]

Ano par

Código do teste

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

Esperado:

[]

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

Código

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.

% 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Pares

Código do teste

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

Esperado:

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

Sem reciprocidade

Código do teste

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

Esperado:

[]

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

Personagens gémeasCódigo

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.

:- 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Encontrar

Código do teste

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

Esperado:

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

Ausente

Código do teste

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

Esperado:

[]

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

Personagens interpretadas por si mesmasCódigo

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).

:- 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Substituir

Código do teste

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

Esperado:

[self]

Repetir

Código do teste

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

Esperado:

[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

Géneros de um livroCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Vários géneros

Código do teste

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

Esperado:

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

Títulos por género

Código do teste

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

Esperado:

['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

Idade ao publicarCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Idade

Código do teste

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

Esperado:

[38]

Autor sem livros

Código do teste

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

Esperado:

[]

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

Retirar uma cláusulaEscolha múltipla

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)?

A tua respostaSubstitui os argumentos da primeira cláusula de predY/2 pelos argumentos de predZ/3.Altera a ordem das cláusulas de predY/2.Altera a ordem dos objetivos de cada cláusula de predY/2.Simula uma chamada a predY/2 sem considerar a primeira cláusula.Nada, qualquer chamada a predZ/3 falha sempre.

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

Autores de livrosCódigo

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

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Título

Código do teste

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

Esperado:

['Stephen King']

Sem livros

Código do teste

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

Esperado:

[]

Autor

Código do teste

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

Esperado:

['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

Contar ingredientesCódigo

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).

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Todos

Código do teste

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

Esperado:

[ratatouille]

Pizza

Código do teste

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

Esperado:

[2]

Inexistente

Código do teste

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

Esperado:

[]

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

Custo de um ingredienteCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Tomate

Código do teste

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

Esperado:

[700]

Zero

Código do teste

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

Esperado:

[0]

Inexistente

Código do teste

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

Esperado:

[]

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

Atualizar custo unitárioCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Existente

Código do teste

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

Esperado:

[8]

Novo

Código do teste

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

Esperado:

[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

Implicação de uma regraEscolha múltipla

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

A tua respostaSe parent(X,Y) é verdadeiro, mother(X,Y) tem de ser verdadeiro.Define um facto novo que torna parent o mesmo predicado que mother.Se mother(X,Y) é verdadeiro, parent(X,Y) é verdadeiro.parent(X,Y) e mother(X,Y) são sempre ambos verdadeiros ou ambos falsos.

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

Pares de progenitoresCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Duas ordens

Código do teste

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

Esperado:

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

Mesmo género

Código do teste

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

Esperado:

[-(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

Filho únicoCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Todos

Código do teste

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

Esperado:

[calhoun,phil]

Sem duplicados

Código do teste

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

Esperado:

Meio-irmão

Código do teste

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

Esperado:

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

Lista de antepassadosCódigo

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

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Diretos

Código do teste

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

Esperado:

[barb,merle]

Sem antepassados

Código do teste

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

Esperado:

[]

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

Unificação, termos e operadores

Selecionar argumentosCódigo

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.



% Define aqui o predicado pedido.

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Seleção

Código do teste

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

Esperado:

book(a,1991,[x])

Sem argumentos

Código do teste

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

Esperado:

Índice inválido

Código do teste

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

Esperado:

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

Operadores para livrosCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Livro

Código do teste

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

Esperado:

[-('John Grisham',36)]

Idade

Código do teste

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

Esperado:

['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

Livros com vários génerosCódigo

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

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Resultados

Código do teste

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

Esperado:

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

Um género

Código do teste

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

Esperado:

[]

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

Unificação com um factoEscolha múltipla

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

A tua respostaFalha imediatamente porque X não está instanciado.Trata X como um novo facto e acrescenta-o à base.Unifica likes(alice,X) com factos ou regras e instancia X.Procura uma regra que derive alice a partir de 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

Unificação de termosEscolha múltipla

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

A tua respostaLiga X a g(Y) e deixa Y livre.Liga Y a X e substitui f por g.Não são unificáveis porque X e Y são variáveis diferentes.Liga X a Y e deixa f inalterado.

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

Leitura de termosEscolha múltipla

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

A tua respostawrite/1 falha se o argumento contiver variáveis não instanciadas.read/1 espera um termo Prolog seguido de ponto, pelo que as instruções e o formato de entrada devem respeitá-lo.write/1 insere automaticamente espaços e mudanças de linha.read/1 só lê números, não átomos ou termos compostos.

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

Operadores para páginasEscolha múltipla

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

A tua respostaop(700, xfx, has) e op(600, xf, pages)op(700, xfx, has) e op(600, fx, pages)op(700, yfy, has) e op(600, xf, pages)op(700, xfx, has) e op(700, xf, pages)op(700, yfy, has) e op(600, fx, 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

Argumento de um termoEscolha múltipla

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

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

A tua respostaO terceiro argumento está por instanciar.O segundo argumento é um átomo.O segundo argumento está por instanciar.O primeiro argumento está por instanciar.O terceiro argumento é um átomo.

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

Operador prefixoEscolha múltipla

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.

A tua respostaop(570, xf, some)op(600, fy, some)op(600, xf, some)op(570, fx, some)op(570, fy, some)

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

Operador de ligaçãoEscolha múltipla

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

A tua respostaop(580, yf, and)op(580, xfy, and)op(580, yxfx, and)op(580, xf, and)op(580, xfx, and)

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

Aridade de um termoAutoavaliação

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

A tua resposta

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

Listas, recursão e aritmética

Código

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.

% 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Seguidores

Código do teste

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

Esperado:

Sem seguidores

Código do teste

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

Esperado:

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

Código

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].

% 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Visíveis

Código do teste

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

Esperado:

[x]

Inexistente

Código do teste

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

Esperado:

[]

Não visível

Código do teste

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

Esperado:

[]

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

Imprimir uma ligaçãoCódigo

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.

:- 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Ligação direta

Código do teste

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

Esperado:

a worked in film with b.

Duas ligações

Código do teste

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

Esperado:

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

Aplicação a listasEscolha múltipla

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?

A tua respostaselect/4scanlist/4cumlist/4maplist/4map_product/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

Rodar um discoCódigo

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]].



% Define aqui o predicado pedido.

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Negativa

Código do teste

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

Esperado:

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

Grande

Código do teste

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

Esperado:

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

Posição inválida

Código do teste

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

Esperado:

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

Alinhar o códigoCó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].



% Define aqui o predicado pedido.

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Alinhado

Código do teste

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

Esperado:

sim

Comprimento

Código do teste

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

Esperado:

nao

Diferente

Código do teste

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

Esperado:

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

Movimentos do cadeadoCódigo

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]].

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Todos os movimentos

Código do teste

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

Esperado:

[[[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

Código do teste

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

Esperado:

[]

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

Coeficiente de JaccardCódigo

Implementa similarity(?Title1, ?Title2, ?Similarity): divide o número de géneros comuns pelo número de géneros distintos na uniã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(Title1, Title2, Similarity).

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Iguais

Código do teste

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

Esperado:

[1.0]

Parcial

Código do teste

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

Esperado:

[0.4]

Disjuntos

Código do teste

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

Esperado:

[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

Lucro de um pratoCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Pizza

Código do teste

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

Esperado:

[300]

Todos

Código do teste

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

Esperado:

[ratatouille]

Desconhecido

Código do teste

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

Esperado:

[]

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

Consumir ingredientesCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Suficiente

Código do teste

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

Esperado:

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

Insuficiente

Código do teste

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

Esperado:

[]

Ausente

Código do teste

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

Esperado:

[]

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

Listar ingredientes dos pratosCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Todos

Código do teste

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

Esperado:

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

Primeiro prato

Código do teste

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

Esperado:

-(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

Ordenar pratos por lucroCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Ordem

Código do teste

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

Esperado:

[[ratatouille,pizza,garlic_bread]]

Último prato

Código do teste

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

Esperado:

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

Pontuar um códigoCó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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Invertido

Código do teste

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

Esperado:

-(0,4)

Repetições

Código do teste

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

Esperado:

-(2,0)

Misto

Código do teste

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

Esperado:

-(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

Recursão de caudaEscolha múltipla

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

A tua respostaOcorre também em factos.Um argumento adicional permite transformar certos predicados em recursão de cauda.Um corte torna qualquer chamada recursiva uma chamada de cauda.Um predicado sem chamada recursiva usa recursão de cauda.Todas as outras afirmações estão erradas.

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

Listas de diferençaEscolha múltipla

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?

A tua respostaA, B e CA e CSó ASó CB e C

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

Contar pratos com ingredienteCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Tomate

Código do teste

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

Esperado:

Ausente

Código do teste

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

Esperado:

Valor dado

Código do teste

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

Esperado:

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

Consumir para um pratoAutoavaliaçã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]).

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.

A tua resposta

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

Representação bináriaCódigo

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

% dec2bin(Dec, BinList, N).

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Sete

Código do teste

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

Esperado:

[[0,0,0,0,0,1,1,1]]

Não cabe

Código do teste

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

Esperado:

[]

Zero bits

Código do teste

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

Esperado:

[[]]

Negativo

Código do teste

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

Esperado:

[]

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

Preparar geraçãoCódigo

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

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Exemplo

Código do teste

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

Esperado:

[[0,0,1,1,0,0,0,0]]

Sem margem

Código do teste

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

Esperado:

[[1,1]]

Não cabe

Código do teste

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

Esperado:

[]

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

Imprimir uma geraçãoCódigo

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.

% print_generation(List).

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Byte

Código do teste

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

Esperado:

|....M.M.|

Parcial

Código do teste

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

Esperado:

|....M.M.|..MM

Vazia
Código do teste
```
main :- print_generation([]).
```
Esperado:
|

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

Atualizar regra celularCódigo

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.

:- dynamic rule/2.

% update_rule(Rule).

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Regra 10

Código do teste

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

Esperado:

[0,1,0,1,0,0,0,0]

Limite

Código do teste

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

Esperado:

[1,1,1,1,1,1,1,1]

Inválida

Código do teste

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

Esperado:

[]

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

Calcular a geração seguinteCódigo

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

:- 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Exemplo

Código do teste

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

Esperado:

[[0,1,0,1,0,1,0,1]]

Vazia

Código do teste

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

Esperado:

[[]]

Uma célula

Código do teste

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

Esperado:

[[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

Corte, negação e falha

Código

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.

% 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Um vídeo

Código do teste

main :- print_genre_videos(vlog).

Esperado:

Daily Coding Vlog by Bruno

Género ausente

Código do teste

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

Esperado:

ok

Todos os vídeos

Código do teste

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

Esperado:

['','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

Filmes distintos por atorCódigo

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.

:- 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Sem duplicados

Código do teste

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

Esperado:

[friends]

Ator ausente

Código do teste

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

Esperado:

[]

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

Autor mais jovemCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Autores

Código do teste

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

Esperado:

['Stephen King']

Outro autor

Código do teste

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

Esperado:

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

Imprimir génerosCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Ordem

Código do teste

main :- genres('The Shining').

Esperado:

Gothic novel
Horror
Psychological horror

Ausente

Código do teste

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

Esperado:

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

Corte na comparaçãoEscolha múltipla

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?

A tua respostaÉ necessário conhecer a implementação de similarity/3 para classificar o corte.O corte pode ser vermelho ou verde consoante os resultados de similarity/3.O corte não é vermelho nem verde e pode ser retirado sem efeitos.O corte é vermelho porque removê-lo altera os resultados de most_similar/4.O corte é verde porque removê-lo só afeta o desempenho.

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

Pratos mais carosCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Empate

Código do teste

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

Esperado:

[pizza,ratatouille]

Não máximo

Código do teste

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

Esperado:

[]

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

Efeito do corteEscolha múltipla

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

A tua respostaImpede a regra de voltar a ser usada.Converte a regra num facto.Aborta toda a query e sai.Impede o retrocesso para além desse ponto na regra atual.

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

Corte após uma escolhaEscolha múltipla

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

A tua respostaNenhuma solução de q(X) é considerada; o corte passa diretamente a r(X).Só se usa a primeira solução de q(X); o retrocesso não tenta alternativas de q(X).Todas as soluções de q(X) são consideradas e r(X) é verificado para cada uma.A cláusula comporta-se como se não tivesse corte, pois cortes só afetam factos.

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

Corte numa consultaEscolha múltipla

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

O corte nesta consulta é verde?

A tua respostaVerdadeiroFalso

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

Mover um corteEscolha múltipla

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?

A tua respostaVerdadeiroFalso

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

Corte na recursãoEscolha múltipla

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

A tua respostaVerdadeiroFalso

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

Recolha de soluções

Código

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.

% 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Média

Código do teste

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

Esperado:

0.5

Ano ausente

Código do teste

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

Esperado:

[]

Outro ano

Código do teste

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

Esperado:

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

Código

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 é [].

% 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Ordenar

Código do teste

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

Esperado:

[3,4]

Gerar utilizadores

Código do teste

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

Esperado:

[-(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

Código

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 é [].

% 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Grupo

Código do teste

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

Esperado:

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

Sem vídeos

Código do teste

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

Esperado:

[]

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

Atores e filmes de uma personagemCódigo

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].

:- 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Um ator

Código do teste

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

Esperado:

[-(harrisonFord,[airForceOne])]

Ausente

Código do teste

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

Esperado:

[]

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

Atores com mais filmesCódigo

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.

:- 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Empate

Código do teste

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

Esperado:

-([harrisonFord,jenniferGarner],3)

Exclusão

Código do teste

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

Esperado:

-([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

Livros com mais génerosCódigo

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'].

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Máximo

Código do teste

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

Esperado:

['Prey']

Uma solução

Código do teste

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

Esperado:

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

Autores por paísCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Países

Código do teste

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

Esperado:

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

Ausente

Código do teste

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

Esperado:

[]

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

Livros popularesCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Todos

Código do teste

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

Esperado:

['The Firm']

Não popular

Código do teste

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

Esperado:

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

Géneros comunsCódigo

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

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Interseção

Código do teste

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

Esperado:

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

Sem interseção

Código do teste

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

Esperado:

[[]]

Título inexistente

Código do teste

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

Esperado:

[]

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

findall e setofEscolha múltipla

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

A tua respostafindall/3 remove duplicados automaticamente e setof/3 conserva-os.findall/3 devolve só a primeira solução e setof/3 devolve todas.setof/3 ordena, remove duplicados e pode agrupar por variáveis livres; findall/3 recolhe todas numa lista.setof/3 falha sem soluções e findall/3 lança um erro.

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

Recolher soluçõesEscolha múltipla

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?

A tua respostaSó A e ESó C e ESó B e DA, B e DSó A e C

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

Árvores SLD e execução

Folha de falha SLDEscolha múltipla

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

A tua respostaUma prova com sucesso de todos os objetivos da query.Um ponto em que é necessário retroceder porque nenhuma cabeça de cláusula unificou com o objetivo atual.Um erro de sintaxe que interrompe toda a pesquisa.Um ponto em que Prolog evita o retrocesso e fixa o ramo atual.

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

Escolha múltipla

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 tua respostaa. Árvore a.b. Árvore b.c. Árvore c.d. Árvore d.

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

Ramos da pesquisaEscolha múltipla

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?

A tua resposta31520

Solução

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

Unificações e corteEscolha múltipla

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?

A tua resposta194205

Solução

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

Procura, grafos e simulação

Ligação entre atoresCódigo

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].

:- 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Direta

Código do teste

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

Esperado:

[jenniferAniston,friends,courteneyCox]

Sem ligação

Código do teste

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

Esperado:

[]

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

Resolver o cadeadoCódigo

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]].

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Já alinhado

Código do teste

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

Esperado:

[[[1,2]]]

Um movimento

Código do teste

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

Esperado:

[[[1,2]],[[2,1]]]

Impossível

Código do teste

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

Esperado:

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

Encontrar códigos consistentesCódigo

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].

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Exemplo

Código do teste

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

Esperado:

[[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

Código do teste

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

Esperado:

[[1,1,1,1]]

Incompatível

Código do teste

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

Esperado:

[]

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

Arestas comunsCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Interseção

Código do teste

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

Esperado:

Mesmo grafo

Código do teste

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

Esperado:

Sem arestas

Código do teste

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

Esperado:

[]

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

Componentes comunsCódigo

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]].

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Componentes

Código do teste

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

Esperado:

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

Sem arestas comuns

Código do teste

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

Esperado:

[]

Mesmo grafo

Código do teste

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

Esperado:

[[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

Simular geraçõesCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Uma
Código do teste
```
main :- play(2,4,0,210,1).
```
Esperado:
|..M.
Duas
Código do teste
```
main :- play(2,4,0,210,2).
```
Esperado:
|..M. |.M.M
Zero
Código do teste
```
main :- play(2,4,0,210,0).
```
Esperado:
(sem saída)

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

Tamanho de um círculoCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Primeiro

Código do teste

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

Esperado:

[6]

Segundo

Código do teste

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

Esperado:

[3]

Desconhecida

Código do teste

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

Esperado:

[]

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

Maior círculo de ofertasCódigo

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.

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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Maior

Código do teste

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

Esperado:

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

Tamanho

Código do teste

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

Esperado:

[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

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

Erro na restrição de produtoEscolha múltipla

:- 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.

A tua respostaDefinição do domínio das variáveis de decisãoDefinição da pesquisa no espaço de estados (labeling)Definição do número de variáveis de decisãoDefinição das restrições

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

Contar fatores paresCódigo

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

:- use_module(library(clpfd)).

% restricao_pares(Posicoes,Nums,NPares).

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Pares

Código do teste

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

Esperado:

Vazio

Código do teste

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

Esperado:

Escolha

Código do teste

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

Esperado:

[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

Consistência de um grafoEscolha múltipla

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 tua resposta1-consistente, 2-consistente e 3-consistente1-consistente e 2-consistente, mas não 3-consistente1-consistente, mas não 2-consistente ou 3-consistenteNem 1-consistente, nem 2-consistente, nem 3-consistente1-consistente e 3-consistente, mas não 2-consistente

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

Primeira etiquetaEscolha múltipla

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 tua resposta{C - 8}{A - 3}{C - 4}{D - 8}{B - 6}

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

Opções de pesquisaEscolha múltipla

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

A tua respostaEscolher aleatoriamente a próxima variável a etiquetar.Definir duas estratégias de pesquisa distintas para cada metade das variáveis de decisão.Definir um tempo máximo para a fase de pesquisa.Escolher aleatoriamente o valor da próxima variável a etiquetar.Definir o número de variáveis de decisão como uma variável de domínio.

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

Propriedades da programação por restriçõesEscolha múltipla

Qual afirmação está correta?

A tua respostaConstraint & Generate tem sempre desempenho temporal igual ou superior a Generate & Test.Todas as restantes afirmações estão erradas.Múltiplas soluções implicam simetria.all_distinct/1 é mais restritiva do que circuit/1.Os sistemas de programação baseados em restrições seguem um paradigma de programação em lógica.

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

Permutações em ziguezagueAutoavaliação

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.

A tua resposta

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

Gerar listas com somas adjacentesAutoavaliação

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.

A tua resposta

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

Contar atribuições de domínioEscolha múltipla

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?

A tua respostaa.

2MN

M^{L1}+M^{L2}

NM

(2N-1)^M

e. [Não Responder]f.

M^{2N-1}

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

Espaço de atribuições bináriasEscolha múltipla

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?

A tua respostaa.

2^{NK}

N^K

NK

K^N

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

Uma variável por presenteEscolha múltipla

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?

A tua respostaa.

NK

2^{NK}

K^N

N^K

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

Atribuir presentes com paridade opostaAutoavaliação

:- 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.

A tua resposta

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

Propagação antes de labelingEscolha múltipla

:- 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?

A tua respostaa. Não.b. O limite inferior ou superior do domínio das variáveis é alterado.c. Todos os valores redundantes são removidos dos domínios das variáveis.d. Sim, mas apenas em algumas das variáveis.

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

Construir uma linha bináriaCódigo

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.

:- use_module(library(clpfd)).
% Define constroi_bins/3.

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Valores conhecidos

Código do teste

main :- constroi_bins(2,[2,1,2],B), write_canonical(B), nl.

Esperado:

[1,0,1]

Do bit ao destinatário

Código do teste

main :- constroi_bins(2,[X],[1]), write_canonical(X), nl.

Esperado:

Excluir um destinatário

Código do teste

main :- X in 1..3, constroi_bins(2,[X],[0]), findall(X,labeling([],[X]),Xs), write_canonical(Xs), nl.

Esperado:

[1,3]

Sem presentes

Código do teste

main :- constroi_bins(1,[],B), write_canonical(B), nl.

Esperado:

[]

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

CLP(FD): modelos e otimização

Corrigir seleção por posiçãoCódigo

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.

:- 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Produto

Código do teste

main :- restricao_produto([P],[2,3],3), labeling([],[P]), writeln(P).

Esperado:

Vazio

Código do teste

main :- restricao_produto([],[],P), writeln(P).

Esperado:

Impossível

Código do teste

main :- (restricao_produto([_],[2,3],5) -> writeln(sim); writeln(nao)).

Esperado:

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

Eliminar permutaçõesCódigo

Implementa restricao_remover_simetrias(+Posicoes) impondo ordem crescente às posições para evitar permutações da mesma seleção.

:- use_module(library(clpfd)).

% restricao_remover_simetrias(Posicoes).

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Ordenado

Código do teste

main :- (restricao_remover_simetrias([1,2,3])->writeln(sim);writeln(nao)).

Esperado:

sim

Permutação

Código do teste

main :- (restricao_remover_simetrias([2,1])->writeln(sim);writeln(nao)).

Esperado:

nao

Vazio

Código do teste

main :- (restricao_remover_simetrias([])->writeln(sim);writeln(nao)).

Esperado:

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

Quantidades de pratosCódigo

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].

:- use_module(library(clpfd)).

% pratos(Precos,Total,Max,Quantidades).

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Exemplo

Código do teste

main :- findall(Q,pratos([10,22,9,8],132,9,Q),L), writeln(L).

Esperado:

[[6,0,0,9],[9,0,2,3]]

Impossível

Código do teste

main :- (pratos([2],3,2,_)->writeln(sim);writeln(nao)).

Esperado:

nao

Zeros

Código do teste

main :- pratos([1,2],0,0,Q), writeln(Q).

Esperado:

[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

Distribuir grupos por autocarrosCódigo

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.

:- use_module(library(clpfd)).

% autocarros(Grupos,Autocarros,IDs,N).

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Mínimo

Código do teste

main :- autocarros([3,5,7,4,3],[11,14,10,20],_,N), writeln(N).

Esperado:

Sem capacidade

Código do teste

main :- (autocarros([5],[4],_,_)->writeln(sim);writeln(nao)).

Esperado:

nao

Sem grupos

Código do teste

main :- autocarros([],[],IDs,N), write_canonical(result(IDs,N)), nl.

Esperado:

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

Colocar restrições antes da pesquisaEscolha múltipla

:- 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?

A tua respostaa. As variáveis de domínio estão a ser instanciadas antes da fase de pesquisa.b. [Não Responder]c. Nem todas as restrições foram colocadas antes da fase da pesquisa.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.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.f. Não é possível etiquetar Is, pois estas variáveis não têm domínio definido.

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

Modelar o ziguezague com CLP(FD)Código

:- 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.

:- use_module(library(clpfd)).
% Define p2/2 e os auxiliares necessários.

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Três valores

Código do teste

main :- findall(L,p2([1,2,3],L),Ls), sort(Ls,S), write_canonical(S), nl.

Esperado:

[[1,3,2],[2,1,3],[2,3,1],[3,1,2]]

Dois valores

Código do teste

main :- findall(L,p2([1,2],L),Ls), sort(Ls,S), write_canonical(S), nl.

Esperado:

[[1,2],[2,1]]

Valores repetidos

Código do teste

main :- findall(L,p2([1,1,2],L),Ls), sort(Ls,S), write_canonical(S), nl.

Esperado:

[[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

Escolher quatro receitasCódigo

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.

:- use_module(library(clpfd)).
% Define receitas/6.

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Limite de ovos

Código do teste

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.

Esperado:

result(28,[1,2,3,5])

Melhor combinação

Código do teste

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.

Esperado:

result(44,[1,3,4,5])

Receitas insuficientes

Código do teste

main :- (receitas(10,10,[1,2,3],[1,1,1],_,_) -> write(true) ; write(false)), nl.

Esperado:

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

Distribuir cortes por pranchasCódigo

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].

:- use_module(library(clpfd)).
% Define corta/3.

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Todas as distribuições

Código do teste

main :- findall(S,corta([100,45,70],[12,50,14,8,10,90,24],S),Ss), sort(Ss,R), write_canonical(R), nl.

Esperado:

[[2,3,3,2,1,1,2],[3,3,2,3,1,1,2]]

Separar duas peças

Código do teste

main :- findall(S,corta([5,5],[3,3],S),Ss), sort(Ss,R), write_canonical(R), nl.

Esperado:

[[1,2],[2,1]]

Sem peças

Código do teste

main :- corta([5],[],S), write_canonical(S), nl.

Esperado:

[]

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

Corrigir restrições e eliminar reflexõesCódigo

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.

:- use_module(library(clpfd)).
% Define prog2/4.

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Duas variáveis e uma soma

Código do teste

main :- findall(result(A,B),prog2(2,5,A,B),Rs), sort(Rs,S), write_canonical(S), nl.

Esperado:

[result([1,2],[3]),result([1,3],[4]),result([1,4],[5]),result([2,3],[5])]

Um elemento

Código do teste

main :- findall(result(A,B),prog2(1,3,A,B),Rs), sort(Rs,S), write_canonical(S), nl.

Esperado:

[result([1],[]),result([2],[]),result([3],[])]

Domínio insuficiente

Código do teste

main :- (prog2(2,2,_,_) -> write(true) ; write(false)), nl.

Esperado:

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

Emparelhar todas as pessoasCódigo

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].

:- use_module(library(clpfd)).
% Define gym_pairs/4.

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Impossível

Código do teste

main :- (gym_pairs([95,78,67,84],[65,83,75,80],10,_) -> write(true) ; write(false)), nl.

Esperado:

false

Solução única

Código do teste

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.

Esperado:

[[-(1,4),-(2,3),-(3,1),-(4,2)]]

Duas combinações

Código do teste

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.

Esperado:

[[-(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

Maximizar pares possíveisCódigo

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.

:- use_module(library(clpfd)).
% Define optimal_skating_pairs/4.

Testes e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Três pares

Código do teste

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.

Esperado:

valid(3)

Listas de tamanhos diferentes

Código do teste

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.

Esperado:

valid(4)

Sem candidatos

Código do teste

main :- optimal_skating_pairs([60],[80],10,P), write_canonical(P), nl.

Esperado:

[]

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

Distribuir objetos pelo armárioCódigo

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|...].

:- 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Todas as distribuições pequenas

Código do teste

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.

Esperado:

[[3,1,3,4,1,4],[3,1,3,4,2,4]]

Só cabe em baixo

Código do teste

main :- prat([[1],[3]],[2-2],V), write_canonical(V), nl.

Esperado:

[2]

Volume excessivo

Código do teste

main :- (prat([[1],[1]],[2-2],_) -> write(true) ; write(false)), nl.

Esperado:

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

Escolher as variáveis do armárioAutoavaliação

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.

A tua resposta

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

Planear o transporte de mobíliaCódigo

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.

:- 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 e resultado

Verifica o código para comparar o resultado com os testes.

Testes

Quatro trabalhadores

Código do teste

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.

Esperado:

result(60,true)

Outros objetos e limites

Código do teste

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.

Esperado:

result(3,true)

Recursos insuficientes

Código do teste

main :- retractall(homens(_)),assertz(homens(2)),(furniture(_,_) -> write(true) ; write(false)),nl.

Esperado:

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

Escolher as variáveis do horárioAutoavaliação

:- 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.

A tua resposta

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

Bases de conhecimento e relações

Unificação, termos e operadores

Listas, recursão e aritmética

Corte, negação e falha

Recolha de soluções

Árvores SLD e execução

Procura, grafos e simulação

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

CLP(FD): modelos e otimização

Bases de conhecimento e relações

Nome do autor de um vídeo

Testes

Identificador

Nome

Anos de nascimento ímpares

Testes

Gerar

Ano par

Amizade recíproca

Testes

Pares

Sem reciprocidade

Personagens gémeas

Testes

Encontrar

Ausente

Personagens interpretadas por si mesmas

Testes

Substituir

Repetir

Géneros de um livro

Testes

Vários géneros

Títulos por género

Idade ao publicar

Testes

Idade

Autor sem livros

Retirar uma cláusula

Autores de livros

Testes

Título

Sem livros

Autor

Contar ingredientes

Testes

Todos

Pizza

Inexistente

Custo de um ingrediente

Testes

Tomate

Zero

Inexistente

Atualizar custo unitário

Testes

Existente

Novo

Implicação de uma regra

Pares de progenitores

Testes

Duas ordens

Mesmo género

Filho único

Testes

Todos

Sem duplicados

Meio-irmão

Lista de antepassados

Testes

Diretos

Sem antepassados

Unificação, termos e operadores

Instância comum de listas

Operador follows

Operador who

Utilidade de univ

Selecionar argumentos

Testes

Seleção