import random
import copy
from string import ascii_lowercase


def get_rand_pair(s_len, symbols):
    return (random.randint(0, s_len-1), random.choice(symbols))

def get_N_most_successful_seqs(offsprings, s_flag, N):
    match_pairs = sorted([(match_strs(string, s_flag), string)
                        for string in offsprings])
    return [el[1] for el in match_pairs[-N::]]

def match_strs(s, s_flag):
    lenght = len(s)
    count = 0
    for i in range(lenght):
        if s[i] == s_flag[i]:
            count += 1
    return count

def gen_new_str(s_list, symbols):
    new_s = copy.copy(s_list)
    pair = get_rand_pair(len(s_list), symbols)
    new_s.pop(pair[0])
    new_s.insert(pair[0], pair[1])
    return new_s

def generate_first_gen(s_start, symbols):
    return [gen_new_str(s_start, symbols) for _ in range(10)]

def generate_new_gen(symbols, offsprings, s_start):
    new_gen = []
    for string in offsprings:
        for i in range(10):
            new_gen.append(gen_new_str(string, symbols))
    return get_N_most_successful_seqs(new_gen, s_flag, 10)

symbols = ascii_lowercase + ' '
s_flag = list('what a lovely day')
s_start = list('rtdafhdkv jfkslgf')

offsprings = generate_first_gen(s_start, symbols)
count = 0

while  True:
    offsprings = generate_new_gen(symbols, offsprings, 10)
    count += 1
    if s_flag in offsprings:
        print(offsprings)
        print(count)
        break