Advent of Code 2021 - Day 15
The problem
Start at top left corner [0,0] of and matrix, find the shortest possible path to reach the bottom right corner at [length-1, length-1] and we can not move diagonally.
Initial thoughs
With given example we can notice that the shortest path would alway be moving forward and moving down, as moving backward and go up would increase the total value for nothing.
Input:
Shortest path:
As first glance, this is a classic Dyanmic Programing / Recursive problem, as given position, we have to choose to lowest value possible.
We have to repeat this process until current item is our destination
My implementation of the algorithm
const findPath = (matrix) => {
const risk = Array.from({ length: matrix.length }, () => Array.from({ length: matrix[0].length }, () => 0));
for (let row = 0; row < matrix.length; row++) {
for (let col = 0; col< matrix[0].length; col++) {
// The staring position is never entered, its risk is not counted
if (row === 0 && col === 0) risk[row][col] = 0;
else {
let risks = [];
if (col > 0) risks.push(risk[row][col - 1]);
if (row > 0) risks.push(risk[row - 1][col]);
risk[row][col] = Math.min(...risks) + matrix[row][col];
}
}
}
return risk;
};
Another approach to solve this problem would be using Dijkstra algorithm or A* algorithm. But personally i'm happy with the dynamic programing approach, my implementation works quite fast for the second parts which require a much bigger input 😛.
That's it for today, thank you for reading.