Skip to content

Commit 6bd984f

Browse files
marijnhmarijnh
committed
Add supporting files for Chapter 22
1 parent d73d94a commit 6bd984f

File tree

6 files changed

+263
-46
lines changed

6 files changed

+263
-46
lines changed

‎code/draw_layout.js‎

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
// The familiar Vec type.
2+
3+
class Vec {
4+
constructor(x, y) {
5+
this.x = x; this.y = y;
6+
}
7+
plus(other) {
8+
return new Vec(this.x + other.x, this.y + other.y);
9+
}
10+
minus(other) {
11+
return new Vec(this.x - other.x, this.y - other.y);
12+
}
13+
times(factor) {
14+
return new Vec(this.x * factor, this.y * factor);
15+
}
16+
get length() {
17+
return Math.sqrt(this.x * this.x + this.y * this.y);
18+
}
19+
}
20+
21+
// Since we will want to inspect the layouts our code produces, let's
22+
// first write code to draw a graph onto a canvas. Since we don't know
23+
// in advance how big the graph is, the `Scale` object computes a
24+
// scale and offset so that all nodes fit onto the given canvas.
25+
26+
const nodeSize = 8;
27+
28+
function drawGraph(graph) {
29+
let canvas = document.querySelector("canvas");
30+
if (!canvas) {
31+
canvas = document.body.appendChild(document.createElement("canvas"));
32+
canvas.width = canvas.height = 400;
33+
}
34+
let cx = canvas.getContext("2d");
35+
36+
cx.clearRect(0, 0, canvas.width, canvas.height);
37+
let scale = new Scale(graph, canvas.width, canvas.height);
38+
39+
// Draw the edges.
40+
cx.strokeStyle = "orange";
41+
cx.lineWidth = 3;
42+
for (let i = 0; i < graph.length; i++) {
43+
let origin = graph[i];
44+
for (let target of origin.edges) {
45+
if (graph.indexOf(target) <= i) continue;
46+
cx.beginPath();
47+
cx.moveTo(scale.x(origin.pos.x), scale.y(origin.pos.y));
48+
cx.lineTo(scale.x(target.pos.x), scale.y(target.pos.y));
49+
cx.stroke();
50+
}
51+
}
52+
53+
// Draw the nodes.
54+
cx.fillStyle = "purple";
55+
for (let node of graph) {
56+
cx.beginPath();
57+
cx.arc(scale.x(node.pos.x), scale.y(node.pos.y), nodeSize, 0, 7);
58+
cx.fill();
59+
}
60+
}
61+
62+
// The function starts by drawing the edges, so that they appear
63+
// behind the nodes. Since the nodes on _both_ side of an edge refer
64+
// to each other, and we don't want to draw every edge twice, edges
65+
// are only drawn then the target comes _after_ the current node in
66+
// the `graph` array.
67+
68+
// When the edges have been drawn, the nodes are drawn on top of them
69+
// as purple discs. Remember that the last argument to `arc` gives the
70+
// rotation, and we have to pass something bigger than 2π to get a
71+
// full circle.
72+
73+
// Finding a scale at which to draw the graph is done by finding the
74+
// top left and bottom right corners of the area taken up by the
75+
// nodes. The offset at which nodes are drawn is based on the top left
76+
// corner, and the scale is based on the size of the canvas divided by
77+
// the distance between those corners. The function reserves space
78+
// along the sides of the canvas based on the `nodeSize` variable, so
79+
// that the circles drawn around nodes’ center points don't get cut off.
80+
81+
class Scale {
82+
constructor(graph, width, height) {
83+
let xs = graph.map(node => node.pos.x);
84+
let ys = graph.map(node => node.pos.y);
85+
let minX = Math.min(...xs);
86+
let minY = Math.min(...ys);
87+
let maxX = Math.max(...xs);
88+
let maxY = Math.max(...ys);
89+
90+
this.offsetX = minX; this.offsetY = minY;
91+
this.scaleX = (width - 2 * nodeSize) / (maxX - minX);
92+
this.scaleY = (height - 2 * nodeSize) / (maxY - minY);
93+
}
94+
95+
// The `x` and `y` methods convert from graph coordinates into
96+
// canvas coordinates.
97+
x(x) {
98+
return this.scaleX * (x - this.offsetX) + nodeSize;
99+
}
100+
y(y) {
101+
return this.scaleY * (y - this.offsetY) + nodeSize;
102+
}
103+
}

