2b:null 2c:["$","title",null,{"children":"Dependencies in a dynamic-programming problem | Philippe Rigovanov | Observable"}] 31:Tc4c,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; }32:T4bc,// 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; } }33:Ta54,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]; } }34:T537,// 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); // } } }35:Tff8,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]; } }36:T692, // 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]; }37:T49d, 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]; } 38:T2a4c,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, 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(); }); } }39:[] 2f:{"id":"7bfd8d10295a1f04","slug":null,"title":"Dependencies in a dynamic-programming problem","thumbnail":"f36f5a9aa41142ae65d8800e3d2ccecae2ba072a228960bfb59df7f7d623e1cc","access_level":"public","create_time":"$D2022-12-29T21:17:41.980Z","update_time":"$D2022-12-29T21:17:41.980Z","view_time":null,"first_public_time":"$D2022-12-29T21:17:41.980Z","fork":{"id":"f0d780a4ab0b0236","slug":null,"title":"Dependencies in a dynamic-programming problem","owner":{"id":"719dc809ddd4992d","login":"slnsoumik","name":"Soumik Rakshit"}},"stars":2,"starred":false,"owner":{"type":"team","id":"b5ee25cc13065361","login":"a1ip","name":"Philippe Rigovanov","avatar_url":"https://avatars-next.observableusercontent.com/6359e02dc30dad37dc8aeff508f64823d0f57f42e9b940688bdd1af508bb839c","tier":"starter_2024"},"version":186,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"968f76daa2a26d11","login":"a1ip","name":"Philippe Rigovanov","avatar_url":"https://avatars-next.observableusercontent.com/6359e02dc30dad37dc8aeff508f64823d0f57f42e9b940688bdd1af508bb839c","tier":null}],"members":[{"type":"individual","id":"968f76daa2a26d11","login":"a1ip","name":"Philippe Rigovanov","avatar_url":"https://avatars-next.observableusercontent.com/6359e02dc30dad37dc8aeff508f64823d0f57f42e9b940688bdd1af508bb839c","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"f12a3f64915c0078","slug":"informatics","title":"Informatics","owner":{"id":"b5ee25cc13065361","login":"a1ip","name":"Philippe Rigovanov"}},"type":"notebook","body":{"title":"Dependencies in a dynamic-programming problem","cells":[{"id":0,"value":"# Dependencies in a dynamic-programming problem\n\nI wanted to illustrate the dependencies in a dynamic-programming problem.\n\nThese visuals are meant to be simple and mostly funky, and not meant to be a substitute for proper explanation of course.\n\nI want to avoid hardcoding animations for different DP problems. Instead, driving the animations by a sequence of events is a better idea. Right now, only 1 type of event makes sense to me - `CellAccess(sourceCells, targetCell)`.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":6,"value":"canvas = html`

