Published
Edited
Mar 12, 2019
1 fork
5 stars
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
viewof gridDisplay = {
const canvas = DOM.canvas(n*size, n*size);
const context = canvas.getContext("2d");
context.canvas.value = context;
return context.canvas;
}
Insert cell
config = ({
'size': 60,
'n': 10,
'step_time': 100,
'show_other_choices': false,
})
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
min_max_path_general_brute_force = {
mode
let min_max_path = [];
let min_max_path_choices = [];
for (let y = 0; y < n; y++) {
let row = [];
let choice_row = [];
min_max_path.push(row);
min_max_path_choices.push(choice_row);
for (let x = 0; x < n; x++) {
row.push(null);
choice_row.push(null);
}
}
function* min_max_path_recursive(y, x) {
if (y < 0 || x < 0 || y >=n || x >= n) {
return 1;
} else if (x == 0 && y == 0) {
min_max_path[y][x] = grid[y][x];
} else {
let choice_values = [];
for(let i = 0; i < move_choices.length; i++) {
let choice = move_choices[i];
let yp = y + choice.dy;
let xp = x + choice.dx;
min_max_path_choices[y][x] = {'choice': i, 'confirmed': false};
yield Promises.delay(config.step_time, {values: min_max_path, choices: min_max_path_choices});
let choice_value = yield* min_max_path_recursive(yp, xp);
min_max_path_choices[y][x] = null;
choice_values.push(choice_value);
};
let minMaxPrev = Math.min(...choice_values);
let choice_index = choice_values.indexOf(minMaxPrev);
if (minMaxPrev < 1) {
min_max_path_choices[y][x] = {'choice': choice_index, 'confirmed': true};
}
min_max_path[y][x] = Math.max(grid[y][x], minMaxPrev);
}
yield Promises.delay(config.step_time, {values: min_max_path, choices: min_max_path_choices});
return min_max_path[y][x];
}
yield* min_max_path_recursive(n-1, n-1)
}
Insert cell
Insert cell
function* explore(y, x, n, min_max_path) {
console.log("Calling:", y, x);
if (y < 0 || x < 0 || y >=n || x >= n) { // Out of bounds set to "max" value that will never be selected
return 1;
} else if (x == 0 && y == 0) { // Base case
min_max_path.values[y][x] = grid[y][x];
} else if (min_max_path.values[y][x] != null) { // Do not explore already-set values.
;
}else { // Explore
// Get value of each choice.
let choice_values = [];
let choice_states = move_choices.map(choice => ({'y': y + choice.dy, 'x': x + choice.dx}))
for(let i = 0; i < choice_states.length; i++) {
let choice_state = choice_states[i]
min_max_path.choices[y][x] = {'choice': i, 'confirmed': false};
yield Promises.delay(config.step_time, min_max_path);
let choice_value = yield* explore(choice_state.y, choice_state.x, n, min_max_path);
min_max_path.choices[y][x] = null;
choice_values.push(choice_value);
};
// Select optimal choice.
let minMaxPrev = Math.min(...choice_values);
let choice_index = choice_values.indexOf(minMaxPrev);
if (minMaxPrev < 1) {
min_max_path.choices[y][x] = {'choice': choice_index, 'confirmed': true};
}
min_max_path.values[y][x] = Math.max(grid[y][x], minMaxPrev);
}
yield Promises.delay(config.step_time, min_max_path);
return min_max_path.values[y][x];
}
Insert cell
min_max_path_general_recursive = {
mode
let min_max_path = initialize_min_max_path(n);
yield* explore(n-1, n-1, n, min_max_path);
}
Insert cell
Insert cell
min_max_path_general_iterative = {
mode
let min_max_path = initialize_min_max_path(n)
for (let y = 0; y < n; y++) {
for (let x = 0; x < n; x++) {
yield* explore(y, x, n, min_max_path);
yield Promises.delay(config.step_time, {values: min_max_path.values, choices: min_max_path.choices});
}
}
}
Insert cell
Insert cell
function initialize_min_max_path(n) {
let min_max_path = {values: [], choices: []};
for (let y = 0; y < n; y++) {
let row = [];
let choice_row = [];
min_max_path.values.push(row);
min_max_path.choices.push(choice_row);
for (let x = 0; x < n; x++) {
row.push(null);
choice_row.push(null);
}
}
return min_max_path
}
Insert cell
Insert cell
tick = {
while (true) {
yield Promises.delay(1000);
}
}
Insert cell
function redrawGridDisplay(context, grid, clr, clear) {
if (clear) { context.clearRect(0, 0, n*size, n*size); }
const canvas = context.canvas;
function showGrid(grid){
for (let x = 0; x < grid.length; x++) {
let row = grid[x];
for (let y = 0; y < row.length; y++) {
let val = row[y];
if (val > 0) {
let square = new SquareDisplay(val, y, x);
square.render(context, clr);
}
}
}
}
showGrid(grid);
}
Insert cell
function redrawLineDisplay(context, lines, clr, clear) {
if (clear) { context.clearRect(0, 0, n*size, n*size); }
const canvas = context.canvas;
function showLines(lines){
for (let x = 0; x < lines.length; x++) {
let row = lines[x];
for (let y = 0; y < row.length; y++) {
let chosen = row[y];
if (chosen != null) {
let choice = move_choices[chosen.choice];
let confirmed = chosen.confirmed;
let line = new LineDisplay(y, x, choice.dx, choice.dy);
let color = confirmed ? clr : 'yellow';
line.render(context, color);
for (let i = 0; i < move_choices.length; i++) {
if (i != chosen && config.show_other_choices) {
let choice = move_choices[i];
let unchosen_line = new LineDisplay(y, x, choice.dx, choice.dy);
unchosen_line.render(context, 'yellow');
}
}
}
}
}
}
showLines(lines);
}
Insert cell
class LineDisplay {
constructor(y, x, dy, dx) {
this.dy = dy * size;
this.dx = dx * size;
this.y = y * size + 0.5 * size;
this.x = x * size + 0.5 * size;
}
render(context, clr) {
makeLine(this.y, this.x, this.dy, this.dx, context, size, clr, 1.0)
}
}

Insert cell
class SquareDisplay {
constructor(value, x, y) {
const ratio = 1.0;
this.value = value;
this.x = x;
this.y = y;
this.xOffset = this.x * size + (1.0 - ratio)/2.0 * size;
this.yOffset = this.y * size + (1.0 - ratio)/2.0 * size;
this.size = size * ratio;
this.width = size * ratio;
this.height = size * ratio;
}
render(context, clr) {
if (this.value == 0) { return; }
makeRect(this.xOffset, this.yOffset, context, this.size, clr, this.value*this.value);
}
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
move_choices = {
return movement_options[movement]
}
Insert cell
min_max_path_program = {
const options = {
'brute_force': min_max_path_general_brute_force,
'recursive': min_max_path_general_recursive,
'iterative': min_max_path_general_iterative,
}
return options[mode]
}
Insert cell
Insert cell

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.
Learn more