#=======================================================================
# 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[0][0] 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[0][0] 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[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 )
# 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 )
