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

(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

(1)

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

Step 2.  List all pathways for cell position b2

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

(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

(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