Discussion on: Daily Challenge #90 - One Step at a Time

View post

So an easy "greedy" implementation isn't going to work for this one since it could easily happen that the best eventual path has the worst first move.

The problem does have a nice optimal substructure though, in that after you make a move, the path from there is the best one from that point, irrespective of what path you took to get to that point.
That points toward using dynamic programming to solve it.

Here's a JS impl:

function oneStepAtATime(matrix) {
  // For keying an object by coordinate
  const getCoorKey = (x, y) => `${x} ${y}`;
  // The a/0, d/5 style when displaying coordinates
  const getDisplayCoorKey = (x, y) => `${String.fromCharCode('a'.charCodeAt(0) + x)}/${y}`;

  // A store of the best single block moves found so far
  const bestMoveFromCoordinateMemo = {}
  // The dynamic programming function. This finds the best of the three options at each point by recursing into itself
  const bestMoveFromCoordinate = (x, y) => {
    // bottom row just early exits
    if (y == matrix.length - 1) return {
      sum: matrix[y][x]
    };
    const coorKey = getCoorKey(x, y);
    // also early exit if we've already memo'd this spot
    if (bestMoveFromCoordinateMemo[coorKey]) return bestMoveFromCoordinateMemo[coorKey];

    // This reduce finds the best sum starting from one of the three reachable spots on the next line
    // the accumulator is an object with `dx` (change in x) and `subsum` properties
    const {
      dx,
      subsum
    } = [-1, 0, 1].reduce((bestSubmove, dx) => {
      // early exit if we went out of bounds
      if (x + dx < 0 || x + dx >= matrix[y + 1].length) return bestSubmove;
      // destructure `bestSubmove`
      const {
        subsum: bestSubsum
      } = bestSubmove
      // Recurse to find the best move from here
      const {
        sum: subsum
      } = bestMoveFromCoordinate(x + dx, y + 1);
      // accumulate the highest possible sum
      return bestSubsum > subsum ? bestSubmove : {
        dx,
        subsum
      };
    }, {
      subsum: -Infinity
    });
    const sum = matrix[y][x] + subsum;
    return bestMoveFromCoordinateMemo[coorKey] = {
      dx,
      sum
    };
  }

  // Present the path from a point for display
  const movesFromCoordinate = (x, y) => {
    if (y >= matrix.length) return []
    const {
      dx
    } = bestMoveFromCoordinate(x, y);
    return [getDisplayCoorKey(x, y)].concat(movesFromCoordinate(x + dx, y + 1))
  }

  // The output of the overall function as a string
  return movesFromCoordinate(matrix[0].length >> 1, 0).join(', ')
}

console.log(oneStepAtATime([
  [2, 1, 4, 5, 3],
  [5, 2, 1, 4, 3],
  [1, 3, 2, 5, 4],
  [1, 5, 2, 3, 4],
  [3, 2, 1, 5, 4]
]))
// > c/0, d/1, d/2, e/3, d/4

const no = -Infinity;
// A "Greedy" solution won't work on this problem
// in this case the right path looks good to start with, but ends up being a bad choice
console.log(oneStepAtATime([
  [no, no, 1, no, no],
  [no, 1, no, 10000, no],
  [1, no, no, no, 100000],
  [1, no, no, no, 1000000],
  [996, no, no, no, no]
]))
// > c/0, b/1, a/2, a/3, a/4