probabilities/model_probabilities4.py

import hashlib
import math
from statistics import median, stdev
import numpy as np
import random

def count_one_bits(n):
    return bin(n).count("1")

def xor_n(n):
    return count_one_bits(n) % 2

def sha_n(n):
    m = hashlib.sha256()
    m.update(str(n).encode("utf-8"))
    result = m.digest()
    return result[0] & 0b1

def xor_by_index(knowns, index, reverse=False):
    mask = 1 << index
    knowns = knowns[:]
    for i in range(len(knowns)):
        known = knowns[i]
        if known[0] & mask or (not (known[0] & mask) and reverse):
            knowns[i] = (known[0], known[1] ^ 1)
    return knowns

def remove_bit(i, n):
    return (i & ((1 << n) - 1)) | ((i & ~((1 << (n + 1)) - 1)) >> 1)

def split_at(knowns, N, i):
    mask = 1 << i
    left = [(remove_bit(j, i), value) for (j, value) in knowns if (j & mask) == 0]
    right = [(remove_bit(j, i), value) for (j, value) in knowns if not (j & mask) == 0]
    return (left, right)

def factor_at(knowns, N, i, identity_value=1):
    mask = 1 << i
    left = [(j, value) for (j, value) in knowns if value == identity_value or (j & mask) == 0]
    right = [(j, value) for (j, value) in knowns if value == identity_value or not (j & mask) == 0]
    return (left, right)

def compute_coherence(pair, N, depth = 0):
    (left, right) = pair
    (left_depth, left_coherence) = compute_split_knowns_r(left, N, depth)
    (right_depth, right_coherence) = compute_split_knowns_r(right, N, depth)
    ratio = min(len(left), len(right)) / max(len(left), len(right))
    # evenness = min(left_coherence, right_coherence) / max(left_coherence, right_coherence) if left_coherence > 0 and right_coherence > 0 else 1.0
    evenness = left_coherence - right_coherence
    # return 0.75 * min(left_coherence, right_coherence) + 0.25 * evenness ** 2
    # return 0.8 * min(left_coherence, right_coherence) + 0.2 * evenness ** 2
    coherence = left_coherence if left_depth > right_depth else right_coherence if right_depth > left_depth else (left_coherence + right_coherence) / 2.0
    depth = max(left_depth, right_depth)
    return (depth, 0.9 * coherence + 0.1 * (1.0 - (evenness ** 2)))

def compute_split_knowns_r(knowns, N, depth = 0):
    if len(knowns) == 0:
        return (depth, 1.0)

    hist = np.zeros(N)
    for i in range(0, N):
        mask = 1 << i
        for (j, value) in knowns:
            if j & mask == 0:
                hist[i] += 1

    constant_bits = [i for i in range(0, N) if hist[i] == 0 or hist[i] == len(knowns)]
    if len(constant_bits) > 0:
        constant_bits.reverse()
        for n in constant_bits:
            knowns = [(remove_bit(j, n), value) for (j, value) in knowns]
        return compute_split_knowns_r(knowns, N - len(constant_bits), depth)

    if len(knowns) == 1:
        return (depth, 1.0)
    if len(knowns) == 2:
        if knowns[0][1] == knowns[1][1]:
            return (depth, 1.0)
        else:
            return (depth, 0.0)

    sum = 0
    denominator = 0
    for i in range(0, N):
        (left, right) = split_at(knowns, N, i)
        (depth, partial) = compute_coherence((left, right), N, depth + 1)
        sum += depth * partial
        denominator += depth
    return (depth, sum / denominator)

def invert(knowns):
    inverted_knowns = []
    for (i, value) in knowns:
        inverted_knowns.append((i, 1 - value))
    return inverted_knowns

def reduce(knowns, N):
    flips = []
    (depth, best_coherence) = compute_split_knowns_r(knowns, N)
    print(best_coherence)
    print(knowns)
    print()
    while best_coherence < 1.0:
        best_index = -1
        best_reverse = False
        # best_coherence = 0
        for i in range(0, N):
            for reverse in [False, True]:
                mutated_knowns = xor_by_index(knowns, i, reverse)
                # coherence = compute_coherence(mutated_knowns, N)
                (depth, coherence) = compute_split_knowns_r(mutated_knowns, N)
                print(i, reverse, coherence)
                if coherence > best_coherence:
                    best_coherence = coherence
                    best_index = i
                    best_reverse = reverse
        if best_index < 0:
            break
        knowns = xor_by_index(knowns, best_index, best_reverse)
        flips.append((best_index, best_reverse))
        print()
        print(best_index, best_reverse, best_coherence)
        print(knowns)
        print()
    return (knowns, best_coherence, flips)

def solve(knowns, N):
    (knowns, coherence, flips) = reduce(knowns, N)
    if coherence == 1.0:
        inverted = knowns[0][1]
        return (inverted, flips, None)
    
    raise Exception('Stop')

    best_coherence = 0
    best_index = -1
    best_identity_value = False
    print()
    for i in range(0, N):
        for identity_value in [0, 1]:
            coherence = compute_coherence(factor_at(knowns, N, i, identity_value), N)
            print(i, identity_value, coherence)
            if coherence > best_coherence:
                best_coherence = coherence
                best_index = i
                best_identity_value = identity_value
    print()
    (left, right) = factor_at(knowns, N, best_index, best_identity_value)
    return (0, flips, (best_identity_value, solve(left, N), solve(right, N)))

def evaluate(model, n, value = 0):
    (inverted, flips, child) = model
    for (i, invert) in flips:
        mask = (1 << i)
        masked_n = n & mask
        if (masked_n > 0 and not invert) or (masked_n == 0 and invert):
            value = 1 - value
    if not child is None:
        (identity, left_child, right_child) = child
        left = evaluate(left_child, n, 1 - identity)
        right = evaluate(right_child, n, 1 - identity)
        if left and right:
            value = 1 - value
        if identity == 0:
            value = 1 - value
    if inverted:
        value = 1 - value
    return value

def main():
    N = 8
    S = 2 ** N
    train_size = 16
    test_size = 100
    f = xor_n

    knowns = [(i, f(i)) for i in [
        # 0, 1, 2, 3, 4, 5, 6, 7
        # 0, 3, 4, 5, 7
        # 3, 5, 6, 10, 12, 14
        # 1, 3, 7, 10, 14, 15
        # 0, 3, 5, 6, 10, 11, 12
        # 0, 3, 5, 6, 10, 11, 12, 24, 30
        # 0, 3, 5, 6, 10, 11, 12, 24, 30, 52, 63, 255, 243, 127
        # 128, 131, 248, 0, 7, 13, 17, 19
        23, 38, 46, 89, 108, 110, 114, 119, 137, 168, 177, 201, 206, 232, 247, 255
    ]]

    # f = xor_n
    # knowns = []
    # train_samples = set()
    # for i in range(0, train_size):
    #     k = random.randint(0, S)
    #     while k in train_samples:
    #         k = random.randint(0, S)
    #     knowns.append((k, f(i)))
    #     train_samples.add(k)

    model = solve(knowns, N)
    # print(model)
    correct = 0
    for i in range(0, test_size):
        if f(i) == evaluate(model, i):
            correct += 1
    print(str(correct) + "/" + str(test_size))

if __name__ == "__main__":
    main()