Last active
November 8, 2021 15:14
-
-
Save ans-4175/82533aa38d7f1e5c5ef3637098e93281 to your computer and use it in GitHub Desktop.
Random password by Genetic Algortihm with syllable constraint
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const charset = "abcdefghijklmnopqrstuvwxyz"; | |
const consonantset = "bcdfghjklmnpqrstvwxyz"; | |
const vocalset = "aiueo"; | |
const VOCAL_TYPE = "vocal"; | |
const CONSONANT_TYPE = "const"; | |
const NUM_TYPE = "num"; | |
const MUTATE_THRESHOLD_LETTERS = 0.9696; | |
const MUTATE_THRESHOLD_CASES = 0.8686; | |
const checkGeneType = (char) => { | |
if (vocalset.includes(char)) | |
return VOCAL_TYPE; | |
else if (consonantset.includes(char)) | |
return CONSONANT_TYPE; | |
else | |
return NUM_TYPE; | |
} | |
const pickOneRandom = (arr) => { | |
return arr[Math.floor(Math.random() * arr.length)]; | |
} | |
function pickNRandom(arr, n) { | |
let result = new Array(n), | |
len = arr.length, | |
taken = new Array(len); | |
if (n > len) | |
throw new RangeError("getRandom: more elements taken than available"); | |
while (n--) { | |
const x = Math.floor(Math.random() * len); | |
result[n] = arr[x in taken ? taken[x] : x]; | |
taken[x] = --len in taken ? taken[len] : len; | |
} | |
return result; | |
} | |
const generateChromosome = (chromLength) => { | |
return [...Array(chromLength)] | |
.map((_) => charset[Math.floor(Math.random() * charset.length)]) | |
.join(""); | |
} | |
const checkFitnessScore = (chromosome) => { | |
// rule1: consonant or vocal cannot be in double occurences sequentially | |
let score = 10 * chromosome.length; | |
let lastGeneType = ""; | |
let lastGeneSeqCount = 1; | |
chromosome.split("").forEach(gene => { | |
if (checkGeneType(gene) === lastGeneType) ++lastGeneSeqCount; | |
if (lastGeneSeqCount > 1) { | |
score = score - 10; | |
lastGeneSeqCount = 1; | |
} | |
lastGeneType = checkGeneType(gene); | |
}); | |
return score; | |
} | |
const mutateCases = (chromosome) => { | |
return chromosome.split("").map(gene => { | |
return (Math.random() < MUTATE_THRESHOLD_CASES ? gene.toLowerCase() : gene.toUpperCase()); | |
}).join(""); | |
} | |
const mutationLetters = (gene) => { | |
switch (gene.toLowerCase()) { | |
case "i": | |
return "1"; | |
case "r": | |
return "2" | |
case "e": | |
return "3" | |
case "a": | |
return "4" | |
case "s": | |
return "5" | |
case "g": | |
return "6" | |
case "z": | |
return "7" | |
case "b": | |
return "8" | |
case "q": | |
return "9" | |
default: | |
return gene | |
} | |
} | |
const mutateLetters = (chromosome) => { | |
return chromosome.split("").map(gene => { | |
return (Math.random() < MUTATE_THRESHOLD_LETTERS ? gene : mutationLetters(gene)); | |
}).join(""); | |
} | |
const geneticProcess = (firstGenes, secondGenes) => { | |
// breed new crossover | |
const randXOver = Math.ceil(Math.random() * firstGenes.length); | |
const firstHalfFront = firstGenes.slice(0, randXOver); | |
const firstHalfLast = firstGenes.slice(randXOver, firstGenes.length); | |
const secondHalfFront = secondGenes.slice(0, randXOver); | |
const secondHalfLast = secondGenes.slice(randXOver, secondGenes.length); | |
let firstXOver = [...firstHalfFront, ...secondHalfLast].join(""); | |
let secondXOver = [...secondHalfFront, ...firstHalfLast].join(""); | |
// mutate letters to numbers | |
firstXOver = mutateLetters(firstXOver); | |
secondXOver = mutateLetters(secondXOver); | |
// mutate cases | |
firstXOver = mutateCases(firstXOver); | |
secondXOver = mutateCases(secondXOver); | |
if (checkFitnessScore(firstXOver) > checkFitnessScore(secondXOver)) | |
return firstXOver | |
else | |
return secondXOver; | |
} | |
const survivalFittest = (population, maxPopulation) => { | |
return population.sort((a,b) => { | |
return checkFitnessScore(b) - checkFitnessScore(a); | |
}).slice(0, maxPopulation); | |
} | |
const generatePasswords = ({ | |
chromosomeLength = 12, maxPopulation = 33, | |
generations = 20, pickCount = 1 | |
}) => { | |
// logic password generator, by genetic programming | |
// initialize population by random chars | |
let population = [...Array(maxPopulation)].map((_) => generateChromosome(chromosomeLength)); | |
population = survivalFittest(population); | |
let currGeneration = 0; | |
while (currGeneration <= generations) { | |
// prepare population to be mated | |
const half = Math.ceil(population.length / 2); | |
const firstHalf = population.slice(0, half); | |
const secondHalf = population.slice(-half); | |
// breeding new | |
firstHalf.forEach(candidate => { | |
population.push(geneticProcess(candidate, pickOneRandom(secondHalf))); | |
}); | |
// sort by fitness score | |
population = survivalFittest(population, maxPopulation); | |
currGeneration++; | |
} | |
// pick population | |
return pickNRandom(population, pickCount); | |
} | |
(async () => { | |
const pickedPasswords = generatePasswords({}); | |
console.log(pickedPasswords); | |
})(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment