algorithm-visualizer
Feature: show pointer indicator and swap indicators
Algorithm Visualizer is a good idea. How about show indicators to points our the "current focus", or "nodes being swapped".
Do you mean items in an array?
Usually, you can achieve this with tracers although the API is maybe a bit clunky but it works.
For example, for arrays, we have 2 visualization states.
There's tracer.select and tracer.patch that would mark the items in any visualization with blue or red (patch also requires providing a value)
For example, in an array we can do:
tracer.select(0)
tracer.patch(0, sameValueThatWasAlreadyHere)
You can see the explicit API's for all the data formats here.
So you should be able to select or patch the nodes currently being swapped, and the visualization should reflect in the appropriate color.
Here's an example of solving the Trapping Rain Water problem leveraging the 2 visualization states.
const { Array2DTracer } = require("algorithm-visualizer")
const heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
// visualize the elevation
const rows = Math.max(...heights);
const cols = heights.length;
const elevation = Array.from({ length: rows }, () =>
Array.from({ length: cols }, () => " ")
);
const elevationTracer = new Array2DTracer("Elevation").set(elevation);
// initialize the elevations using patching, i.e. mark them as red and give them blank values
let temp = heights.slice();
let r = rows - 1;
while (r >= 0) {
for (let i = 0; i < cols; i++) {
const val = temp[i] === 0 ? 0 : 1;
if (val > 0) {
elevationTracer.patch(r, i, " ");
}
}
temp = temp.map(n => (n === 0 ? 0 : n - 1));
r -= 1;
}
function TrappingRainWater() {
let left = 0;
let leftMax = 0;
let right = heights.length - 1;
let rightMax = 0;
let result = 0;
while (left <= right) {
if (leftMax < rightMax) {
leftMax = Math.max(leftMax, heights[left]);
result += leftMax - heights[left];
if (leftMax - heights[left] > 0) {
for (let i = 0; i < leftMax - heights[left]; i++) {
// mark the solution in blue via selection
elevationTracer.select(rows - 1 - heights[left] - i, left);
}
}
left++;
} else {
rightMax = Math.max(rightMax, heights[right]);
result += rightMax - heights[right];
if (rightMax - heights[right] > 0) {
for (let i = 0; i < rightMax - heights[right]; i++) {
// mark the solution in blue via selection
elevationTracer.select(rows - 1 - heights[right] - i, right);
}
}
right--;
}
}
return result;
}
TrappingRainWater();
The code is quite verbose though.
@parkjs814 it might be worth introducing code-folding to tracer statements by default.
Maybe also extending the API of each tracer so that it can target a ([startLine, startCol], [endLine, endCol]) so that invoking a tracer statement, even when folded off screen, highlights the targetted statement instead of the actual tracer statement.
@nanw1103 Sorry for the (extremely) late response 😭 I just came up with an idea that by adding .swap(i1, i2) method to Array1DTracer (and similarly .swap(i1, j1, i2, j2) method to Array2DTracer) we can actually animate two elements being swapped. How do you guys think of it?
@nem035 I love your idea of highlighting the targetted statement. It might be tedious work for myself and contributors to update line/col numbers every time code is changed, but I think it is worth it.
@parkjs814 What might be a great feature is something like the variable watch in Chrome Dev Tools.
We could attach the statements that change the data to renderers (i.e. mark them as "watched") , as opposed to adding the tracer statements directly which are much noisier. ("watching" would still leverage tracers behind the scenes)
I'll try and think about a potential implementation and circle back for feedback.
The noisiness of tracers becomes an issue when you wanna keep track of 3,4 variables or more.
Here's the same code from above, just keeping track of all the variables that are changing and logging the changes (it's very hard to see where the actual algorithm logic is):
const { Array1DTracer, Array2DTracer, LogTracer } = require('algorithm-visualizer');
const heights = [0,1,0,2,1,0,1,3,2,1,2,1];
// visualize the elevation
const rows = Math.max(...heights);
const cols = heights.length;
const elevation = Array.from({ length: rows }, () =>
Array.from({ length: cols }, () => ' ')
);
const elevationTracer = new Array2DTracer('Elevation').set(elevation);
let temp = heights.slice();
let r = rows - 1;
while (r >= 0) {
for (let i = 0; i < cols; i++) {
const val = temp[i] === 0 ? 0 : 1;
if (val > 0) {
elevationTracer.patch(r, i, ' ')
}
}
temp = temp.map(n => n === 0 ? 0 : n - 1);
r -= 1;
}
// create tracers for each variable. Instead We could do something on the UI level for this and mark the vars as "watched"
const leftTracer = new Array1DTracer('left');
const leftMaxTracer = new Array1DTracer('leftMax');
const rightTracer = new Array1DTracer('right');
const rightMaxTracer = new Array1DTracer('rightMax');
const resultTracer = new Array1DTracer('result');
const logTracer = new LogTracer();
function TrappingRainWater() {
let left = 0;
let leftMax = 0;
let right = heights.length - 1;
let rightMax = 0;
let result = 0;
logTracer.print('initializing data').delay();
leftTracer.set([left]);
leftMaxTracer.set([leftMax]);
rightTracer.set([right]);
rightMaxTracer.set([rightMax]);
resultTracer.set([result]);
logTracer.print('Comparing left < right').delay();
leftTracer.select(0).delay();
rightTracer.select(0).delay();
while (left <= right) {
leftTracer.deselect(0);
rightTracer.deselect(0);
logTracer.print('Comparing leftMax < rightMax').delay();
leftMaxTracer.select(0).delay();
rightMaxTracer.select(0).delay();
leftMaxTracer.deselect(0);
rightMaxTracer.deselect(0);
if (leftMax < rightMax) {
logTracer.print('Updating leftMax = max(leftMax, heights[left])').delay();
leftMaxTracer.select(0).delay();
leftMax = Math.max(leftMax, heights[left]);
leftMaxTracer.patch(0, leftMax).delay();
logTracer.print('Incrementing result by leftMax - heights[left]').delay();
leftMaxTracer.select(0).delay();
result += leftMax - heights[left];
resultTracer.patch(0, result).delay();
if ((leftMax - heights[left]) > 0) {
for (let i = 0; i < leftMax - heights[left]; i++) {
elevationTracer.select(rows - 1 - heights[left] - i, left);
}
}
logTracer.print('Incrementing left').delay();
leftTracer.patch(0, left + 1).delay();
left ++;
} else {
logTracer.print('Updating rightMax = max(rightMax, heights[right])').delay();
rightMaxTracer.select(0).delay();
rightMax = Math.max(rightMax, heights[right]);
rightMaxTracer.patch(0, rightMax).delay();
logTracer.print('Incrementing result by rightMax - heights[left]').delay();
rightMaxTracer.select(0).delay();
result += rightMax - heights[right];
resultTracer.patch(0, result).delay();
if ((rightMax - heights[right]) > 0) {
for (let i = 0; i < rightMax - heights[right]; i++) {
elevationTracer.select(rows - 1 - heights[right] - i, right);
}
}
logTracer.print('Decrementing right').delay();
rightTracer.patch(0, right - 1).delay();
right --;
}
logTracer.print('Comparing left < right').delay();
leftTracer.select(0).delay();
rightTracer.select(0).delay();
}
return result;
}
TrappingRainWater();
We could also play with writing a babel plugin for the editor that hides away the tracers and leverages source maps to highlight the proper line
@nem035 For hiding visualization codes, I think using Non Standard Code Folding supported by the ACE editor is enough. I made them initially folded when code is loaded (de8cd96). I need to document this coding convention and update all the algorithms accordingly.
Check out the newly written visualization of Bucket Sort.
I have also been thinking of "watching" variables and messing around with it. Since we cannot literally watch the change of variables like Chrome Dev Tools, what we can do is to provide a getter to the watcher (or Variable class below) and whenever tracer is .delay()ed, we can call the getter to get the updated value. The usage would look like below:
const tracer = new Array2DTracer('array');
const array = new Array(4).fill(0).map(() => new Array(4).fill(0));
tracer.set(array, (i, j) => array[i][j]);
Tracer.delay();
let i = 0;
let j = 3;
const varI = new Variable('i', () => i);
const varJ = new Variable('j', () => j);
tracer.watch(varI, varJ);
for (let t = 0; t < 3; t++) {
array[++i][--j] = t;
Tracer.delay();
}
tracer.unwatch(varI, varJ);
varI.destroy();
varJ.destroy();
Tracer.delay();
Also, we might be able to integrate variable watchers with other tracers. In the above example, we still can keep track of an array without even calling .patch()/.depatch() or .select()/.deselect(). I'm not sure yet which backfires it would bring, so I'm planning to mess around with it little more.
Hmmm, so I can see how having our own abstractions over language constructs like Variable, Loop etc would solve this. The tradeoff would be that we'd be introducing a minor learning curve (via our own DSL of sorts).
Another solution that comes to mind, albeit more complex, is to attach watchers into the syntax of the language itself, rather than wrapping them in external abstractions. We could allow the user to select any syntactically valid token in a language (at least the ones for which we have tracers) and opt-in to "track" them. This can be done by hovering/clicking, double-clicking, right-click then confirm, etc.
This would require dedicated parsers for each supported language, so that we can examine the AST (or another type of syntax tree if more applicable) and know when a user opted into tracking a supported token.
Try clicking around this AST Explorer to get the visual idea
@nem035 I love this approach. If we can implement your second solution, we would significantly lower the barrier to entry for new users. I'll test it out on JavaScript using Acorn when I get time.
Sounds good!
For a multi-language approach we could try out tree-sitter (it's built by the Atom team @ Github)