`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":91,"value":"viewof problemType = Inputs.radio([\"word_break\", \"knapsack\", \"edit_distance\"], {label: \"problem type\"})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"viewof durationPerCellInSecs = Inputs.range([0.2, 0.8], {label: \"Duration per cell in seconds\", step: 0.2})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":106,"value":"numRows = 10","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":108,"value":"numCols = 10 ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"glm = import('https://unpkg.com/gl-matrix@3.4.3/esm/index.js?module')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":155,"value":"vec2 = glm.vec2","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":157,"value":"vec3 = glm.vec3","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":159,"value":"mat3 = glm.mat3","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"mathjs = require('mathjs@11.5.0/lib/browser/math.js')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"pixelsPerMillimeter = 10;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"class StepInterpolator {\n timestampStart;\n timestampEnd;\n maxT;\n onComplete;\n onCompleteCalled;\n\n constructor(timestampStart, timestampEnd, maxT = 1) {\n this.timestampStart = timestampStart;\n this.timestampEnd = timestampEnd;\n this.maxT = maxT;\n this.onComplete = null;\n this.onCompleteCalled = false;\n }\n\n t(currentTime) {\n if (currentTime < this.timestampStart) {\n return [0, false];\n }\n if (currentTime > this.timestampEnd) {\n if (!this.onCompleteCalled && !!this.onComplete) {\n this.onCompleteCalled = true;\n this.onComplete();\n }\n return [this.maxT, true];\n }\n return [0, false];\n }\n\n setOnComplete(onCompleteCallback) {\n this.onComplete = onCompleteCallback;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"\nclass OnCompleteCaller {\n completed;\n onComplete;\n\n constructor(onCompleteCallback = null) {\n this.onComplete = onCompleteCallback;\n this.completed = false;\n }\n\n setOnComplete(onCompleteCallback) {\n this.onComplete = onCompleteCallback;\n }\n\n setCompleted(extraMsg = '') {\n if (!this.completed && !!this.onComplete) {\n console.log('completed', extraMsg);\n this.completed = true;\n this.onComplete();\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"\n class InterpolatedLine extends OnCompleteCaller {\n startPoint; // const\n endPoint; // const\n interpolator; // const\n\n curEndPoint;\n\n // startPoint: vec2, endPoint: vec2\n constructor(interpolator, startPoint, endPoint) {\n super();\n\n this.drawableType = \"line\";\n\n this.startPoint = glm.vec2.clone(startPoint);\n this.endPoint = glm.vec2.clone(endPoint);\n this.curEndPoint = glm.vec2.clone(endPoint);\n this.interpolator = interpolator;\n }\n\n // currentTimestamp: number\n // interpolator: LinearInterpolator\n update(currentTimestamp) {\n const [t, completed] = this.interpolator.t(currentTimestamp);\n this.curEndPoint = glm.vec2.lerp(this.curEndPoint, this.startPoint, this.endPoint, t);\n this.completed = completed;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"$35","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"$36","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"function fromMillisecond(x) {\n return x * 0.001;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"function millimeter(x) {\n return x * 0.001;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":47,"value":"wp = new WindowParams();","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"function clearCanvas({ color = \"#ffffffff\" }) {\n const c = wp.canvas;\n c.fillStyle = color;\n c.clearRect(0, 0, wp.canvasWidth, wp.canvasHeight);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":49,"value":"class Queue {\n constructor() {\n this.stacks = [[], []];\n }\n\n push(e) {\n this.stacks[0].push(e);\n }\n\n pop(e) {\n const pushStack = 0;\n const popStack = 1 - pushStack;\n if (this.stacks[popStack].length > 0) {\n return this.stacks[popStack].pop();\n }\n\n while (this.stacks[pushStack].length > 0) {\n this.stacks[popStack].push(this.stacks[pushStack].pop());\n }\n return this.stacks[popStack].pop();\n }\n}\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":121,"value":"cellSize = millimeter(((wp.canvasElement.width - 200) / Math.max(numRows, numCols)) / pixelsPerMillimeter)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":123,"value":"topLeft = glm.vec2.fromValues(-cellSize * numCols / 2, cellSize * numCols / 2)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"function saveCanvasStyle(callback) {\n const strokeStyle = wp.canvas.strokeStyle;\n const fillStyle = wp.canvas.fillStyle;\n const lineWidth = wp.canvas.lineWidth;\n callback();\n wp.canvas.lineWidth = lineWidth;\n wp.canvas.strokeStyle = strokeStyle;\n wp.canvas.fillStyle = fillStyle;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":73,"value":"function requestAnimationFrameInSec(callback) {\n return window.requestAnimationFrame((ts) => {\n callback(fromMillisecond(ts));\n })\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"function rgbCssFromVec3(v) {\n const r = Math.floor(v[0] * 255);\n const g = Math.floor(v[1] * 255);\n const b = Math.floor(v[2] * 255);\n return \"rgb(\" + r + ',' + g + ',' + b + ')';\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"CellDataflowCommandEnum = \"cell_dataflow\";","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"CellFillCommand = \"cell_fill\"; // Not used","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"class CellDataflowCommand {\n constructor(sourceCellIndices, targetCellIndex, duration) {\n this.type = CellDataflowCommandEnum;\n\n this.sourceCellIndices = sourceCellIndices;\n this.targetCellIndex = targetCellIndex;\n this.duration = duration;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"$38","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":75,"value":"function* algoWordBreak(numRows, numCols) {\n for (let diagonal = 0; diagonal < numRows + 1; diagonal++) {\n for (let start = 0; start < numRows - diagonal; start++) {\n const sourceIndices = [];\n const end = start + diagonal;\n for (let i = start; i < end; i++) {\n sourceIndices.push(glm.vec2.fromValues(start, i));\n sourceIndices.push(glm.vec2.fromValues(i, end));\n }\n yield new CellDataflowCommand(sourceIndices, glm.vec2.fromValues(start, end), durationPerCellInSecs);\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"function* algoKnapsack(numRows, numCols) {\n for (let row = 1; row < numRows; row++) {\n for (let col = 1; col < numCols; col++) {\n const cmd = new CellDataflowCommand([\n glm.vec2.fromValues(row - 1, col - 1),\n glm.vec2.fromValues(row - 1, col)],\n glm.vec2.fromValues(row, col), durationPerCellInSecs);\n yield cmd;\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":134,"value":"function* algoEditDistance(numRows, numCols){\n for (let s = 1; s < numRows; s++) {\n for (let t = 1; t < numCols; t++) {\n const s1 = glm.vec2.fromValues(s - 1, t - 1);\n const s2 = glm.vec2.fromValues(s, t - 1);\n const s3 = glm.vec2.fromValues(s - 1, t);\n\n yield new CellDataflowCommand([s1, s2, s3], glm.vec2.fromValues(s, t), durationPerCellInSecs);\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":79,"value":"function runAlgoVis(algoFn) {\n const mat = new MatrixGrid(numRows, numCols, {\n cellSize: cellSize,\n topLeftPos: topLeft,\n wallWidth: 5,\n });\n\n const gen = algoFn(numRows, numCols);\n\n // mat.worldStartTimestamp = fromMillisecond(performance.now());\n\n const step = (curTimestamp) => {\n if (mat.worldStartTimestamp === 0) {\n mat.worldStartTimestamp = curTimestamp;\n requestAnimationFrameInSec(step);\n return;\n }\n\n clearCanvas({});\n curTimestamp = curTimestamp - mat.worldStartTimestamp;\n if (curTimestamp < 0) {\n throw new Error('curTimestamp < 0!!!');\n }\n\n // console.log('ts =', curTimestamp);\n\n // Run one step of the algo\n const genResult = gen.next();\n if (!genResult.done) {\n mat.pushCommand(genResult.value, curTimestamp);\n }\n\n mat.step(curTimestamp);\n // console.log('drawables =', mat.drawables);\n requestAnimationFrameInSec(step);\n };\n\n requestAnimationFrameInSec(step);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":83,"value":"{\n let algoFn = algoWordBreak;\n if (problemType === \"word_break\") {\n algoFn = algoWordBreak;\n } else if (problemType === \"knapsack\") {\n algoFn = algoKnapsack;\n } else if (problemType === \"edit_distance\") {\n algoFn = algoEditDistance;\n }\n\n runAlgoVis(algoFn)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 30:"$2f:body"