|
|
|
|
|
Assignment 3 Solution
The strategy for this solution is to use a boolean propogation map
that identifies all the points water can flow down to. In each
iteration, the propogation map is extended until no change is made.
To extend the propogation map, consider some cell, (X, Y). To
determine whether (X, Y) should be set to true in the next iteration,
look at all the neighbors of (X, Y). If it has a neighbor which is
already set to true, and whose elevation is higher (or equal), then
that means water can get to (X, Y). If the elevation matrix is
A and the propogation matrix is Dn, then this is
computed using the expression:
Dn := Dn | (A<=A@no & Dn@no) | (A<=A@ne & Dn@ne)
| (A<=A@ea & Dn@ea) | (A<=A@se & Dn@se)
| (A<=A@so & Dn@so) | (A<=A@sw & Dn@sw)
| (A<=A@we & Dn@we) | (A<=A@nw & Dn@nw);
Note that this computation is written from the perspective of the cell
being propogated to, not the cell we are propogating from. It
essentially asks, "is my neighbor in the propogation map and can water
flow from my neighbor to me."
This allows us to compute all the cells water can get to from the high
point. However, it may pass off the grid or pool up at a local
minima. In order to account for this, we compute basically the same
function, but starting at the low point(s) and working up. We then
AND these two maps together to get only those cells on a path from
high to low. This requires setting a border around the matrix to
avoid incorrect propogation. Making reasonable assumptions about the
minimum and maximum values we'll encounter, we handle this with two
matrices Aup and Adn. Adn has a border of 0s
(since we can never propogate down from a zero cell) and Aup
has a border of 100,000( ensuring that we'll never propogate up from a
border cell.) It might be slightly more efficient to completely
compute the down propogation map with one loop and then the up
propogation map in a separate loop, as one map may require more
iterations to complete. This would also remove the need for both the
Aup and Adn matrices, since a single bordered matrix could be used and
the border just set appropriately for the down computation and then
reset for the up computation.
Code
Adding code to read an input file, display the map at the end, etc. we
get:
program drainage;
prototype GetDim(infile:file):integer;
prototype ReadElev();
config var
filename: string = "A.mat";
infile: file = open(filename,file_read);
default_size:integer = 5;
m:integer = GetDim(infile);
n:integer = GetDim(infile);
region R = [1..m, 1..n];
Rbig = [0..m+1, 0..n+1];
direction no = [-1, 0];
ne = [-1, 1];
ea = [ 0, 1];
se = [ 1, 1];
so = [ 1, 0];
sw = [ 1,-1];
we = [ 0,-1];
nw = [-1,-1];
var A : [R] double;
Tu,Td,Up,Dn : [R] boolean;
procedure drainage();
var
Aup, Adn : [Rbig] double;
[R] begin
ReadElev();
Up := 0; Dn := 0;
Up := A=(min<<A); -- Set low point(s) to true
Dn := A=(max<<A); -- Set high point(s) to true
[Rbig] Aup := 100000; -- Set up borders
[Rbig] Adn := 0;
Aup := A;
Adn := A;
repeat
Tu := Up; Td := Dn; -- Remember previous iteration
Dn := Dn | (Adn<=Adn@no & Dn@no) | (Adn<=Adn@ne & Dn@ne)
| (Adn<=Adn@ea & Dn@ea) | (Adn<=Adn@se & Dn@se)
| (Adn<=Adn@so & Dn@so) | (Adn<=Adn@sw & Dn@sw)
| (Adn<=Adn@we & Dn@we) | (Adn<=Adn@nw & Dn@nw);
Up := Up | (Aup>=Aup@no & Up@no) | (Aup>=Aup@ne & Up@ne)
| (Aup>=Aup@ea & Up@ea) | (Aup>=Aup@se & Up@se)
| (Aup>=Aup@so & Up@so) | (Aup>=Aup@sw & Up@sw)
| (Aup>=Aup@we & Up@we) | (Aup>=Aup@nw & Up@nw);
until ! |<<((Tu != Up) | (Td != Dn)); -- Any change from before?
writeln("Drainage is:\n", Up & Dn);
end;
procedure ReadElev();
var step:double;
begin
if (infile != znull) then
read(infile, A);
end;
end;
procedure GetDim(infile:file):integer;
var dim:integer;
begin
dim := 0;
if (infile != znull) then
read(infile,dim);
end;
return dim;
end;
Test Cases
The test cases we used are:
- mat01.in - Basic path from high to low with a moat around the high
point and a berm restricting the path to the low point.
Input:
10 10
51 51 51 51 51 50 50 50 50 50
51 50 50 50 51 50 50 50 50 50
51 50 52 50 51 50 50 50 50 50
51 50 50 50 51 51 50 50 50 50
51 51 51 51 50 51 51 50 50 50
50 50 50 51 51 50 51 51 50 50
50 50 50 50 51 51 50 51 51 50
50 50 50 50 50 51 51 50 51 51
50 50 50 50 50 50 51 51 49 51
50 50 50 50 50 50 50 51 51 51
Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
- mat02.in - From 2 separate high points to the same low point
Input:
10 10
51 51 51 51 51 51 51 51 51 51
51 50 50 50 51 51 50 50 50 51
51 50 52 50 51 51 50 52 50 51
51 50 50 50 51 51 50 50 50 51
51 51 51 51 50 50 51 51 51 51
50 50 50 51 51 50 51 51 50 50
50 50 50 50 51 51 50 51 51 50
50 50 50 50 50 51 51 50 51 51
50 50 50 50 50 50 51 51 49 51
50 50 50 50 50 50 50 51 51 51
Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 1 1 1 0
0 1 1 1 0 0 1 1 1 0
0 1 1 1 0 0 1 1 1 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
- mat03.in - From 2 separate high points to two separate low points
Input:
10 10
51 51 51 51 51 51 51 51 51 51
51 50 50 50 51 51 50 50 50 51
51 50 52 50 51 51 50 52 50 51
51 50 50 50 51 51 50 50 50 51
51 51 50 51 51 51 51 50 51 51
50 51 50 51 51 51 51 50 51 51
50 51 50 51 51 51 51 50 51 51
50 51 50 51 51 51 51 50 51 51
50 49 51 51 50 50 51 51 49 51
50 50 50 50 50 50 50 51 51 51
Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 1 1 1 0
0 1 1 1 0 0 1 1 1 0
0 1 1 1 0 0 1 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
- mat04.in - A separate path to a local minimum (should not be taken).
Input:
10 10
53 53 53 53 53 53 53 53 53 53
53 50 50 50 53 50 53 53 53 53
53 50 55 50 53 53 53 53 53 53
53 52 50 50 53 53 53 53 53 53
53 51 53 53 50 53 53 53 53 53
53 50 53 53 53 50 53 53 53 53
50 50 53 53 53 53 50 53 53 50
53 53 53 53 53 53 53 50 53 53
53 53 53 53 53 53 53 53 49 53
53 53 53 53 53 53 53 53 53 53
Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
- mat05.in - A path from the low point to a local maximum (should not be taken)
Input:
10 10
53 53 53 53 53 53 53 53 53 53
53 50 50 50 53 50 53 53 53 53
53 50 55 50 53 53 53 53 53 53
53 50 50 50 53 53 53 53 53 53
53 53 53 53 50 53 53 53 53 53
53 53 53 53 53 50 53 53 53 53
53 53 53 53 53 53 50 53 53 53
53 53 53 53 53 53 53 49 53 53
53 53 53 53 53 53 53 53 50 53
53 53 53 53 53 53 53 53 53 53
Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
- mat06.in - wrap-around alternate path to min (path goes down from moat
and then coes across from column 0 to column 9. Would work if matrix
was a torus, but we shouldn't take it, since we're not wrapping around.)
Input:
10 10
53 53 53 53 53 53 53 53 53 53
53 50 50 50 53 50 53 53 53 53
53 50 55 50 53 53 53 53 53 53
53 52 50 50 53 53 53 53 53 53
53 51 53 53 50 53 53 53 53 53
53 50 53 53 53 50 53 53 53 53
50 50 53 53 53 53 50 53 50 50
53 53 53 53 53 53 53 49 53 53
53 53 53 53 53 53 53 53 50 53
53 53 53 53 53 53 53 53 53 53
Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
- mat07.in - another wrap-around alternate path to min
Input:
10 10
53 53 53 53 53 53 53 53 53 53
53 50 50 50 53 50 53 53 53 53
53 50 55 50 53 53 53 53 53 53
53 52 50 50 53 53 53 53 53 53
53 51 53 53 50 53 53 53 53 53
53 50 53 53 53 50 53 53 53 53
50 50 53 53 53 53 50 53 53 50
53 53 53 53 53 53 53 49 53 50
53 53 53 53 53 53 53 53 50 53
53 53 53 53 53 53 53 53 53 53
Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
- mat08.in - Low point in the upper right hand corner is unreachable.
Input:
10 10
51 51 51 51 51 50 50 50 50 50
51 50 50 50 51 50 50 50 49 50
51 50 52 50 51 50 50 50 50 50
51 50 50 50 51 51 50 50 50 50
51 51 51 51 50 51 51 50 50 50
50 50 50 51 51 50 51 51 50 50
50 50 50 50 51 51 50 51 51 50
50 50 50 50 50 51 51 50 51 51
50 50 50 50 50 50 51 51 49 51
50 50 50 50 50 50 50 51 51 51
Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
- mat09.in - Low and high points are disconnected, no path exists.
Input:
10 10
51 51 51 51 51 50 50 50 50 50
51 50 50 50 51 50 50 50 50 50
51 50 53 50 51 50 50 50 50 50
51 50 50 50 51 51 50 50 50 50
51 51 51 51 50 51 51 50 50 50
50 50 50 51 51 52 51 51 50 50
50 50 50 50 51 51 50 51 51 50
50 50 50 50 50 51 51 50 51 51
50 50 50 50 50 50 51 51 49 51
50 50 50 50 50 50 50 51 51 51
Result:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
|
CSE Home 
