// The Dawkins Weasel
// 20111129 e.martin@gold.ac.uk
import java.io.*;
import java.util.*;
import javax.servlet.*;
import javax.servlet.http.*;
public class MethinksItIsLikeAWeasel extends HttpServlet {
// Class for generating sequences
static class SequenceGenerator {
// The target sequence
String TARGET = "METHINKS IT IS LIKE A WEASEL";
// The available characters
String CHARSET = " ABCDEFGHIJKLMNOPQRSTUVWXYZ";
// Number of offspring per generation
int OFFSPRING = 100;
// Mutation ratio
int MUTATION = 20;
// Random number generator
Random RND;
// A character sequence
class Sequence {
// The character buffer
StringBuffer buffer;
// Constructor - Initialize buffer
public Sequence() {
buffer = new StringBuffer();
buffer.setLength(TARGET.length());
}
// Get character at index
char getCharacter(int index) {
return buffer.charAt(index);
}
// Set character at index
void setCharacter(int index, char ch) {
buffer.setCharAt(index, ch);
}
// Set a random character at index
void setRandomCharacter(int index) {
setCharacter(index, CHARSET.charAt(RND.nextInt(CHARSET.length())));
}
// Copy (and mutate) this sequence to child (returns score)
int copyTo(Sequence child) {
int score = 0;
for (int i=0; i < buffer.length(); ++i) {
// Mutate
if (RND.nextInt(MUTATION)==0) child.setRandomCharacter(i);
// Copy
else child.setCharacter(i, getCharacter(i));
// Count target character matches
if (child.getCharacter(i)==TARGET.charAt(i)) ++score;
}
return score;
}
// Return the score for this sequence (target character matches)
int getScore() {
int score = 0;
for (int i=0; i < buffer.length(); ++i)
if (getCharacter(i)==TARGET.charAt(i)) ++score;
return score;
}
// Format this sequence as a string
String toString(int generation) {
return String.format("%3d", generation) + ": " + buffer.toString() + " -- score: " + getScore();
}
}
// Check the character set contains the target
boolean validate(PrintWriter out) {
for (int i=0; i < TARGET.length(); ++i) {
char ch = TARGET.charAt(i);
if (CHARSET.indexOf(ch) < 0) {
out.println("Target character '" + ch + "' is not specified in the Character Set");
return false;
}
}
return true; // All good
}
// Main program loop - generate the target sequence
int generate(PrintWriter out) {
// Abort if inputs are not valid
if (!validate(out)) return 0;
// Initialize random number generator
RND = new Random();
// Initialize parent
Sequence parent = new Sequence();
// Initialize random character sequence for parent
for (int i=0; i < TARGET.length(); ++i) parent.setRandomCharacter(i);
// Print initial sequence
out.println(parent.toString(0));
// Initialize buffers for offspring
Sequence offspring[] = new Sequence[OFFSPRING];
for (int i=0; i < offspring.length; ++i) offspring[i] = new Sequence();
// Generate child sequences and select best child as the next parent
int generation = 0, bestscore = 0;
while (bestscore < TARGET.length()) {
bestscore = 0;
int bestchild = 0;
// Copy/mutate parent to offspring
for (int i=0; i < offspring.length; ++i) {
int score = parent.copyTo(offspring[i]);
if (score > bestscore) {
bestscore = score;
bestchild = i;
}
}
// Swap parent and best child
Sequence nextparent = offspring[bestchild];
offspring[bestchild] = parent;
parent = nextparent;
// Print the new parent
out.println(parent.toString(++generation));
}
return generation;
}
// Return null if s is null or empty, otherwise s
String toNull(String s) { return (s==null) ? null : (s.length()==0) ? null : s; }
// Servlet sequence response
public void toHtmlSequence(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
String
target = toNull(request.getParameter("target")),
offspring = toNull(request.getParameter("offspring")),
mutation = toNull(request.getParameter("mutation")),
charset = toNull(request.getParameter("charset"));
// Replace defaults with form inputs
if (target!=null) TARGET = target;
if (offspring!=null) try { OFFSPRING = Integer.parseInt(offspring.trim()); } catch (NumberFormatException e){}
if (mutation!=null) try { MUTATION = Integer.parseInt(mutation.trim()); } catch (NumberFormatException e){}
if (charset!=null) CHARSET = charset;
response.setContentType("text/html");
PrintWriter out = response.getWriter();
out.print(
"<html><head><title>The Dawkins Weasel</title>\n" +
"<style type=\"text/css\">\n" +
" th.heading { font-size: 1.5em; }\n" +
" table.option { background: #F0F0F0; }\n" +
" th.option, th.button, td.text, td.number, td.output { padding-left: 6px; padding-right: 6px; }\n" +
" th.option { text-align: left; }\n" +
" th.button { background: #D7D7D7; }\n" +
" td.text, td.number { padding-bottom: 6px; }\n" +
" td.text { width: 100%; }\n" +
" input.text { width: 100%; }\n" +
" input.number { width: 50px; text-align: right; }\n" +
" textarea.output { width: 100%; height: " + ((26 * 16) + 4) + "px; }\n" + // 16px per line + 4px
"</style>\n" +
"</head><body onLoad=\"document.inputs.target.focus()\">\n" +
// Page heading and source-link
"<p><table cellspacing=0 cellpadding=0 width=\"100%\"><tr>" +
"<th class=heading align=left>The Dawkins Weasel</th>" +
"<td align=right><a href=\"?source=true\">Source</a></td>" +
"</tr></table></p>\n" +
"<hr size=1>\n" +
"<form name=inputs method=post>\n" +
// Input parameters
"<table class=option cellspacing=0 cellpadding=0>" +
"<tr>" +
"<th class=option nowrap>Target Sequence</th>" +
"<th class=option>Offspring</th>" +
"<th class=button rowspan=4><input type=submit value=\"Generate\"></th>" +
"</tr>\n" +
"<tr>\n" +
"<td class=text><input type=text name=target value=\"" +
TARGET + "\" class=text onFocus=\"select()\"></td>\n" +
"<td class=number nowrap><input type=text name=offspring value=\"" +
OFFSPRING + "\" class=number onFocus=\"select()\"> per generation</td>\n" +
"</tr>\n" +
"<tr>" +
"<th class=option nowrap>Character Set</th>" +
"<th class=option nowrap>Character Mutation</th>" +
"</tr>\n" +
"<tr>\n" +
"<td class=text><input type=text name=charset value=\"" +
CHARSET + "\" class=text onFocus=\"select()\"></td>\n" +
"<td class=number nowrap><input type=text name=mutation value=\"" +
MUTATION + "\" class=number onFocus=\"select()\"> to 1</td>\n" +
"</tr>\n" +
// Output
"<tr><th class=option colspan=3>Output</th></tr>\n" +
"<tr><td class=output colspan=3><textarea class=output readonly>\n"
);
int generations = generate(out);
out.println(
"</textarea></td></tr>\n" +
"<tr><th class=option colspan=3>" + generations + " generations</th></tr>\n" +
"</table>\n" +
"</form>\n" +
"</body></html>"
);
out.flush();
}
// Servlet java source response
void toHtmlSource(HttpServletRequest request, HttpServletResponse response, HttpServlet servlet) throws ServletException, IOException {
String
path = servlet.getServletContext().getRealPath("/"),
name = servlet.getServletConfig().getServletName(),
source = path + "WEB-INF/classes/" + name + ".java";
response.setContentType("text/plain");
PrintWriter out = response.getWriter();
try {
BufferedReader file = new BufferedReader(new FileReader(source));
for (String s = file.readLine(); s!=null; s = file.readLine()) out.println(s);
file.close();
}
catch (FileNotFoundException e) {
out.println("Cannot open file: " + source);
}
out.flush();
}
// Parse servlet request and send response
public void toHtml(HttpServletRequest request, HttpServletResponse response, HttpServlet servlet) throws ServletException, IOException {
if (request.getParameter("source")==null) toHtmlSequence(request, response);
else toHtmlSource(request, response, servlet);
}
// Command-line help text
String getTextHelp() {
return
"Usage:\n\n" +
" MethinksItIsLikeAWeasel [option ...]\n\n" +
"Options:\n\n" +
" -c, --charset CHARACTER_SET\n" +
" The available character set\n\n" +
" -m, --mutation MUTATION_RATIO\n" +
" The ratio of copies to mutations (MUTATION_RATIO:1)\n\n" +
" -o, --offspring NUMBER_OF_OFFSPRING\n" +
" The number of offspring in each generation\n\n" +
" -t, --target TARGET_STRING\n" +
" The target string to mutate into\n\n" +
"Example:\n\n" +
" MethinksItIsLikeAWeasel -o " + OFFSPRING + " -m " + MUTATION +
" -t \"" + TARGET + "\" -c \"" + CHARSET + "\"\n\n" +
" Equivalent to the default settings\n\n";
}
// Parse command-line args and print output to stdout
void toText(String args[]) {
boolean Help = false;
for (int i=0; i < args.length; ++i) {
if ("-c".equals(args[i]) || "--charset".equals(args[i]))
if ((i+1)==args.length) Help = true; else CHARSET = args[++i];
else if ("-o".equals(args[i]) || "--offspring".equals(args[i]))
if ((i+1)==args.length) Help = true;
else try { OFFSPRING = Integer.parseInt(args[++i]); } catch (NumberFormatException e) {}
else if ("-m".equals(args[i]) || "--mutation".equals(args[i]))
if ((i+1)==args.length) Help = true;
else try { MUTATION = Integer.parseInt(args[++i]); } catch (NumberFormatException e) {}
else if ("-t".equals(args[i]) || "--target".equals(args[i]))
if ((i+1)==args.length) Help = true; else TARGET = args[++i];
else Help = true;
}
if (Help) System.out.print(getTextHelp()); else generate(new PrintWriter(System.out, true));
}
}
// Servlet entry point - format as a web page
public void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
doPost(request, response);
}
public void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
new SequenceGenerator().toHtml(request, response, this);
}
// Application entry point - format as text
public static void main(String args[]) { new SequenceGenerator().toText(args); }
}