hats_in_line_en.py

def give_answer(prev_answers, next_hats_colors, m): 
    #prev_answers - sequence of previous answers that were called out
    #next_hats_colors - colors of the hats that wee see ahead,
    #m - number of different possible colors
    next_colors_sum = 0
    for next_color in next_hats_colors:
        next_colors_sum += next_color #sum all the colors that you we ahead
    answer = next_colors_sum #by default this sum will already be our answer
    if len(prev_answers) > 0: #but if we heard some answers from previous wise-men in line, we recompute
        answer = prev_answers[0] #the answer of the last man in line, he sees all n-1 colors
        for i in range(1, len(prev_answers)):
            answer -= prev_answers[i] #subtract all the next called out answers from the first answer
        answer -= next_colors_sum #and also subtract all the colors that we see ahead
    #Result: difference between called out and seen ahead
    #if prev_answers was empty we simply call out what we see ahead (i.e. we are the last in line)
    return answer % m 

import random
m = 10 #suppose we have 10 colors
n = 1000 #and 1000 wise-men
#generate random colors: these will be hats on wise-men
colors_set = [random.randint(0,m-1) for _ in range(n)]
#create list for answers that are called out, by default no answer (-1)
answers_given = [-1 for _ in range(n)]
#collect answers from the last man in line to the first man
for i in range(n):
    prev_answers, next_hats_colors = answers_given[0:i], colors_set[i+1:n+1]
    answers_given[i] = give_answer(prev_answers, next_hats_colors, m)
    
#check answers, we expect that all except one are guaranteed to survive (but maybe all will)
survived_count = 0
dead_positions = []
for i in range(n):
    if answers_given[i] != colors_set[i]:
        dead_positions.append(i)
    else:
        survived_count += 1
print('Survived:',survived_count,'Dead:',n-survived_count,'Dead positions:',dead_positions)
#We get something like: "Survived: 999 Dead: 1 Dead positions: [0]"
#And if we are lucky enough we get: "Survived: 1000 Dead: 0 Dead positions: []"