The code was written for fun, and it is by far the most complicated program I've written yet. It's also my first step from C into C++. I have some training in algorithms but almost none in coding. It is pretty long and I don't expect anyone to analyze the whole thing. I would, however, appreciate it if anyone has the time to scan through looking for bad coding practice and give me some style suggestions or topics to look into that would help me write better/more efficient code. Also I'd like to hear about it if you spot any room for OOP in this code as I will be venturing into that area soon and would love to use it in this program. There is a description of what the code does at the bottom if you would like to get an idea of what is being accomplished.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#include <string>
#include <math.h>
using namespace std;

/*
Idea for program comes from Richard Dawkins' "The Blind Watchmaker"
*/

char chargen(void);  
//Generates a random character for insertion

string sentgen(int length);  
//Generates the initial random sentence

int compare(string ancestor,string s);  
//discovers the number of correct letters in each baby

void reproduce(string ancestor, string s[], string target, int length);
//produces 8 mutated offspring

int mutations();  
//randomly determines a number of mutations between 0 and 10

int whichone(int length); 
//randomly determines which letter to mutate

int wholives(int alike[8], int *who);  
//determines which baby survives to reproduce

string evolution(string initial, string target, int *alike);  //coordinates the evolution

string initialize();  
//determines the target string and such

void introduction();  //the concept

long double probability(int length);  
//determines the alternative probability, could be done inline

int main()
{
	string initial, target, parents[3000], tab = "   ";
	int complete = 0, count = 1;
	srand((unsigned)time(0));          //seeds rand()
	introduction();                            //the background
	target = initialize();                   //user input
	int length = target.length();
	initial = sentgen(length);     //generates initial random sentence

	cout << "Ancestor:  " << initial << endl << endl << "Enter to continue." << endl;
	fflush(stdin);
	getchar();
	
	parents[0] = initial;

	for (int k = 1; (unsigned int)complete < target.length(); k++)
	{
//main loop generates offspring and chooses the next ancestor thru evolution().
		parents[k] = evolution(parents[k-1], target, &complete);
		cout << parents[k];//output
		count++;//generation counter
		cout << tab << "|| Good Chars:  " <<  complete;
		cout << " || Count:  " << count << endl;
	}
	cout << endl << "Generations to completion:  " << count << endl;
	cout << "Probability of this string randomly mutating without natural selection:  ";
	cout << endl << "One in " << probability(target.length()) << endl;
	cout << endl << "Enter to exit." << endl;
	getchar();
}

string evolution(string initial, string target, int *complete)
{
//controls the evolutionary process through calls to the other functions
	string s[8], nancestor;//s-array of 8 strings, nancestor - next ancestor
	int alike[8], who, size = target.length();
	//alike-int array holding the number of correct chars
	//who - allows the winner to be accessed without calling wholives() twice.  probably not needed

	reproduce(initial, s, target, size);    //makes the babies
	for (int y = 0; y < 8; y++)	alike[y] = compare(target,s[y]); //gets the #of correct chars for each
	nancestor = s[wholives(alike, &who)];//identifies the chosen

	*complete = alike[who];   //CBR to MAIN(), allows main loop to know when it is finished

	return nancestor;
}


int compare(string target,string s)//outputs # of correct characters
{
	int alike = 0;
		for (int i = 0; (unsigned int)i < target.length(); i++)
		{
			if (target[i] == s[i]) alike++;
		}
	return alike;
}


void reproduce(string ancestor, string s[], string target, int length)
{//makes the babies
	int mut = mutations();//# of mutations
	for (int i = 0; i <= 7; i++)	s[i] = ancestor;//babies are first copies of ancestor
	for (int k = 0; k <= 7; k++)
	{
		for (int j = 0; j <= mut; j++)//then they are mutated
		{
			int L = whichone(ancestor.length());
			if (ancestor[L] == target[L]) continue;//if a char is correct don't change it
			s[k].replace(L, 1, 1, chargen());	
		}
	}
}
char chargen(void)
{
	char r,s;

	while (1)
	{
	s = rand() % 100;  //could be more efficient (do research on rand division and such)
	r = s + 25;
	if ( (r == 44) || (r == 46) || (r == 32) || (r == 33) || (r == 63) || (r == 59) ||\
		(r == 58) || ( (r >= 65) && (r <= 90) ) || ((r >= 97) && (r <= 122)) || \
		(r == 39) || (r == 34))   //upper, lower, space, punctuation (ASCII)
		break;
	else continue;
	}
return r;
}

