Skip to content

Instantly share code, notes, and snippets.

@jeremybradbury
Last active May 18, 2024 07:27
Show Gist options
  • Save jeremybradbury/20b563037f7ab5bc795d45435e0c8450 to your computer and use it in GitHub Desktop.
Save jeremybradbury/20b563037f7ab5bc795d45435e0c8450 to your computer and use it in GitHub Desktop.
Fisher Yates Shuffle
// Crypto PseudoRandom Shuffle: one right way to randomize, esp for gaming
// https://replit.com/@jeremybradbury/CSPRNG-Fisher-Yeats-Shuffle
// NodeJS - CJS version (backward comaptible)
const crypto = require("crypto");
// the secret sauce
const getRndInt = (bytes) =>
parseFloat(
parseFloat(crypto.randomBytes(bytes).toString("hex"), 16).toString(10),
10
);
// the SDK
function getCSPRNG(min, max) {
// validate
if (min == null || max == null) {
throw new Error("min and max must be defined");
}
if (min < 0) {
return console.error("min must be at least 0");
}
if (min > max) {
return console.error("min must be less than max");
}
let bytes;
// choose the correct array type
switch (true) {
case max < 1:
console.error("max must be at least 1");
return;
case max < 256: // 1-255
bytes = 1;
break;
case max < 65536: // 256-65535
bytes = 2; // default
break;
case max < 4294967296: // 65536-4294967295
bytes = 4;
break;
default:
console.error("max must be no more than 4294967295");
return;
}
let randomNumber = getRndInt(bytes);
let attempts = 1;
while (randomNumber > max || randomNumber < min) {
randomNumber = getRndInt(bytes); // retry until result is in range
attempts++; // track failed generations
}
// console.debug({randomNumber, attempts });
return randomNumber;
};
// const random = () => Math.random(); // between 0 and 1
const cryptoRandom = () => getCSPRNG(0, 10) / 10; // between 0 and 1
// Fisher–Yates shuffle - https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
function shuffle (array = []) {
let index = array.length;
while (index) {
const next = Math.floor(cryptoRandom() * index--);
const temp = array[index];
if (array[next] == null) { // == null, includes undefined too, but not '' or 0
continue;
}
array[index] = array[next]; // set to a random value
// console.log(next, array[next]);
array[next] = temp; // swap with the previous number
}
return array;
};
// implementation variables
const getDie = (length = 6) => Array.from({ length }, (v, i) => i + 1);
const getCoin = () => getDie(2);
const langs = ['C++', 'C#', 'Java', 'JavaScript', 'Python', 'Ruby', 'PHP', 'Go', 'CSS', 'HTML', 'SQL', 'TypeScript', 'Swift', 'Kotlin', 'Rust', 'Scala'];
// usage examples - logged simplest to most complex
console.log("coin flip:", shuffle(getCoin())[0] === 1 ? 'heads' : 'tails'); // grab the first item in the array
console.log("d6 roll:", shuffle(getDie(6))[0]); // grab the first item in the array
console.log("d20 roll:", shuffle(getDie(20))[0]); // grab the first item in the array
console.log("languages winner:", shuffle(langs)[0]); // grap the first item in the array
console.log("languages shuffled:", shuffle(langs)); // show the whole array, randomized
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment