Advent of Code 2021 - Day 15

Day 15 - Advent of Code 2021

Advent of Code 2021

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.