249 lines
8.5 KiB
Python
Executable File
249 lines
8.5 KiB
Python
Executable File
import hashlib
|
|
import math
|
|
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 span(s, N):
|
|
lower_bound = (1 << N) - 1
|
|
upper_bound = 0
|
|
for (x, _) in s:
|
|
upper_bound |= x
|
|
lower_bound &= x
|
|
return 2 ** count_one_bits(lower_bound ^ upper_bound)
|
|
|
|
def compute_coherence(pair, N):
|
|
(left, right) = pair
|
|
left_coherence = compute_split_knowns_r(left, N)
|
|
right_coherence = compute_split_knowns_r(right, N)
|
|
|
|
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
|
|
evenness = (1.0 - ((1.0 - left_coherence) - (1.0 - right_coherence)) ** 2)
|
|
# 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)))
|
|
# return 0.8 * min(left_coherence, right_coherence) + 0.2 * (1.0 - (evenness ** 2))
|
|
# return 0.75 * min(left_coherence, right_coherence) + 0.25 * (evenness ** 2)
|
|
# return ((left_coherence * len(left) + right_coherence * len(right)) / (len(left) +len(right))) * min(left_coherence, right_coherence) * evenness
|
|
# return min(left_coherence, right_coherence) * (evenness ** 2)
|
|
# coherence = ((len(left) / (len(left) + len(right))) * left_coherence + (len(right) / (len(left) + len(right))) * right_coherence)
|
|
# return min(left_coherence, right_coherence) * (evenness ** 2)
|
|
span_left = span(left, N)
|
|
span_right = span(right, N)
|
|
weighted_left_coherence = span_left * left_coherence / (span_left + span_right)
|
|
weighted_right_coherence = span_right * right_coherence / (span_left + span_right)
|
|
return (weighted_left_coherence + weighted_right_coherence) * (evenness ** 2)
|
|
|
|
def compute_split_knowns_r(knowns, N):
|
|
# if len(knowns) == 0:
|
|
# return 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 1.0
|
|
if len(knowns) == 2:
|
|
if knowns[0][1] == knowns[1][1]:
|
|
return 1.0
|
|
else:
|
|
return 0.0
|
|
|
|
sum = 0
|
|
denominator = 0
|
|
for i in range(0, N):
|
|
(left, right) = split_at(knowns, N, i)
|
|
if len(left) == 0 or len(right) == 0:
|
|
continue
|
|
weight = min(span(left, N), span(right, N))
|
|
# weight = max(span(left, N), span(right, N)) / min(span(left, N), span(right, N))
|
|
# weight = 1.0 - (abs(len(left) - len(right)) / (len(left) + len(right)))
|
|
if weight == 0:
|
|
continue
|
|
partial = compute_coherence((left, right), N - 1)
|
|
sum += weight * partial
|
|
denominator += weight
|
|
return 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 = []
|
|
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)
|
|
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 run_for_input(input):
|
|
N = 8
|
|
S = 2 ** N
|
|
train_size = 128
|
|
test_size = 100
|
|
f = xor_n
|
|
|
|
knowns = [(i, f(i)) for i in input]
|
|
|
|
# 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)
|
|
# print(model)
|
|
correct = 0
|
|
for i in range(0, test_size):
|
|
k = random.randint(0, S - 1)
|
|
if f(k) == evaluate(model, k):
|
|
correct += 1
|
|
print(str(correct) + "/" + str(test_size))
|
|
|
|
def run():
|
|
inputs = [
|
|
# [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]
|
|
]
|
|
results = []
|
|
for i, input in enumerate(inputs):
|
|
success = False
|
|
try:
|
|
run_for_input(input)
|
|
success = True
|
|
except:
|
|
pass
|
|
results.append(success)
|
|
print(results)
|
|
|
|
if __name__ == "__main__":
|
|
run() |