Skip to content

Instantly share code, notes, and snippets.

@diegoconcha

diegoconcha/index.html

Created March 22, 2015 00:30
Show Gist options
  • Save diegoconcha/7785aaaed57779920ce9 to your computer and use it in GitHub Desktop.
Save diegoconcha/7785aaaed57779920ce9 to your computer and use it in GitHub Desktop.
Download ZIP
WorkPop Coding Challenge: Fair Shuffler (http://jsbin.com/wahefa/25/edit)
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JS Bin</title>
</head>
<body>
<script id="jsbin-javascript">
/**
* Shuffle an array
*
* References:
* https://github.com/lodash/lodash/blob/3.0.0-npm/collection/shuffle.js
* https://en.wikipedia.org/wiki/Fisher-Yates_shuffle
* https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random
* https://github.com/lodash/lodash/blob/3.0.0-npm/internal/baseRandom.js
* https://sites.google.com/site/samkennerly/ShuffleTest.zip
* http://en.wikipedia.org/wiki/Standard_deviation
*
* @param array {Array} Original array
* @returns {Array} An efficiently and fairly shuffled array
*/
function shuffle(array) {
var length = array.length,
result = Array(length);
j = 0;
for (var i = 0; i < length; i++) {
j = Math.floor(Math.random() * (i + 1)); // random int [0,i]
if (j != i) {
result[i] = result[j];
}
result[j] = array[i];
}
return result;
}
/**
* Check if a given shuffle function is a fair
*
* @param shuffleFunction {Function} A function that takes an array as an argument. It shuffles arrays
* @param array {Array} Initial array to shuffle
* @param numTrials {Int} Number of trials
* @params stdTreshold {Float} Standard Deviation Treshold for fairness consideration
* @params debug {Boolean} Optional flag for debug output
* @returns {boolean} Whether or not this shuffle function fairly shuffles arrays
*/
function isShuffleFair(shuffleFunction, array, numTrials, stdThreshold, debug) {
var arrayLength = array.length,
shuffledArray = Array(arrayLength),
countsMatrix = Array(arrayLength),
probabilityMatrix,
totalCounts = numTrials * arrayLength,
meanProbability = 0,
sumProbability = 0,
sumOfSquares = 0,
standardDeviation = 0,
i = 0,
j = 0,
isFair = false,
debugFlag = debug || false;
// Create 2D array for counts
for (i = 0; i < arrayLength; i++) {
countsMatrix[i] = Array(arrayLength);
for (j = 0; j < arrayLength; j++) {
countsMatrix[i][j] = 0;
}
}
probabilityMatrix = countsMatrix.slice(0); // shallow copy the contents blank counts matrix
// Shuffle many times and sum counts in the counts matrix
for (i = 0; i < numTrials; i++) {
shuffledArray = shuffleFunction(array);
countsMatrix = computeCounts(array, shuffledArray, countsMatrix);
}
// Compute probability matrix
for (i = 0; i < arrayLength; i++) {
for (j = 0; j < arrayLength; j++) {
probabilityMatrix[i][j] = parseFloat((countsMatrix[i][j]/totalCounts * 100).toFixed(2));
sumProbability += probabilityMatrix[i][j];
}
}
// Compute mean and STD of probabilities
meanProbability = sumProbability / (arrayLength * arrayLength);
for (i = 0; i < arrayLength; i++) {
for (j = 0; j < arrayLength; j++) {
sumOfSquares += Math.pow((probabilityMatrix[i][j] - meanProbability), 2);
}
}
standardDeviation = Math.sqrt(sumOfSquares / (arrayLength * arrayLength));
// Compute fairness based on standard deviation threshold
if (standardDeviation >= stdThreshold) {
isFair = false;
} else {
isFair = true;
}
// Optionally provide console output
if (debugFlag) {
console.log('Probability Matrix: ', plotMatrix(probabilityMatrix));
console.log('Mean Probability ' + meanProbability.toFixed(2) + ' +/- ' +
standardDeviation.toFixed(2) + '%');
console.log('Fair: ' + isFair);
}
return isFair;
}
/**
* Plot matrix as 2D string
*
* @param matrix {Array} original array
* @returns {String} string
*/
function plotMatrix(matrix) {
var result = '',
i = 0,
j = 0,
length = matrix.length,
width = matrix[0].length;
for (i = 0; i < length; i++) {
for (j = 0; j < width; j++) {
result += (matrix[i][j] + ' ');
if (j === (width - 1)) {
result += '\n';
}
}
}
return result;
}
/**
* Compute 2D counts matrix
*
* @param array {Array} original array
* @param mutatedArray {Array} modified array
* @param existingCounts {Array} existing matrix
* @returns {Array} resulting matrix[i][j] where i index refers to the original positon
* and j index refers to the new position
*/
function computeCounts(array, mutatedArray, existingCounts) {
var arrayLength = array.length,
newCounts = Array(arrayLength),
i = 0,
j = 0,
newPosition;
// Check if existingCounts were passed in
if (typeof existingCounts === 'undefined') {
existingCounts = null;
for (i = 0; i < arrayLength; i++) {
newCounts[i] = Array(arrayLength);
for (j = 0; j < arrayLength; j++) {
newCounts[i][j] = 0;
}
}
} else {
newCounts = existingCounts;
}
for (i = 0; i < arrayLength; i++) {
newPosition = mutatedArray.indexOf(array[i]);
newCounts[i][newPosition] += 1;
}
return newCounts;
}
isShuffleFair(shuffle, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 100, 1, true);
isShuffleFair(function(array) {
return array;
}, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 100, 1, true);
isShuffleFair(function(array) {
return ([].concat(array)).sort(function(a, b) {return a - b;});
}, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 100, 1, true);
</script>
<script id="jsbin-source-javascript" type="text/javascript">/**
* Shuffle an array
*
* References:
* https://github.com/lodash/lodash/blob/3.0.0-npm/collection/shuffle.js
* https://en.wikipedia.org/wiki/Fisher-Yates_shuffle
* https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random
* https://github.com/lodash/lodash/blob/3.0.0-npm/internal/baseRandom.js
* https://sites.google.com/site/samkennerly/ShuffleTest.zip
* http://en.wikipedia.org/wiki/Standard_deviation
*
* @param array {Array} Original array
* @returns {Array} An efficiently and fairly shuffled array
*/
function shuffle(array) {
var length = array.length,
result = Array(length);
j = 0;
for (var i = 0; i < length; i++) {
j = Math.floor(Math.random() * (i + 1)); // random int [0,i]
if (j != i) {
result[i] = result[j];
}
result[j] = array[i];
}
return result;
}
/**
* Check if a given shuffle function is a fair
*
* @param shuffleFunction {Function} A function that takes an array as an argument. It shuffles arrays
* @param array {Array} Initial array to shuffle
* @param numTrials {Int} Number of trials
* @params stdTreshold {Float} Standard Deviation Treshold for fairness consideration
* @params debug {Boolean} Optional flag for debug output
* @returns {boolean} Whether or not this shuffle function fairly shuffles arrays
*/
function isShuffleFair(shuffleFunction, array, numTrials, stdThreshold, debug) {
var arrayLength = array.length,
shuffledArray = Array(arrayLength),
countsMatrix = Array(arrayLength),
probabilityMatrix,
totalCounts = numTrials * arrayLength,
meanProbability = 0,
sumProbability = 0,
sumOfSquares = 0,
standardDeviation = 0,
i = 0,
j = 0,
isFair = false,
debugFlag = debug || false;
// Create 2D array for counts
for (i = 0; i < arrayLength; i++) {
countsMatrix[i] = Array(arrayLength);
for (j = 0; j < arrayLength; j++) {
countsMatrix[i][j] = 0;
}
}
probabilityMatrix = countsMatrix.slice(0); // shallow copy the contents blank counts matrix
// Shuffle many times and sum counts in the counts matrix
for (i = 0; i < numTrials; i++) {
shuffledArray = shuffleFunction(array);
countsMatrix = computeCounts(array, shuffledArray, countsMatrix);
}
// Compute probability matrix
for (i = 0; i < arrayLength; i++) {
for (j = 0; j < arrayLength; j++) {
probabilityMatrix[i][j] = parseFloat((countsMatrix[i][j]/totalCounts * 100).toFixed(2));
sumProbability += probabilityMatrix[i][j];
}
}
// Compute mean and STD of probabilities
meanProbability = sumProbability / (arrayLength * arrayLength);
for (i = 0; i < arrayLength; i++) {
for (j = 0; j < arrayLength; j++) {
sumOfSquares += Math.pow((probabilityMatrix[i][j] - meanProbability), 2);
}
}
standardDeviation = Math.sqrt(sumOfSquares / (arrayLength * arrayLength));
// Compute fairness based on standard deviation threshold
if (standardDeviation >= stdThreshold) {
isFair = false;
} else {
isFair = true;
}
// Optionally provide console output
if (debugFlag) {
console.log('Probability Matrix: ', plotMatrix(probabilityMatrix));
console.log('Mean Probability ' + meanProbability.toFixed(2) + ' +/- ' +
standardDeviation.toFixed(2) + '%');
console.log('Fair: ' + isFair);
}
return isFair;
}
/**
* Plot matrix as 2D string
*
* @param matrix {Array} original array
* @returns {String} string
*/
function plotMatrix(matrix) {
var result = '',
i = 0,
j = 0,
length = matrix.length,
width = matrix[0].length;
for (i = 0; i < length; i++) {
for (j = 0; j < width; j++) {
result += (matrix[i][j] + ' ');
if (j === (width - 1)) {
result += '\n';
}
}
}
return result;
}
/**
* Compute 2D counts matrix
*
* @param array {Array} original array
* @param mutatedArray {Array} modified array
* @param existingCounts {Array} existing matrix
* @returns {Array} resulting matrix[i][j] where i index refers to the original positon
* and j index refers to the new position
*/
function computeCounts(array, mutatedArray, existingCounts) {
var arrayLength = array.length,
newCounts = Array(arrayLength),
i = 0,
j = 0,
newPosition;
// Check if existingCounts were passed in
if (typeof existingCounts === 'undefined') {
existingCounts = null;
for (i = 0; i < arrayLength; i++) {
newCounts[i] = Array(arrayLength);
for (j = 0; j < arrayLength; j++) {
newCounts[i][j] = 0;
}
}
} else {
newCounts = existingCounts;
}
for (i = 0; i < arrayLength; i++) {
newPosition = mutatedArray.indexOf(array[i]);
newCounts[i][newPosition] += 1;
}
return newCounts;
}
isShuffleFair(shuffle, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 100, 1, true);
isShuffleFair(function(array) {
return array;
}, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 100, 1, true);
isShuffleFair(function(array) {
return ([].concat(array)).sort(function(a, b) {return a - b;});
}, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 100, 1, true);</script></body>
</html>
Raw
jsbin.wahefa.js
/**
* Shuffle an array
*
* References:
* https://github.com/lodash/lodash/blob/3.0.0-npm/collection/shuffle.js
* https://en.wikipedia.org/wiki/Fisher-Yates_shuffle
* https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random
* https://github.com/lodash/lodash/blob/3.0.0-npm/internal/baseRandom.js
* https://sites.google.com/site/samkennerly/ShuffleTest.zip
* http://en.wikipedia.org/wiki/Standard_deviation
*
* @param array {Array} Original array
* @returns {Array} An efficiently and fairly shuffled array
*/
function shuffle(array) {
var length = array.length,
result = Array(length);
j = 0;
for (var i = 0; i < length; i++) {
j = Math.floor(Math.random() * (i + 1)); // random int [0,i]
if (j != i) {
result[i] = result[j];
}
result[j] = array[i];
}
return result;
}
/**
* Check if a given shuffle function is a fair
*
* @param shuffleFunction {Function} A function that takes an array as an argument. It shuffles arrays
* @param array {Array} Initial array to shuffle
* @param numTrials {Int} Number of trials
* @params stdTreshold {Float} Standard Deviation Treshold for fairness consideration
* @params debug {Boolean} Optional flag for debug output
* @returns {boolean} Whether or not this shuffle function fairly shuffles arrays
*/
function isShuffleFair(shuffleFunction, array, numTrials, stdThreshold, debug) {
var arrayLength = array.length,
shuffledArray = Array(arrayLength),
countsMatrix = Array(arrayLength),
probabilityMatrix,
totalCounts = numTrials * arrayLength,
meanProbability = 0,
sumProbability = 0,
sumOfSquares = 0,
standardDeviation = 0,
i = 0,
j = 0,
isFair = false,
debugFlag = debug || false;
// Create 2D array for counts
for (i = 0; i < arrayLength; i++) {
countsMatrix[i] = Array(arrayLength);
for (j = 0; j < arrayLength; j++) {
countsMatrix[i][j] = 0;
}
}
probabilityMatrix = countsMatrix.slice(0); // shallow copy the contents blank counts matrix
// Shuffle many times and sum counts in the counts matrix
for (i = 0; i < numTrials; i++) {
shuffledArray = shuffleFunction(array);
countsMatrix = computeCounts(array, shuffledArray, countsMatrix);
}
// Compute probability matrix
for (i = 0; i < arrayLength; i++) {
for (j = 0; j < arrayLength; j++) {
probabilityMatrix[i][j] = parseFloat((countsMatrix[i][j]/totalCounts * 100).toFixed(2));
sumProbability += probabilityMatrix[i][j];
}
}
// Compute mean and STD of probabilities
meanProbability = sumProbability / (arrayLength * arrayLength);
for (i = 0; i < arrayLength; i++) {
for (j = 0; j < arrayLength; j++) {
sumOfSquares += Math.pow((probabilityMatrix[i][j] - meanProbability), 2);
}
}
standardDeviation = Math.sqrt(sumOfSquares / (arrayLength * arrayLength));
// Compute fairness based on standard deviation threshold
if (standardDeviation >= stdThreshold) {
isFair = false;
} else {
isFair = true;
}
// Optionally provide console output
if (debugFlag) {
console.log('Probability Matrix: ', plotMatrix(probabilityMatrix));
console.log('Mean Probability ' + meanProbability.toFixed(2) + ' +/- ' +
standardDeviation.toFixed(2) + '%');
console.log('Fair: ' + isFair);
}
return isFair;
}
/**
* Plot matrix as 2D string
*
* @param matrix {Array} original array
* @returns {String} string
*/
function plotMatrix(matrix) {
var result = '',
i = 0,
j = 0,
length = matrix.length,
width = matrix[0].length;
for (i = 0; i < length; i++) {
for (j = 0; j < width; j++) {
result += (matrix[i][j] + ' ');
if (j === (width - 1)) {
result += '\n';
}
}
}
return result;
}
/**
* Compute 2D counts matrix
*
* @param array {Array} original array
* @param mutatedArray {Array} modified array
* @param existingCounts {Array} existing matrix
* @returns {Array} resulting matrix[i][j] where i index refers to the original positon
* and j index refers to the new position
*/
function computeCounts(array, mutatedArray, existingCounts) {
var arrayLength = array.length,
newCounts = Array(arrayLength),
i = 0,
j = 0,
newPosition;
// Check if existingCounts were passed in
if (typeof existingCounts === 'undefined') {
existingCounts = null;
for (i = 0; i < arrayLength; i++) {
newCounts[i] = Array(arrayLength);
for (j = 0; j < arrayLength; j++) {
newCounts[i][j] = 0;
}
}
} else {
newCounts = existingCounts;
}
for (i = 0; i < arrayLength; i++) {
newPosition = mutatedArray.indexOf(array[i]);
newCounts[i][newPosition] += 1;
}
return newCounts;
}
isShuffleFair(shuffle, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 100, 1, true);
isShuffleFair(function(array) {
return array;
}, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 100, 1, true);
isShuffleFair(function(array) {
return ([].concat(array)).sort(function(a, b) {return a - b;});
}, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 100, 1, true);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment