#include <stdio.h>
#include <iostream>
#include <string.h>
#include <cstdlib>
#include <fstream>
#include <cmath>
#include <ctime>

using namespace std;

class coordinate
{
public:
	int X;
	int Y;
};

class Dog
{
public:
	int fitness;
	int path[1000];
	double share;
	coordinate c;
};

int StSousage(Dog dog)
{
	coordinate point;
	point.X = 500;
	point.Y = 500;
	for (int i = 0; i<1000; i++)
	{
		switch (dog.path[i]) {
		case 0:
			point.Y--;
			break;
		case 1:
			point.Y++;
			break;
		case 2:
			point.X--;
			break;
		case 3:
			point.X++;
			break;
		default:
			cout << "Error step" << endl;
			system("Pause");
			exit(1);
			break;
		}
	}
	int Step[4] = { 0 };
	Step[0] = abs(point.X - 200) + abs(point.Y - 800);
	Step[1] = abs(point.X - 800) + abs(point.Y - 800);
	Step[2] = abs(point.X - 200) + abs(point.Y - 200);
	Step[3] = abs(point.X - 800) + abs(point.Y - 200);
	int min = INT_MAX;
	for (int i = 0; i<4; i++)
	{
		if (Step[i]<min)min = Step[i];
	}
	return min;
}
coordinate getCoordinate(Dog d)
{
	coordinate point;
	point.X = 500;
	point.Y = 500;
	for (int i = 0; i<1000; i++)
	{
		switch (d.path[i]) {
		case 0:
			point.Y--;
			break;
		case 1:
			point.Y++;
			break;
		case 2:
			point.X--;
			break;
		case 3:
			point.X++;
			break;
		default:
			cout << "Error coordinate" << endl;
			system("Pause");
			exit(1);
			break;
		}
	}
	return point;
}

double Distation(coordinate point1, coordinate point2)
{
	return abs(point1.X - point2.X) + abs(point1.Y - point2.Y);
}

double funcS(int Dij)
{
	if (Dij < 5)
		return (1 - (double)Dij / 5.0);
	else return 0;
}
int main(int argc, char** argv)
{
	srand(time(NULL));
	Dog predstav[12];
	for (int i = 0; i<12; i++)
		for (int j = 0; j<1000; j++)
		{
			predstav[i].path[j] = rand() % 4;
		}
	for (int i = 0; i<12; i++)
	{
		predstav[i].c = getCoordinate(predstav[i]);
		cout << i << " x=" << predstav[i].c.X << "  y=" << predstav[i].c.Y << endl;
	}
	int iteration = 0;
	while (true)
	{
		for (int i = 0; i<12; i++)
			predstav[i].fitness = 600 - StSousage(predstav[i]);

		for (int i = 0; i<12; i++)
		{
			double Znam = 0;
			coordinate Point_i = getCoordinate(predstav[i]);
			for (int j = 0; j<12; j++)
			{
				if (i == j)
				{
					Znam += 1;
					continue;
				}
				coordinate Point_j = getCoordinate(predstav[j]);
				int Distance = Distation(Point_i, Point_j);
				Znam += funcS(Distance);
			}
			double ShareFun = 0;
			ShareFun = predstav[i].fitness / Znam;
			predstav[i].share = ShareFun;
		}
		Dog temp;
		int max;
		for (int i = 0; i<11; i++)
		{
			max = i;
			for (int j = i + 1; j<12; j++)
			{
				if (predstav[j].share > predstav[max].share)max = j;
			}
			if (max != i)
			{
				temp = predstav[i];
				predstav[i] = predstav[max];
				predstav[max] = temp;
			}
		}
		cout << "Prosortirovanno:" << endl;
		cout << "Best fitness = " << predstav[0].share << endl;
		for (int i = 0; i<12; i++)
			cout << "Predstavitel fitness =: " << predstav[i].share << endl;
		Dog best[4];
		for (int i = 0; i<4; i++)
			best[i] = predstav[i];
		for (int i = 0; i<12; i++)
		{
			int Par1, Par2;

			do {
				Par1 = rand() % 4;
				Par2 = rand() % 4;
			} while (Par1 == Par2);

			int cut = (rand() % 999) + 1;

			Dog childDog1, childDog2;

			for (int k = 0; k<cut; k++)
			{
				childDog1.path[k] = best[Par1].path[k];
				childDog2.path[k] = best[Par2].path[k];
			}

			for (int k = cut; k<1000; k++)
			{
				childDog1.path[k] = best[Par2].path[k];
				childDog2.path[k] = best[Par1].path[k];
			}
			childDog1.fitness = 600 - StSousage(childDog1);
			childDog2.fitness = 600 - StSousage(childDog2);

			if (childDog1.fitness > childDog2.fitness)
				predstav[i] = childDog1;
			else
				predstav[i] = childDog2;
		}
		for (int i = 0; i<12; i++)
			if (predstav[i].fitness == 200)
				break;
		cout << endl;
		if (iteration != 20)
		cout << "Iteration number: "<< iteration << endl;
		iteration++;
		if (iteration == 21)
			break;
	}
	system("Pause");
	return 0;
}