import numpy as np
import random
import hashlib
import math

def get_state_id(state):
    return ','.join([str(x) for x in sorted(state)])

class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def id(self):
        return ''.join([str(x) for x in self.x])

class Influence():
    def __init__(self, a, b):
        self.a = a
        self.b = b
        self.original_dof = set()
        self.dof = set()
        for i in range(0, len(a.x)):
            if a.x[i] != b.x[i]:
                self.original_dof.add(i)
                self.dof.add(i)
        self.coherent = self.a.y == self.b.y

    def coherent(self):
        return self.a.y == self.b.y

def encode(v):
    byte_values = []
    for i in range(0, math.ceil(len(v) / 8)):
        x = 0
        for j in range(0, 8):
            index = i * 8 + j
            if index >= len(v):
                continue
            x <<= 1
            x |= int(v[index])
        byte_values.append(x)
    return bytearray(byte_values)

def sha(v):
    x = encode(v)
    m = hashlib.sha256()
    m.update(x)
    result = m.digest()
    return result[0] & 0b1

def hamming_distance(a, b, flips):
    distance = 0
    for i in range(0, len(a.x)):
        if i in flips:
            continue
        distance += 1 if a.x[i] != b.x[i] else 0
    return distance

def random_x(N):
    x = np.zeros((N))
    for i in range(0, N):
        x[i] = random.randint(0, 1)
    return x

def xor(x):
    return np.sum(x[16:]) % 2

def create_dof_map(influences):
    dof_map = {}
    for influence in influences:
        for i in influence.dof:
            if not i in dof_map:
                dof_map[i] = []
            dof_map[i].append(influence)
    return dof_map

def flip(influences, i):
    for influence in influences:
        if i in influence.dof:
            influence.a.y = int(influence.a.y) ^ 1

def remove_dof(dof_map, i, flip = False):
    for influence in dof_map[i]:
        influence.dof.remove(i)
        if flip:
            influence.a.y = int(influence.a.y) ^ 1
        # if len(influence.dof) == 0 and not influence.coherent():
        #     raise Exception('Invalid')
    del dof_map[i]

def solve(dof_map, all_influences, all_samples):
    eliminated = True
    while eliminated:
        eliminated = False
        for influence in all_influences:
            if len(influence.dof) == 1:
                i = next(iter(influence.dof))
                if influence.coherent:
                    remove_dof(dof_map, i)
                    eliminated = True
                else:
                    print('Forced', i)
                    remove_dof(dof_map, i, True)
                    eliminated = True
                
    lowest_dof = None
    for influence in all_influences:
        if not influence.coherent and len(influence.dof) > 1:
            if lowest_dof is None or len(influence.dof) < len(lowest_dof.dof):
                lowest_dof = influence

    flip = None
    highest_score = -1

    for i in lowest_dof.dof:
        per_point_scores = {}
        i_influences = dof_map[i]
        left = 0
        right = 0
        for influence in i_influences:
            if not influence.a in per_point_scores:
                per_point_scores[influence.a] = [0, 0]
            if not influence.b in per_point_scores:
                per_point_scores[influence.b] = [0, 0]
            if influence.coherent:
                per_point_scores[influence.a][0] += 1
                per_point_scores[influence.b][0] += 1
                left += 1
            else:
                per_point_scores[influence.a][1] += 1
                per_point_scores[influence.b][1] += 1
                right += 1
        print(i, left / (left + right))
        num = 0
        denom = 0
        for _, score in per_point_scores.items():
            if score[0] == score[1]:
                continue
            print(i, score)
            num += score[1] / (score[0] + score[1])
            denom += 1
        score = num / denom if denom > 0 else 0
        print(score)
    
    return None

        
    #     score_sum = 0
    #     for j, j_influences in dof_map.items():
    #         if j in lowest_dof.dof:
    #             continue
    #         double_score = 0
    #         double_totals = [0, 0, 0, 0, 0, 0]
    #         for influence in i_influences:
    #             if influence in j_influences:
    #                 weight = 1.0 / ((len(influence.dof) - 2) ** 2)
    #                 if influence.coherent:
    #                     double_score += weight
    #                     double_totals[0] += 1
    #                 else:
    #                     double_score -= weight
    #                     double_totals[3] += 1
    #             else:
    #                 weight = 1.0 / ((len(influence.dof) - 1) ** 2)
    #                 if influence.coherent:
    #                     double_score -= weight
    #                     double_totals[4] += 1
    #                 else:
    #                     double_score += weight
    #                     double_totals[1] += 1
    #         for influence in j_influences:
    #             if influence in i_influences:
    #                 continue
    #             weight = 1.0 / ((len(influence.dof) - 1) ** 2)
    #             if influence.coherent:
    #                 double_score -= weight
    #                 double_totals[5] += 1
    #             else:
    #                 double_score += weight
    #                 double_totals[2] += 1
                    
    #         score = double_score
    #         score_sum += score
    #         # print((i, j), score, single_totals, double_totals)

    #     if flip is None or score_sum > highest_score:
    #         highest_score = score_sum
    #         flip = [i]
    #     print(i, score_sum)

    # if flip is None:
    #     return None
    # print('Chose', flip, 'from', lowest_dof.dof, highest_score)
    # for i in flip:
    #     remove_dof(dof_map, i, True)
    # return flip

