Optimum Grid Harvest
by Isai Damier

#=======================================================================
# Author: Isai Damier
# Title:  Optimum Grid Harvest
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
#   Given n boxes of avocados tightly arranged in a h*w grid, and given
#   that you may only move down or to the right, amass the maximum
#   number of avocados.
#
# Time-complexity: O(n)
#
# Dynamic Programming Strategy:
#
#   As it turns out this problem is easily solved by considering one
#   box of avocado at a time. For each box of avocado: look up, look left,
#   then pick the box that has more avocados and add it to the box on
#   which you are standing.
#
#   Here is how you might go about it:
#   0] Think of the boxes of avocados as an A[1..h][1..w] matrix or array.
#   1] Take a sheet of paper and draw an h*w grid on it. Say V[1..h][1..w].
#   2] In the upper-left cell, V[0][0], write the number of avocados
#      that's in the corresponding box: so V[0][0] = A[0][0]. This is
#      because at A[0][0] there is nothing to the left or above. Simple.
#   3] Imagine you took your next step to the right, then after looking
#      up and looking left, you would have all the avocados in A[0][0]
#      plus those in A[0][1]. Hence, cell V[0][1] would have
#      V[0][0]+A[0][1] avocados. Again there is if you look up.
#   4] But if instead of going right you went down, then after looking
#      up and looking left, you would have all the avocados in A[0][0]
#      plus those in A[1][0]. So that cell V[1][0] would have
#      V[0][0]+A[0][1] avocados. (there is if you look left.)
#   5] After filling each new cell on your sheet of paper, you can fill
#      the next cell by evaluating the same possibilities as in step 3
#      and step 4. So your overall process is
#
#      V[i][j]=A[i][j] + max(V[i-1][j],V[i][j-1])
#
#   6] When you are done with cell V[h][w], it will have the maximum
#      number of avocados you can amass.
#
# Of course in a real implementation, unless you are told not to modify
# the input array A[1..h][1..w] you can double it as V[1..h][1..w]. In
# this implementation, we assume we should not touch the original.
#
# DETAILS YOU MAY NOT CARE FOR:
#
# You could summarize the strategy above as follows:
#
#   For each box we consider, we actually calculate the optimum solution
#   up to that box. Further, to calculate the next box, we use the
#   solutions for the previous boxes. So really we start with a small
#   grid and then keep solving for larger and larger grids until we
#   reach the final answer. Hence, we say the problem shows Optimal
#   Substructures: each smaller segment of the grid is a grid, and the
#   optimal solution to a smaller grid can be applied for solving a
#   larger grid.
#
#   Additionally, the grids overlap. What we mean is the grid
#   A[1..i][1..j] is contained in A[1..i][1..j+1] which in turn is
#   contained in A[1..i+1][1..j+1] up until A[1..h][1..w]. Hence,
#   some of the smaller grids are actually completely parts of the
#   larger grids. This trait is referred to as Overlapping Subproblems.
#
#   Consequently, although we already knew that our strategy is
#   Dynamic Programming, we can confirm that indeed it is Dynamic
#   Programming since we used a table (i.e. V[1..h][1..w]) to solve
#   a problem that exhibits both optimal substructures and overlapping
#   subproblems. You may also hear the word memoize, which basically
#   means we use V[1..h][1..w] to write down memos about each subproblem
#   we solve.
#=======================================================================
 
 def gridHarvest( grid ):
  if grid is None:
    return 0

  value = [[0 for y in range( len( grid[0] ) )] for x in range( len( grid ) )]
  xMax = len( grid ) - 1
  yMax = len( grid[0] ) - 1
  for x in range( xMax + 1 ):
    for y in range( yMax + 1 ):
      amass( grid, x, y, value )

  return value[xMax][yMax]


def amass( grid, x, y, value ):
  if 0 < x and 0 < y:
    value[x][y] = grid[x][y] + max( value[x - 1][y], value[x][y - 1] )
  elif 0 < x:
    value[x][y] = grid[x][y] + value[x - 1][y]
  elif 0 < y :
    value[x][y] = grid[x][y] + value[x][y - 1]
  else:
    value[x][y] = grid[x][y]
import unittest
from dynamic_programming import Harvesting as harvest

class Test( unittest.TestCase ):

  def testGridHarvest( self ):
      grid = [
        [51, 42, 33, 25, 18],
        [13, 21, 34, 55, 89],
        [82, 63, 45, 27, 11],
        [13, 17, 19, 23, 29]
      ]
      expResult = 344
      result = harvest.gridHarvest( grid )
      self.assertEquals( expResult, result )



  def testGridHarvest7( self ):
      grid = [
        [51, 92, 93, 97, 98],
        [13, 21, 34, 55, 89],
        [82, 63, 45, 27, 11],
        [13, 17, 19, 23, 29]
      ]
      expResult = 560
      result = harvest.gridHarvest( grid )
      self.assertEquals( expResult, result )



  def testGridHarvestL( self ):
      grid = [
        [51, 42, 33, 25, 18],
        [93, 21, 34, 55, 89],
        [92, 63, 45, 17, 11],
        [93, 67, 59, 23, 29]
      ]
      expResult = 507
      result = harvest.gridHarvest( grid )
      self.assertEquals( expResult, result )