Path of Optimum Grid Harvest
by Isai Damier

#=======================================================================
# 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 )