bogocircle.js

/*
 * empirically tests the complexity of a bogosort based algorithm which
 * shuffles circles until they don't overlap (for stimulus presentation)
 * is a function of the circle radius, the canvas width and height
 *
 * call it with (first arg is radius, then width and height of canvas)
 * > node test.js 10 300 500
 * > node test.js 10
 * etc.
 */

var _ = require('lodash');
var stats = require('simple-statistics');

var RADIUS;
var WIDTH;
var HEIGHT;


function uniform(a, b) { return ((Math.random() * (b - a)) + a); }
function fillArray(val, len) { return _.times(len, _.constant(val)); }

function samplePoint(color) {
  var x = uniform(RADIUS + 10, WIDTH - RADIUS - 10);
  var y = uniform(RADIUS + 10, HEIGHT - RADIUS - 10);
  var point = {x: x, y: y, color: color};
  return point;
}

function getPoints(nr_points, nr_white) {
  var DIFF = Math.sqrt(2) * RADIUS;
  var points = [];
  var nr_black = nr_points - nr_white;
  var pointcolors = _.shuffle(fillArray('white', nr_white))
                     .concat(fillArray('black', nr_black));

  var done = function(point, points) {
    for (var i = 0; i < points.length; i++) {
      var other_point = points[i];
      var check = Math.abs(point.x - other_point.x) > DIFF &&
                  Math.abs(point.y - other_point.y) > DIFF;
      if (!check) return false;
    }
    return true;
  };

  var count = 0;
  for (var i = 0; i < nr_points; i++) {
    var point = samplePoint(pointcolors[i]);

    // Bogosort like algorithm in all its elegant simplicity
    while (!done(point, points)) {
      count++;
      point = samplePoint(pointcolors[i]);
    }

    points[i] = point;
  }

  return count;
}

var test = function(times, spec) {
  var counts = [];
  RADIUS = spec[0] || 10;
  WIDTH = spec[1] || 500;
  HEIGHT = spec[2] || 300;

  for (var i = 0; i < times; i++) {
    counts.push(getPoints(10, _.random(0, 10)));
  }

  console.log(['mean', stats.mean(counts)].join(': '));
  console.log(['mode', stats.mode(counts)].join(': '));
  console.log(['median', stats.median(counts)].join(': '));
  console.log(['min', stats.min(counts)].join(': '));
  console.log(['max', stats.max(counts)].join(': '));
};

test(1000, _.map(process.argv.slice(2), Number));