Feature: show pointer indicator and swap indicators #228

nanw1103 · 2018-03-23T03:46:01Z

Algorithm Visualizer is a good idea.
How about show indicators to points our the "current focus", or "nodes being swapped".

nem035 · 2019-02-06T18:13:26Z

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.

nem035 · 2019-02-06T18:17:53Z

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.

nem035 · 2019-02-06T18:36:50Z

I just noticed this comment is from early 2018 😂

64json · 2019-02-07T01:47:29Z

@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?

64json · 2019-02-07T01:52:29Z

@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.

nem035 · 2019-02-07T16:56:17Z

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

nem035 · 2019-02-07T16:58:03Z

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

64json · 2019-02-07T23:20:29Z

@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.

64json · 2019-02-07T23:37:24Z

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.

nem035 · 2019-10-13T14:53:03Z

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

64json · 2019-10-14T07:42:49Z

@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.

nem035 · 2019-10-14T12:21:44Z

Sounds good!

For a multi-language approach we could try out tree-sitter (it's built by the Atom team @ Github)

Try out their playground here

peterschussheim mentioned this issue Oct 10, 2019

Simplify and reduce the complexity of visualization creation #272

Open

Aug	SEP	Oct
	08
2019	2020	2021

algorithm-visualizer / algorithm-visualizer

Feature: show pointer indicator and swap indicators #228

Feature: show pointer indicator and swap indicators #228

nanw1103 commented Mar 23, 2018

nem035 commented Feb 6, 2019 •

edited

nem035 commented Feb 6, 2019 •

edited

nem035 commented Feb 6, 2019

64json commented Feb 7, 2019

64json commented Feb 7, 2019

nem035 commented Feb 7, 2019 •

edited

nem035 commented Feb 7, 2019

64json commented Feb 7, 2019 •

edited

64json commented Feb 7, 2019

nem035 commented Oct 13, 2019 •

edited

64json commented Oct 14, 2019

nem035 commented Oct 14, 2019

algorithm-visualizer / algorithm-visualizer

Sponsor algorithm-visualizer/algorithm-visualizer

Join GitHub today

Feature: show pointer indicator and swap indicators #228

Feature: show pointer indicator and swap indicators #228

Comments

nanw1103 commented Mar 23, 2018

nem035 commented Feb 6, 2019 • edited

nem035 commented Feb 6, 2019 • edited

nem035 commented Feb 6, 2019

64json commented Feb 7, 2019

64json commented Feb 7, 2019

nem035 commented Feb 7, 2019 • edited

nem035 commented Feb 7, 2019

64json commented Feb 7, 2019 • edited

64json commented Feb 7, 2019

nem035 commented Oct 13, 2019 • edited

64json commented Oct 14, 2019

nem035 commented Oct 14, 2019

nem035 commented Feb 6, 2019 •

edited

nem035 commented Feb 6, 2019 •

edited

nem035 commented Feb 7, 2019 •

edited

64json commented Feb 7, 2019 •

edited

nem035 commented Oct 13, 2019 •

edited