def main():
    N = 32
    sample_size = 32
    p_dist = np.ones(N)
    p_dist.fill(0.5)
    epoch = 0

    while True:
        sample_ids = set()
        samples = []

        for i in range(0, sample_size):
            x = random_x(N)
            y = int(sha(x))
            p = Point(x, y)
            p_id = p.id()
            if p_id in sample_ids:
                continue
            sample_ids.add(p_id)
            samples.append(p)

        influences = []
        for i in range(0, len(samples)):
            a = samples[i]
            for j in range(i + 1, len(samples)):
                b = samples[j]
                influences.append(Influence(a, b))

        visited = set()
        state = []

        iterations = 0
        while sum([0 if influence.coherent else 1 for influence in influences]) > 0:
            # if iterations > 5000:
            #     state = []
            #     break
            iterations += 1
            # print(state)
            lowest_dof = None
            num_influences = -1
            for influence in influences:
                if influence.coherent:
                    continue

                if lowest_dof is not None and len(influence.dof) >= num_influences:
                    continue

                has_unvisited_state = False
                for i in influence.dof:
                    state_id = get_state_id(state + [i])
                    if state_id not in visited:
                        has_unvisited_state = True
                        break

                if not has_unvisited_state:
                    continue

                if lowest_dof is None or len(influence.dof) < num_influences:
                    lowest_dof = influence
                    num_influences = len(influence.dof)

            added = False
            if lowest_dof is not None:
                valid_choices = []
                for i in lowest_dof.dof:
                    state_id = get_state_id(state + [i])
                    if state_id in visited:
                        continue
                    valid_choices.append(i)

                if len(valid_choices) > 0:
                    i = valid_choices[0]
                    if len(valid_choices) > 1:
                        p_partial = np.zeros(len(valid_choices))
                        index = 0
                        for j in valid_choices:
                            p_partial[index] = p_dist[j]
                        np.divide(p_partial, np.sum(p_partial), p_partial)
                        i = np.random.choice(valid_choices, p=p_partial)

                    state_id = get_state_id(state + [i])
                    visited.add(state_id)
                    state.append(i)
                    added = True

            revert = False
            if added:
                i = state[-1]
                for influence in influences:
                    if i in influence.dof:
                        if len(influence.dof) == 1 and influence.coherent:
                            revert = True
                        influence.coherent = not influence.coherent
                        influence.dof.remove(i)

            if revert or not added:
                if len(state) == 0:
                    break
                i = state.pop(random.randrange(len(state)))
                for influence in influences:
                    if i in influence.original_dof and not i in influence.dof:
                        influence.coherent = not influence.coherent
                        influence.dof.add(i)
        
        if len(state) > 0:
            epoch += 1
            p_dist -= 0.0001 * (sample_size ** 2)
            for i in state:
                p_dist[i] += 0.0002 * (sample_size ** 2)
            # sample_size += 1
            print(p_dist)
        else:
            # sample_size -= 1
            pass


if __name__ == "__main__":
    main()