import math import numpy as np import sys np.set_printoptions(threshold=sys.maxsize) def decode(x, N): index = 0 output = np.zeros((N)) while x > 0 and index < N: output[index] = x & 0b1 x >>= 1 index += 1 return output def hamming_distance(a, b): return np.sum(np.logical_xor(a, b)) def xor(x, bits): return np.sum(x[:bits]) % 2 def compute_pseudopascal(N): dist = np.zeros((N, N)) for j in range(0, N): dist[0][j] = math.comb(N - 1, j) dist[-1][j] = math.comb(N, j + 1) * (1 - (j % 2)) for i in range(1, N): for j in range(0, i + 1): dist[i][j] = math.comb(i + 1, j + 1) * (1 - (j % 2)) for k in range(i + 1, N): for j in reversed(range(0, k)): dist[i][j+1] = dist[i][j] + dist[i][j+1] return dist def compute_pyramids(N): num_orders = max(int(N / 2), 1) pyramids = np.zeros((num_orders, N, N)).astype(np.int32) # 1st order can be filled in as multiplication and forms the base case for i in range(0, N): for j in range(0, i + 1): pyramids[0][i][j] = (i - j + 1) * (j + 1) for order in range(1, num_orders): offset = order * 2 # fill in the LHS and diagonal for i in range(0, N - offset): value = math.comb(2 * (order + 1) + i - 1, i) pyramids[order][i + offset][0] = value # mirror pyramids[order][i + offset][i + offset] = value # accumulate along the diagonals for i in range(1, N): value = pyramids[order][i][0] acc = value for j in range(1, N - i): value += acc pyramids[order][i + j][j] = value acc += pyramids[order - 1][i + j - 1][j - 1] return pyramids # 2 # 4, 4, # 6, 8, 6 # 8, 12, 12, 8 # 10, 16, 18, 16, 10 # 12, 20, 24, 24, 20, 12 # 14, 24, 30, 32, 30, 24, 14 # 16, 28, 36, 40, 40, 36, 28, 16 # 1 # 2, 2 # 3, 4, 3 # 4, 6, 6, 4 # 5, 8, 9, 8, 5 # 6, 10, 12, 12, 10, 6 # 7, 12, 15, 16, 15, 12, 7 # 6, 0, 6 # 24, 12, 12, 24 # 60, 48, 36, 48, 60 # 120, 120, 96, 96, 120, 120 # 210, 240, 210, 192, 210, 240, 210 # 336, 420, 396, 360, 360, 396, 420, 336 # 504, 672, 672, 624, 600, 624, 672, 672, 504 # 1, 0, 1 # 4, 2, 2, 4 # 10, 8, 6, 8, 10 # 20, 20, 16, 16, 20, 20 # 35, 40, 35, 32, 35, 40, 35 # 56, 70, 66, 60, 60, 66, 70, 56 # 84, 112, 112, 104, 100, 104, 112, 112, 84 # # 20, 0, 20, 0, 20, # 120, 40, 80, 80, 40, 120 # 420, 240, 260, 320, 260, 240, 420 # 1120, 840, 760, 880, 880, 760, 840, 1120 # 1, 0, 1, 0, 1 # 6, 2, 4, 4, 2, 6 # 21, 12, 13, 16, 13, 12, 21 # 56, 42, 38, 44, 44, 38, 42, 56 # 70, 0, 70, 0, 70, 0, 70 # 560, 140, 420, 280, 280, 420, 140, 560 # 252, 0, 252, 0, 252, 0, 252, 0, 252 # 2520, 504, 2016, 1008, 1512, 1512, 1008, 2016, 504, 2520 # 1, 2, 3, 4, # 1, 3, 6, 10 # 1, 4, 10, 20 # 1, 5, 15, 35 # 1, 6, # 1, 2, 1 # 1, 3, 3, 1 # 1, 4, 6, 4, 1 # 1, 5, 10, 10, 5, 1 # 1, 6, 15, 20, 15, 6, 1 # 2, 6, 12, 20, 30, 42, 56 # 6, 30, 90, 210, 420 # 20, 140, 560, # 70 # 1, 3, 6, 10, 15, 21, 28 # 1, 5, 15, 35 def main(): last_incoherent_distances = None last_incoherent_bands = None last_incoherent_sub_bands = None for N in range(4, 5): # print(compute_pseudopascal(10)) # print(compute_pyramids(10)) points = [] for i in range(0, 2 ** N): points.append(decode(i, N)) bands = [[[] for _ in range(0, N + 1)] for _ in range(0, len(points))] for i in range(0, len(points)): a = points[i] for j in range(0, len(points)): if i == j: continue b = points[j] distance = hamming_distance(a, b) bands[i][distance].append(b) # for t in range(0, len(points)): for t in range(0, 1): incoherent_distances = np.zeros((N + 1, N + 1)) incoherent_bands = np.zeros((N + 1, N + 1, N + 1)).astype(np.int32) incoherent_sub_bands = np.zeros((N + 1, N + 1, N + 1, N + 1)).astype(np.int32) for k in range(1, N + 1): # print(k, '================================') x_a = points[t] y_a = xor(x_a, k) total_bands = np.zeros((N + 1, N + 1)).astype(np.int32) for distance in range(0, N + 1): # print('distance', distance) band = bands[t][distance] for x_b in band: y_b = xor(x_b, k) if y_a != y_b: incoherent_distances[k][distance] += 1 if len(band) < 2: continue for band_origin in range(0, len(band)): x_p = band[band_origin] y_p = xor(x_p, k) sub_bands = [[] for _ in range(0, N + 1)] for i in range(0, len(band)): if i == band_origin: continue x_q = band[i] y_q = xor(x_q, k) band_distance = hamming_distance(x_p, x_q) total_bands[distance][band_distance] += 1 if y_p != y_q: incoherent_bands[k][distance][band_distance] += 1 sub_bands[band_distance].append(x_q) # incoherent_sub_bands = np.zeros((N + 1, N + 1)).astype(np.int32) # total_sub_bands = np.zeros((N + 1, N + 1)).astype(np.int32) for band_distance in range(0, N + 1): sub_band = sub_bands[band_distance] if len(sub_band) < 2: continue for sub_band_origin in range(0, len(sub_band)): x_u = sub_band[sub_band_origin] y_u = xor(x_u, k) for i in range(0, len(sub_band)): if i == sub_band_origin: continue x_v = sub_band[i] y_v = xor(x_v, k) sub_band_distance = hamming_distance(x_v, x_u) # total_sub_bands[band_distance][sub_band_distance] += 1 if y_u != y_v: incoherent_sub_bands[k][distance][band_distance][sub_band_distance] += 1 # print(incoherent_sub_bands) # print(total_sub_bands) # print('==========================') if last_incoherent_sub_bands is not None: for distance in range(1, int(N / 2) + 1): for band_distance in range(0, N + 1): for sub_band_distance in range (0, N + 1): if band_distance >= N or sub_band_distance >= N or last_incoherent_sub_bands[1][distance][band_distance][sub_band_distance] == 0: value = incoherent_sub_bands[1][distance][band_distance][sub_band_distance] if value > 0: print(N, value, (distance, band_distance, sub_band_distance)) last_incoherent_distances = incoherent_distances last_incoherent_bands = incoherent_bands last_incoherent_sub_bands = incoherent_sub_bands # print(bands) if __name__ == "__main__": main()