A digital-collectibles drop builds each avatar by picking one option for every trait (background, hat, glasses, ...). Some options are rarer than others, so every option carries a positive integer weight: an option with weight 6 should come up three times as often as one with weight 2 in the same trait. Two avatars may end up identical; that's allowed.
Implement:
NFTGenerator(config: dict[str, list[tuple[str, int]]]):configmaps each trait name to its options as(value, weight)pairs. RaiseValueErrorif some trait has no options or some weight is not a positive integer.generate(n: int, rng: random.Random) -> list[dict[str, str]]: returnnavatars, each a dict with one chosen value per trait.n = 0gives[].
Exact sampling rule (so the output is reproducible): build the avatars one at a time. For each avatar, go through the traits in config's order, and for each trait call rng.randrange(W) exactly once, where W is the sum of that trait's weights. With that number r, choose the first option (in list order) whose running total of weights is greater than r.
config = {
"background": [("blue", 1), ("gold", 3)], # running totals 1, 4
"hat": [("none", 5), ("cap", 4), ("crown", 1)], # running totals 5, 9, 10
}
gen = NFTGenerator(config)
# If the draws come out as r = 2 (background, W=4) and r = 7 (hat, W=10):
# background: 1 > 2? no; 4 > 2? yes -> "gold"
# hat: 5 > 7? no; 9 > 7? yes -> "cap"
# -> {"background": "gold", "hat": "cap"}
gen.generate(3, random.Random(0)) # three such dicts, depending on the rng
A trait can have 100,000 options and generate may be asked for tens of thousands of avatars, so a linear scan over the options per draw is too slow. Do the per-trait preparation once, then make each pick in O(log k).
Show hint
Store each trait's running totals (prefix sums). The chosen option is the first index whose prefix sum is > r, which is exactly bisect.bisect_right(prefix, r).