Skip to content

Instantly share code, notes, and snippets.

@tylshe
Created August 15, 2017 08:05
Show Gist options
  • Save tylshe/016f0dd8b5f9ae99bb67fbfab0617c7f to your computer and use it in GitHub Desktop.
Save tylshe/016f0dd8b5f9ae99bb67fbfab0617c7f to your computer and use it in GitHub Desktop.
let isSolvable = (matrix, startPoint, endPoint) => {
let nextPoints = isSolvable.getNextPoints(matrix, startPoint);
for (let i=0; i < nextPoints.length; i++) {
if (nextPoints[i].join(' ') === endPoint.join(' ')) {
isSolvable.status = true;
break;
} else {
isSolvable(matrix, nextPoints[i], endPoint);
}
}
return isSolvable.status;
};
isSolvable.getNextPoints = (matrix, startPoint) => {
isSolvable.history.push(startPoint.join(' '));
return isSolvable.nextPoints.map(delta => {
return [startPoint[0] + delta[0], startPoint[1] + delta[1]];
}).filter(nextPoint => {
return matrix[nextPoint[0]]
&& matrix[nextPoint[0]][nextPoint[1]] === 1;
}).filter(nextPoint => {
return isSolvable.history.indexOf(nextPoint.join(' ')) === -1;
});
};
isSolvable.nextPoints = [
[0,1],
[0,-1],
[-1,0],
[1,0]
];
isSolvable.history = [];
isSolvable.status = false;
isSolvable.clear = () => {
isSolvable.history = [];
isSolvable.status = false;
};
let matrix = [
[0,1,0,0,0,0],
[1,1,1,1,0,0],
[0,0,0,1,0,0]
];
let matrix2 = [
[0,1,0,0,0,0],
[1,1,1,1,1,1],
[0,0,0,1,0,0],
[1,1,1,1,1,1],
[1,0,0,1,0,0],
[1,1,0,1,0,0]
];
console.log(isSolvable(matrix, [1,0], [2,3]));
isSolvable.clear();
console.log(isSolvable(matrix, [1,0], [1,3]));
isSolvable.clear();
console.log(isSolvable(matrix, [1,0], [1,4]));
isSolvable.clear();
console.log(isSolvable(matrix2, [0,1], [5,1]));
isSolvable.clear();
console.log(isSolvable(matrix2, [2,4], [4,1]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment