Dependencies in a dynamic-programming problem / Philippe Rigovanov

Philippe Rigovanov

math & informatics teacher

Workspace

Public

Informatics

Edited

Dec 29, 2022

Fork of Dependencies in a dynamic-programming problem

2 stars

Informatics

ЕГЭ по Информатике. Вариант №01092023, 2023г. Составил Евгений Джобс.ЕГЭ по Информатике. Вариант №16012023, 2023г. Составил Марат Ишимов.Оптимизация перебора Dynamic Programming Notes Automatic Recursive Memoization Problem with recursion and memoization Орграф для задачи №13 ЕГЭ по информатике.

Dependencies in a dynamic-programming problem

canvas = html`<canvas id="myCanvas" width="900", height="900" style="border:1px solid #000000; background-color: #E5E7EB;"></canvas>`

viewof problemType = Inputs.radio(["word_break", "knapsack", "edit_distance"], {label: "problem type"})

viewof durationPerCellInSecs = Inputs.range([0.2, 0.8], {label: "Duration per cell in seconds", step: 0.2})

numRows = 10

numCols = 10

glm = import('https://unpkg.com/gl-matrix@3.4.3/esm/index.js?module')

vec2 = glm.vec2

vec3 = glm.vec3

mat3 = glm.mat3

mathjs = require('mathjs@11.5.0/lib/browser/math.js')

pixelsPerMillimeter = 10;

WindowParams = {canvas;

class WindowParams {

constructor() {

this.canvasElement = document.getElementById("myCanvas");

this.canvasWidth = this.canvasElement.width;

this.canvasHeight = this.canvasElement.height;

console.log('width, height =', this.canvasWidth, this.canvasHeight);

this.canvasCenter = glm.vec2.fromValues(

this.canvasWidth / 2,

this.canvasHeight / 2

);

this.pixels_per_meter = pixelsPerMillimeter * 1000;

// World x and y axes wrt canvas canvas coordinates. Don't know why we're

// keeping these.

this.worldXRelCanvas = glm.vec2.fromValues(this.pixels_per_meter, 0.0);

this.worldYRelCanvas = glm.vec2.fromValues(0.0, -this.pixels_per_meter);

this.canvasFromWorld = glm.mat3.fromScaling(

glm.mat3.create(),

glm.vec2.fromValues(this.pixels_per_meter, -this.pixels_per_meter)

);

this.canvasFromWorld = glm.mat3.mul(

glm.mat3.create(),

glm.mat3.fromTranslation(glm.mat3.create(), this.canvasCenter),

this.canvasFromWorld

);

this.canvasFromWorld = mat3.rotate(this.canvasFromWorld, this.canvasFromWorld, Math.PI / 50);

console.log("canvasFromWorld =", this.canvasFromWorld);

this.canvas = this.canvasElement.getContext("2d");

}

clearRect() {

this.canvas.clearRect(0, 0, this.canvasWidth, this.canvasHeight);

}

xPointToCanvas(out, point) {

out = glm.vec2.transformMat3(out, point, this.canvasFromWorld);

return out;

}

lengthToCanvas(l) {

return this.pixels_per_meter * l;

}

canvasBoundsInWorldUnits() {

const toWorld = glm.mat3.invert(glm.mat3.create(), this.canvasFromWorld);

console.log('worldFromCanvas =', toWorld);

const min = glm.vec2.transformMat3(

glm.vec2.create(),

glm.vec2.fromValues(0, 0),

toWorld

);

const max = glm.vec2.transformMat3(

glm.vec2.create(),

glm.vec2.fromValues(this.canvasWidth, this.canvasHeight),

toWorld

);

return { min, max };

}

moveTo(p) {

const canvasPoint = this.xPointToCanvas(glm.vec2.create(), p);

this.canvas.moveTo(canvasPoint[0], canvasPoint[1]);

}

lineTo(p) {

const canvasPoint = this.xPointToCanvas(glm.vec2.create(), p);

this.canvas.lineTo(canvasPoint[0], canvasPoint[1]);

}

rect(topLeft, widthAlongX, heightAlongY) {

let wh = glm.vec3.fromValues(widthAlongX, -heightAlongY, 0);

wh = glm.vec3.transformMat3(wh, wh, this.canvasFromWorld);

topLeft = this.xPointToCanvas(glm.vec2.create(), topLeft);

// console.log('fill coords =', topLeft[0], topLeft[1], wh[0], wh[1]);

this.canvas.rect(topLeft[0], topLeft[1], wh[0], wh[1]);

}

bezierCurveTo(curvePoints) {

let points = curvePoints.map(p => this.xPointToCanvas(glm.vec2.create(), p));

// TODO: remove moveTo, be same as canvas' API

this.canvas.moveTo(points[0][0], points[0][1]); // starting end point

this.canvas.bezierCurveTo(

// cp 1

points[1][0],

points[1][1],

// cp 2

points[2][0],

points[2][1],

// ending end point

points[3][0],

points[3][1]

);

}

return WindowParams;

}

// TODO: use a base-class to hold the common params for all the interpolators.

// Ideal use-case for a bit of OOP right here :)

class LinearInterpolator {

timestampStart;

timestampEnd;

maxT;

onComplete;

onCompleteCalled;

// Create a new Interpolator given the start and end timestamps. The unit of

// the timestamps does not matter.

constructor(timestampStart, timestampEnd, maxT = 1) {

this.timestampStart = timestampStart;

this.timestampEnd = timestampEnd;

this.maxT = maxT;

this.onComplete = null;

this.onCompleteCalled = false;

}

// Return the interpolated parameter which we call "t" at the current time

t(currentTime) {

if (currentTime < this.timestampStart) {

return [0, false];

}

if (currentTime > this.timestampEnd) {

if (!this.onCompleteCalled && !!this.onComplete) {

this.onCompleteCalled = true;

this.onComplete();

}

return [this.maxT, true];

}

const factor = (currentTime - this.timestampStart) / (this.timestampEnd - this.timestampStart);

return [Math.min(this.maxT, Math.max(0, factor)), false];

}

setOnComplete(onCompleteCallback) {

this.onComplete = onCompleteCallback;

}

class StepInterpolator {

timestampStart;

timestampEnd;

maxT;

onComplete;

onCompleteCalled;

constructor(timestampStart, timestampEnd, maxT = 1) {

this.timestampStart = timestampStart;

this.timestampEnd = timestampEnd;

this.maxT = maxT;

this.onComplete = null;

this.onCompleteCalled = false;

}

t(currentTime) {

if (currentTime < this.timestampStart) {

return [0, false];

}

if (currentTime > this.timestampEnd) {

if (!this.onCompleteCalled && !!this.onComplete) {

this.onCompleteCalled = true;

this.onComplete();

}

return [this.maxT, true];

}

return [0, false];

}

setOnComplete(onCompleteCallback) {

this.onComplete = onCompleteCallback;

}

class LinearRoundtripInterpolator {

// Note that timestampEnd is the end time of the forward interpolation only.

// So total time is twice that of taken by forward interpolation.

constructor(timestampForwardStart, timestampForwardEnd, timestampBackwardStart, timestampBackwardEnd, oscillate = false, maxT = 1) {

this.timestampForwardStart = timestampForwardStart;

this.timestampForwardEnd = timestampForwardEnd;

this.timestampBackwardStart = timestampBackwardStart;

this.timestampBackwardEnd = timestampBackwardEnd;

this.maxT = maxT;

this.oscillate = oscillate;

this.totalPeriod = timestampBackwardEnd - timestampForwardStart;

this.onForwardCompleteCalled = false;

this.onBackwardCompleteCalled = false;

this.onForwardComplete = null;

this.onBackwardComplete = null;

}

setOnForwardComplete(onForwardCompleteCallback) {

this.onForwardComplete = onForwardCompleteCallback;

}

setOnBackwardComplete(onBackwardCompleteCallback) {

this.onBackwardComplete = onBackwardCompleteCallback;

}

forwardDuration() {

return this.timestampForwardEnd - this.timestampForwardStart;

}

backwardDuration() {

return this.timestampBackwardEnd - this.timestampBackwardStart;

}

t(currentTime) {

// Find the period number

// TODO: If you want an oscillating interpolator, the constructor api should be relative also, better to think that way.

if (this.oscillate) {

const durationSinceStart = currentTime - this.timestampForwardStart;

const numPeriods = durationSinceStart / this.totalPeriod;

currentTime = currentTime - (Math.floor(numPeriods) * this.totalPeriod + this.timestampForwardStart);

}

if (currentTime < this.timestampForwardStart) {

return [0, false];

}

if (currentTime <= this.timestampForwardEnd) {

const factor = (currentTime - this.timestampForwardStart) / this.forwardDuration();

return [Math.min(this.maxT, Math.max(0, factor)), false];

}

if (currentTime < this.timestampBackwardStart) {

if (!this.onForwardCompleteCalled && !!this.onForwardComplete) {

this.onForwardCompleteCalled = true;

this.onForwardComplete();

}

return [this.maxT, false];

}

if (currentTime <= this.timestampBackwardEnd) {

const factor = (currentTime - this.timestampBackwardStart) / this.backwardDuration();

return [Math.min(this.maxT, Math.max(0, 1 - factor)), false];

}

if (!this.onBackwardCompleteCalled && !!this.onBackwardComplete) {

this.onBackwardCompleteCalled = true;

this.onBackwardComplete();

}

return [0, true];

}

class OnCompleteCaller {

completed;

onComplete;

constructor(onCompleteCallback = null) {

this.onComplete = onCompleteCallback;

this.completed = false;

}

setOnComplete(onCompleteCallback) {

this.onComplete = onCompleteCallback;

}

setCompleted(extraMsg = '') {

if (!this.completed && !!this.onComplete) {

console.log('completed', extraMsg);

this.completed = true;

this.onComplete();

}

class InterpolatedLine extends OnCompleteCaller {

startPoint; // const

endPoint; // const

interpolator; // const

curEndPoint;

// startPoint: vec2, endPoint: vec2

constructor(interpolator, startPoint, endPoint) {

super();

this.drawableType = "line";

this.startPoint = glm.vec2.clone(startPoint);

this.endPoint = glm.vec2.clone(endPoint);

this.curEndPoint = glm.vec2.clone(endPoint);

this.interpolator = interpolator;

}

// currentTimestamp: number

// interpolator: LinearInterpolator

update(currentTimestamp) {

const [t, completed] = this.interpolator.t(currentTimestamp);

this.curEndPoint = glm.vec2.lerp(this.curEndPoint, this.startPoint, this.endPoint, t);

this.completed = completed;

}

// A very ad-hoc vec3 color interpolator, interpreted in the RGB-space. TBH,

// this should simply be a color info, the rect dimensions are kept here since I

// just want a place to keep them. Dirty, but idc atm.

class InterpolatedRectFiller extends OnCompleteCaller {

topLeft; // const

width; // const

height; // const

startColor; // const

endColor; // const

interpolator; // const

curColor;

constructor(interpolator, topLeft, width, height, startColor, endColor) {

super();

this.drawableType = "rect_fill";

this.topLeft = topLeft;

this.width = width;

this.height = height;

this.interpolator = interpolator;

this.startColor = startColor;

this.endColor = endColor;

this.curColor = glm.vec3.clone(this.startColor);

}

update(currentTimestamp) {

const [t, completed] = this.interpolator.t(currentTimestamp);

if (completed) {

this.setCompleted('rect filler');

this.curColor = glm.vec3.clone(this.endColor);

// console.log("reached completed", this.curColor);

return;

}

this.curColor = glm.vec3.lerp(this.curColor, this.startColor, this.endColor, t);

// if (this.interpolator.startTime <= currentTimestamp && currentTimestamp <= this.interpolator.endTime) {

// console.log("updated curColor to", this.curColor);

// }

}

class InterpolatedBezierCurve extends OnCompleteCaller {

originalPoints; // const

curTruncatedPoints;

arrowHeadLeft;

arrowHeadRight;

interpolator;

shouldDrawArrows;

// points is an array of vec2 of length 4

constructor(interpolator, points) {

super();

this.drawableType = "bezier_curve";

if (!Array.isArray(points)) {

throw `expected points to be an array but received: ${points}`

}

if (points.length !== 4) {

throw `expected points to have length 4 but received length: %{points.length}`

}

this.originalPoints = [...points];

this.curTruncatedPoints = [...points];

this.arrowHeadLeft = vec2.create();

this.arrowHeadRight = vec2.create();

this.cacheArrowHeads();

this.interpolator = interpolator;

this.shouldDrawArrows = false;

this.arrowSideLength = 1;

this.arrowSideAngle = Math.PI / 6;

}

update(currentTimestamp,) {

const [t, completed] = this.interpolator.t(currentTimestamp);

if (completed) {

this.setCompleted('bezier curve');

}

this.curTruncatedPoints = this._truncate(0, t);

if (this.shouldDrawArrows) {

this.cacheArrowHeads();

}

setShouldDrawArrows(b) {

this.shouldDrawArrows = b;

if (this.shouldDrawArrows) {

this.cacheArrowHeads();

}

static evaluate(cp, t) {

// (1 - t) ^ 3 P_0 + 3t.(1 - t) ^ 2 P_1 + 3t ^ 2.(1 - t) P_2 + t ^ 3 P_3

const oneMinusT = (1 - t)

const c0 = oneMinusT * oneMinusT * oneMinusT;

const c1 = 3 * t * oneMinusT * oneMinusT;

const c2 = 3 * t * t * oneMinusT;

const c3 = t * t * t;

// CONSIDER: can be optimized to use just one out parameter

const a = vec2.scale(vec2.create(), cp[0], c0);

const b = vec2.scale(vec2.create(), cp[1], c1);

const c = vec2.scale(vec2.create(), cp[2], c2);

const d = vec2.scale(vec2.create(), cp[3], c3);

let r = vec2.create();

r = vec2.add(r, a, b);

r = vec2.add(r, r, c);

r = vec2.add(r, r, d);

return r;

}

static evaluateTangent(cp, t) {

// (-3 + 6t + -3t ^ 2) P_0 + (3 - 12t + 9t ^ 2) P_1 + (6t - 9t ^ 2) P_2 + 3t ^ 2.P_3

const c0 = -3 + (6 * t) - 3 * (t * t);

const c1 = 3 - (12 * t) + 9 * (t * t);

const c2 = (6 * t) - 9 * (t * t);

const c3 = 3 * (t * t);

// CONSIDER: can be optimized to use just one out parameter

const a = vec2.scale(vec2.create(), cp[0], c0);

const b = vec2.scale(vec2.create(), cp[1], c1);

const c = vec2.scale(vec2.create(), cp[2], c2);

const d = vec2.scale(vec2.create(), cp[3], c3);

let r = vec2.create();

r = vec2.add(r, a, b);

r = vec2.add(r, r, c);

r = vec2.add(r, r, d);

return r;

}

cacheArrowHeads() {

// const tan0 = vec3.sub(out, this.curTruncatedPoints[1], this.curTruncatedPoints[0]);

let headTangent = vec2.sub(vec2.create(), this.curTruncatedPoints[3], this.curTruncatedPoints[2]);

headTangent = vec2.normalize(headTangent, headTangent);

headTangent = vec2.scale(headTangent, headTangent, this.arrowSideLength);

let pointAtHeadTangent = vec2.add(headTangent, this.curTruncatedPoints[3], headTangent);

this.arrowHeadLeft = vec2.rotate(this.arrowHeadLeft, pointAtHeadTangent, this.curTruncatedPoints[3], Math.PI - this.arrowSideAngle);

this.arrowHeadRight = vec2.rotate(this.arrowHeadRight, this.arrowHeadLeft, this.curTruncatedPoints[3], 2 * this.arrowSideAngle);

}

_truncate(tStart, tEnd) {

// Yeah I know my usecase will always make tStart = 0, but keeping it general.

const q0 = InterpolatedBezierCurve.evaluate(this.originalPoints, tStart);

const q3 = InterpolatedBezierCurve.evaluate(this.originalPoints, tEnd);

let tan0 = InterpolatedBezierCurve.evaluateTangent(this.originalPoints, tStart);

tan0 = vec2.scale(tan0, tan0, (tEnd - tStart) / 3);

let tan3 = InterpolatedBezierCurve.evaluateTangent(this.originalPoints, tEnd);

tan3 = vec2.scale(tan3, tan3, (tEnd - tStart) / 3);

const q1 = vec2.add(vec2.create(), q0, tan0);

const q2 = vec2.sub(vec2.create(), q3, tan3);

return [q0, q1, q2, q3];

}

// Returns the control points of a bezier curve that can also be represented by

// a parabola having the given startPoint, endPoint and peakLength. If

// peakLength is positivethen the parabola's peak is towards the direction

// perpendicular to the left of (endPoint - startPoint). If invertQ2 is true,

// this is no longer a parabola but a symmetric s-shaped bezier curve.

function parabolicBezierCurvePoints(startPoint, endPoint, peakLength, invertQ2 = false) {

let midPoint = glm.vec2.add(glm.vec2.create(), startPoint, endPoint);

midPoint = glm.vec2.scale(midPoint, midPoint, 0.5);

const startToEnd = glm.vec2.sub(glm.vec2.create(), endPoint, startPoint);

const distance = glm.vec2.length(startToEnd);

const lineDir = glm.vec2.normalize(glm.vec2.create(), startToEnd);

const normal = glm.vec2.fromValues(-lineDir[1], lineDir[0]);

const halfPeakLengthNormal = glm.vec2.scale(glm.vec2.create(), normal, peakLength / 2);

const q0 = glm.vec2.clone(startPoint);

const q3 = glm.vec2.clone(endPoint);

// q1 = (q0 + (distance/4) * lineDir) + ((peakLength / 2) * normal)

let q1 = glm.vec2.add(glm.vec2.create(),

q0, glm.vec2.scale(glm.vec2.create(), lineDir, distance / 4));

q1 = glm.vec2.add(q1, q1, halfPeakLengthNormal);

let q3Direction = 1;

if (invertQ2) {

q3Direction = -1;

}

// q2 = (q3 - (distance/4) * lineDir) + ((peakLength / 2) * normal)

let q2 = glm.vec2.add(glm.vec2.create(),

q3, glm.vec2.scale(glm.vec2.create(), lineDir, -distance / 4));

q2 = glm.vec2.add(q2, q2, glm.vec3.scale(halfPeakLengthNormal, halfPeakLengthNormal, q3Direction));

// console.log("points =", q0, q1, q2, q3);

return [q0, q1, q2, q3];

}

function bezierCurvePointsFromWeights(startPoint, endPoint, weights, heights) {

const startToEnd = glm.vec2.sub(glm.vec2.create(), endPoint, startPoint);

const distance = glm.vec2.length(startToEnd);

const lineDir = glm.vec2.normalize(glm.vec2.create(), startToEnd);

const normal = glm.vec2.fromValues(-lineDir[1], lineDir[0]);

if (!Array.isArray(weights) || weights.length != 2) {

throw new Error('Expected weights to be an array of length 2, got:', weights);

}

if (!Array.isArray(heights) || weights.length != 2) {

throw new Error('Expected heights to be an array of length 2, got:', heights);

}

const totalWeight = weights.reduce((s, c) => s + c, 0);

const normalizedWeights = weights.map((w) => w / totalWeight);

const q1Proj = glm.vec2.lerp(glm.vec2.create(), startPoint, endPoint, normalizedWeights[0]);

const q2Proj = glm.vec2.lerp(glm.vec2.create(), startPoint, endPoint, normalizedWeights[1]);

const q1 = glm.vec2.add(q1Proj, q1Proj, glm.vec2.scale(glm.vec2.create(), normal, heights[0]));

const q2 = glm.vec2.add(q2Proj, q2Proj, glm.vec2.scale(glm.vec2.create(), normal, heights[1]));

return [startPoint, q1, q2, endPoint];

}

function fromMillisecond(x) {

return x * 0.001;

}

function millimeter(x) {

return x * 0.001;

}

wp = new WindowParams();

function clearCanvas({ color = "#ffffffff" }) {

const c = wp.canvas;

c.fillStyle = color;

c.clearRect(0, 0, wp.canvasWidth, wp.canvasHeight);

}

class Queue {

constructor() {

this.stacks = [[], []];

}

push(e) {

this.stacks[0].push(e);

}

pop(e) {

const pushStack = 0;

const popStack = 1 - pushStack;

if (this.stacks[popStack].length > 0) {

return this.stacks[popStack].pop();

}

while (this.stacks[pushStack].length > 0) {

this.stacks[popStack].push(this.stacks[pushStack].pop());

}

return this.stacks[popStack].pop();

}

cellSize = millimeter(((wp.canvasElement.width - 200) / Math.max(numRows, numCols)) / pixelsPerMillimeter)

topLeft = glm.vec2.fromValues(-cellSize * numCols / 2, cellSize * numCols / 2)

function saveCanvasStyle(callback) {

const strokeStyle = wp.canvas.strokeStyle;

const fillStyle = wp.canvas.fillStyle;

const lineWidth = wp.canvas.lineWidth;

callback();

wp.canvas.lineWidth = lineWidth;

wp.canvas.strokeStyle = strokeStyle;

wp.canvas.fillStyle = fillStyle;

}

function requestAnimationFrameInSec(callback) {

return window.requestAnimationFrame((ts) => {

callback(fromMillisecond(ts));

})

}

function rgbCssFromVec3(v) {

const r = Math.floor(v[0] * 255);

const g = Math.floor(v[1] * 255);

const b = Math.floor(v[2] * 255);

return "rgb(" + r + ',' + g + ',' + b + ')';

}

CellDataflowCommandEnum = "cell_dataflow";

CellFillCommand = "cell_fill"; // Not used

class CellDataflowCommand {

constructor(sourceCellIndices, targetCellIndex, duration) {

this.type = CellDataflowCommandEnum;

this.sourceCellIndices = sourceCellIndices;

this.targetCellIndex = targetCellIndex;

this.duration = duration;

}

class MatrixGrid {

constructor(rows, columns, {

cellSize = millimeter(10),

topLeftPos = glm.vec2.fromValues(millimeter(20), millimeter(-20)),

wallWidth = 2,

}) {

this.numRows = rows;

this.numColumns = columns;

this.cellSize = cellSize;

this.topLeftPos = topLeftPos;

this.wallWidth = wallWidth;

this.topLeftCellCenter = glm.vec2.set(glm.vec2.create(), this.topLeftPos[0] + this.cellSize / 2, this.topLeftPos[1] - this.cellSize / 2);

this.oneCellDownward = glm.vec2.fromValues(0, -this.cellSize);

this.oneCellRightward = glm.vec2.fromValues(this.cellSize, 0);

const properRowLineLength = this.cellSize * this.numColumns;

const properColLineLength = this.cellSize * this.numRows;

this.lengthOfRowLine = [...Array(rows + 1)].map(() => properRowLineLength + mathjs.random(0, this.cellSize));

this.lengthOfColLine = [...Array(columns + 1)].map(() => properColLineLength + mathjs.random(0, this.cellSize));

this.bezierCurvePointsOfRowLine = this.lengthOfRowLine.map((length, row) => {

const rowLineOffset = length - (this.cellSize * this.numColumns);

let lineStart = glm.vec2.add(glm.vec2.create(), this.topLeftPos, glm.vec2.scale(glm.vec2.create(), this.oneCellDownward, row));

lineStart = glm.vec2.set(lineStart, lineStart[0] - rowLineOffset / 2, lineStart[1]);

let lineEnd = glm.vec2.add(glm.vec2.create(), lineStart, glm.vec2.scale(glm.vec2.create(), this.oneCellRightward, this.numColumns));

lineEnd = glm.vec2.set(lineEnd, lineEnd[0] + rowLineOffset, lineEnd[1]);

const w1 = mathjs.random(0.1, 0.7);

const w2 = mathjs.random(w1, 0.9);

const h1 = mathjs.random(-this.cellSize / 5, this.cellSize / 5);

const h2 = mathjs.random(-this.cellSize / 5, this.cellSize / 5);

const points = bezierCurvePointsFromWeights(lineStart, lineEnd, [w1, w2], [h1, h2]);

return points;

});

this.bezierCurvePointsOfColLine = this.lengthOfColLine.map((length, col) => {

const colLineOffset = length - (this.cellSize * this.numRows);

let lineStart = glm.vec2.add(glm.vec2.create(), this.topLeftPos, glm.vec2.scale(glm.vec2.create(), this.oneCellRightward, col));

lineStart = glm.vec2.set(lineStart, lineStart[0], lineStart[1] + colLineOffset / 2);

let lineEnd = glm.vec2.add(glm.vec2.create(), lineStart, glm.vec2.scale(glm.vec2.create(), this.oneCellDownward, this.numRows));

lineEnd = glm.vec2.set(lineEnd, lineEnd[0], lineEnd[1] - colLineOffset);

const w1 = mathjs.random(0.1, 0.7);

const w2 = mathjs.random(w1, 0.9);

const h1 = mathjs.random(-this.cellSize / 5, this.cellSize / 5);

const h2 = mathjs.random(-this.cellSize / 5, this.cellSize / 5);

const points = bezierCurvePointsFromWeights(lineStart, lineEnd, [w1, w2], [h1, h2]);

return points;

});

this.lineCurvePoints = [...this.bezierCurvePointsOfRowLine, ...this.bezierCurvePointsOfColLine];

// this.cells = [];

// for (let i = 0; i < rows; i++) {

// const row = [];

// for (let j = 0; j < columns; j++) {

// row.push(new MatrixCell());

// }

// this.cells.push(row);

// }

this.pendingCommands = new Queue();

this.drawables = [];

this.updateables = [];

this.drawables = [];

this.worldStartTimestamp = 0;

this.justCompletedUpdateables = new Queue();

this.poppedFirstCommand = false;

}

getCellCenter(row, col) {

let c = glm.vec2.add(glm.vec2.create(), this.topLeftCellCenter, glm.vec2.scale(glm.vec2.create(), this.oneCellRightward, col))

c = glm.vec2.add(c, c, glm.vec2.scale(glm.vec2.create(), this.oneCellDownward, row));

return c;

}

// offset is added as the vector (offset, -offset)

getCellTopLeft(row, col, offset = 0) {

let topLeftCorner = glm.vec2.clone(this.topLeftPos);

topLeftCorner = glm.vec2.add(topLeftCorner, topLeftCorner, glm.vec2.scale(glm.vec2.create(), this.oneCellRightward, col));

topLeftCorner = glm.vec2.add(topLeftCorner, topLeftCorner, glm.vec2.scale(glm.vec2.create(), this.oneCellDownward, row));

glm.vec2.set(topLeftCorner, topLeftCorner[0] + offset, topLeftCorner[1] - offset);

return topLeftCorner;

}

draw() {

saveCanvasStyle(() => {

wp.canvas.lineWidth = this.wallWidth;

let rowStart = glm.vec2.clone(this.topLeftPos);

let rowEnd = glm.vec2.add(glm.vec2.create(), rowStart, glm.vec2.fromValues(this.cellSize * this.numColumns, 0));

wp.canvas.beginPath();

wp.canvas.strokeStyle = "#020202";

for (let curvePoints of this.lineCurvePoints) {

wp.canvas.beginPath();

wp.bezierCurveTo(curvePoints);

wp.canvas.stroke();

}

});

}

pushCommand(command) {

this.pendingCommands.push(command);

// console.log('push:', command);

}

popCommand(timestampOfPop, msg, throwOnNoCommand = false) {

// console.log('pop command called from', msg);

const cmd = this.pendingCommands.pop();

if (!cmd) {

if (throwOnNoCommand) {

throw new Error('no command to pop!');

}

return false;

}

// console.log('pop result:', cmd, 'from:', msg);

// For the arrows

const perCellForwardDuration = cmd.duration * 0.8;

const perCellPauseDuration = 0;

const perCellBackwardDuration = cmd.duration - perCellForwardDuration;

const durationPerCell = perCellForwardDuration + perCellPauseDuration + perCellBackwardDuration;

const timestampForwardStart = timestampOfPop;

const timestampForwardEnd = timestampForwardStart + perCellForwardDuration;

const timestampBackwardStart = timestampForwardEnd + perCellPauseDuration;

const timestampBackwardEnd = timestampBackwardStart + perCellBackwardDuration;

const padding = this.cellSize / 20;

const targetCellTopLeft = this.getCellTopLeft(cmd.targetCellIndex[0], cmd.targetCellIndex[1], padding);

// console.log('enqueued interpolator starts at', timestampForwardStart);

// console.log('enqueued interpolator ends at', timestampForwardEnd);

if (cmd.type === CellDataflowCommandEnum) {

// console.log('processing new popped command:', cmd);

// Create the cell fill

const cellFillInterpolator = new LinearInterpolator(timestampForwardStart, timestampBackwardEnd);

const rectFiller = new InterpolatedRectFiller(

cellFillInterpolator,

targetCellTopLeft,

this.cellSize - 2 * padding,

glm.vec3.fromValues(0.8, 0.8, 0.8),

glm.vec3.fromValues(0.3, 0.3, 0.3));

rectFiller.setOnComplete(() => {

console.log('oncomplete rect filler for', cmd.targetCellIndex);

this.justCompletedUpdateables.push({

updateable: rectFiller,

timestampEnd: rectFiller.interpolator.timestampEnd, action: (ts) => {

console.log('popping new command which starts at', Math.max(rectFiller.interpolator.timestampEnd, ts));

this.popCommand(Math.max(rectFiller.interpolator.timestampEnd, ts), `from rectFiller at ${timestampOfPop}`);

}

});

// console.log('enqueueing rect filler at', timestampForwardStart);

this.updateables.push(rectFiller);

this.drawables.push(rectFiller);

const targetPoint = this.getCellCenter(cmd.targetCellIndex[0], cmd.targetCellIndex[1]);

// Create the arrows

for (let sourceCellIndex of cmd.sourceCellIndices) {

let sourcePoint = this.getCellCenter(sourceCellIndex[0], sourceCellIndex[1]);

if (glm.vec2.equals(sourceCellIndex, cmd.targetCellIndex)) {

sourcePoint = glm.vec2.set(sourcePoint, sourcePoint[0], sourcePoint[1] + this.cellSize / 10);

}

const curvePoints = parabolicBezierCurvePoints(sourcePoint, targetPoint, this.cellSize / 2);

const arrowInterpolator = new LinearRoundtripInterpolator(timestampForwardStart, timestampForwardEnd, timestampBackwardStart, timestampBackwardEnd, false);

const arrow = new InterpolatedBezierCurve(arrowInterpolator, curvePoints);

arrow.setOnComplete(() => {

console.log("oncomplete for arrow from", sourceCellIndex, cmd.targetCellIndex);

this.justCompletedUpdateables.push({

updateable: arrow, timestampEnd: arrow.interpolator.timestampBackwardEnd

});

arrow.setShouldDrawArrows(true);

arrow.arrowSideLength = this.cellSize / 4;

arrow.cacheArrowHeads();

// console.log("enqueueing arrow at", arrow, timestampForwardStart);

this.updateables.push(arrow);

this.drawables.push(arrow);

}

return true;

}

step(ts) {

if (!this.poppedFirstCommand) {

const didPop = this.popCommand(ts, `from step at ${ts}`);

if (didPop) {

this.poppedFirstCommand = true;

}

} else {

// Pop from the just-completed updateable. We pop a command if we find one.

const completedInfo = this.justCompletedUpdateables.pop();

if (completedInfo && completedInfo.action) {

completedInfo.action(ts);

}

// Iterate through all updateables and update them

for (let upd of this.updateables) {

if (!upd.completed) {

// console.log("updating:", upd);

upd.update(ts);

}

const drawableOrder = ["rect_fill", "bezier_curve"];

for (let curDrawable of drawableOrder) {

for (let drawable of this.drawables) {

if (drawable.drawableType !== curDrawable) {

continue;

}

switch (drawable.drawableType) {

case "bezier_curve":

this.drawBezierCurve(drawable);

break;

case "rect_fill":

this.drawRectFill(drawable);

break;

default:

throw new Error('Unknown drawable', drawable);

}

this.draw();

}

drawBezierCurve(drawable) {

saveCanvasStyle(() => {

wp.canvas.lineWidth = 4;

wp.canvas.strokeStyle = "#2a2a2a";

wp.canvas.beginPath();

wp.bezierCurveTo(drawable.curTruncatedPoints);

wp.canvas.stroke();

wp.canvas.beginPath();

// console.log('arrowHeadLeft =', drawable.arrowHeadLeft);

// console.log('arrowHeadRight =', drawable.arrowHeadRight);

wp.moveTo(drawable.curTruncatedPoints[3]);

wp.lineTo(drawable.arrowHeadLeft);

wp.lineTo(drawable.arrowHeadRight);

wp.lineTo(drawable.curTruncatedPoints[3]);

wp.canvas.fillStyle = "#2a2a2a";

wp.canvas.fill();

});

}

drawRectFill(drawable) {

saveCanvasStyle(() => {

wp.canvas.beginPath();

wp.canvas.fillStyle = rgbCssFromVec3(drawable.curColor);

wp.rect(drawable.topLeft, drawable.width, drawable.height);

wp.canvas.fill();

wp.canvas.closePath();

});

}

function* algoWordBreak(numRows, numCols) {

for (let diagonal = 0; diagonal < numRows + 1; diagonal++) {

for (let start = 0; start < numRows - diagonal; start++) {

const sourceIndices = [];

const end = start + diagonal;

for (let i = start; i < end; i++) {

sourceIndices.push(glm.vec2.fromValues(start, i));

sourceIndices.push(glm.vec2.fromValues(i, end));

}

yield new CellDataflowCommand(sourceIndices, glm.vec2.fromValues(start, end), durationPerCellInSecs);

}

function* algoKnapsack(numRows, numCols) {

for (let row = 1; row < numRows; row++) {

for (let col = 1; col < numCols; col++) {

const cmd = new CellDataflowCommand([

glm.vec2.fromValues(row - 1, col - 1),

glm.vec2.fromValues(row - 1, col)],

glm.vec2.fromValues(row, col), durationPerCellInSecs);

yield cmd;

}

function* algoEditDistance(numRows, numCols){

for (let s = 1; s < numRows; s++) {

for (let t = 1; t < numCols; t++) {

const s1 = glm.vec2.fromValues(s - 1, t - 1);

const s2 = glm.vec2.fromValues(s, t - 1);

const s3 = glm.vec2.fromValues(s - 1, t);

yield new CellDataflowCommand([s1, s2, s3], glm.vec2.fromValues(s, t), durationPerCellInSecs);

}

function runAlgoVis(algoFn) {

const mat = new MatrixGrid(numRows, numCols, {

cellSize: cellSize,

topLeftPos: topLeft,

wallWidth: 5,

});

const gen = algoFn(numRows, numCols);

// mat.worldStartTimestamp = fromMillisecond(performance.now());

const step = (curTimestamp) => {

if (mat.worldStartTimestamp === 0) {

mat.worldStartTimestamp = curTimestamp;

requestAnimationFrameInSec(step);

return;

}

clearCanvas({});

curTimestamp = curTimestamp - mat.worldStartTimestamp;

if (curTimestamp < 0) {

throw new Error('curTimestamp < 0!!!');

}

// console.log('ts =', curTimestamp);

// Run one step of the algo

const genResult = gen.next();

if (!genResult.done) {

mat.pushCommand(genResult.value, curTimestamp);

}

mat.step(curTimestamp);

// console.log('drawables =', mat.drawables);

requestAnimationFrameInSec(step);

};

requestAnimationFrameInSec(step);

}

{

let algoFn = algoWordBreak;

if (problemType === "word_break") {

algoFn = algoWordBreak;

} else if (problemType === "knapsack") {

algoFn = algoKnapsack;

} else if (problemType === "edit_distance") {

algoFn = algoEditDistance;

}

runAlgoVis(algoFn)

}

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