Skip to content

Instantly share code, notes, and snippets.

@ademar111190
Last active January 3, 2016 15:49
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ademar111190/8485329 to your computer and use it in GitHub Desktop.
Save ademar111190/8485329 to your computer and use it in GitHub Desktop.
A little algorithm using genetic concepts to find a secret word.
#!/usr/bin/python
# -*- coding: utf-8 -*-
__author__ = "Ademar Alves de Oliveira"
__copyright__ = "Copyright 2014, Ademar"
__credits__ = ["Diego Queiroz"]
__license__ = "GPL"
__version__ = "1.5"
__maintainer__ = "Ademar Alves"
__email__ = "ademar111190@gmail.com"
from random import random, choice, randint
from collections import OrderedDict
class witsw:
#variables to be changed
maxWordSize = 1000 #the max size of the word
populationSize = 100 #the size of the population
populationToCrossOver = 10 #the number of qualified to reproduction
mutationRate = 0.01 #the mutation rate
generationsLimite = 0 #max number of generations, 0 no limit
minSimilarity = 0 #min similarity target to stop
secretWord = "Top Secret" #the word to be founded, use only python asc characters! and the len need be equal or minor then maxWordSize. Set empty to generate a randow secret word with maxWordSize size
#script variables
letters = []
population = []
def __init__(self):
if(len(self.secretWord) == 0):
for i in range(self.maxWordSize):
self.secretWord += chr(int(random() * 256))
print "random secret word is %s" % (self.secretWord)
for letter in range(256):
self.letters.append(chr(letter))
for i in range(self.populationSize):
self.population.append(self.makeRandomWord())
def makeRandomWord(self):
wordSize = int(self.maxWordSize * random())
randomWord = ""
for w in range(wordSize):
randomWord += choice(self.letters)
return randomWord
def pontualizeWord(self, word):
diff = abs(len(self.secretWord) - len(word)) * 255
for i in range(min(len(self.secretWord), len(word))):
diff += self.getBitDifference(ord(self.secretWord[i]), ord(word[i]))
return diff
def getBitDifference(self, numA, numB):
diff = 0
numC = numA ^ numB
while numC > 0:
diff += numC % 2
numC /= 2
return diff
def rankPopulation(self):
classificationMap = {}
for p in self.population:
classificationMap[p] = self.pontualizeWord(p)
classificationMap = OrderedDict(sorted(classificationMap.items(), key=lambda t: t[1]))
self.population = classificationMap.keys()
return classificationMap.values()
def makeNewGeneration(self):
betters = self.population[:self.populationToCrossOver]
self.population = [b for b in betters]
while len(self.population) < self.populationSize:
for b1 in betters:
for b2 in betters:
self.population.append(self.crossover(betters[int(random()*self.populationToCrossOver)], betters[int(random()*self.populationToCrossOver)]))
if len(self.population) >= self.populationSize:
return
def crossover(self, father, mother):
#make a children
lenMin = min(len(father), len(mother))
children = []
for i in range(lenMin):
if self.mutationRate >= random(): #do a mutation
children.append(chr(randint(0,255)))
else:
randomMask = randint(0,255)
children.append(chr((ord(father[i]) & randomMask) | (ord(mother[i]) & ~randomMask)))
#change the word size with mutation
if self.mutationRate >= random() and lenMin > 0:
mutatioType = random()
if mutatioType < 0.5: #type add letter
pos = int(random() * lenMin)
if pos >= lenMin: #add on end
children.append(chr(int(random() * 256)))
else: #add on middle or begin
children.append(children[pos])
children[pos] = chr(int(random() * 256))
else: #type delete a letter
del children[int(random() * lenMin)]
#return the children as String
return ''.join(children)
def run(self):
temp = None
if self.generationsLimite <= 0:
generation = 0
while not temp:
generation += 1
temp = self.runGeneration(generation)
else:
for generation in range(self.generationsLimite):
temp = self.runGeneration(generation)
if temp:
break
return temp
def runGeneration(self, generation):
rank = self.rankPopulation()
print "better at generation %d is \"%s\" with %d points" % (generation, self.population[0], rank[0])
if rank[0] <= self.minSimilarity:
return self.population[0]
self.makeNewGeneration()
return None
print "The Secret word is %s" % (witsw().run())
@ademar111190
Copy link
Author

To run download the script and run on console:

python whatIsTheSecretWord.py

Try change the secretWord variable, and the others variables too.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment