Description
Part 1. In the graph below you see the possible flights between some of the cities in Turkey. Write the
predicate “route(X,Y) – a route between X and Y exists” that returns true of if there is a route between
any given two cities.
Your program should have all the facts and predicates/rules. See the following:
% knowledge base
…
flight(istanbul,antalya). % the fact that Istanbul and Antalya has a flight.
…
% rules
…
route(X,Y) :- flight(X,Y). % a predicate indicating there exist a route between
% X and Y if there is flight between X and Y.
…
Istanbul
Ankara
Van
Izmir
Rize
Antalya
Gaziantep
Konya
Edirne
Edremit
Erzincan
Isparta
Burdur
A single query to complete your program should check if there is a direct route between two given
cities. Alternatively, it can list all the connected cities for a given city. See the following:
?- route(edirne,X).
X = erzincan ;
X = edremit ;
Make sure that your predicate implementation handles cycles properly avoiding infinite loops.
Part 2. Continuing with the previous problem, you are asked to write a program that checks if a route
exists between two cities and if so, provides the shortest route.
In the first step, you are to expand the knowledge by adding distances for the direct flights. E.g.,
% knowledge base
…
flight(istanbul, antalya). % the fact that Istanbul and Antalya has a flight.
distance(istanbul, antalya, 481). % flight distance – calculated using
% https://www.distancecalculator.net
% complete all the flights and distances …
…
A query to complete your program should check if there is a direct route between two given cities and
the shortest distance between them. See the following example:
?- sroute(edremit,erzincan,X).
X = 1044 ;
Part 3. You are given the following database about classes, classrooms and student enrollment.
Classes Enrollment
Class Time Room Student Class
102 10 z23 a 102
108 12 z11 a 108
341 14 z06 b 102
455 16 207 c 108
452 17 207 d 341
e 455
Write the predicates “when(X,Y) – time of the course X is Y”, “where(X,Y) – place of the course X is Y”,
and “enroll(X,Y) – student X is enrolled in course Y”. For example:
% facts..
when(102,10).
3.1. Define/write a predicate “schedule(S,P,T)” that associates a student to a place and time of class.
See the example query and its result.
?- schedule(a,P,T).
P = 102
T = 10 ;
P = 108
T = 12 ;
3.2. Define/write another predicate “usage(P,T)” that gives the usage times of a classroom. See the
example query and its result.
?- usage(207,T).
T = 455 ;
T = 456 ;
3.3. Define/write another predicate “conflict(X,Y)” that gives true if X and Y conflicts due to classroom
or time.
3.4. Define/write another predicate “meet(X,Y)” that gives true if student X and student Y are present
in the same classroom at the same time.
Part 4. Write the following predicates operating on sets.
4.1. Define a Prolog predicate “element(E,S)” that returns true if E is in S.
4.2. Define a Prolog predicate “union(S1,S2,S3)” that returns true if S3 is the union of S1 and S2.
4.3. Define a Prolog predicate “intersect(S1,S2,S3)” that returns true if S3 is the intersection of of S1
and S2.
4.3. Define a Prolog predicate “equivalent(S1,S2)” that returns true if S1 and S2 are equivalent sets.
Part 5. Given a list of integes, find a correct way of inserting arithmetic (operators) such that the result
is a correct equation. Example: With the list of numbers [5,3,5,7,49] we can form the equations (5-
3+5*7) = 11. Please pay attention to the arithmetic operator precedence.
Part 6. In this part you will solve a puzzle, Essentially, each row and column of a rectangular bitmap
is annotated with the respective lengths of its distinct strings of occupied cells. The person who solves
the puzzle must complete the bitmap given only these lengths.
Problem statement: Solution:
|_|_|_|_|_|_|_|_| 3 |_|X|X|X|_|_|_|_| 3
|_|_|_|_|_|_|_|_| 2 1 |X|X|_|X|_|_|_|_| 2 1
|_|_|_|_|_|_|_|_| 3 2 |_|X|X|X|_|_|X|X| 3 2
|_|_|_|_|_|_|_|_| 2 2 |_|_|X|X|_|_|X|X| 2 2
|_|_|_|_|_|_|_|_| 6 |_|_|X|X|X|X|X|X| 6
|_|_|_|_|_|_|_|_| 1 5 |X|_|X|X|X|X|X|_| 1 5
|_|_|_|_|_|_|_|_| 6 |X|X|X|X|X|X|_|_| 6
|_|_|_|_|_|_|_|_| 1 |_|_|_|_|X|_|_|_| 1
|_|_|_|_|_|_|_|_| 2 |_|_|_|X|X|_|_|_| 2
1 3 1 7 5 3 4 3 1 3 1 7 5 3 4 3
2 1 5 1 2 1 5 1
For the example above, the problem can be stated as the two lists
[[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]] and [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]] which give the
“solid” lengths of the rows and columns, top-to-bottom and left-to-right, respectively.
Test Cases: Top-to-bottom or Left-to-right
1. ([[3], [2,1], [3,2], [2,2], [6], [1,5], [6], [1], [2]],
[[1,2], [3,1], [1,5], [7,1], [5], [3], [4], [3]])
2. ( [[3,1], [2,4,1], [1,3,3], [2,4], [3,3,1,3], [3,2,2,1,3], [2,2,2,2,2],
[2,1,1,2,1,1], [1,2,1,4], [1,1,2,2], [2,2,8], [2,2,2,4], [1,2,2,1,1,1],
[3,3,5,1], [1,1,3,1,1,2], [2,3,1,3,3], [1,3,2,8], [4,3,8], [1,4,2,5], [1,4,2,2],
[4,2,5], [5,3,5], [4,1,1], [4,2], [3,3]],
[[2,3], [3,1,3], [3,2,1,2], [2,4,4], [3,4,2,4,5], [2,5,2,4,6], [1,4,3,4,6,1],
[4,3,3,6,2], [4,2,3,6,3], [1,2,4,2,1], [2,2,6], [1,1,6], [2,1,4,2], [4,2,6],
[1,1,1,1,4], [2,4,7], [3,5,6], [3,2,4,2], [2,2,2], [6,3]])
3. ( [[5], [2,3,2], [2,5,1], [2,8], [2,5,11], [1,1,2,1,6], [1,2,1,3],[2,1,1],
[2,6,2], [15,4], [10,8], [2,1,4,3,6], [17], [17], [18], [1,14], [1,1,14], [5,9],
[8], [7]], [[5], [3,2], [2,1,2], [1,1,1], [1,1,1], [1,3], [2,2], [1,3,3],
[1,3,3,1], [1,7,2], [1,9,1], [1,10], [1,10], [1,3,5], [1,8],
[2,1,6],[3,1,7], [4,1,7], [6,1,8], [6,10], [7,10], [1,4,11], [1,2,11], [2,12],
[3,13]] )
