MAP = `
#################
# & #
## ##############
# #
# ##### ### ####
# #
######## ########
# @ #
#################
`.split('\n').slice(1,-1);
DIRS = [
[0, 1], // right
[1, 0], // down
[-1, 0], // left
[0, -1], // up
];
function move([i, j], [di, dj]) {
return [i + di, j + dj];
}
on = ([i, j], [i2, j2]) =>
i == i2 && j == j2
char = ([i, j]) => MAP[i][j];
isWall = (p) => char(p) == "#";
function findPath(origin, dest) {
let found = false;
let visited = {};
const isWall = (p) => char(p) == "#";
const isDest = (p) => on(p, dest);
const isOrigin = (p) => on(p, origin);
function visit(current, prev) {
if (found) return;
visited[current] = prev;
if (isDest(current)) {
found = true;
return;
}
for (let dir of DIRS) {
let next = move(current, dir);
if (isWall(next)) continue;
if (visited[next]) continue;
visit(next, current);
}
}
function assemblePath(visited) {
let p = dest;
const res = [p];
while ((p = visited[p])) {
if (isOrigin(p)) break;
res.push(p);
}
return res.reverse();
}
visit(origin, null);
return assemblePath(visited);
}
findPath([7,10],[1,5])
findPath([7,10],[3,15])
function findPathL(origin, dest) {
let found = false;
let visited = {};
const isDest = (p) => on(p, dest);
const isOrigin = (p) => on(p, origin);
let stack = [[origin, null]];
let current, prev;
while (([current, prev] = stack.pop())) {
visited[current] = prev;
if (isDest(current)) break;
for (let dir of [...DIRS].reverse()) {
let next = move(current, dir);
if (isWall(next)) continue;
if (visited[next]) continue;
stack.push([next, current]);
}
}
function assemblePath(visited) {
let p = dest;
const res = [p];
while ((p = visited[p])) {
if (isOrigin(p)) break;
res.push(p);
}
return res;
}
return assemblePath(visited).reverse();
}
findPathL([7,10],[1,5])
DIRS2 = [
[0, -1], // left
[-1, 0], // up
[0, 1], // right
[1, 0], // down
];
function findPathD(origin, dest, DIRS) {
let found = false;
let visited = {};
const isDest = (p) => on(p, dest);
const isOrigin = (p) => on(p, origin);
function visit(current, prev) {
if (found) return;
visited[current] = prev;
if (isDest(current)) {
found = true;
return;
}
for (let dir of DIRS) {
let next = move(current, dir);
if (isWall(next)) continue;
if (visited[next]) continue;
visit(next, current);
}
}
function assemblePath(visited) {
let p = dest;
const res = [p];
while ((p = visited[p])) {
if (isOrigin(p)) break;
res.push(p);
}
return res;
}
visit(origin, null);
return assemblePath(visited).reverse();
}
findPathD([7,10],[1,5], DIRS2)
findPathD([7,10], [3,15], DIRS2)
function findPathA(origin, dest) {
let visited = {};
const isDest = (p) => on(p, dest);
const isOrigin = (p) => on(p, origin);
const paths = []
function visit(current) {
if (isDest(current)) {
paths.push(assemblePath(visited))
return;
}
for (let dir of DIRS) {
let next = move(current, dir);
if (isWall(next)) continue;
if (visited[next]) continue;
visited[next] = current;
visit(next);
visited[next] = null;
}
}
function assemblePath(visited) {
let p = dest;
const res = [p];
while ((p = visited[p])) {
if (isOrigin(p)) break;
res.push(p);
}
return res.reverse();
}
visited[origin] = true;
visit(origin);
return paths;
}
findPathA([7,10], [7,5])
findPathA([7,10], [1,5])
findPathA([7,10], [3,15])
function findPathM(origin, dest, MAP) {
let visited = {};
const char = ([i, j]) => MAP[i][j];
const isWall = (p) => char(p) == "#";
const isDest = (p) => on(p, dest);
const isOrigin = (p) => on(p, origin);
const paths = []
function visit(current) {
if (isDest(current)) {
paths.push(assemblePath(visited))
return;
}
for (let dir of DIRS) {
let next = move(current, dir);
if (isWall(next)) continue;
if (visited[next]) continue;
visited[next] = current;
visit(next, current);
visited[next] = null;
}
}
function assemblePath(visited) {
let p = dest;
const res = [p];
while ((p = visited[p])) {
if (isOrigin(p)) break;
res.push(p);
}
return res.reverse();
}
visited[origin] = true;
visit(origin, null);
return paths;
}
MAP2 = `
#####
#& #
# #
# @#
#####
`.split("\n").slice(1, -1);
findPathM([3,3],[1,1],MAP2)
MAP3 = `
#################
#& #
# @#
#################
`.split("\n").slice(1, -1);
findPathM([2,15],[1,1],MAP3)
MAP4 = `
#########
#& #
# #
# @ #
# #
# #1
#########
`.split("\n").slice(1, -1);
findPathM([3,4],[1,1],MAP4)
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.