BUTE School of Electrical Engineering and Informatics
Informatics Major
2006 Spring semester

Declarative Programming

Homework Assignment, Version 1.7


This page describes the homework assignment for the Declarative Programming course.

The problem

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:

  1. the river consists of a single field or a set of fields connected by their sides, it does not fork, roots at the source and leads to the lake;
  2. exacly one neighbor sharing a side with the source and the lake must be a river field;
  3. the river cannot cross itself, and its non-neighboring fields may only touch each other with their corners (i.e., a river cannot flow two fields north, one east and then one south);
  4. out of the eight side and corner neighbors the number of water fields must be equal to the capacity of the port;
  5. the river and the lake may only touch each other with their corners (hence there can be no port of capacity 8).

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

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


compound structure, where

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


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


Specification of the procedure and function to be written

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:
        % 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),
          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_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 =
  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

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) =
        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)) =
          | 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
        (* 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

You can assume that your River.river SML function will only be given problem specifications which satisfy this test.

The framework

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

The Prolog framework exports the following five procedures:

The test procedure shown above.
river_in(file::in, rivermap::out)
Reads a rivermap from the given text file and returns it in the second argument.
river_out(file::in, rivermap::in, riverpath::in)
Writes the solution in the given text file.
solve(file::in, file::in)
Reads a problem from the file in the first argument, solves it using the river/2 procedure (must be defined), and writes the solutions in the file in the second argument.
timer(file::in, file::in)
Like 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
| ?- 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

The SML framework export the following four functions:

signature FRiver =
  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
valid_problem rm
Checks the validity of rm rivermap; as shown above.
river_in f
The rivermap read from the text file f.
river_out(f, rm, rps)
The rps solution list of the rm rivermap is written into the f text file.
solve(i, o)
Reads a problem from the text file 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.

Documentation requirements

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.

Further requirements and information

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!

Last modified: Tue May 2 15:01:06 CEST 2006