MAP=`
##########
# a b@ c #
##########
`.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
function findItems(origin) {
let visited = {};
let queue = [[origin, null]];
let items = [];
const isOrigin = (p) => on(p, origin);
const char = ([i, j]) => MAP[i][j];
const isWall = (p) => char(p) == "#";
const isItem = (p) => char(p) >= "a" && char(p) <= "z";
function assemblePath(dest) {
let p = dest;
const res = [p];
while ((p = visited[p])) {
if (isOrigin(p)) break;
res.push(p);
}
return res.reverse();
}
while (queue.length) {
let [current, parent] = queue.shift();
visited[current] = parent;
if (isItem(current)) {
let path = assemblePath(current);
items.push([char(current), current, path.length])
}
for (let dir of DIRS) {
let next = move(current, dir);
if (isWall(next)) continue;
if (visited[next]) continue;
queue.push([next, current]);
}
}
return items;
}
findItems([1, 5])
function findObjectsW(origin) {
let visited = {};
let queue = [[origin, null]];
let objects = [];
const isOrigin = (p) => on(p, origin);
const char = ([i, j]) => MAP[i][j];
const isWall = (p) => char(p) == "#";
const isObject = (p) => char(p) >= "a" && char(p) <= "z";
function assemblePath(dest) {
let p = dest;
const res = [p];
while ((p = visited[p])) {
if (isOrigin(p)) break;
res.push(p);
}
return res.reverse();
}
while (queue.length) {
let [current, parent] = queue.shift();
visited[current] = parent;
if (isObject(current)) {
let path = assemblePath(current);
objects.push([char(current), current, path.length])
continue
}
for (let dir of DIRS) {
let next = move(current, dir);
if (isWall(next)) continue;
if (visited[next]) continue;
queue.push([next, current]);
}
}
return objects;
}
findObjectsW([1,5])
findObjectsW([1, 4])
function findItemsN(origin, collected) {
let visited = {};
let queue = [[origin, null]];
let items = [];
const isOrigin = (p) => on(p, origin);
const char = ([i, j]) => MAP[i][j];
const isWall = (p) => char(p) == "#";
const isItem = (p) => {
const c = char(p)
return c >= "a" && c <= "z" && !collected.includes(c)
}
function assemblePath(dest) {
let p = dest;
const res = [p];
while ((p = visited[p])) {
if (isOrigin(p)) break;
res.push(p);
}
return res.reverse();
}
while (queue.length) {
let [current, parent] = queue.shift();
visited[current] = parent;
if (isItem(current)) {
let path = assemblePath(current);
items.push([char(current), current, path.length])
continue
}
for (let dir of DIRS) {
let next = move(current, dir);
if (isWall(next)) continue;
if (visited[next]) continue;
queue.push([next, current]);
}
}
return items;
}
findItemsN([1, 4], 'b')
findItemsN([1, 2], 'ba')
findItemsN([1, 7], 'bac')
findItemsN([1, 5], '')
findItemsN([1, 7], 'c')
findItemsN([1, 4], 'cb')
findItemsN([1, 2], 'cba')
function findItemsM(map, origin, collected) {
let visited = {};
let queue = [[origin, null]];
let objects = [];
const isOrigin = (p) => on(p, origin);
const char = ([i, j]) => map[i][j];
const isWall = (p) => char(p) == "#";
const isItem = (p) => {
const c = char(p)
return c >= "a" && c <= "z" && !collected.includes(c)
}
function assemblePath(dest) {
let p = dest;
const res = [p];
while ((p = visited[p])) {
if (isOrigin(p)) break;
res.push(p);
}
return res.reverse();
}
while (queue.length) {
let [current, parent] = queue.shift();
visited[current] = parent;
if (isItem(current)) {
let path = assemblePath(current);
objects.push([char(current), current, path.length])
continue
}
for (let dir of DIRS) {
let next = move(current, dir);
if (isWall(next)) continue;
if (visited[next]) continue;
queue.push([next, current]);
}
}
return objects;
}
function findMinRoute(map, origin) {
let minCollected, minDist = Infinity
function visit(current, distance, collected) {
const items = findItemsM(map, current, collected)
if (items.length == 0) {
if (distance < minDist) {
minDist = distance
minCollected = collected
}
return
}
for (let [name, pos, steps] of items) {
visit(pos, distance + steps, collected + name)
}
}
visit(origin, 0, '')
return [minDist, minCollected]
}
findMinRoute(MAP, [1, 5])
MAP2 = `
##################
# a @ d #
### ##############
# e b c #
##################
`.split('\n').slice(1,-1)
findMinRoute(MAP2, [1, 5])
MAP3 = `
########################
# @a b d#
### # # ## ### ########
#h# # # ## ### ######e#
# #g#f## c# #
########################
`.split("\n")
.slice(1, -1);
findMinRoute(MAP3, [1, 5])
function findMinRouteR(map, origin) {
function minDistance(collected, current) {
const items = findItemsM(map, current, collected)
if (items.length == 0) return 0
let distances = []
for (let [item, itemPos, itemSteps] of items) {
distances.push(itemSteps + minDistance(collected + item, itemPos))
}
return Math.min(...distances)
}
return minDistance('', origin)
}
findMinRouteR(MAP, [1, 5])
findMinRouteR(MAP2, [1, 5])
findMinRouteR(MAP3, [1, 5])
function key(str) {
return str.slice(0, -1).split('').sort().join('') + str[str.length - 1]
}
function findMinRouteM(map, start) {
const m = {}
function minDistance(collected, current) {
const items = findItemsM(map, current, collected)
if (items.length == 0) return 0
const k = key(collected)
if (k in m) return m[k]
let distances = []
for (let [item, itemPos, itemDist] of items) {
distances.push(itemDist +
minDistance(collected + item, itemPos)
)
}
m[k] = Math.min(...distances)
return m[k]
}
return minDistance('', start)
}
findMinRouteM(MAP, [1, 5])
findMinRouteM(MAP2, [1, 5])
findMinRouteM(MAP3, [1, 5])
MAP4 = `
#################
#i. ..c...e.. .p#
########.########
#j. ..b...f.. .o#
########@########
#k. ..a...g.. .n#
########.########
#l. ..d...h.. .m#
#################
`.split('\n').slice(1,-1)
findMinRouteM(MAP4, [4, 8])
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.
