from math import log, ceil
from random import random

"""
Broadcasting in unsure graphs
"""

# utils
mean1 = lambda f, p, k : sum(f(p) for _ in range(k))/k
mean2 = lambda f, n, p, k : sum(f(n,p) for _ in range(k))/k
mean3 = lambda f, n, m, p, k : sum(f(n,m,p) for _ in range(k))/k 

# edge
geo = lambda p : ceil(log(random(),1-p))

# star
star = lambda n, p : max(geo(p) for _ in range(n))
uninformed_star = lambda n, p, k : sum(1 for _ in range(n) if geo(p) > k)

mstar = lambda n, m, p : max(path(n,p) for _ in range(m))

# cost of the star
H = lambda n : sum(1/i for i in range(1,n+1))
approx1 = lambda n,p : H(n)/log(1/(1-p))+1/2
approx2 = lambda n,p : log(n*1.781072418,1/(1-p))+1/2

# path
path = lambda n, p : sum(geo(p) for _ in range(n))

# bi-path
bipath = lambda n, m, p : max(path(n,p),path(m,p))

# ring
def ring(n,p):
    nb_draws, nb_informed = 0, 1
    while nb_informed < n:
        if random() <= p:
            nb_informed += 1
        if random() <= p:
            nb_informed += 1
        nb_draws +=1
    return nb_draws

cost_circle = lambda n,p : n/(2*p) - (2-p)/(4*p)*(1+pow(p/(2-p),n))

# trees
tree = lambda d, h, p : max(tree(d,h-1,p)+geo(p) for _ in range(d)) if h != 0 else 0 

## cost
import operator as op
from functools import reduce
def ncr(n, r):
    r = min(r, n-r)
    if r == 0: return 1
    numer = reduce(op.mul, range(n, n-r, -1))
    denom = reduce(op.mul, range(1, r+1))
    return numer//denom

from math import sqrt
bound = lambda n, k, p : n/p * (1+k*sqrt(1-p)*sqrt(n)) + approx(k,p)
lbound = lambda n,k,p : approx(k,p)*n
ubound = lambda n,k,p : approx(k,p)*ncr(n+1,2)


### General simulation algorithm ###
# Généraliser cet algorithme pour qu'il marche pour n'importe quel graphe

def grid(n,m,p):
    def neighbors(i,j):
        return [(x,y) for (x,y) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)] if 0<=x<n and 0<=y<m]

    grid = [[False for j in range(m)] for i in range(n)]
    rounds = 0
    grid[0][0] = True
    frontier = set(neighbors(0,0))
    
    while len(frontier) :
        rounds += 1
        new = set()
        for i,j in frontier:
            for a,b in neighbors(i,j):
                if grid[a][b] and random() < p:
                    new.add((i,j))
                    
        for x,y in new:
            grid[x][y] = True
            frontier.remove((x,y))
            for a,b in neighbors(x,y):
                if not grid[a][b]:
                    frontier.add((a,b))
    return rounds

def broadcast(G):
    pass

def meangrid(n,p,sim=100):
    return sum(grid(n,n,p) for _ in range(sim))/sim

def inftree(h,delta,p,k):
    if h == 0: return 0
    informed = 0
    informed_children = 0
    rounds = 0
    while informed != delta and rounds < k:
        rounds += 1
        for i in range(delta-informed):
            if random() < p:
                informed += 1
                informed_children += inftree(h-1,delta,p,k-rounds)
    return informed+informed_children

def meanuninftree(h,delta,p,k,sim=100):
    n=(delta*(delta**h-1))//(delta-1)
    return sum(n-inftree(h,delta,p,k) for _ in range(sim))/sim

def simtree(n,k,p):
    if n==0:
        return 0
    return max(geo(p)+simtree(n-1,k,p) for _ in range(k))

def meansimtree(n,k,p,sim=100):
    return sum(simtree(n,k,p) for _ in range(sim))/sim

def quasiunitgraph(n,d1,d2,p):
    node = [(random(),random()) for _ in range(n)]
    informed = [False for _ in range(n)]

    distance = lambda a,b : (a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1])

    neighborsG = [[j for j in range(n) if j != i \
                   and distance(node[i],node[j]) <= d1] for i in range(n)]

    neighborsGp = [[j for j in range(n) if j != i \
                   and d1 < distance(node[i],node[j]) <= d2] for i in range(n)]

    print(sum(len(v) for v in neighborsG)/n)
    print(sum(len(v) for v in neighborsGp)/n)

    visited = [False for _ in range(n)]
    def dfs(u):
        visited[u] = True
        for v in neighborsGp[u]:
            if not visited[v]:
                dfs(v)
    dfs(0)
    print(visited, all(visited))
    for v in range(n):
        if not visited[v]:
            print(neighborsG[v], neighborsGp[v])
    
    informed[0] = True
    nb_informed = 1
    rounds = 0

    while nb_informed < n:
        rounds += 1
        new = set()
        
        for i in range(n):
            if informed[i]:
                for j in neighborsG[i]:
                    if not informed[j]:
                        new.add(j)
                        
                for j in neighborsGp[i]:
                    if not informed[j] and random() < p:
                        new.add(j)

        for j in new:
            informed[j] = True
            nb_informed += 1

    return rounds