/
Weasel.js
142 lines (118 loc) · 3.62 KB
/
Weasel.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
/**
* @class Weasel
* @author Ed Spencer (http://edspencer.net)
* JavaScript implementation of Richard Dawkins' Weasel Program
* (http://en.wikipedia.org/wiki/Weasel_program)
*/
Weasel = function(config) {
var config = config || {},
defaults = {
target : "METHINKS IT IS A LIKE WEASEL",
mutateRate : 0.9,
numChildren: 5
};
for (key in defaults) {
config[key] = config[key] || defaults[key];
}
for (key in config) {
this[key] = config[key];
}
};
Weasel.prototype = {
/**
* Starts the search towards the target. Returns an array of all generated ancester strings
* @param {String} seed The seed string (defaults to a random string)
* @return {Array} The array of ancestors
*/
find: function(seed) {
var seed = seed || this.generateSeed(this.target.length),
species = [seed],
current = seed;
while (this.score(current) < current.length) {
var parent = species[species.length - 1],
children = this.breedChildren(parent),
current = this.select(children);
species.push(current);
}
return species;
},
/**
* Breeds the desired number of children by mutating a parent string
* @param {String} parent The parent string
* @param {Number} num The number of children to beed (defaults to this.numChildren)
* @return {Array} Array of mutant children
*/
breedChildren: function(parent, num) {
var children = [];
for (var i = this.numChildren; i >= 1; i--){
var a = this.mutate(parent);
children.push(a);
}
return children;
},
/**
* Function description
* @param {String} parent The string that will be mutated
* @return {String} The mutated version of the
*/
mutate: function(parent) {
var newStr = "",
length = parent.length;
for (var i=0; i < length; i++) {
var character = parent[i],
incorrect = parent[i] != this.target[i],
mutates = Math.random() < this.mutateRate;
newStr += incorrect && mutates
? this.characters[Math.floor(Math.random() * this.characters.length)]
: character;
};
return newStr;
},
/**
* Selects the fittest string from an array
* @param {Array} children The children to score
* @return {String} The winning string
*/
select: function(children) {
var bestScore = 0,
bestChild = children[0];
for (var i = children.length - 1; i >= 0; i--){
var score = this.score(children[i]);
if (Math.max(bestScore, score) > bestScore) {
bestChild = children[i];
bestScore = score;
}
};
return bestChild;
},
/**
* Assesses a string using a selection function, returning the string's 'score'
* @param {String} str The string to apply the selection function
* @return {String} The value of the string
*/
score: function(str) {
var score = 0;
for (var i=0; i < str.length; i++) {
if (str[i] == this.target[i]) score += 1;
}
return score;
},
/**
* Returns a random string of the length given
* @param {Number} length The desired seed string length
* @return {String} The seed string
*/
generateSeed: function(length) {
var str = "";
for (var i=0; i < length; i++) {
str += this.characters[Math.floor(Math.random() * this.characters.length)];
};
return str;
},
/**
* @property characters
* @type String
* A string which contains all the characters the Weasel will mutate to
*/
characters: " ABCDEFGHIJKLMNOPQRSTUVWXYZ"
};