bmg@mck-csc.UUCP (Bernard M. Gunther) (10/29/85)
This is my implementation of flibs (see the Scientific American, This is my implementation of flibs (see the Scientific American,
November 1985, Computer Recreations column). It is fully parameterized
and will work on a PC also. If you are going to compile it on a
PC remember to declare malloc (char *malloc()).
I have another few versions including one for the PC only which includes
a graphic display of all the flibs which are currently alive and another
version which is being tested which has a few patterns and the idea is
to accept or reject them. If anyone out there is interested, I'd be
willing to post these or mail them to you.
This is just a single file. A standard invoking of the program would
be:
flibs -n10 -s4 -p6 100101
which says:
10 flibs
4 states per flib
pattern length of 6
pattern of 100101
Feel free to mail me questions or comments. Hope you like it.
Bernie Gunther
ihnp4!mit-eddie!mck-csc!bmg
#!/bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #!/bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
# flibs.c
# This archive created: Tue Oct 29 11:45:39 1985
export PATH; PATH=/bin:$PATH
if test -f 'flibs.c'
then
echo shar: over-writing existing file "'flibs.c'"
fi
cat << \SHAR_EOF > 'flibs.c'
/* This is a flibs program as taken from Scientific American, Nov. 1985 */
#include <stdio.h>
int nflibs = 10;
int nstates = 4;
int psize = 6;
int finish = 100;
int iternum = 100;
int buckets = 20;
int quick = 0;
int mcount = 1;
int npatterns = 1;
int pbreed = 30;
int *chrom; /* [nflibs][ nstates*4]; */
int *state; /* [nflibs]; */
int *score; /* [nflibs]; */
int *pattern; /* [psize]; */
int *hist; /* for histogram */
int max,min; /* min/max check values */
int top,bot; /* holder of position */
int cmax, cmin;
main(argc, argv)
int argc;
char *argv[];
{
int i,j;
int generation =0;
int sinput;
char c;
char *s;
sinput = 1;
while ( sinput < argc && *argv[sinput] == '-') {
c = *(argv[sinput]+1);
switch(c) {
case 'n':
nflibs = atoi( argv[sinput]+2);
break;
case 's':
nstates = atoi( argv[sinput]+2);
break;
case 'p':
psize = atoi( argv[sinput]+2);
break;
case 'f':
finish = atoi(argv[sinput]+2);
break;
case 'i':
iternum = atoi(argv[sinput]+2);
break;
case 'q':
quick = 1;
break;
case 'b':
buckets = atoi(argv[sinput]+2);
break;
case 'c':
mcount = atoi(argv[sinput]+2);
break;
case 'm':
pbreed = atoi(argv[sinput]+2);
break;
default:
break;
}
sinput++;
}
if (argc < npatterns+sinput) {
printf(
"Flibs [-n number of flibs] [-s number of states] [-p pattern size]\n");
printf(" [-f finish threshhold] [-i number of iterations per test] [-quick]\n");
printf(" [-b buckets] [-c how many must solve to finish] [-m % chance to mate ]\n");
printf(" pattern \n");
exit(1);
}
printf("starting \n");
init();
for (j=0; j<npatterns; j++) {
s = argv[sinput+j];
for (i=0; i< psize; i++) {
if ( *s == '\0') {
printf("error in pattern %d \n",j);
exit(1);
}
pattern[i] = (*s++ == '0') ? 0 : 1;
}
}
while ( max < finish || cmax < mcount) {
test();
check();
if ( getrand(100) < pbreed)
breed();
mutate();
if (!quick)
printf(" Generation #%4d: Max = %3d(%2d), min = %3d(%2d) ",
generation++,max,cmax,min,cmin);
for(i=0; i<buckets+1; i++) {
if (hist[i] == 0)
printf(" ");
else if (hist[i] > 35)
printf("*");
else if (hist[i] > 9)
printf("%c", (char)('A'+hist[i]-10));
else printf("%d",hist[i]);
}
printf("\n");
}
printf("finished \n");
}
init()
{
int i,j;
extern long time();
chrom = (int *)malloc( nflibs*(nstates*4) *sizeof(i));
state = (int *)malloc(nflibs * sizeof(i)); /* [nflibs]; */
score = (int *)malloc(nflibs * sizeof(i)); /* [nflibs]; */
pattern = (int*)malloc(psize *sizeof(i)); /* [psize]; */
hist = (int*) malloc((buckets+1)*sizeof(i));
srand( (unsigned) time( (long *) 0));
for (i=0;i<nflibs; i++) {
state[i] = 0; /* getrand(nstates); */
for (j=0; j<nstates*4; j += 2) {
chrom[i* (nstates*4) + j] = getrand(2);
chrom[i* (nstates*4) + j+1] = getrand(nstates);
}
}
max = 0;
min = 0;
}
test()
{
int i,j,l;
int stat;
for(i=0; i<nflibs; i++) {
score[i] = 0;
stat = state[i];
for (j=0; j< iternum; j++) {
l = 4*stat + 2*pattern[j%psize];
if ( chrom[i*(nstates*4) + l] ==
pattern[((j+1)%psize)])score[i]++;
stat = chrom[(i* (nstates*4)) + l+1];
if ( stat> nstates) printf("error!! stat = %d i=%d j=%d l=%d \n",stat,i,j,l);
}
}
}
check()
{
int i,x;
min = iternum;
max = 0;
cmin = 0;
cmax = 0;
for( i =0; i<nflibs; i++) {
if ( score[i] > max) {
max = score[i];
top = i;
cmax = 0;
}
if (score[i] < min) {
min = score[i];
bot = i;
cmin = 0;
}
}
for (i=0; i<buckets+1; i++) hist[i] = 0;
for( i =0; i<nflibs; i++) {
if ( score[i] == max) cmax++;
if ( score[i] == min) cmin++;
x = (int) (score[i]/(iternum/buckets));
hist[(x>buckets)?buckets:x]++;
}
if (cmax >1) {
i = getrand(cmax)+1;
for (x=0; x<nflibs && i; x++)
if (score[x] == max) {
i--;
top=x;
}
}
if (cmin >1) {
i = getrand(cmin)+1;
for (x=0; x<nflibs && i; x++)
if (score[x] == min) {
i--;
bot=x;
}
}
}
breed()
{
int i,x,c1,c2,temp,partner;
c1 = getrand(nstates*4);
c2 = getrand(nstates*4);
partner = top;
while (partner == top) partner = getrand(nflibs);
for (i=c1; i != c2; i = (i+1)%(4*nstates))
chrom[bot* (nstates*4) + i] = chrom[partner* (nstates*4) + i];
for (i=c2; i != c1; i = (i+1)%(4*nstates))
chrom[bot* (nstates*4) + i] = chrom[top* (nstates*4) + i];
}
mutate()
{
int x,y;
x = getrand(nflibs);
y = getrand(nstates*4);
chrom[x* (nstates*4) + y] = getrand ((y%2 == 1)?nstates:2);
}
getrand(i)
int i;
{
return( (rand()%i));
}
SHAR_EOF
# End of shell archive
exit 0