Water Retention Homework 2010

Problem #1.  Find the water capacity for the following square and write your solution in code that will find the water capacity for any order 5 square

 8 11 22 20 4 8 11 22 20 4 14 24 1 5 21 14 24 1 5 21 15 6 23 2 19 15 6 23 2 19 18 7 3 25 12 18 7 3 25 12 10 17 16 13 9 10 17 16 13 9

(1)

Method  1  :  list all pathways of escape from each interior cell to the exterior

There are only 3 unique cell positions in the interior  b2, b3, c3

Step 1.  List all pathways for cell position c3

 a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 d1 d2 d3 d4 d5 e1 e2 e3 e4 e5

(1)

Starting from  cell c3  and moving through cell b3 there are 5 paths

Step 2.  List all pathways for cell position b2

 a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 d1 d2 d3 d4 d5 e1 e2 e3 e4 e5

Starting from cell b2 and moving to a2 or through b3 there are 18 paths

(1)

The number of pathways defined for b2 … obviously apply to b4,d2 and d4

Step 3.  List all pathways off the square for cell b3

 a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 d1 d2 d3 d4 d5 e1 e2 e3 e4 e5

(1)

Taking into account all the symmetrical redundancies :

For cell c3 = 20 paths  off the square x 1 =  20 paths

For cell b2 =36 paths off the square x 4 = 144 paths

For cell b3 =30 paths off the square x 4 = 120 paths

_______________________________________________

Total paths order 5 square  =                      284 paths

Once the paths have been defined sorting all the paths for the path with the least obstruction off the square is a straight forward process.

Example  #1  of code that will find the capacity for any order 5 square:

Local Int a, b, c, d, e, f, g, h, z, r, s

' a e b

' f z g

' c h d

a = MaxI(j22, MinI(j21, j12))

b = MaxI(j42, MinI(j41, j52))

c = MaxI(j24, MinI(j14, j25))

d = MaxI(j44, MinI(j54, j45))

e = MaxI(j32, MinI(j31, a, b))

f = MaxI(j23, MinI(j13, a, c))

g = MaxI(j43, MinI(j53, b, d))

h = MaxI(j34, MinI(j35, c, d))

z = MaxI(j33, MinI(e, f, g, h))

If (e > j32) And (e > z) Then e = MaxI(j32, z)

If (f > j23) And (f > z) Then f = MaxI(j23, z)

If (g > j43) And (g > z) Then g = MaxI(j43, z)

If (h > j34) And (h > z) Then h = MaxI(j34, z)

If a > j22 Then r = MinI(e, f) : If a > r Then a = MaxI(j22, r)

If b > j42 Then r = MinI(e, g) : If b > r Then b = MaxI(j42, r)

If c > j24 Then r = MinI(f, h) : If c > r Then c = MaxI(j24, r)

If d > j44 Then r = MinI(g, h) : If d > r Then d = MaxI(j44, r)

If z = j33

If e > j32 Then r = MinI(a, b) : If e > r Then e = MaxI(j32, r)

If f > j23 Then r = MinI(a, c) : If f > r Then f = MaxI(j23, r)

If g > j43 Then r = MinI(b, d) : If g > r Then g = MaxI(j43, r)

If h > j34 Then r = MinI(c, d) : If h > r Then h = MaxI(j34, r)

If a > j22 Then r = MinI(e, f) : If a > r Then a = MaxI(j22, r)

If b > j42 Then r = MinI(e, g) : If b > r Then b = MaxI(j42, r)

If c > j24 Then r = MinI(f, h) : If c > r Then c = MaxI(j24, r)

If d > j44 Then r = MinI(g, h) : If d > r Then d = MaxI(j44, r)

If e > j32 Then r = MinI(a, b) : If e > r Then e = MaxI(j32, r)

If f > j23 Then r = MinI(a, c) : If f > r Then f = MaxI(j23, r)

If g > j43 Then r = MinI(b, d) : If g > r Then g = MaxI(j43, r)

If h > j34 Then r = MinI(c, d) : If h > r Then h = MaxI(j34, r)

If a > j22 Then r = MinI(e, f) : If a > r Then a = MaxI(j22, r)

If b > j42 Then r = MinI(e, g) : If b > r Then b = MaxI(j42, r)

If c > j24 Then r = MinI(f, h) : If c > r Then c = MaxI(j24, r)

If d > j44 Then r = MinI(g, h) : If d > r Then d = MaxI(j44, r)

If e > j32 Then r = MinI(a, b) : If e > r Then e = MaxI(j32, r)

If f > j23 Then r = MinI(a, c) : If f > r Then f = MaxI(j23, r)

If g > j43 Then r = MinI(b, d) : If g > r Then g = MaxI(j43, r)

If h > j34 Then r = MinI(c, d) : If h > r Then h = MaxI(j34, r)

End If

r = 0 : s = 0

If j22 < a Then r += a - j22 : s = Bset(s, 0)

If j42 < b Then r += b - j42 : s = Bset(s, 2)

If j24 < c Then r += c - j24 : s = Bset(s, 6)

If j44 < d Then r += d - j44 : s = Bset(s, 8)

If j32 < e Then r += e - j32 : s = Bset(s, 1)