‎code/solutions/22_1_pathfinding.js‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
function findPath(a, b) {
2+
let work = [[a]];
3+
for (let path of work) {
4+
let end = path[path.length - 1];
5+
if (end == b) return path;
6+
for (let next of end.edges) {
7+
if (!work.some(path => path[path.length - 1] == next)) {
8+
work.push(path.concat([next]));
9+
}
10+
}
11+
}
12+
}
13+
14+
let graph = treeGraph(4, 4);
15+
let root = graph[0], leaf = graph[graph.length - 1];
16+
console.log(findPath(root, leaf).length);
17+
// → 4
18+
19+
leaf.connect(root);
20+
console.log(findPath(root, leaf).length);
21+
// → 2

‎code/solutions/22_2_timing.js‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
function findPath(a, b) {
2+
let work = [[a]];
3+
for (let path of work) {
4+
let end = path[path.length - 1];
5+
if (end == b) return path;
6+
for (let next of end.edges) {
7+
if (!work.some(path => path[path.length - 1] == next)) {
8+
work.push(path.concat([next]));
9+
}
10+
}
11+
}
12+
}
13+
14+
function time(findPath) {
15+
let graph = treeGraph(6, 6);
16+
let startTime = Date.now();
17+
let result = findPath(graph[0], graph[graph.length - 1]);
18+
console.log(`Path with length ${result.length} found in ${Date.now() - startTime}ms`);
19+
}
20+
time(findPath);

‎code/solutions/22_3_optimizing.js‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
function time(findPath) {
2+
let graph = treeGraph(6, 6);
3+
let startTime = Date.now();
4+
let result = findPath(graph[0], graph[graph.length - 1]);
5+
console.log(`Path with length ${result.length} found in ${Date.now() - startTime}ms`);
6+
}
7+
8+
function findPath_set(a, b) {
9+
let work = [[a]];
10+
let reached = new Set([a]);
11+
for (let path of work) {
12+
let end = path[path.length - 1];
13+
if (end == b) return path;
14+
for (let next of end.edges) {
15+
if (!reached.has(next)) {
16+
reached.add(next);
17+
work.push(path.concat([next]));
18+
}
19+
}
20+
}
21+
}
22+
23+
time(findPath_set);
24+
25+
function pathToArray(path) {
26+
let result = [];
27+
for (; path; path = path.via) result.unshift(path.at);
28+
return result;
29+
}
30+
31+
function findPath_list(a, b) {
32+
let work = [{at: a, via: null}];
33+
let reached = new Set([a]);
34+
for (let path of work) {
35+
if (path.at == b) return pathToArray(path);
36+
for (let next of path.at.edges) {
37+
if (!reached.has(next)) {
38+
reached.add(next);
39+
work.push({at: next, via: path});
40+
}
41+
}
42+
}
43+
}
44+
45+
time(findPath_list);

‎src/chapter_info.js‎

Lines changed: 71 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -3,53 +3,52 @@
33
// together with the solution code.
44

55
const PJSON = require("./pseudo_json")
6-
var fs = require("fs");
6+
let fs = require("fs");
77

8-
var output = [], failed = false;
8+
let output = [], failed = false;
99

10-
var allSolutions = fs.readdirSync("code/solutions/").filter(function(file) { return !/^2[012]/.test(file); });
10+
let allSolutions = fs.readdirSync("code/solutions/").filter(file => !/^2[012]/.test(file));
1111

