Dynamic Programming Notes / Philippe Rigovanov

Philippe Rigovanov

math & informatics teacher

Workspace

Public

Informatics

Edited

Dec 30, 2022

Fork of Dynamic Programming Notes

Informatics

ЕГЭ по Информатике. Вариант №01092023, 2023г. Составил Евгений Джобс.ЕГЭ по Информатике. Вариант №16012023, 2023г. Составил Марат Ишимов.Оптимизация перебора

Dynamic Programming Notes

viewof gridDisplay = {

const canvas = DOM.canvas(n*size, n*size);

const context = canvas.getContext("2d");

context.canvas.value = context;

return context.canvas;

}

config = ({

'size': 60,

'n': 10,

'step_time': 100,

'show_other_choices': false,

})

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)

}

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];

}

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);

}

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});

}

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

}

tick = {

while (true) {

yield Promises.delay(1000);

}

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);

}

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);

}

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)

}

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);

}

move_choices = {

return movement_options[movement]

}

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]

}

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