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

# River

## The problem

Let us call a map a rectangular board consisting of `n*m` fields, where each field is one of the following:

• source,
• lake,
• port (its capacity - the number of its docks - is specified by a number between 1 and 7),
• river.

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 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:
• `river`
• `source`
• `lake`
• `meadow`
• `port(N)`, where `N` is an integer between 1 and 7

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:

`    [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)]]`

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

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

`valid_problem(rivermap::in)`
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
| ?- `[friver]`.
% consulting /home/dhanak/bme/dp06s/frame/friver.pl...
%  module river_frame imported into user
%  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

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

• Analysis of requirements
• Description of the applied algorithm
• Planning, specification of major procedures and functions
• Potential tricky details of the implementation
• Test planning
• Experiences

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!

dp@inf.bme.hu