Daily Challenge #90 - One Step at a Time

const bestPath = (matrix = []) => {
  let currentIndex = Math.round((matrix[0].length - 1) / 2);
  const path = [
    `${String.fromCharCode(97 + currentIndex)}/0`
  ];

  matrix.forEach((row, index) => {
    if(index !== matrix.length - 1) {
      const arr = [
        matrix[index+1][currentIndex - 1] || 0,
        matrix[index+1][currentIndex] || 0,
        matrix[index+1][currentIndex + 1] || 0
      ];
      currentIndex = currentIndex - 1 + arr.indexOf(Math.max(...arr));
      path.push(`${String.fromCharCode(97 + currentIndex)}/${index + 1}`);
    }
  });
  return path.join(', ');
};

bestPath([
  [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

bestPath([
  [9, 10, 5],
  [1, 2, 6],
  [1, 6, 1]
]); // b/0, c/1, b/2

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