hats_in_circle_4000colors_en.py

def raise_hand(man_position, hats_colors): 
    #here we find out if wiseman should raise hand
    #man_position - wiseman position number
    #hats_colors - list of hats colors (we play fair and don't look here on our own color)
    bits_sum = 0 
    last_man = len(hats_colors) - 1
    if man_position != last_man: #these are wise-men 1-12
        #calculate parity of the selected bit-plane sum, except bit in our own hat's color
        for i in range(len(hats_colors)):
            if i == man_position: #skip our own color to play fair
                continue
            bits_sum += (hats_colors[i] >> man_position) & 1 #collect sum
    else:
        #this is wiseman 13, we calculate sum of all the bits that we can see (skip our own hat's color)
        for i in range(last_man):
            buf_val = hats_colors[i]
            while buf_val > 0:
                bits_sum += (buf_val) & 1 #collect sum
                buf_val = buf_val >> 1 #bitshift
    return bits_sum % 2 #return parity

def give_answer(man_position, hands_up, hats_colors):
    last_man = len(hats_colors) - 1
    answer = 0
    #first we restore all the bits except for one using raised hand of wiseman 13
    for i in range(last_man):
        if i == man_position: #we skip our own color
            continue
        #calc sum of i-th bit except for our own color and i-th man hat color
        bit_sum = 0
        for j in range(len(hats_colors)):
            if i == j or j == man_position:
                continue
            bit_sum += (hats_colors[j] >> i) & 1
        #restore i-th answer bit
        answer += (2 ** i) * ((hands_up[i] - bit_sum) % 2)
    if man_position != last_man:
        #here we already restored all except one bit
        #collect sum of all the bits we see, except for bits from hat color of wiseman 13
        bit_sum = 0
        for i in range(last_man):
            if i == man_position: #skip our color to play fair
                continue
            buf_value = hats_colors[i]
            while buf_value > 0:
                bit_sum += buf_value & 1
                buf_value = buf_value >> 1
        #add the bits that we already restored to the sum
        buf_value = answer
        while buf_value > 0:
            bit_sum += buf_value & 1
            buf_value = buf_value >> 1
        #now we finally can correct the bit that we did not know yet
        answer += (2 ** man_position) * ((hands_up[last_man] - bit_sum) % 2)
    return answer
        

import random
#let's model the task, 13 wise-men, 4000 colors randomly set
n = 13
m = 4000
hats_colors = [random.randint(0,4000) for _ in range(n)]
#these arrays are empty for now
hands_up = [0 for _ in range(n)]
answers = [-1 for _ in range(n)]
#first wise-men select who will raise hand (0-not raised, 1-raised)
for man_position in range(n):
    hands_up[man_position] = raise_hand(man_position, hats_colors)
#then they give answers (one of 4000 colors for each)
for man_position in range(n):
    answers[man_position] = give_answer(man_position, hands_up, hats_colors)
#now let's compare their answers and hat colors that were set
are_equal = True
for i in range(n):
    if hats_colors[i] != answers[i]:
        are_equal = False
        break
print('All answers are correct:', are_equal)
#and we get "All answers are correct: True", this was a bit tough