From 364a4bc48dc8680b1e8b947575a81c92256b6f6d Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Fri, 2 Oct 2009 08:47:08 +0000 Subject: methinks it is like a weasel --- Makefile | 7 +++ weasel.c | 171 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 178 insertions(+) create mode 100644 Makefile create mode 100644 weasel.c 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 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 + * + * 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 +#include +#include +#include +#include +#include +#include + +/* 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; +} -- cgit v1.2.3