#We simulate the Stemann parallel algorithm
import random
import math

#The principal variables are defined here
#k is the parameter that appears in the description of the algorithm
#Bins answer to all the messages if they received less than k and else 0
k = 3
n = 1000000
#Balls choose the bins they are communicating with at the beginning
#Choices is the list of their initial choices
choices = range(n)
#Balls[i]=j means that the ball i is in the bin j (if j is -1 then i hasn't commited)
Balls = range(n)
#Bins[i] is the load of the bin i
Bins = range(n)
#Bins_round[i] is the list of the balls that have sent a message to bin i during the round simulated
bins_round = range(n)
#Balls_round[i] is the list of bins that have answered to the ball i during the round simulated
balls_round = range(n)
#An useful list
l = range(n)

#It puts k in all the cases of the list l
def place(k,l):
	for i in range(len(l)):
		l[i] = k

#It begins a simulation by defining the different lists according to the number of balls
def change_n(k):
	global n
	global Balls
	global Bins
	global bins_round
	global balls_round
	global l
	n = k
	l = range(n)
	Balls = range(n)
	Bins = range(n)
	bins_round = range(n)
	balls_round = range(n)
	l = range(n)

#It allows to begin a new simulation
def remise_zero():
	place(-1,Balls)
	place(0,Bins)
	for i in l:
		choices[i] = random.sample(l,2)

#This function simulates a round of the algorithm without priority
#nb_balls is the number of balls left
#Current_ball lists the balls that are still her : we have nb_balls = len(current_balls)
def round(nb_balls,current_balls):
	place([],balls_round)
	place([],bins_round)
	for i in range(nb_balls):
                #The choices are defined before by remise_zero
		for b in choices[current_balls[i]]:
			bins_round[b] = bins_round[b] + [current_balls[i]]
	#If the balll i got less than k messages it answers
	for i in range(n):
		len_i = len(bins_round[i])
		if len_i <= k: 
			for j in bins_round[i]:
				balls_round[j] = balls_round[j] + [i]
	#If a ball can commit, it commits
	for i in range(n):
		if len(balls_round[i]) !=  0:
			choice_commit = random.choice(balls_round[i])
			Balls[i] = choice_commit
			Bins[choice_commit] = Bins[choice_commit] + 1			

#It sumulates one time the algorithm
def simulation():
	current_balls = range(n)
	remise_zero()
	nb_balls = n
	nb_rounds = 0
	while nb_rounds < 3:
		round(nb_balls,current_balls)
		current_balls = [b for b in range(n) if Balls[b] == -1]
		nb_balls = len(current_balls)
		nb_rounds = nb_rounds +1
		print(nb_balls)
	return(nb_balls)
		
	
def nb_moy(essais):
	nb_balls_moy = 0.
	for i in range(essais):
		remise_zero()
		nb_balls_moy = nb_balls_moy + (float(simulation()))/(float(essais))	
	print(nb_balls_moy)
	
nb_moy(10)