## DEV Community is a community of 888,741 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 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 yo+challenge@dev.to with your suggestions!

## Discussion (3) K.V.Harish

My solution in js

``````const bestPath = (matrix = []) => {
let currentIndex = Math.round((matrix.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 • Edited on

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.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
``````