tree = (function() {
return {
"a": {
"b": {
"e": {},
"f": {
"j": {
"o": {},
"p": {}
},
"k": {
"q": {
"w": {}
}
}
},
"g": {}
},
"c": {},
"d": {
"h": {
"l": {
"r": {},
"s": {},
"t": {
"x": {},
"y": {}
}
},
"m": {}
},
"i": {
"n": {
"u": {},
"v": {
"z": {}
}
}
}
}
}
}
})()
function traversePre() {
const visited = []
function visit(name, obj) {
visited.push(name)
for (let key in obj) {
visit(key, obj[key])
}
}
visit('a', tree.a)
return visited.join('');
}
traversePre()
traversePre().length
function traversePost() {
const visited = []
function visit(name, obj) {
for (let key in obj) {
visit(key, obj[key])
}
visited.push(name)
}
visit('a', tree.a)
return visited.join('');
}
traversePost()
traversePost().length
function traversePreReverse() {
const visited = []
function visit(name, object) {
visited.push(name)
const children = Object.keys(object).reverse()
for (let key of children) {
visit(key, object[key])
}
}
visit('a', tree.a)
return visited.join('');
}
traversePreReverse()
function traversePostReverse() {
const visited = []
function visit(name, object) {
const children = Object.keys(object).reverse()
for (let key of children) {
visit(key, object[key])
}
visited.push(name)
}
visit('a', tree.a)
return visited.join('');
}
traversePostReverse()
function traverseL() {
const visited = []
const stack = [['a', tree.a]]
let current
while (current = stack.pop()) {
const [name, obj] = current
visited.push(name)
for (let key in obj) {
stack.push([key, obj[key]])
}
}
return visited.join('');
}
traverseL(tree)
function traverseR() {
const visited = []
const stack = [['a', tree.a]]
let current
while (current = stack.pop()) {
const [name, obj] = current
visited.push(name)
const children = Object.keys(obj).reverse()
for (let key of children) {
stack.push([key, obj[key]])
}
}
return visited.join('');
}
traverseR(tree)
function traverseBreadth() {
const visited = []
const queue = [['a', tree.a]]
let current
while (current = queue.shift()) {
const [name, obj] = current
visited.push(name)
for (let key in obj) {
queue.push([key, obj[key]])
}
}
return visited.join('');
}
traverseBreadth(tree)
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 findPathB(origin, dest) {
let found = false;
let visited = {};
const isDest = (p) => on(p, dest);
const isOrigin = (p) => on(p, origin);
let queue = [[origin, null]];
let current, prev;
while (([current, prev] = queue.shift())) {
visited[current] = prev;
if (isDest(current)) break;
for (let dir of DIRS) {
let next = move(current, dir);
if (isWall(next)) continue;
if (visited[next]) continue;
queue.push([next, current]);
}
}
function assemblePath() {
let p = dest;
const res = [p];
while ((p = visited[p])) {
if (isOrigin(p)) break;
res.push(p);
}
return res;
}
return assemblePath().reverse();
}
findPathB([7,10], [1,5])
findPathB([7,10], [3,15])
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.
