code contest

Blood Test

    A. First Edition

    This is the result of my argument with my friend Mr.Zhu Chun Ming. He is such a persistent believer

    of blood type that whenever he see somebody he would ask about his/her blood type. And he will

    repeatedly attribute all success and failure of famous persons or even nations to blood type. It

    seems to me to be quite extreme! I don't really want to deny the certain connections between

    personality and blood type, but it cannot count for all, right?

    ¡¡

    B.The problem

I heard that the original blood type of human kind is O type. However, I am not sure. Otherwise, it

is quite unexplainable that O type is majority of people in the world because from perspective of

purely generic O type has smallest chances to be inherited.

My base knowledge is from what I learned from middle school:

There are only THREE inheritable blood elements: A, B, O.

¡¡ | A element | B element | O element
A element | A blood type | AB blood type | A blood type
B element | AB blood type | B blood type | B blood type
O element | A blood type | B blood type | O blood type

That is O is an insignificant element that only combination of O and O will give you child of O

type. Please note that I am not talking about blood type here!!! What I am saying is that each

blood type can split into two basic elements:

Blood Type | element1 | element2

A | A | O
B | B | O
AB | A | B
O | O | O

Originally there will be a certain number of people with averagely equal number of blood type which

is called generation 1. Every male and female sex has a number of chances to find his/her match

among opposite sex of same generation. (After a while, I allow them to find older generations who

is not married. :)) Every couple cannot divorce and can have maximum three children.

For the mating function, I make each person to randomly search from some point in people chain so

that there is some small chances that this person cannot find match at first time or, say for

his/her whole life.

You know the basic data structure is just a "people chain", or array of "Person".

¡¡

C.The idea of program
¡¡

For some time, I even believed what Mr. Zhu claimed that each blood type has equal chances to be

inherited. But the result confirmed my belief which established since my childhood. If my basic

knowledge for blood is correct, then, my calculation should be meaningful.

The result seems to be wrong because according to my calculation type A and B should have highest

possibility among all and type O is only the second highest one. How come in the result type O

becomes the highest one?

I kept debugging and finally realized that it might be correct. Please see following:

Type A and B are high because they depend a lot on quantity of AB. However, type O is not depending

on AB at all. And AB is very low, only 2/16. So, both A,B are not increasing as far as O if we all

agree that AB is the slowest one in increasing.

¡¡

¡¡ | A | B | O | AB
A | 0.75*A, 0.25*O | 0.25*A,0.25*B,0.25*AB,0.25*O | 0.5*A,0.5*O | 0.5*A,0.25*B,0.25*AB
B | 0.25*A,0.25*B,0.25*AB,0.25*O | 0.75*B,0.25*O | 0.5*B,0.5*O | 0.5*B,0.25*A,0.25*AB
O | 0.5*A,0.5*O | 0.5*B,0.5*O | 1*O | 0.5*A,0.5*B
AB | 0.5*A,0.25*B,0.25*AB | 0.5*B,0.25*A,0.25*AB | 0.5*A,0.5*B | 0.5*AB,0.25*A,0.25*B

The table is a kind of symmetric relative to diagonal line with background of blue color. So, the calculation:

A total: 1* AxA + 2* AxB + 2* AxO+ 2* AxAB+ 2* BxAB +2* ABxO+ 1* ABxAB

= 0.75 + 2*(0.25+0.5+0.5+0.25+0.5) + 0.25 = 5

B total: 1* BxB + 2* BxA + 2* BxO+ 2* BxAB+ 2* AxAB +2* ABxO+ 1* ABxAB

= 0.75 + 2*(0.25+0.5+0.5+0.25+0.5) + 0.25 = 5

O total: 1* AxA + 1*BxB+ 1*OxO+2* AxB + 2*AxO + 2*BxO

= 0.25+ 0.25+ 1 +2*(0.25+0.5+0.5)= 4

AB total: 1*ABxAB + 2* AxB + 2* AxAB + 2* BxAB

