T-93.540 Logic Programming, autumn 05

Optional Home Exercises, series 1

This is the first part of the home exercises. By returning the answers to these proglems students can earn two points for the exam. The deadline for the return 30.9.2005.

Return is done by submit-system quide. (The ID logic2005 is confirmed).

These exercises are meant to motivate students to use Prolog during the course, before the final rush before the deadline of the assignment.

Problems 1-2: The Railways of Eastern Europe

1. Basic Programming, Non-deterministic Automaton

The Railways of Eastern Europe have the following train lines: 

Departure       Arrival         Train
Helsinki        Vyborg           4833
Vyborg          Helsinki         4822
Vyborg          Tartu             201
Vyborg          St. Petersburg    614
Tartu           St. Petersburg    322
Tartu           Vyborg            212
Riga            Vyborg	          458
Riga            St. Petersburg  ic621
St. Petersburg  Tartu             323
St. Petersburg  Vyborg            613
St. Petersburg  Riga            ic620

Ivan Helsin has been on a business trip to Vyborg. He has to get to Tartu using the mentioned train routes, and he has to get his wife Natasha from Riga on the way home. Use Prolog to construct a nondeterministic finite automaton describing the case. The program is not allowed to go into an infinite loop.

2. Data Structure, Defining Own Predicates

Below is a more accurate time-table for the previous lines:

timetable(helsinki,vyborg,
  [ 9:40 .. 10:50 .. 4733 .. alldays,
   13:40 .. 14:50 .. 4773 .. alldays,
   19:40 .. 20:50 .. 4833 .. [mo,tu,we,th,fr,su]]).

timetable(vyborg,helsinki,
  [ 9:40 .. 10:50 .. 4732 .. alldays,
   11:40 .. 12:50 .. 4752 .. alldays,
   18:40 .. 19:50 .. 4822 .. [mo,tu,we,th,fr]]).

timetable(vyborg,tartu,
  [13:20 .. 16:20 .. 201 .. [fr],
   13:20 .. 16:20 .. 213 .. [su]]).

timetable(vyborg,st_petersburg,
  [ 9:10 .. 11:45 .. 614 .. alldays,
   14:45 .. 17:20 .. 805 .. alldays]).

timetable(vyborg,riga,
  [ 8:30 .. 11:20 .. 510 .. alldays,
   11:00 .. 13:50 .. 459 .. alldays]).

timetable(tartu,st_petersburg,
  [11:30 .. 12:40 .. 322 .. [tu,th]]).

timetable(tartu,vyborg,
  [11:10 .. 12:20 .. 200 .. [fr],
   11:25 .. 12:20 .. 212 .. [su]]).

timetable(riga,st_petersburg,
  [ 9:25 .. 10:15 .. ic621 .. alldays,
   12:45 .. 13:35 .. ic623 .. alldays]).

timetable(riga,vyborg,
  [ 9:10 .. 10:00 .. 458 .. alldays,
   12:20 .. 13:10 .. 511 .. alldays]).

timetable(st_petersburg,tartu,
  [13:30 .. 14:40 .. 323 .. [tu,th]]).

timetable(st_petersburg,vyborg,
  [ 9:00 ..  9:40 .. 613 .. [mo,tu,we,th,fr,sa],
   16:10 .. 16:55 .. 806 .. [mo,tu,we,th,fr,su]]).

timetable(st_petersburg,riga,
  [ 7:55 .. 8:45 .. ic620 .. alldays]).

Implement a train route planner that uses the previous train timetable facts.

The program should contain the following predicates:

    % main planner
    route(Place1,Place2,Day,Route) :- ...

    % a description of one train
    train(Place1,Place2,Day,Train_number,Departure_time,Arrival_time) :- ...

    % the connection of several train, with the transfer constant of 10 minutes between two
    % consecutive trains
    transfer(Time1,Time2) :- ...

The Route variable satisfies the following:

The Route data structure should be a list of the following objects:

    From – To ::: Train_number ::: Departure_time

The program is not allowed to go into an infinite loop.

Problem 3: Sudoku

Sudoku rules are extremely easy: Fill all empty squares so that the numbers 1 to 9 appear once in each row, column and 3x3 box. Rules.

Construct a logic program for generating random Sudoku-puzzle and solving it. Cell vales are hidden in the puzzle with a probability given as an attribute to the program. ( The following examples provide some codes for generating full Sudoku-tables in lexical code1 and random code2 order.) Have some heuristic in the search for solution. Minimum requirement solve the homework assignment for miniature Sudoku puzzle with 4x4 size and numbers 1 to 4.

Problem 4: Study of a social network

After having completed the studies of European air and rail traffic, Prof. Helsin has redirected his research interest to sociometric studies. He has recorded a data base of trust relations between individuals.

He has defined two a transitive trust relations - strong and weak forms of trust:

  1. weak trust: there are two different paths from the person trusting to the person trusted.
  2. strong trust: there are two paths having no common nodes from the person trusting to the person being trusted.

But absent minded as he is, Prof Helsing lost the analytic software. He asks you to reimplement it in Prolog. Fortunately there is listing od a session (below) that shows the top level calls.

The person that implemented the original analysis software told that predicate named distinct_paths/5 was the core of the implementation. it counted the paths having no common intermediate elements.

Task: Write Prolog code that calculations that are needed to generate the output shown in the required dialogue below.

REQUIRED DIALOGUE:

%
% ?- trust_path0(john,mark,[],Path).
%
% Path = [mary] ;
% 
% Path = [jerry, lisa] ;
%  
% No
%
% ?- different_paths(john,tom,N).
%  
% N = 6 ;
%  
% No
%
% ?- weak(mark,B).
% 
% B = lisa ;
% 
% B = fred ;
% 
% B = anna ;
% 
% B = paul ;
%  
% B = tom ;
% 
% No
%
% ?- strong(mark,B).
% 
% B = lisa ;
%  
% B = tom ;
% 
% No
%
%
% ?- trust_level(2,P).
% 
% P = [[john, mark], [john, tom], [john, lisa], [mark, lisa], [mark, tom], [jack, tom], [lisa, tom]] ;
% 
% No
% ?- max_trust(M).
%  
% M = 3 ;
%  
% No
%

% DATABASE

trust(john,mary).
trust(mary,mark).
trust(mark,jack).
trust(jack,john).
trust(jack,tom).

trust(john,jerry).
trust(jerry,lisa).
trust(lisa,mark).
trust(mark,lisa).
trust(mark,pat).
trust(pat,tom).

trust(lisa,fred).
trust(fred,anna).
trust(anna,paul).
trust(paul,tom).