Path of Optimum Grid Harvest
by 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/java/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.
 *   
 **********************************************************************/ 
 public List<Integer> gridHarvestPath(int[][] grid) {

  if (null == grid) {
    return null;
  }
  //exactly as simple gridHarvest problem
  int[][] value = new int[grid.length][grid[0].length];
  int xMax = grid.length - 1;
  int yMax = grid[0].length - 1;
  for (int x = 0; x <= xMax; x++) {
    for (int y = 0; y <= yMax; y++) {
      amass(grid, x, y, value);
    }
  }

  //trace the boxes selected
  List<Integer> path = new ArrayList<Integer>();
  path.add(grid[xMax][yMax]);
  int x = xMax;
  int y = yMax;
  while (x > 0 && y > 0) {
    if (value[x][y - 1] < value[x - 1][y]) {
      path.add(grid[--x][y]);
    } else {
      path.add(grid[x][--y]);
    }
  }
  
  while(x > 0){
    path.add(grid[--x][y]);
  }
  while(y > 0){
    path.add(grid[x][--y]);
  }
  return path;
}

private void amass(int[][] grid, int x, int y, int[][] value) {
  if (0 < x && 0 < y) {
    value[x][y] = grid[x][y] + Math.max(value[x - 1][y], value[x][y - 1]);
  } else if (0 < x) {
    value[x][y] = grid[x][y] + value[x - 1][y];
  } else if (0 < y) {
    value[x][y] = grid[x][y] + value[x][y - 1];
  } else {
    value[x][y] = grid[x][y];
  }
}

package algorithm.programming.dynamic;

import java.util.Arrays;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class HarvestingTest {

  /**
   * Test of gridHarvestPath method, of class Harvesting.
   */
  @Test
  public void testGridHarvestStaircasePath() {
    System.out.println("gridHarvestPath");
    int[][] grid = {
      {51, 42, 33, 25, 18},
      {13, 21, 34, 55, 89},
      {82, 63, 45, 27, 11},
      {13, 17, 19, 23, 29}
    };
    Harvesting instance = new Harvesting();
    List expResult = Arrays.asList(29,11,89,55,34,33,42,51);
    List result = instance.gridHarvestPath(grid);
    assertEquals(expResult, result);
  }
  
  /**
   * Test of gridHarvestPath method, of class Harvesting.
   */
  @Test
  public void testGridHarvest7Path() {
    System.out.println("gridHarvestPath");
    int[][] grid = {
      {51, 92, 93, 97, 98},
      {13, 21, 34, 55, 89},
      {82, 63, 45, 27, 11},
      {13, 17, 19, 23, 29}
    };
    Harvesting instance = new Harvesting();
    List expResult = Arrays.asList(29,11,89,98,97,93,92,51);
    List result = instance.gridHarvestPath(grid);
    assertEquals(expResult, result);
  }
  
  /**
   * Test of gridHarvestPath method, of class Harvesting.
   */
  @Test
  public void testGridHarvestLPath() {
    System.out.println("gridHarvestPath");
    int[][] grid = {
      {51, 42, 33, 25, 18},
      {93, 21, 34, 55, 89},
      {92, 63, 45, 17, 11},
      {93, 67, 59, 23, 29}
    };
    Harvesting instance = new Harvesting();
    List expResult = Arrays.asList(29,23,59,67,93,92,93,51);
    List result = instance.gridHarvestPath(grid);
    assertEquals(expResult, result);
  }
}