=0.5 + 2*(0.25+ 0.25+0.25)= 2

Total of A+B+AB+O=4.5+4.5+5+2=16

¡¡

    D.The major functions

    If by any chance, you understand Chinese you maybe interested in take a look at the recursive formula here.

    E.Further improvement

    ¡¡

    F.File listing

    1. blood.cpp

    ¡¡

    file name: blood.cpp

    #include <iostream>
    #include <time.h>
    using namespace std;

    const int MaxPersonNumber=10000;
    const int SexNumber=2;
    const int BloodTypeNumber=4;
    const int MaxGeneration=15;
    const int BloodItemNumber=3;
    const int MaxBirthNumber=3;//assume couples can have 3 kids since first mating
    const int InitialNumber=20;
    const int RunGenerationNumber=10;
    const int TestRunNumber=5;

    enum Blood
    {
    	A, B, O, AB
    };

    enum Sex
    {
    	Male, Female
    };

    const char* bloodName[BloodTypeNumber]=
    {"A","B","O","AB"};

    class Person
    {
    private:
    	Blood blood;
    	Sex sex;
    	int generation;
    	Blood splitBlood(Blood, int choice);
    public:
    	int father;
    	int mother;
    	int indexNo;
    	int match;
    	Sex getSex(){ return sex;}
    	Blood getBlood(){ return blood;}
    	void setSex(Sex theSex){sex=theSex;}
    	void setBlood(Blood theBlood){ blood=theBlood;}
    	void giveBirth(const Person& spouse);
    	int getGeneration(){return generation;}
    	void setGeneration(int theGeneration){generation=theGeneration;}
    	int getMatch(){return match;}
    	void setMatch(int theMatch){match=theMatch;}
    	bool mate();
    };

    int index;
    Person people[MaxPersonNumber];
    int generations[MaxGeneration];
    int bloodCount[MaxGeneration][BloodTypeNumber]={0};

    //pls note that the below is not blood type
    //but the blood item which is the genetic factor of blood
    Blood bloodTable[BloodItemNumber][BloodItemNumber]=
    {
    	//A   B  O
    //A
    	{A, AB, A},
    //B
    	{AB, B, B},
    //O
    	{A, B, O}
    };

    void initialize();
    int first(int theGeneration);

    void nextGeneration(int theGeneration);
    void run();

    int main()
    {
    	srand(time(0));
    	for (int i=0; i<TestRunNumber; i++)
    	{
    		cout<<"test no."<<i+1<<" and result is\n";
    		run();
    	}

    	return 0;
    }

    void run()
    {
    	initialize();
    	for (int i=0; i<RunGenerationNumber; i++)
    	{
    		nextGeneration(i);
    	}
    	cout<<"after 10 generations, the total number of people is:"
    		<<index<<endl;
    	for (i=0; i<RunGenerationNumber; i++)
    	{
    		cout<<"for "<<i+1<<"th generation the blood distribution is\n";

    		for (int j=0; j<BloodTypeNumber; j++)
    		{
    			cout<<bloodName[j]<<":";
    			cout<<bloodCount[i][j]<<"\t";
    		}
    		cout<<"\n";
    	}
    }

    Blood Person::splitBlood(Blood theBlood, int choice)
    {
    	Blood result;
    	switch (theBlood)
    	{
    	case A:
    		if (choice==0)
    		{
    			result= O;
    		}
    		else
    		{
    			result= A;
    		}
    		break;
    	case B:
    		if (choice==0)
    		{
    			result= O;
    		}
    		else
    		{
    			result= B;
    		}
    		break;
    	case O:
    		result= O;
    		break;
    	case AB:
    		if (choice==0)
    		{
    			result= A;
    		}
    		else
    		{
    			result= B;
    		}
    		break;
    	}
    	return result;
    }

    int first(int theGeneration)
    {
    	if (theGeneration==0)
    	{
    		return 0;
    	}
    	else
    	{
    		return generations[theGeneration-1]+1;
    	}
    }
    void initialize()
    {
    	index=0;
    	//there are 4 women and 4 man with one person of each blood type exactly
    	/*
    	for (int i=0; i<SexNumber; i++)
    	{
    		for (int j=0; j<BloodTypeNumber; j++)
    		{
    			people[index].setSex((Sex)i);
    			people[index].setBlood((Blood)j);
    			people[index].setGeneration(0);
    			people[index].indexNo=index;
    			people[index].match=-1;
    			people[index].father=people[index].mother=-1;//I don't know where they are from.
    			bloodCount[0][people[index].getBlood()]++;
    			index++;
    		}
    	}

    	generations[0]=SexNumber*BloodTypeNumber-1;
    	*/
    	//there are a fixed number of people created by God
    	for (int i=0; i<InitialNumber; i++)
    	{
    		people[index].setSex((Sex)(rand()%2));
    		people[index].setBlood((Blood)(rand()%4));
    		people[index].setGeneration(0);
    		people[index].match=-1;
    		people[index].father=people[index].mother=-1;
    		bloodCount[0][people[index].getBlood()]++;
    		index++;
    	}
    	generations[0]=index-1;

    }

    void Person::giveBirth(const Person& spouse)
    {
    	int choice;
    	Blood self, theOther;
    	choice=rand()%2;
    	//splite blood to blooditem
    	self=splitBlood(blood, choice);
    	choice=rand()%2;
    	theOther=splitBlood(spouse.blood, choice);
    	choice=rand()%2;
    	people[index].setBlood(bloodTable[self][theOther]);
    	choice=rand()%2;
    	people[index].setGeneration(generation+1);
    	choice=rand()%2;
    	people[index].setSex((Sex)choice);
    	bloodCount[generation+1][people[index].blood]++;
    	people[index].match=-1;
    	people[index].indexNo=index;
    	people[index].father=sex==Male?indexNo:spouse.indexNo;
    	people[index].mother=sex==Female?indexNo:spouse.indexNo;
    	index++;
    }

    bool Person::mate()
    {
    	if (match!=-1)//married
    	{
    		return false;
    	}
    	//randomly start from some place where he might marry older generations
    	//who happened to be unmarried
    	for (int i=rand()%generations[generation]; i<=generations[generation]; i++)
    	{
    		if (i!=indexNo)
    		{
    			if (people[i].match==-1)
    			{
    				if (sex!=people[i].sex)//we don't allow gay to be married, right?
    				{
    					people[i].match=indexNo;
    					match=i;
    					return true;
    				}
    			}
    		}
    	}
    	return false;
    }

    void nextGeneration(int theGeneration)
    {
    	for (int birth=0; birth<MaxBirthNumber; birth++)
    	{
    		for (int i=first(theGeneration); i<=generations[theGeneration]; i++)
    		{
    			if (people[i].mate())//first married and...
    			{
    				people[i].giveBirth(people[people[i].getMatch()]);
    			}
    			else
    			{
    				//he/she is married and his/her spouse is younger than he/she
    				if (people[i].match>people[i].indexNo)
    				{
    					people[i].giveBirth(people[people[i].match]);
    				}
    			}

    		}
    	}
    	generations[theGeneration+1]=index-1;//records the end of generation
    }

    The result is like following:

    test no.1 and result is
    after 10 generations, the total number of people is:1148
    for 1th generation the blood distribution is
    A:3 B:4 O:6 AB:7
    for 2th generation the blood distribution is
    A:8 B:9 O:5 AB:5
    for 3th generation the blood distribution is
    A:6 B:7 O:9 AB:4
    for 4th generation the blood distribution is
    A:8 B:12 O:14 AB:4
    for 5th generation the blood distribution is
    A:10 B:16 O:17 AB:8
    for 6th generation the blood distribution is
    A:24 B:17 O:19 AB:4
    for 7th generation the blood distribution is
    A:30 B:20 O:38 AB:2
    for 8th generation the blood distribution is
    A:31 B:27 O:63 AB:8
    for 9th generation the blood distribution is
    A:43 B:34 O:91 AB:3
    for 10th generation the blood distribution is
    A:41 B:43 O:120 AB:14
    test no.2 and result is
    after 10 generations, the total number of people is:1425
    for 1th generation the blood distribution is
    A:9 B:7 O:10 AB:14
    for 2th generation the blood distribution is
    A:20 B:19 O:9 AB:9
    for 3th generation the blood distribution is
    A:18 B:19 O:18 AB:10
    for 4th generation the blood distribution is
    A:28 B:24 O:26 AB:8
    for 5th generation the blood distribution is
    A:35 B:32 O:34 AB:14
    for 6th generation the blood distribution is
    A:54 B:38 O:48 AB:11
    for 7th generation the blood distribution is
    A:63 B:40 O:89 AB:9
    for 8th generation the blood distribution is
    A:71 B:57 O:135 AB:16
    for 9th generation the blood distribution is
    A:82 B:77 O:209 AB:13
    for 10th generation the blood distribution is
    A:95 B:103 O:273 AB:23
    test no.3 and result is
    after 10 generations, the total number of people is:1644
    for 1th generation the blood distribution is
    A:12 B:13 O:15 AB:20
    for 2th generation the blood distribution is
    A:29 B:31 O:9 AB:15
    for 3th generation the blood distribution is
    A:29 B:27 O:26 AB:15
    for 4th generation the blood distribution is
    A:39 B:39 O:39 AB:12
    for 5th generation the blood distribution is
    A:47 B:57 O:55 AB:18
    for 6th generation the blood distribution is
    A:65 B:62 O:91 AB:22
    for 7th generation the blood distribution is
    A:84 B:74 O:147 AB:18
    for 8th generation the blood distribution is
    A:110 B:100 O:217 AB:21
    for 9th generation the blood distribution is
    A:132 B:139 O:332 AB:25
    for 10th generation the blood distribution is
    A:160 B:193 O:449 AB:36
    test no.4 and result is
    after 10 generations, the total number of people is:1095
    for 1th generation the blood distribution is
    A:17 B:17 O:19 AB:27
    for 2th generation the blood distribution is
    A:34 B:44 O:12 AB:21
    for 3th generation the blood distribution is
    A:37 B:48 O:33 AB:18
    for 4th generation the blood distribution is
    A:48 B:60 O:51 AB:18
    for 5th generation the blood distribution is
    A:56 B:83 O:73 AB:21
    for 6th generation the blood distribution is
    A:77 B:89 O:115 AB:24
    for 7th generation the blood distribution is
    A:96 B:108 O:187 AB:23
    for 8th generation the blood distribution is
    A:128 B:134 O:274 AB:23
    for 9th generation the blood distribution is
    A:153 B:178 O:418 AB:31
    for 10th generation the blood distribution is
    A:189 B:236 O:574 AB:50
    test no.5 and result is
    after 10 generations, the total number of people is:1307
    for 1th generation the blood distribution is
    A:26 B:25 O:19 AB:30
    for 2th generation the blood distribution is
    A:44 B:51 O:15 AB:25
    for 3th generation the blood distribution is
    A:52 B:55 O:39 AB:25
    for 4th generation the blood distribution is
    A:67 B:64 O:62 AB:22
    for 5th generation the blood distribution is
    A:81 B:90 O:93 AB:25
    for 6th generation the blood distribution is
    A:107 B:101 O:142 AB:30
    for 7th generation the blood distribution is
    A:129 B:127 O:231 AB:27
    for 8th generation the blood distribution is
    A:172 B:149 O:348 AB:27
    for 9th generation the blood distribution is
    A:207 B:196 O:534 AB:32
    for 10th generation the blood distribution is
    A:253 B:259 O:737 AB:56
    Press any key to continue

    ¡¡