do_min

import numpy as np

m = 6
n = 9
a = np.arange((m+2)*(n+2)).reshape(m+2, n+2)
default = np.ones_like(a)
for i in range(m+2):
    for j in range(n+2):
        if i == 0 or j == 0:
            default[i,j] = 0
        if i == m+1 or j == n+1:
            default[i,j] = 0

def make_nd(data):
    a = np.array(default).astype(float)
    for i in range(1, m+1):
        for j in range(1, n+1):
            a[i,j] = data[i-1][j-1]
    return a

def sum_nd(data):
    a = np.array(default).astype(float)
    for i in range(1, m+1):
        for j in range(1, n+1):
            a[i,j] = np.sum(data[i-1:i+2,j-1:j+2]) - data[i,j]
    return a

def avg_nd(data):
    a = np.array(default).astype(float)
    count = sum_nd(default)
    for i in range(1, m+1):
        for j in range(1, n+1):
            a[i,j] = (np.sum(data[i-1:i+2,j-1:j+2]) - data[i,j]) / count[i,j]
    return a

def max_nd(data):
    a = np.array(default).astype(float)
    b = np.array(data).astype(float)
    for i in range(1, m+1):
        for j in range(1, n+1):
            temp = data[i,j]
            data[i,j] = 0
            a[i,j] = np.amax(data[i-1:i+2,j-1:j+2])
            data[i,j] = temp
    return a

def list_nd(data):
    a = dict()
    b = np.array(data).astype(float)
    for i in range(1, m+1):
        a[i] = dict()
        for j in range(1, n+1):
            temp = data[i,j]
            data[i,j] = 0
            a[i][j] = data[i-1:i+2,j-1:j+2].flatten()
            data[i,j] = temp
    return a

def divide_nd(data):
    a = np.array(default).astype(float)
    count = sum_nd(default)
    for i in range(1, m+1):
        for j in range(1, n+1):
            a[i,j] = data[i,j] / count[i,j]
    return a

def make_data_test(m, n):
    a = []
    for i in range(m):
        b = []
        for j in range(n):
            b.append(np.random.binomial(1,0.5))
        a.append(b)
    b = np.arange((m+2)*(n+2)).reshape(m+2, n+2)
    default = np.ones_like(b)
    for i in range(m+2):
        for j in range(n+2):
            if i == 0 or j == 0:
                default[i,j] = 0
            if i == m+1 or j == n+1:
                default[i,j] = 0
    c = sum_nd(make_nd(a))[1:m+1, 1:n+1].astype(int)
    d = []
    for i in range(m):
        b = []
        for j in range(n):
            b.append(c[i,j])
        d.append(b)
    return d, a

# input_data = [
#     [1,3,3,1],
#     [2,3,4,4],
#     [3,6,5,3],
#     [1,3,3,3]
# ]

input_data, output_data = make_data_test(m=m, n=n)
process_data = make_nd(input_data)
broadcast_probability = divide_nd(process_data)

max_bcp = max_nd(broadcast_probability)
avg_bcp = avg_nd(broadcast_probability)
lst_bcp = list_nd(broadcast_probability)

# Start EA

# initiate the population
def init_one():
    a = np.array(default).astype(float)
    for i in range(1, m+1):
        for j in range(1, n+1):
            method = np.random.randint(0,3)
            if method == 0:
                possibilities = lst_bcp[i][j]
                k = np.random.randint(0, len(possibilities))
                a[i,j] = np.random.binomial(1, possibilities[k])
            elif method == 1:
                a[i,j] = np.random.binomial(1, avg_bcp[i,j])
            else:
                a[i,j] = np.random.binomial(1, max_bcp[i,j])
    return a

def init_ppl(n):
    return [init_one() for i in range(n)]

def evaluate_one(a):
    return np.sum(np.absolute(sum_nd(a) - process_data))

def evaluate_ppl(ppl):
    return [evaluate_one(i) for i in ppl]

def crossover(x,y):
    a = np.array(default).astype(float)
    for i in range(1, m+1):
        for j in range(1, n+1):
            k = np.random.randint(0, 2)
            if k == 0:
                a[i,j] = x[i,j]
            else:
                a[i,j] = y[i,j]
    return a

def mutate(x, p=0.1):
    a = np.array(default).astype(float)
    for i in range(1, m+1):
        for j in range(1, n+1):
            k = np.random.binomial(1, p)
            if k == 1:
                a[i,j] = 0 if x[i,j] > 0 else 1
            else:
                a[i,j] = x[i,j]
    return a

def new_ppl(ppl, num_crossover, num_mutate):
    a = []
    len_ppl = len(ppl)
    for i in range(num_crossover):
        a.append(crossover(ppl[np.random.randint(0, len_ppl)], ppl[np.random.randint(0, len_ppl)]))
    for i in range(num_mutate):
        a.append(mutate(ppl[np.random.randint(0, len_ppl)], p=0.1))
    return ppl + a

def select_ppl(P, n):
    P_points = evaluate_ppl(P)
    avg_point = np.average(P_points)
    temp_pp = [[id_v,v] for id_v, v in enumerate(P_points)]
    def getKey(a):
        return a[1]
    ordered_pp = sorted(temp_pp, key=getKey)
    new_P = []
    i = 0
    n_bias = 50
    while len(new_P) < n-n_bias and i < n:
        new_P.append(P[ordered_pp[i][0]])
        i += 1
    for i in range(n_bias):
        new_P.append(P[ordered_pp[len(ordered_pp)-1-i][0]])
    return new_P

def is_finished_ppl(ppl):
    is_finished = -1
    for id_p, point in enumerate(evaluate_ppl(ppl)):
        if point == 0:
            is_finished = id_p
    return is_finished

def run():
    P = init_ppl(1000)
    number_generations = 1000
    for i in range(number_generations):
        P = new_ppl(P, 900, 100)
        P = select_ppl(P, 1000)
        is_fn = is_finished_ppl(P)
        if is_fn > -1:
            print("Terminate at generation: ", i+1)
            break
    return P[is_fn] if is_fn > -1 else P[0]

import time

print("The input data is: ")
for i in input_data:
    print(i)
start = time.time()
res = run()
print(res[1:m+1,1:n+1].astype(int))
print("It takes: ", time.time() - start, "secs")

print("The answer is: ")
for i in output_data:
    print(i)