Random Number Generator Scaling

HardPython

Problem

Course Hero uses a uniform random generator that returns an integer from 1 through 5. Implement a function that produces a uniformly distributed integer from 1 through 7, using only values from that generator.

For deterministic testing, the function receives rolls, a list of successive independent outputs from the 1-through-5 generator. Consume values from left to right and return the generated value. Test inputs contain enough values to produce a result.

Formal Specification

Implement generate_random_7(rolls):

Input: rolls, a list of integers where every value is uniformly generated from [1, 5].
Output: One integer uniformly distributed from [1, 7].
Each value in rolls may be consumed at most once.

Combine two rolls to create 25 equally likely outcomes. Keep the first 21 outcomes, reject the remaining 4, and map the accepted outcome evenly to values 1 through 7.

Constraints

1 <= len(rolls) <= 10^5
Every roll is an integer in [1, 5].
The input contains enough rolls to produce one output.
Each underlying generator result is independent and uniformly distributed.

Function Signature

def generate_random_7(rolls):

Formal Specification

Implement generate_random_7(rolls):

Input: rolls, a list of integers where every value is uniformly generated from [1, 5].
Output: One integer uniformly distributed from [1, 7].
Each value in rolls may be consumed at most once.

Combine two rolls to create 25 equally likely outcomes. Keep the first 21 outcomes, reject the remaining 4, and map the accepted outcome evenly to values 1 through 7.