# Path of Optimum Grid Harvestby Isai Damier, Android Engineer @ Google

```#=======================================================================
# Author: Isai Damier
# Title:  Path of 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 and show the path taken.
#
# Time-complexity: O(n)
#
# Dynamic Programming Strategy:
#
#   The solution to this problem is exactly as describe in the Optimum
#   Grid Harvest implementation -- plus one more step.
#   http://www.geekviewpoint.com/python/dynamic_programming/grid_harvest.
#
#   To find the optimum number of avocados we keep moving down and
#   to the right from the first cell A to the last cell A[h][w].
#   For the second phase, to find the optimal path, simply do the reverse
#   with V[1..h][1..w]. That is, we walk from V[h][w] to V by
#   moving left and up, always toward the maximum.
#=======================================================================
def gridHarvestPath( grid ):

if grid is None:
return None

# exactly as simple gridHarvest problem
value = [[0 for y in range( len( grid ) )] for x in range( len( grid ) )]
xMax = len( grid ) - 1
yMax = len( grid ) - 1
for x in range( xMax + 1 ):
for y in range( yMax + 1 ):
amass( grid, x, y, value )

# trace the boxes selected
path = []
path.append( grid[xMax][yMax] )
x, y = xMax, yMax
while x > 0 and y > 0:
if value[x][y - 1] < value[x - 1][y]:
x -= 1
path.append( grid[x][y] )
else:
y -= 1
path.append( grid[x][y] )

while x > 0:
x -= 1
path.append( grid[x][y] )

while y > 0:
y -= 1
path.append( grid[x][y] )

return path

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 testGridHarvestStaircasePath( self ):
grid = [
[51, 42, 33, 25, 18],
[13, 21, 34, 55, 89],
[82, 63, 45, 27, 11],
[13, 17, 19, 23, 29]
]
expResult = [29, 11, 89, 55, 34, 33, 42, 51]
result = harvest.gridHarvestPath( grid )
self.assertEquals( expResult, result )

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

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

```