Published
Edited
Dec 15, 2021
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
// takes a point in a maze
// returns the safest path to finish
// todo: fill path
function solve({maze, point = [0, 0], safest, path = []} = {}) {

const [r, c] = point;

if (!safest) safest = Array.from({length: maze.length}).map(() => new Array(maze[0].length));

let risk = 0;

// been there, done that? => short circuit (a.k.a. memoized)
if (safest[r][c]) {
risk = safest[r][c];
}

// finish?
else if (r === maze.length - 1 && c === maze[0].length - 1) {
risk = safest[r][c] = maze[r][c];
}

// at bottom edge, can only go right
else if (r === maze.length - 1) {
risk = safest[r][c] = maze[r][c] + solve({maze, point: [r, c + 1], safest, path}).risk;
}

// at right edge, can only go down
else if (c === maze[0].length - 1) {
risk = safest[r][c] = maze[r][c] + solve({maze, point: [r + 1, c], safest, path}).risk;
}

// somewhere else; pick safest of right or down
else {
const right = solve({maze, point: [r, c + 1], safest, path});
const down = solve({maze, point: [r + 1, c], safest, path});
risk = safest[r][c] = Math.min(right.risk, down.risk)
+ ((r === 0 && c === 0) ? 0 : maze[r][c]) // omit start; never entered
;
}
return {risk, safest, path};
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more