12-
var dir = fs.readdirSync(".");
13-
dir.sort();
14-
dir.forEach(function(file) {
15-
var match = /^((\d+).*).md$/.exec(file), chapNum = match && match[2];
16-
if (!match) return;
17-
var text = fs.readFileSync(file, "utf8");
12+
for (let file of fs.readdirSync(".").sort()) {
13+
let match = /^((\d+).*).md$/.exec(file), chapNum = match && match[2];
14+
if (!match || chapNum == 22) continue;
15+
let text = fs.readFileSync(file, "utf8");
1816

1917
let meta = (/{{meta (.*)}}/.exec(text) || {1: "{}"})[1]
20-
var includes = /\bload_files: (\[.*?\])/.exec(meta)
18+
let includes = /\bload_files: (\[.*?\])/.exec(meta)
2119
if (includes) includes = JSON.parse(includes[1]);
22-
var chapter = {number: +chapNum,
20+
let chapter = {number: +chapNum,
2321
id: match[1],
2422
title: text.match(/(?:^|\n)# (.*?)\n/)[1],
2523
start_code: getStartCode(text, includes),
2624
exercises: [],
2725
include: includes};
28-
var zip = chapterZipFile(text, chapter);
29-
var extraLinks = meta.match(/\bcode_links: (\[.*?\])/);
26+
let zip = chapterZipFile(text, chapter);
27+
let extraLinks = meta.match(/\bcode_links: (\[.*?\])/);
3028
if (extraLinks) extraLinks = JSON.parse(extraLinks[1]);
3129
if (extraLinks || zip)
3230
chapter.links = (zip ? [zip] : []).concat(extraLinks || []);
3331

34-
var exerciseSection = text.indexOf("\n## Exercises\n");
35-
var exerciseBlock = exerciseSection >= 0 ? text.slice(exerciseSection) : "";
36-
var header = /\n### (.*?)\n/g, nextHeader = /\n##+ \w/g;
37-
var num = 1;
32+
let exerciseSection = text.indexOf("\n## Exercises\n");
33+
let exerciseBlock = exerciseSection >= 0 ? text.slice(exerciseSection) : "";
34+
let header = /\n### (.*?)\n/g, nextHeader = /\n##+ \w/g;
35+
let num = 1;
3836
while (match = header.exec(exerciseBlock)) {
3937
nextHeader.lastIndex = header.lastIndex
4038
let foundNext = nextHeader.exec(exerciseBlock)
41-
var nextsection = foundNext ? foundNext.index : -1
42-
for (var pos = header.lastIndex;;) {
43-
var ifdef = exerciseBlock.indexOf("{{if interactive", pos);
39+
let nextsection = foundNext ? foundNext.index : -1
40+
for (let pos = header.lastIndex;;) {
41+
let ifdef = exerciseBlock.indexOf("{{if interactive", pos);
4442
if (ifdef == -1 || nextsection > 0 && nextsection < ifdef) break;
45-
var indef = exerciseBlock.slice(pos = ifdef + 15, exerciseBlock.indexOf("if}}", ifdef));
46-
var sourceBlock = indef.match(/```(.*)\n([^]+?)\n```/);
43+
let indef = exerciseBlock.slice(pos = ifdef + 15, exerciseBlock.indexOf("if}}", ifdef));
44+
let sourceBlock = indef.match(/```(.*)\n([^]+?)\n```/);
4745
if (!sourceBlock || sourceBlock[1].indexOf("null") > -1) continue;
48-
var type = sourceBlock[1].indexOf("html") > -1 ? "html" : "js";
49-
var file = chapNum + "_" + num + "_" + match[1].toLowerCase().replace(/[^\-\s\w]/g, "").replace(/\s/g, "_") + "." + type;
46+
let type = sourceBlock[1].indexOf("html") > -1 ? "html" : "js";
47+
let file = chapNum + "_" + num + "_" + match[1].toLowerCase().replace(/[^\-\s\w]/g, "").replace(/\s/g, "_") + "." + type;
48+
let solution, extra
5049
try {
51-
var solution = fs.readFileSync("code/solutions/" + file, "utf8");
52-
var extra = /^\s*<!doctype html>\s*(<base .*\n(<script src=.*\n)*)?/.exec(solution);
50+
solution = fs.readFileSync("code/solutions/" + file, "utf8");
51+
extra = /^\s*<!doctype html>\s*(<base .*\n(<script src=.*\n)*)?/.exec(solution);
5352
if (extra) solution = solution.slice(extra[0].length);
5453
allSolutions.splice(allSolutions.indexOf(file), 1);
5554
} catch(e) {
@@ -71,7 +70,7 @@ dir.forEach(function(file) {
7170
++num;
7271
}
7372

74-
var nodeInfo = "// Node exercises can not be ran in the browser,\n// but you can look at their solution here.\n";
73+
let nodeInfo = "// Node exercises can not be ran in the browser,\n// but you can look at their solution here.\n";
7574
if (chapter.number == 20) chapter.exercises = [
7675
{name: "Search tool",
7776
file: "code/solutions/20_1_search_tool.js",
@@ -113,6 +112,36 @@ dir.forEach(function(file) {
113112
];
114113

115114
output.push(chapter);
115+
}
116+
117+
output.push({
118+
title: "JavaScript and Performance",
119+
number: 22,
120+
start_code: "<!-- This chapter exists in the paper book, not in the online version -->\n\n<script>\n runLayout(forceDirected_simple, treeGraph(4, 4));\n</script>\n",
121+
include: ["code/draw_layout.js", "code/chapter/22_fast.js"],
122+
exercises: [
123+
{name: "Pathfinding",
124+
file: "code/solutions/22_1_pathfinding.js",
125+
number: 1,
126+
type: "js",
127+
code: "function findPath(a, b) {\n // Your code here...\n}\n\nlet graph = treeGraph(4, 4);\nlet root = graph[0], leaf = graph[graph.length - 1];\nconsole.log(findPath(root, leaf).length);\n// → 4\n\nleaf.connect(root);\nconsole.log(findPath(root, leaf).length);\n// → 2\n",
128+
solution: fs.readFileSync("code/solutions/22_1_pathfinding.js", "utf8")
129+
},
130+
{name: "Timing",
131+
file: "code/solutions/22_2_timing.js",
132+
number: 2,
133+
type: "js",
134+
code: "",
135+
solution: fs.readFileSync("code/solutions/22_2_timing.js", "utf8")
136+
},
137+
{name: "Optimizing",
138+
file: "code/solutions/22_3_optimizing.js",
139+
number: 3,
140+
type: "js",
141+
code: "",
142+
solution: fs.readFileSync("code/solutions/22_3_optimizing.js", "utf8")
143+
}
144+
]
116145
});
117146

118147
if (allSolutions.length) {
@@ -126,25 +155,23 @@ else
126155
process.exit(1);
127156

128157
function prepareHTML(code, include) {
129-
return "<!doctype html>\n" + (include || []).map(function(s) {
130-
return "<script src=\"" + s + "\"></script>\n";
131-
}).join("") + "\n" + code;
158+
return "<!doctype html>\n" + (include || []).map(s => "<script src=\"" + s + "\"></script>\n").join("") + "\n" + code;
132159
}
133160

134161
function guessType(code) {
135162
return /^[\s\w\n:]*</.test(code) ? "html" : "js";
136163
}
137164

138165
function getStartCode(text, includes) {
139-
var found = /\n```(.*?\bstartCode:.*)\n([^]*?\n)```/.exec(text);
166+
let found = /\n```(.*?\bstartCode:.*)\n([^]*?\n)```/.exec(text);
140167
if (!found) return ""
141168

142-
var snippet = found[2].replace(/(\n|^)\s*\/\/ →.*\n/g, "$1");
143-
var directive = String(PJSON.parse(found[1]).startCode), m;
169+
let snippet = found[2].replace(/(\n|^)\s*\/\/ →.*\n/g, "$1");
170+
let directive = String(PJSON.parse(found[1]).startCode), m;
144171
if (m = directive.match(/top_lines:\s*(\d+)/))
145172
snippet = snippet.split("\n").slice(0, Number(m[1])).join("\n") + "\n";
146173
if (m = directive.match(/bottom_lines:\s*(\d+)/)) {
147-
var lines = snippet.trimRight().split("\n");
174+
let lines = snippet.trimRight().split("\n");
148175
snippet = lines.slice(lines.length - Number(m[1])).join("\n") + "\n";
149176
}
150177
if (guessType(snippet) == "html")
@@ -154,28 +181,28 @@ function getStartCode(text, includes) {
154181
}
155182

156183
function chapterZipFile(text, chapter) {
157-
var spec = text.match(/\n:zip: (\S+)(?: include=(.*))?/);
184+
let spec = text.match(/\n:zip: (\S+)(?: include=(.*))?/);
158185
if (!spec) return null;
159186
if (!chapter.start_code) throw new Error("zip but no start code");
160-
var name = "code/chapter/" + chapter.id + ".zip";
161-
var files = (chapter.include || []).concat(spec[2] ? JSON.parse(spec[2]) : []);
162-
var exists = fs.existsSync(name) && fs.statSync(name).mtime;
163-
if (exists && files.every(function(file) { return fs.statSync("html/" + file).mtime < exists; }))
187+
let name = "code/chapter/" + chapter.id + ".zip";
188+
let files = (chapter.include || []).concat(spec[2] ? JSON.parse(spec[2]) : []);
189+
let exists = fs.existsSync(name) && fs.statSync(name).mtime;
190+
if (exists && files.every(file => fs.statSync("html/" + file).mtime < exists))
164191
return name;
165192

166-
var zip = new (require("jszip"));
167-
files.forEach(function(file) {
193+
let zip = new (require("jszip"));
194+
for (let file of files) {
168195
zip.file(chapter.id + "/" + file, fs.readFileSync("html/" + file));
169-
});
196+
}
170197
if (spec[1].indexOf("html") != -1) {
171-
var html = chapter.start_code;
198+
let html = chapter.start_code;
172199
if (guessType(html) != "html")
173200
html = prepareHTML("<body><script>\n" + html.trim() + "\n</script></body>", chapter.include);
174201
zip.file(chapter.id + "/index.html", html);
175202
}
176203
if (spec[1].indexOf("node") != -1) {
177204
zip.file(chapter.id + "/code/load.js", fs.readFileSync("code/load.js", "utf8"));
178-
var js = chapter.start_code;
205+
let js = chapter.start_code;
179206
if (chapter.include) js = "// load dependencies\nrequire(\"./code/load\")(" + chapter.include.map(JSON.stringify).join(", ") + ");\n\n" + js;
180207
zip.file(chapter.id + "/run_with_node.js", js);
181208
}

0 commit comments

Comments
 (0)