If j23 < f Then r += f - j23 : s = Bset(s, 3)

If j43 < g Then r += g - j43 : s = Bset(s, 5)

If j34 < h Then r += h - j34 : s = Bset(s, 7)

If j33 < z Then r += z - j33 : s = Bset(s, 4)

cnt(sym(s), r)++

(1)

Example  #2  of code that will find the capacity for any order 5 square:

Local Int x, y, r = 0, s = 0, b = 0

ArrayFill v(), 0

For y = 2 To 4

For x = 2 To 4

Barrier = 25

v(x, y)++

Path(x, y, 0)

v(x, y)--

If Barrier > j(x, y)

r += Barrier - j(x, y)

s = Bset(s, b)

End If

b++

End For

End For

cnt(sym(s), r)++

Proc Path(ByVal x As Int, ByVal y As Int, ByVal h As Int)

If v(x, y) > 1 Then Exit Proc

h = MaxI(h, j(x, y))

If (x = 1) Or (x = 5) Or (y = 1) Or (y = 5)

Barrier = MinI(Barrier, h)

Else

v(x - 1, y)++

v(x + 1, y)++

v(x, y - 1)++

v(x, y + 1)++

Path(x - 1, y, h)

Path(x + 1, y, h)

Path(x, y - 1, h)

Path(x, y + 1, h)

v(x - 1, y)--

v(x + 1, y)--

v(x, y - 1)--

v(x, y + 1)--

End If

(1)

Problem #2 :  label all unique water retention patterns for the order 5 square (1)

Problem #3.  Write code that will find the water capacity of any order of square

The number of paths off the square and the number of water patterns increase exponentially as the order of the square increases.   The table below shows that there are 4211744 different water patterns for a order 7 square.  The list all pathways method is losing its appeal as a method to solve this problem

 Order n Number of water patterns 3 2 4 6 5 102 6 8548 7 4211744 8 8590557312 9 7.03689E+13

(1)

The table above shows the necessity for abandoning the list all pathway process to determine the water capacity for  squares   >  order 5.   A general algorithm is needed that will determine the water capacity of any order of square.

Water Retention Algorithm  (Python) (2)

def process(square):

n = len(square) # square is a list of lists

bounds = [n*[n*n] for i in range(n)]

queue = [] # lousy implementation, just for algorithm testing

# head of queue is last element

# big numbers for high priority

for i in range(n-1):

bounds[i] = square[i]

queue.append((-bounds[i],i,0))

bounds[n-1][i] = square[n-1][i]

queue.append((-bounds[n-1][i],n-1,i))

bounds[i+1][n-1] = square[i+1][n-1]

queue.append((-bounds[i+1][n-1],i+1,n-1))

bounds[i+1] = square[i+1]

queue.append((-bounds[i+1],0,i+1))

while queue:

queue.sort()

(b,i,j) = queue.pop()

for (di,dj) in [(-1,0),(1,0),(0,-1),(0,1)]:

u=i+di; v=j+dj

if 0<=u<n and 0<=v<n:

b1 = max(square[u][v],-b)

if b1 < bounds[u][v]:

bounds[u][v] = b1

queue.append((-b1,u,v))

return bounds

def capacity(square):

bounds = process(square)

n = len(square)

s = 0

for i in range(n):

for j in range(n):

delta = bounds[i][j]-square[i][j]

print bounds[i][j],delta

if delta>0: s += delta

return s

result = capacity([[57,38,31,47,32,40,45,46,33],

[27,58,60,23,66,9,15,72,39],

[29,61,12,65,8,69,77,11,37],

[30,64,6,81,3,80,7,62,36],

[48,19,78,14,41,68,4,63,34],

[44,20,75,2,79,1,76,18,54],

[42,71,5,13,74,17,70,21,56],

[43,10,67,73,16,59,22,24,55],

[49,28,35,51,50,26,53,52,25]])

print(result)

(2)

Explanation of how the water retention algorithm works (1)

The water number table in blue to the right is generated by setting all interior cells to the maximum number for the square and leaving all the exterior values from the original square.

Original Square                                                          Water Number   W - number

 16 3 2 13 16 3 2 13 5 10 11 8 5 16 16 8 9 6 7 12 9 16 16 12 4 15 14 1 4 15 14 1 No cell can retain more water than the w-number. Therefore we just have to consider how much water flows away from each inner cell. Search the lowest w-number. w = 1 This cell already has got its final water level. Let the water flow from the neighbor cells, if possible. From 14 and 12 no water can flow to 1. Because 14 and 12 are the original numbers. 16 3 2 13 16 3 2 13 5 10 11 8 5 16 16 8 9 6 7 12 9 16 16 12 4 15 14 1 4 15 14 1 Search the lowest w-number. w = 2 This cell already has got its final water level. Let the water flow from the neighbour cells, if possible. From 3 and 13 no water can flow to 2. But from the cell below (16) 5 units of water flow to 2. 16 3 2 13 16 3 2 13 5 10 11 8 5 16 11 8 9 6 7 12 9 16 16 12 4 15 14 1 4 15 14 1 Search the lowest w-number. w = 3 This cell already has got its final water level. Let the water flow from the neighbor cells, if possible. From the cell below (16) 6 units of water flow to 3. 16