Daily Challenge #90 - One Step at a Time

You have a square matrix of unsigned integer values. Say, 5 + 5.
Each row of that matrix contains numbers from 1 to 5 (or to whatever length of the matrix), randomly sorted.

You can move through the matrix only one step at the time - either straight down, left-down or right-down.

Your challenge is to write a code that will start at the middle of the top row, and find the path down with the highest sum.

Example:

For the following matrix, you start in c/0. For this matrix the best path would be: c/0, d/1, d/2, e/3, d/4 which scores 4+4+5+4+5 = 22.

---

This challenge comes from peledzohar here on DEV.

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[K.V.Harish]

My solution in js

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

[willsmart]

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