aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2009-10-02 08:47:08 +0000
committerDimitri Sokolyuk <demon@dim13.org>2009-10-02 08:47:08 +0000
commit364a4bc48dc8680b1e8b947575a81c92256b6f6d (patch)
tree05be7f1e0416914f257093e37aac894be822f018
methinks it is like a weasel
-rw-r--r--Makefile7
-rw-r--r--weasel.c171
2 files changed, 178 insertions, 0 deletions
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..c00627d
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,7 @@
+# $Id$
+
+PROG= weasel
+NOMAN=
+LDADD+= -lcurses
+
+. include <bsd.prog.mk>
diff --git a/weasel.c b/weasel.c
new file mode 100644
index 0000000..ca70e32
--- /dev/null
+++ b/weasel.c
@@ -0,0 +1,171 @@
+/* $Id$ */
+/*
+ * Copyright (c) 2009 Dimitri Sokolyuk <demon@dim13.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/queue.h>
+#include <assert.h>
+#include <curses.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <term.h>
+
+/* const char aim[] = "METHINKS IT IS LIKE A WEASEL"; */
+const char aim[] = "THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG'S BACK 1234567890 TIMES.";
+const char alphabet[] = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEEFGHIJKLMNOPQRSTUVWXYZ[\\]^_abcdefghijklmnopqrstuvwxyz{|}~";
+extern int LINES;
+int mutationrate = 100; /* 1/n */
+
+TAILQ_HEAD(creatures, creature) generation;
+struct creature {
+ char *genom;
+ int length;
+ float fitness;
+ TAILQ_ENTRY(creature) link;
+} *cp;
+
+char
+rndchar()
+{
+ return alphabet[arc4random() % (sizeof(alphabet) - 1)];
+}
+
+void
+initpopulation(int length, int number)
+{
+ int i;
+
+ TAILQ_INIT(&generation);
+
+ while (number--) {
+ cp = malloc(sizeof(struct creature));
+ assert(cp);
+ cp->genom = malloc(length + 1);
+ assert(cp->genom);
+ cp->length = length;
+ for (i = 0; i < length; i++)
+ cp->genom[i] = rndchar();
+ cp->genom[i] = '\0';
+ cp->fitness = 0.0;
+ TAILQ_INSERT_HEAD(&generation, cp, link);
+ }
+}
+
+void
+sortfitness()
+{
+ struct creature *next;
+
+ for (cp = TAILQ_FIRST(&generation); cp; cp = next) {
+ next = TAILQ_NEXT(cp, link);
+ if (next && next->fitness > cp->fitness) {
+ TAILQ_REMOVE(&generation, next, link);
+ TAILQ_INSERT_BEFORE(cp, next, link);
+ next = TAILQ_NEXT(cp, link);
+ sortfitness(); /* FIXME */
+ }
+ }
+}
+
+void
+calculatefitness()
+{
+ int i, good;
+
+ TAILQ_FOREACH(cp, &generation, link) {
+ good = 0;
+ for (i = 0; i < cp->length; i++)
+ if (aim[i] == cp->genom[i])
+ good++;
+ cp->fitness = good / (float)cp->length;
+ }
+}
+
+void
+intercourse(int probability)
+{
+ int i, length;
+ struct creature *parent[2], *child, *next;
+
+ parent[0] = TAILQ_FIRST(&generation);
+ parent[1] = TAILQ_NEXT(parent[0], link);
+ length = strlen(parent[0]->genom);
+
+ /* produce children */
+ TAILQ_FOREACH(cp, &generation, link) {
+ child = malloc(sizeof(struct creature));
+ assert(child);
+ child->genom = malloc(length + 1);
+ assert(child->genom);
+ child->length = length;
+
+ /* recombine and mutate */
+ for (i = 0; i < length; i++) {
+ if (arc4random() % probability == 0) {
+ child->genom[i] = rndchar();
+ } else {
+ child->genom[i] = parent[arc4random() % 2]->genom[i];
+ }
+ }
+ child->genom[i] = '\0';
+ TAILQ_INSERT_HEAD(&generation, child, link);
+ }
+
+ /* remove old generation */
+ for (cp = parent[0]; cp; cp = next) {
+ next = TAILQ_NEXT(cp, link);
+ TAILQ_REMOVE(&generation, cp, link);
+ free(cp->genom);
+ free(cp);
+ }
+}
+
+void
+printpopulation()
+{
+ move(0, 0);
+ printw("%1.3f\t%s\n\n", 1.0, aim);
+ TAILQ_FOREACH(cp, &generation, link)
+ printw("%1.3f\t%s\n", cp->fitness, cp->genom);
+ refresh();
+}
+
+int
+main()
+{
+ int i;
+
+ struct creature *first;
+ initscr();
+ setterm("vt220");
+ initpopulation(strlen(aim), LINES - 5);
+
+ for (i = 0;; i++) {
+ intercourse(mutationrate);
+ calculatefitness();
+ sortfitness();
+ first = TAILQ_FIRST(&generation);
+ printpopulation();
+ if (strcmp(first->genom, aim) == 0)
+ break;
+ }
+
+ printw("\nhalted after %d generations\n", i);
+ refresh();
+ endwin();
+
+ return 0;
+}