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

Water Patterns(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][0] = square[i][0]

    queue.append((-bounds[i][0],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[0][i+1] = square[0][i+1]

    queue.append((-bounds[0][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