Felix A Behrend's Algorithm for Set Coloring used for Communication Complexity

behrend.py

'''
This script is an implementation of Behrend's algorithm for set coloring.
Here we use it for communication complexity:

The question is, if the numbers [x,y,z] add up to n.
You can set n as well as the numbers
'''

import math
import numpy as np 

n = 16
numbers = [2,5,8]

def baseN(num,b,numerals="0123456789abcdefghijklmnopqrstuvwxyz"):
    # (see: http://code.activestate.com/recipes/65212/)
    return ((num == 0) and numerals[0]) or (baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b])

def exact_n(n, numbers):
    r = math.sqrt(math.log(n, 2))
    d = 2**r 
    bound = d**r
    based_numbers = [baseN(number, int(d)) for number in range(1,n+1)]
    vectors = [ np.array(list(bn), dtype=int) for bn in based_numbers ]
    norms = [ int(np.linalg.norm(v)**2) for v in vectors ]
    print("Colors:", norms)
    
    x = numbers[0]
    y = numbers[1]
    z = numbers[2]
    
    xp = n - y - z
    yp = n - x - z
    
    print("")
    
    try:
        print("Alice computes color of x' + 2y = %s:  " % (xp+2*y), norms[xp+2*y-1])
        print("Bob computes color of x + 2y =  %s:    " % (x+2*y), norms[x+2*y-1])
        print("Charlie computes color of x + 2y' = %s:" % (x+2*yp), norms[x+2*yp-1])
    except:
        print("Not possible")
    
exact_n(n, numbers)