| BUTE School of Electrical Engineering and Informatics
Informatics Major |
2006 Spring semester |
This page describes the homework assignment for the Declarative Programming course.
Let us call a map a rectangular board consisting of
n*m fields, where each field is one of the following:
The source, the lake and the arbitrary number of ports all constist of exactly one field each. The river is built up of a series of consecutive fields. All other fields belong to the meadow. There is exactly one source and one lake, but there can be any number of ports and meadows. The task is to determine the location of the water fields (source, lake and river) on a partially unkown map (where not all fields are specified), such that the following conditions hold:
The location and capacity of all ports is part of a problem specification, further fields may or may not be part of it. A consequence of the conditions is that a solution must contain at least three water fields: there must be at least one river field beside the source and the lake. A problem specification may naturally have multiple solutions.
Figure 1 shows a problem, Figure 2 shows the (only) solution of this problem. Notations: S = source, L = lake, @ = river, number = port of given capacity, M = meadow, empty square = unknown field in the problem, meadow in the solution.
+---+---+---+---+---+ | | 3 | | | | +---+---+---+---+---+ | L | | | M | | +---+---+---+---+---+ | | | | | @ | +---+---+---+---+---+ | S | | 6 | | | +---+---+---+---+---+ | | | | | | +---+---+---+---+---+ |
+---+---+---+---+---+ | | 3 | | | | +---+---+---+---+---+ | L | @ | @ | M | | +---+---+---+---+---+ | | | @ | @ | @ | +---+---+---+---+---+ | S | @ | 6 | | @ | +---+---+---+---+---+ | | @ | @ | @ | @ | +---+---+---+---+---+ |
|
Figure 1: A problem (n=5, m=5)
|
Figure 2: The only solution of the problem |
Your task will be to write a Prolog procedure and an SML function called
river, which finds all solutions of a given problem
specification!
The Prolog procedure has two arguments. The first (input) argument represents the problem, the second (output) argument describes the solution. The procedure must enumerate all solutions via backtracking. If the problem has no solutions, the predicate must fail.
The input argument of the Prolog procedure is a
r(R-C,FieldL)
compound structure, where
R and C are the number of rows and columns
of the board respectively (the upper left corner has coordinates
1-1).FieldL is the list of known fields, where the list
contains elements of the form f(Row,Column,Type). These
determine the position and type of the known fields. Type
can be any of the following terms:
riversourcelakemeadowport(N), where N is an integer between 1
and 7In case of the example shown in Figure 1, the input argument of the Prolog procedure would look like:
r(5-5, [f(1,2,port(3)),f(2,1,lake),f(2,4,meadow),f(3,5,river),f(4,1,source),f(4,3,port(6))])
The output argument of the Prolog procedure is the list of coordinates of the water fields leading from the source to the lake (including the source and the lake).
The following list describes the solution seen in Figure 2:
[4-1,4-2,5-2,5-3,5-4,5-5,4-5,3-5,3-4,3-3,2-3,2-2,2-1]
The single argument of the SML function is a
((R,C), FieldL) pair, where R and C
are the same as above, FieldL is a list of
(Row,Column,Type) tuples, where the meaning of
Row, Column and Type are also like
above.
The Type parameter has type ftype and can have
values according to the following declaration:
datatype ftype = River | Source | Lake | Meadow | Port of int
In case of the problem shown in Figure 1, the parameter of the SML function would be:
((5,5), [(1,2,Port 3),(2,1,Lake),(2,4,Meadow),(3,5,River),(4,1,Source),(4,3,Port 6)])
The result of the SML function application is a list, which contains all solutions of the problem, and each solution exactly once. If the problem has no solutions, the result list must be empty. One solution must be given as a list of coordinates (pairs), just like in case of the Prolog procedure.
The solution shown in Figure 2 is described by the following solution list (containing a single solution):
[[(4,1),(4,2),(5,2),(5,3),(5,4),(5,5),(4,5),(3,5),(3,4),(3,3),(2,3),(2,2),(2,1)]]
The arguments of the river/2 procedure are described by the
following Prolog type specifications (given as
comments).
% :- type field ---> f(row, column, field_type).
% :- type field_type ---> river ; source ; lake ; meadow ; port(dockcnt).
% :- type row == integer.
% :- type column == integer.
% :- type dockcnt == integer.
% :- type location ---> row-column.
% :- type bsize ---> row-column.
% :- type rivermap ---> r(bsize, list(field)).
% :- type riverpath == list(location).
The first argument of river/2 procedure (of type
rivermap) is guaranteed to satisfy the following test
predicate:
valid_problem(r(Bsize,FieldL)) :- % the size of the board is correct: valid_location(Bsize,inf-inf), % FieldL has no invalid element: \+ ( member(Field, FieldL), \+ valid_field(Field, Bsize) ), % source and lake cannot be side neighbors, % their distance must be larger than 1: ( member(f(SF,OF,source),FieldL), member(f(ST,OT,lake),FieldL) -> distance(SF-OF, ST-OT, Dist), Dist > 1 ; true ), % there is at most one source in the list: ( select(f(_,_,source),FieldL,FieldLF) -> \+ member(f(_,_,source),FieldLF) ; true ), % there is at most one lake in the list: ( select(f(_,_,lake),FieldL,FieldLT) -> \+ member(f(_,_,lake),FieldLT) ; true ), % FieldL is lexicographically sorted: sort(FieldL, FieldL), % all elements of FieldL specify a field with a unique coordinate % (becuase the list is sorted, it is enough to make sure that no % two neighbors specify the same field): \+ append(_, [p(R,C,_),p(R,C,_)|_], FieldL). valid_location(S-O, MaxS-MaxO) :- integer(S), S >= 1, S =< MaxS, integer(O), O >= 1, O =< MaxO. distance(S1-O1, S2-O2, T) :- T is sqrt( (S1-S2)**2 + (O1-O2)**2 ). valid_field(f(S,O,Tipus),Bsize) :- valid_location(S-O,Bsize), valid_type(Tipus). valid_type(river). valid_type(source). valid_type(lake). valid_type(meadow). valid_type(port(N)) :- integer(N), N >= 1, N =< 7.
You can assume that your river/2 Prolog procedure will only
be given problem specifications which satisfy this test.
The types of the argument and result of the river (fully
qualified name River.river) SML function are defined by the
following SML type specifications.
structure TRiver = struct type row = int (* 0 < row *) type column = int (* 0 < column *) type dockcnt = int (* 1 <= dockcnt <= 7 *) datatype ftype = River | Source | Lake | Meadow | Port of dockcnt type location = row * column type bsize = row * column type field = row * column * ftype type rivermap = bsize * field list type riverpath = location list end
The argument passed to the River.river function is of type
TRiver.rivermap, and is guaranteed to satisfy the following
test function:
app load ["Listsort", "Math", "TRiver"]; open TRiver; (* valid_problem rm = rm is a valid problem specification; the first argument of River.river is guaranteed to satisfy this test. *) fun valid_problem (Bsize, FieldL) = let val (MaxR, MaxC) = Bsize fun valid_location (Row, Column) = 1 <= Row andalso 1 <= Column andalso Row <= MaxR andalso Column <= MaxC fun valid_type (Port n) = 1 <= n andalso n <= 7 | valid_type _ = true fun valid_field (Row, Column, Type) = valid_location (Row, Column) andalso valid_type Type fun distance (SOME (S1, O1), SOME (S2, O2)) = Math.sqrt(Math.pow(real(S1)-real(S2),2.0)+ Math.pow(real(O1)-real(O2),2.0)) | distance _ = 10e6 fun lex_compare ((x1,y1,_), (x2,y2,_)) = if x1 < x2 orelse x1 = x2 andalso y1 < y2 then LESS else if x1 > x2 orelse x1 = x2 andalso y1 > y2 then GREATER else EQUAL fun neighbors_different (rp1::(rps as rp2::_)) = lex_compare (rp1, rp2) <> EQUAL andalso neighbors_different rps | neighbors_different _ = true fun source (_, _, Source) = true | source _ = false fun lake (_, _, Lake) = true | lake _ = false fun coords (SOME (S, O, _)) = SOME (S, O) | coords NONE = NONE in (* the size of the board is correct: *) 1 <= MaxR andalso 1 <= MaxC andalso (* all elements of FieldL are valid: *) List.all valid_field FieldL andalso (* source and lake are not side neighbors: *) distance(coords(List.find source FieldL), coords(List.find lake FieldL)) > 1.0 andalso (* there is at most one source in the list: *) List.length (List.filter source FieldL) < 2 andalso (* there is at most one lake in the list: *) List.length (List.filter lake FieldL) < 2 andalso (* FieldL is lexicographically sorted: *) Listsort.sorted lex_compare FieldL andalso (* all elements of FieldL specify a field with a unique coordinate: *) neighbors_different FieldL end
You can assume that your River.river SML function will only
be given problem specifications which satisfy this test.
You can test your programs with the provided framework. The framework, including the specification modules and a set of test cases (similar to those which will be used to test your submission) can be downloaded here.
The framework can parse text files of the following structure. The
first line must contain two integers: the number of rows and columns of the
board. All further lines descibe one known field each. These lines begin
with the row and column coordinate of the given field, followied by the
type of the field: one of the river, source,
lake, meadow, port words. In case
of a port, the line is terminated with a third integer: the capacity of the
port. The specification must satisfy the conditions described so far.
5 5 1 2 port 3 2 1 lake 2 4 meadow 3 5 river 4 1 source 4 3 port 6 |
| Figure 3: The input text file for the problem in Figure 1 |
Furthermore, the framework can produce text files containing figures similar to Figure 2 (one for each solution).
The Prolog framework exports the following five procedures:
valid_problem(rivermap::in)river_in(file::in, rivermap::out)river_out(file::in, rivermap::in, riverpath::in)solve(file::in, file::in)river/2 procedure (must be defined), and writes the
solutions in the file in the second argument.timer(file::in, file::in)solve/2, but also prints the run time after the run
completes.The framework relies on the file type:
% :- type file == atom.
By passing the atom user in a file argument, we can read
resp. write data from resp. to the terminal. Otherwise, the file with the
given name will be used.
Usage: put your own program in the file
river.pl, otherwise the framework will not be
able to locate it. Then run the SICStus interpreter, and load the
framework. Example run:
SICStus 3.12.2 (x86-linux-glibc2.3): Sun May 29 11:59:09 CEST 2005
Licensed to BUTE SZIT
| ?- [friver].
% consulting /home/dhanak/bme/dp06s/frame/friver.pl...
% module river_frame imported into user
% loading /opt/sicstus/lib/sicstus-3.12.2/library/lists.po...
% module lists imported into river_frame
% loaded /opt/sicstus/lib/sicstus-3.12.2/library/lists.po in module lists, 0 msec 11800 bytes
% consulted /home/dhanak/bme/dp06s/frame/friver.pl in module river_frame, 30 msec 32144 bytes
yes
| ?- timer(..., ...).
Calling either of timer/2 or solve/2
procedures will automatically load your program into the interpreter (if
necessary), therefore there is no need to restart the interpreter or to
reload the framework even if you modify the source.
The SML framework export the following four functions:
signature FRiver = sig val valid_problem : TRiver.rivermap -> bool val river_in : string -> TRiver.rivermap val river_out : string * TRiver.rivermap * TRiver.riverpath list -> unit val solve : string * string -> string end
valid_problem rmrm rivermap; as shown above.river_in ff.river_out(f, rm, rps)rps solution list of the rm rivermap is
written into the f text file.solve(i, o)i and writes all its solutions
into the text file o. Requires a correct implementation of
River.river. The result of this function is a string
containing the number of solutions and run time statistics.The input resp. output can be redirected to the terminal by using the
file name /dev/stdin resp. /dev/stdout under
Unices, con for both under MS DOS/Windows systems.
Usage: first compile all modules, including your
River.sml containing the implementation of
the river function with the following command:
mosmlc -c TRiver.sml River.sig River.sml FRiver.sig FRiver.sml
Then load the FRiver module into the interpreter and open
it:
Moscow ML version 2.01 (January 2004)
Enter `quit();' to quit.
- load "FRiver";
> val it = () : unit
- open FRiver;
> val river_in : string -> (int * int) * (int * int * ftype) list
val river_out :
string * ((int * int) * (int * int * ftype) list) *
(int * int) list list -> unit
val solve : string * string -> string
val valid_problem : (int * int) * (int * int * ftype) list -> bool
- solve (..., ...);
When you modify your program, it is enough to recompile
River.sml and restart the interpreter.
Make sure that the source files are easily readable: pick meaningful names for procedures, functions and variables, specify the role and domain of arguments, explain the role and behavior of particular predicates and functions! Follow the conventions used in class! Don't write lines longer than 72 characters! Write head comments for all procedures and functions!
Document your algorithm and both implementations in a single document. The contents of this document should conver:
Submit the documentation electronically in HTML, PDF or ASCII format.
You may choose to implement your programs under MS Windows, but it is required that they run under Linux. All programs will be tested under Linux, using SICStus Prolog 3.12.x and MOSML 2.01.
You can submit the programs and the documentation electronically by
e-mailing them to the address dhanak[at]cs[dot]bme[dot]hu by no
later than two days before the exam (TBD).
Solving the homework is not a hard requirement, but it gives an unparalleled means of learning declarative programming at an advanced level. Therefore it is strongly recommended to solve it in both languages. However, we accept solutions in only one of the two languages with at most half of the total available scores.
Warning! It is almost impossible to get a high mark without solving the homework.
It is strictly forbidden to share anything other than ideas of algorithms with each other! The programs will be analyized for similarities systematically. Copying pieces of code from someone elses program will be severely penalized!