# Simple vs complex contagion (Centola & Macy 2007; Centola 2010).
# 400 people, each with 8 contacts. Clustered network: a ring where everyone knows their 4 nearest
# neighbours on each side. Random network: the same contacts shuffled by degree-preserving swaps.
# Simple contagion: adopt after 1 adopting contact. Complex contagion: adopt only after 2 or 3 (a behaviour
# that needs reinforcement from more than one person). Simplified model.
import random
random.seed(5)
N, K = 400, 4

def ring():
    return {(min(i, (i + j) % N), max(i, (i + j) % N)) for i in range(N) for j in range(1, K + 1)}

def shuffled(edges, swaps=20000):
    e = list(edges)
    s = set(e)
    for _ in range(swaps):
        i, j = random.randrange(len(e)), random.randrange(len(e))
        (a, b), (c, d) = e[i], e[j]
        if len({a, b, c, d}) < 4:
            continue
        n1, n2 = (min(a, d), max(a, d)), (min(c, b), max(c, b))
        if n1 in s or n2 in s:
            continue
        s -= {e[i], e[j]}
        s |= {n1, n2}
        e[i], e[j] = n1, n2
    return s

def spread(edges, threshold):
    nb = {i: set() for i in range(N)}
    for a, b in edges:
        nb[a].add(b)
        nb[b].add(a)
    adopted = {0} | nb[0]                     # one person and their contacts start
    steps = 0
    while True:
        new = {i for i in range(N) if i not in adopted and len(nb[i] & adopted) >= threshold}
        if not new:
            return len(adopted) / N, steps
        adopted |= new
        steps += 1

lattice = ring()
print("threshold   clustered network          random networks (20): mean reach, networks reaching > 90 %")
for threshold in (1, 2, 3):
    f_lat, s_lat = spread(lattice, threshold)
    runs = [spread(shuffled(lattice), threshold) for _ in range(20)]
    mean = sum(r[0] for r in runs) / len(runs)
    full = [r[1] for r in runs if r[0] > 0.9]
    speed = f" (in {sum(full) / len(full):4.1f} rounds)" if full else ""
    print(f"{threshold:5d}       {100 * f_lat:5.1f} % in {s_lat:3d} rounds     {100 * mean:5.1f} %, {len(full):2d} of 20{speed}")
# threshold   clustered network          random networks (20): mean reach, networks reaching > 90 %
#     1       100.0 % in  49 rounds     100.0 %, 20 of 20 (in  3.9 rounds)
#     2       100.0 % in  65 rounds      71.1 %, 14 of 20 (in 11.9 rounds)
#     3       100.0 % in  98 rounds       2.3 %,  0 of 20

# A 30-day course in 4 stages, 120 learners per arm. Arm A: study alone. Arm B "teach to unlock":
# after passing a stage you must help 2 classmates before the next stage opens (if no classmate is
# left on that stage, it opens anyway). Three ways of counting "help 2":
#   B1  2 classmates must PASS while you are their tutor; one tutor per classmate
#   B2  the same, but a classmate may have two tutors at once (a learning trio)
#   B3  2 logged tutoring sessions with different classmates, whether or not they have passed yet
# Simplified model; every number is an assumption, chosen only to show the mechanics.
import random
random.seed(2)
DAYS, STAGES, COHORT, REPS = 30, 4, 120, 40
P_ALONE, P_HELPED = 0.22, 0.30     # daily chance of passing the current stage: alone / with a tutor
QUIT = 0.02                        # daily chance of quitting, arm A

def run(rule, quit_cut):
    q = QUIT * (1 - quit_cut) if rule != "A" else QUIT
    max_tutors = 2 if rule == "B2" else 1
    passed, teaching, credit = [0] * COHORT, [False] * COHORT, [set() for _ in range(COHORT)]
    out = [False] * COHORT
    for _ in range(DAYS):
        live = [i for i in range(COHORT) if not out[i] and passed[i] < STAGES]
        for i in live:
            if random.random() < q:
                out[i] = True
        live = [i for i in live if not out[i]]
        studying = [i for i in live if not teaching[i]]
        tutors = {s: [] for s in studying}
        if rule != "A":
            for t in (i for i in live if teaching[i]):
                pool = [s for s in studying if passed[s] == passed[t] - 1
                        and len(tutors[s]) < max_tutors and s not in credit[t]]
                if pool:
                    s = random.choice(pool)
                    tutors[s].append(t)
                    if rule == "B3":
                        credit[t].add(s)          # a session counts as help
        for s in studying:
            if random.random() < (P_HELPED if tutors[s] else P_ALONE):
                passed[s] += 1
                if rule in ("B1", "B2"):
                    for t in tutors[s]:
                        credit[t].add(s)          # only a pass counts as help
                if rule != "A" and passed[s] < STAGES:
                    teaching[s], credit[s] = True, set()
        if rule != "A":
            for t in live:
                if teaching[t]:
                    left = [s for s in live if not teaching[s] and passed[s] == passed[t] - 1]
                    if len(credit[t]) >= 2 or not left:
                        teaching[t] = False
    return sum(1 for p in passed if p >= STAGES) / COHORT

def mean(rule, cut=0.0):
    return sum(run(rule, cut) for _ in range(REPS)) / REPS

a = mean("A")
print(f"A   study alone: {100 * a:4.1f} % complete by day 30")
print("rule   quitting reduced by:     0 %      30 %      60 %")
for rule in ("B1", "B2", "B3"):
    row = "  ".join(f"{100 * mean(rule, c):6.1f} %" for c in (0.0, 0.3, 0.6))
    print(f"{rule}                        {row}")
print(f"why B1 jams: on each stage, {COHORT} learners need 2 x {COHORT} = {2 * COHORT} credited passes,")
print(f"but at most {COHORT - 1} classmates can pass after someone else - so most tutors wait for the slowest")
# A   study alone: 65.6 % complete by day 30
# rule   quitting reduced by:     0 %      30 %      60 %
# B1                           5.6 %     6.4 %     6.7 %
# B2                          10.9 %    11.2 %    12.8 %
# B3                          56.4 %    62.8 %    70.8 %
# why B1 jams: on each stage, 120 learners need 2 x 120 = 240 credited passes,
# but at most 119 classmates can pass after someone else - so most tutors wait for the slowest