Simulating a Lucky Streak

A sports commentator claims that a team winning r coin tosses in a row during a season of n tosses is "astonishing". Before arguing, estimate how likely such a streak is by simulation.

Write streak_estimate(n, r, trials, seed). It must follow these rules exactly, so that its result can be checked:

• Create one generator rng = random.Random(seed) at the start, and use no other randomness.
• Run trials seasons one after the other. In each season, toss n coins in order; a toss is heads when rng.random() < 0.5 and tails otherwise. Always make all n tosses of a season, even after a streak has appeared, so every season uses exactly n random numbers.
• A season counts when its longest run of consecutive heads is at least r.

Return the fraction of seasons that count, as a float.

Examples

Input:  n = 10, r = 3, trials = 1000, seed = 1
Output: 0.508
Explanation: 508 of the 1000 simulated seasons had three or more heads in a row.
The exact probability is 520/1024 = 0.5078, so the estimate is good to about 0.01.

Input:  n = 10, r = 3, trials = 20000, seed = 1
Output: 0.5033

Constraints

• 1 <= n <= 200, 1 <= r <= n, 1 <= trials, and n * trials <= 10**6
• 0 <= seed < 2**32
• the result must not depend on the clock or on any other randomness

Goals

• Estimate a probability by repeating a random experiment many times
• Use one seeded random.Random generator so results can be reproduced and checked
• Track the longest run of a repeated outcome