int whichone(int length)//randomly determines which char to change
{                    //randomly determines which char to change
	double x = RAND_MAX/length;
	double r = ((rand()/x));
	return (int)r;
}

int mutations()          //random # of mutations
{
	double mut = ((rand() / 3276.002442));//up to ten
	return (int) mut;
}

string sentgen(int length)
{                  //generates initial sentence
	string st;
	for(int i = 0; i < length/*strlen(s)*/; i++)	st += chargen();
	return st;
}

int wholives(int alike[8], int *who)
{                 //goes thru alike array and chooses next ancestor
	int winner = 0;
	for (int i = 0; i < 8; i++)
	{
		if (alike[i] > alike[winner])
		{
			winner = i;
		}
	}
	*who = winner;//call by reference
	return winner;
}


string initialize()
{                        //User input
	string target;
	int choice = 0;
	cout << "1.  Default starting sentence." << endl \
		 << "2.  Enter starting sentence." << endl;
	cin >> choice;

	if (choice == 2) 
	{
		cout <<endl<< "Upper and lower case letters, spaces, and common punctuation are \
allowed." << endl << "Input target sentence:  " ;
		cin.ignore();	cin.clear();
		getline(cin, target);
		cout << endl;
	}
	else target = "Also Spracht Zarathustra";
	cout << "Target:    " << target << endl;

	return target;
}
long double probability(int length)
{                     //could be inline
	return pow((long double)61, (long double)length);
void introduction()
{
cout<<"This program attempts to demonstrate the fact" << endl; 
cout<<"that natural selection is not random chance, but a chance-" << endl; 
cout<<"driven process guided by positive and negative feedback."  << endl; 
cout<<"This concept is demonstrated by randomly generating an" << endl; 
cout<<"""ancestor"" sentence of the length of the target string." << endl; 
cout<<"Each ""generation"" eight babies are born with variations." << endl;
cout<<"The offspring closest to the target sentence survive as a" <<endl; 
cout<<"result of natural selection and passes it's ""genes"" on " <<endl; 
cout<<"to the next generation with a random number of mutations." << endl; 
cout<<"The remaining progeny die off.  One unrealistic aspect of " <<endl; 
cout<<"the simulation is the frequency of mutation, but this does" <<endl; 
cout<<"not ruin the concept; it only shrinks the number of " << endl;
cout<<"generations required for convenience (and to prevent stack" << endl; 
cout<<"overflow)." << endl << endl;
cout<<"The credit for the idea goes to Richard Dawkins in "<< endl;
cout<<"'The Blind Watchmaker'.  I just implemented the program" << endl;
cout<<"for practice in coding."  << endl << endl;

I always pass things as const if the function will not change them. Also you should pass anything bigger than a single int or double by reference. Both techniques are shown here:

int compare(const string &target, const string &s)//outputs # of correct characters
{
	int alike = 0;
		for (int i = 0; (unsigned int)i < target.length(); i++)
		{
			if (target[i] == s[i]) alike++;
		}
	return alike;
}

Goodluck!

Dave

Please when posting to these forums, wrap your code in code tags (like daviddoria did above).

Use either:

[code] ... [/code]
or
[code=c++]... [/code]

The second form provides for syntax highlighting and line numbers.

I like the feedback so far, thanks and keep it coming.
And I did use [code] ... [/code], i didn't do [code=c++]... [/code]".
If I hadn't used code tags, I don't think you would see (Toggle Plain Text) above... But let me know if I'm missing something.

While this is not critical in any way, you should note that the large outputting section at the bottom won't actually print any of the embedded quotes. In this line:

cout<<"Each ""generation"" eight babies are born with variations." << endl;

You are actually writing separated strings but the compiler is concatenating them for you, so no error is given. You want something like this:

cout<<"Each \"generation\" eight babies are born with variations." << endl;

The backslash make it into a special control character.

I'm impressed at the use of genetic programming; I'm doing some work with it as well. As for use of objects, anything more complicated could like use objects to store genes and whatnot, instead of using strings like you did in this example.

Oh, so instead of using evolution as a control function, create a class with all the randomizing functions as members? I could see that... Especially since I plan on proceeding down the road of genetic programming, an object could hold the individual genes as well as the functions which mutate them. Could probably zoom out another level as well as the ideas get more complicated, and the class would reduce the chain of pointers being passed back and forth, too! Easier to control the scope of variables to all the functions that need them. Thanks, that's great. I started reading about the concepts today but I wasn't yet really seeing how to use them and such.

And I had noticed the quotes weren't printing but hadn't figured out how to do it yet, I left it in hoping somebody would advise me. I was thinking along the lines of %%, but naturally with quotes that would just concatenate the strings (I hadn't realized that was what was happening yet, though). Thanks alot!

I always pass things as const if the function will not change them. Also you should pass anything bigger than a single int or double by reference.

Goodluck!

Dave

Thanks. I see the advantage of passing them as a const, but I don't see the advantage of passing larger variables by reference if they aren't able to be modified due to the const. Would love to be enlightened, though. I would guess it is an efficiency thing, so the variable doesn't have to be copied in it's entirety for the function?

Yep, the const is just so you stop yourself from accidentally changing it if you don't want to change it. The reference is so it does not get copied by value which, as you say, is to save memory and I guess time. Even though you can't change it, the reference means you are looking at the values from the original variable.

First of all, this is an excellent effort and an interesting program. Here are some suggestions.

  • Give the user the option to go again.
  • Use C++ style includes: cstdio, cstdlib, etc.
  • Never let a line go over, say, 78 columns. (Definintely not over 80.)
  • Splitting string constants across lines can be done like this:
    cout << "\nUpper and lower case letters, spaces, "
                    "and common punctuation are allowed."
                    "\nInput target sentence:  ";

    As noted by death_oclock, this mechanism is why you didn't get the double-quotes you wanted around ancestor (and no syntax error either).

  • It's best to have an overall program description at the top. Since your intro message is a good summary, you could put something like this at the top of your program.
    // Sentence Evolver by Me & Dawkins
    
    const char* Description =
    "This program attempts to demonstrate the fact\n"
    "that natural selection is not random chance, but a chance-\n"
    ...
    "\"ancestor\" sentence of the length of the target string.\n"
    ...;

    Then get rid of the function "introduction" and replace the call to it by cout << Description;

  • Use \n for newline when there's already a double-quoted string right there. E.g:
    cout << "Ancestor:  " << initial << endl << endl
              << "Enter to continue." << endl;
    // could be:
        cout << "Ancestor:  " << initial << "\n\nEnter to continue.\n";
  • In general, I would rather see the comments before their target (rather than after or on the same line). I suppose that's just my particular taste, though.
  • Overall there are too many comments. This can be alleviated in two ways. Firstly, eliminate text-book comments like these:
    srand((unsigned)time(0));          //seeds rand()
    ...
    	*who = winner;//call by reference

    Text book comments are there for people learning the language. You should assume that the reader knows the language and even the overall strategy / structure of the program since that should be described at the top.

    Secondly, use more specific function (or variable) names so you don't feel the need to also say what the function is doing in a little comment.
    sentgen ==> generateRandomSentence
    compare ==> countCorrectLetters
    count ==> generation or nGeneration (if you're part Hungarian)
    Use verbs for functions and nouns for variables.

Overall I like it. Definitely post the next generation.

Thanks alot! Lots of great feedback, like I said I appreciate it since I'm pretty much learning in a bubble. I took an abbreviated basic C class over the summer, and I've gotten a lot of practice with general algorithms and some coding in other languages (VHDL, assembly) as an Electronics Engineer, but haven't seen much in this area other than the generic "Make sure you comment your code" line.

Sorry to DP, couldn't seem to edit my last one.
I've tried to implement every piece of advice I received. Hopefully it's all good advice, right? As I implemented each suggestion, it sure felt like good practice and I could see the value in it.

fflush(stdin) gone
Many comments eliminated or replaced with more descriptive variable names
using namespace std;
const and CBR implemented where appropriate
C++ includes used
user given option to repeat
all ASCII characters space thru tilde now allowed
double quotes corrected
program description at top (still in function, was easier and, I felt, cleaner)
/n used where appropriate
lines shortened
[code = c++] used :)

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <string>
#include <cmath>

/*
Programmer:  Phillip Daw
Idea for program comes from Richard Dawkins' "The Blind Watchmaker"
*/

void introduction()
{
cout<<"This program attempts to demonstrate the fact\n" 
"that natural selection is not random chance, but a chance-\n"
"driven process guided by positive and negative feedback.\n"
"This concept is demonstrated by randomly generating an\n"
"\"ancestor\" sentence of the length of the target string.\n" 
"Each \"generation\" eight babies are born with variations.\n"
"The offspring closest to the target sentence survive as a\n" 
"result of \"natural selection\" and passes it's \"genes\" on \n"
"to the next generation with a random number of mutations.\n" 
"The remaining progeny die off.  One unrealistic aspect of \n" 
"the simulation is the frequency of mutation, but this does\n" 
"not ruin the concept; it only shrinks the number of \n"
"generations required for convenience (and to prevent stack\n" 
"overflow).\n\n"
"The credit for the idea goes to Richard Dawkins in \n"
"'The Blind Watchmaker'.  I just implemented the program\n"
"for practice in coding.\n\n";
}

char GenerateCharacter(void);
string GenerateString(const int length);  //used to initialize
int CountCorrectLetters(const string &ancestor, string s);
int HowManyMutations();
int SelectRandomCharacter(const int length);
int SelectString(int AlikeChars[8], int *who);
string Evolve(const string *InitialString,
	const string *target, int *AlikeChars);
string Initialize();
long double CalculateProbability(const int length);
void ReproduceString(const string &ancestor, string s[], const string &target, const int length);  //produces 8 mutated offspring

int main()
{
	string InitialString, target, parents[3000];
	int DoneYet = 0, Generations = 1;
	static int choice = 0;

	//seeds rand() with system clock
	srand((unsigned)time(0));  
	if (choice != 1) introduction();
	//user input
	target = Initialize();
	
	InitialString = GenerateString(target.length());
	
	cout << "Ancestor:  " << InitialString << endl << endl 
		 << "Enter to continue." << endl;
	
	//fflush(stdin);
	getchar();
	
	parents[0] = InitialString;

//main loop: generates offspring, chooses next string thru Evolve().	
	for (int k = 1; (unsigned int)DoneYet < target.length(); k++)
	{
		parents[k] = Evolve(&parents[k-1], &target, &DoneYet);
		cout << parents[k];
		Generations++;
		cout << "\t|| Good Chars:  " <<  DoneYet;
		cout << " || Count:  " << Generations << endl;
	}

	cout << endl << "Generations to completion:  " << Generations << endl;
	cout << "Probability of this string randomly mutating without "
			"natural selection:  \n";
	cout << "\n\tOne in " << CalculateProbability(target.length()) << endl;
	cout << "\nEnter Selection:  \n1.  Repeat\n2.  Quit\n\n";
	cin >> choice;
	if (choice == 1) main();
	
}

//Evolve controls the process through calls to the other functions
string Evolve(const string *InitialString,
			  const string *target, int *DoneYet)
{
	string s[8], NextParent;
	int AlikeChars[8], who;

	ReproduceString(*InitialString, s, *target, target->length());
	for (int y = 0; y < 8; y++)	AlikeChars[y] = 
		CountCorrectLetters(*target,s[y]);
	NextParent = s[SelectString(AlikeChars, &who)];

	//DoneYet goes to main() to signal all chars correct
	*DoneYet = AlikeChars[who];

	return NextParent;
}


int CountCorrectLetters(const string &target,string s)
{
	int AlikeChars = 0;
		for (int i = 0; (unsigned int)i < target.length(); i++)
		{
			if (target[i] == s[i]) AlikeChars++;
		}
	return AlikeChars;
}


void ReproduceString(const string &ancestor, string s[],
					 const string &target, const int length)
{
	int mut = HowManyMutations();

	//copy ancestor into babies
	for (int i = 0; i <= 7; i++)	s[i] = ancestor;
	for (int k = 0; k <= 7; k++)
	{
		//then mutate
		for (int j = 0; j <= mut; j++)
		{
			int L = SelectRandomCharacter(ancestor.length());

			//if a char is correct don't change it
			if (ancestor[L] == target[L]) continue;
			s[k].replace(L, 1, 1, GenerateCharacter());	
		}
	}
}
char GenerateCharacter(void)
{
	char r;
	//ASCII space thru tilde
	r = (rand() % 95) + 32;

return r;
}

int SelectRandomCharacter(const int length)
{
	double x = RAND_MAX/length;
	double r = ((rand()/x));
	return (int)r;
}

int HowManyMutations()
{
	double mut = ((rand() / 3276.002442));//up to ten
	return (int) mut;
}

string GenerateString(const int length)
{
	string st;
	for(int i = 0; i < length; i++)  st += GenerateCharacter();
	return st;
}

//goes thru AlikeChars array and chooses next ancestor
int SelectString(int AlikeChars[8], int *who)
{
	int winner = 0;
	for (int i = 0; i < 8; i++)
	{
		if (AlikeChars[i] > AlikeChars[winner])
		{
			winner = i;
		}
	}
	*who = winner;//who goes back to evolve
	return winner;
}


string Initialize()
{
	string target;
	int choice = 0;
	cout << "\n1.  Default starting sentence.\n"
		    "2.  Enter starting sentence.\n";
	cin >> choice;

	if (choice == 2) 
	{
		cout <<endl<< "Upper and lower case letters, spaces, and common "
			"punctuation are allowed.\nInput target sentence:  " ;
		cin.ignore();	cin.clear();
		getline(cin, target);
		cout << endl;
	}
	else
	{
		target = "Also Spracht Zarathustra";
		cin.clear();  cin.ignore();
	}
	cout << "Target:    " << target << endl;

	return target;
}
long double CalculateProbability(const int length)
{
	return pow((long double)61, (long double)length);
}

About variable names, Stroustrup makes a good point saying that as the scope gets larger the names should get bigger. If you plan on doing any Windows API, it's nice to distinguish your functions by starting them with a lower-case letters, since the API always (or at least almost always) uses mixed case starting with uppercase.

Anyway, you are coding in the procedural mode, making your program look more like C than C++. A couple of points on your C-like program. You have a constant 8 (sometimes appearing as 7) throughout your program. So either: #define SIZE 8 /* Hard-core C */ const int SIZE = 8; // C++ You could get rid of other constants similarly, and calling main recursively to go again is probably not the best idea. Put the quit option as number 3 in your main menu (you could exit(0) there and use an ininite loop in main for now at least).

So your decision now is whether to learn pure C first or whether to go straight to C++.

...it's nice to distinguish your functions by starting them with a lower-case letters, since the <Windows> API always (or at least almost always) uses mixed case starting with uppercase.

Nice, I'd been wondering why so many people do that.

Anyway, you are coding in the procedural mode, making your program look more like C than C++. A couple of points on your C-like program. You have a constant 8 (sometimes appearing as 7) throughout your program. So either: #define SIZE 8 /* Hard-core C */ const int SIZE = 8; // C++ You could get rid of other constants similarly

That's good too, I see the value of using const where appropriate, for reliability, consistency, and ease of modifying the code.

...calling main recursively to go again is probably not the best idea. Put the quit option as number 3 in your main menu (you could exit(0) there and use an ininite loop in main for now at least).
So your decision now is whether to learn pure C first or whether to go straight to C++.

Are you suggesting I place the entirety of it in a loop instead of calling main()? That is the only alternative I can think of.

I have recognized that the code I've written is a C program with cout and cin and the convenience of strings (the reason I elected to use C++). However, in my C# program I am using classes, but I feel like I am using them as an alternative to global variables. One of the classes (named biomorph) includes functions which modify the variables, which I feel is a definite step towards object oriented programming, but the other is simply an array of public static biomorphs, which feels more like a shortcut than an advanced programming technique. So would the use of classes and members really have made this more of a C++ program?

I suppose it would, as it would mask the variables while allowing them to be accessed indirectly from any function, but I'd like to hear a bit of wisdom on that note.

Yes, you need a loop in main. main should not (as far as I know) be called recursively. Since it's simple tail recursion, it's possible in this case that it would be optimized away. But it's still not a usual idiom and not necessary. In general, your main and overall program structure are a little messy. What about a structure like this (still using C++ in the procedural style):

const char* introduction = "howdy";
const int NCHILDREN = 25;
const int MAXMUTATIONS = 3;

int main()
{
    srand(time(0));
    string goal;
    cout << introduction << endl;
    while (getString(goal)) { // getString returns false on "q"uit
        string start = rndString(goal.size());
        cout << s << endl;
        cout << evolve(start, goal);
    }
    return 0;
}

int evolve(string str, string goal)
{
    string children[NCHILDREN];
    int nGeneration = 0;
    while (str != goal) {
        reproduce(str, children);
        str = select(children, goal);
        nGeneration++;
    }
    return nGeneration;
}

void reproduce(string str, string children[])
{
    for (int i = 0; i < NCHILDREN; i++) {
        children[i] = str;
        mutate(str);
    }
}

// mutate will even mutate correct characters (see * below)
void mutate(string str)
{
    int nMutations = rand() % MAXMUTATIONS + 1;
    for (int i = 0; i < nMutations; i++) {
        str[rand() % str.size()] = rndChar();
    }
}

That's basically the heart of your code, but much cleaner looking. (I haven't run it, yet, so no guarantees. Note that it doesn't bother to save all the "parents".)

And yes, a C++ programmer would probably define at least one object in this program since it would be useful and not much extra work. You could make a Sentence class (either inheriting from string or containing one) with member functions to randomize the sentence, evolve, mutate, compare, etc. With this small program there's not much difference. main might look like this:

int main()
{
    Sentence goal;
    while (goal.get()) {
        Sentence s;
        s.randomize(goal.size());
        cout << s << endl;
        s.evolve(goal);
    }
}

* As for your evolution simulation, it seems like cheating to allow the letters that are correct to be bypassed by further mutations. Mutations should occur evenly across the genome, one would think. Maybe there's a good reason to pass them over, but it seems to me that they should be able to be mutated away from perfection as well as towards it. As long as your children pool is big enough (NCHILDREN in the code above), like 25 or even 50 (instead of just 8) it should still be able to evolve the sentence. This would be even more of a "proof", such that it is. Even with the prospects more likely to mutate away from the goal then towards it, the power of selection leads them up "mount improbable".

This is the Error I get when running your program on g++ with -Wall flag on,phillipdaw is: ISO C++ forbids taking address of function ‘::main’ So, I guess that answered all the doubts regarding calling of main(). So the rule of thumb: NEVER CALL MAIN()

Rather than exit(0), you can use return(0), if you want to exit the program from main.

This question has already been answered. Start a new discussion instead.