#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import division
import sys
import random
import math


def std_deviation(points):
    """ среднеквадратичное отклонение """
    return math.sqrt(reduce(lambda x,y: x+(y-sum(points)/len(points))**2, points)/len(points))
    #return sum(points)/len(points)


def fitness_func(k1, k2, points):
    """ при одном x разность y должна стремиться к 0 для всех точек """
    deviations = map(lambda p: abs(p[1] - (k1*p[0]+k2)), points)
    return std_deviation(deviations)


def gen_population(prev_population, points):
    """ prev_population = [([k1, k2,], ff),] """
    best_two = sorted(prev_population, key=lambda x: abs(x[1]))[:2]
    population = []
    mutation_rate = 0.2
    #print '======'
    for parent in best_two:
        population.append(parent)
        for i in xrange(10):
            koeffs = [parent[0][0],parent[0][1]]
            rand_pos = random.randint(0, len(koeffs)-1)
            koeffs[rand_pos] = koeffs[rand_pos] + (random.random()*2 - 1)  # koeffs[rand_pos]*(random.random()*2 - 1) * mutation_rate
            ff = fitness_func(koeffs[0], koeffs[1], points)
            #print 'y = %s*x + %s    %s' % (koeffs[0], koeffs[1], ff)
            population.append(([koeffs[0], koeffs[1]], ff))
    return population


if __name__ == '__main__':
    random.seed()
    print 'y = k*x + b  _deviation_'
    points = [(1,3), (2,5), (6,6), (3,3), (4,8)]  # y = 2x + 1
    population = []
    for i in xrange(10):
        k1 = random.randint(-5, 5)
        k2 = random.randint(-5, 5)
        ff = fitness_func(k1, k2, points)
        # print 'y = %s*x + %s    %s' % (k1, k2, ff)
        population.append(([k1, k2], ff))

    print '=========='
    import matplotlib.pyplot as plt
    for i in xrange(100):
        fig, ax = plt.subplots( nrows=1, ncols=1 )
        x = range(-10, 10)
        best = sorted(population, key=lambda x: abs(x[1]))[0]
        koeffs = best[0]
        ff = best[1]
        y = [koeffs[0]*_x+koeffs[1] for _x in x]
        ax.set_autoscaley_on(False)
        ax.set_ylim([0,10])
        ax.plot(x, y)
        ax.plot(*zip(*points), marker='o', color='r', ls='')
        lbl = 'y = %s*x + %s    %s' % (koeffs[0], koeffs[1], ff)
        ax.text(0.5, 0.5,lbl,
                horizontalalignment='center',
                verticalalignment='center',
                transform = ax.transAxes)
        fig.savefig('%s.png' % i)
        plt.close(fig)
        population = gen_population(population, points)
    best_two = sorted(population, key=lambda x: abs(x[1]))[:2]
    print best_two[0]