The Demonetization Game

demonetization_game.py

#!/usr/bin/env python3

"""
A script inspired by Vsauce2's video: "The Demonetization Game"
https://www.youtube.com/watch?v=kOnEEeHZp94
"""

import random
from typing import List, Tuple
from dataclasses import dataclass

try:
    from tqdm import tqdm
except ImportError:
    tqdm = lambda x: x


@dataclass
class AbstractPicker:

    list_length: int = 100
    limit: int = 50

    def generate_permutation(self) -> List[int]:
        # Generate a random permutation of all integers
        # from 0 to self.list_length
        permutation = list(range(0, self.list_length))
        random.shuffle(permutation)
        return permutation

    def _pick(self, i: int, permutation: List[int]) -> bool:
        raise NotImplementedError

    def run_once(self) -> Tuple[bool, float]:
        # run the test once and returns a boolean indicating whether
        # or not the operation was a success, along with the average success
        # at the individual level
        permutation = self.generate_permutation()
        group_success = True
        individual_success_average = 0

        for i in range(self.list_length):
            success = self._pick(i, permutation)
            group_success = group_success and success
            individual_success_average += int(success)

        if self.list_length > 0:
            individual_success_average /= self.list_length
        return group_success, individual_success_average

    def run_multiple(self, nb_runs: int) -> Tuple[float, float]:
        # run multiple times the test and compute the success average
        # for the group and at the individual level
        average_group_success = 0
        average_individual_success = 0
        for _ in tqdm(range(nb_runs)):
            group_success, individual_success = self.run_once()
            average_group_success += group_success
            average_individual_success += individual_success

        if nb_runs > 0:
            average_group_success /= nb_runs
            average_individual_success /= nb_runs
        return average_group_success, average_individual_success


class RandomPicker(AbstractPicker):
    # each pick is made randomly
    def _pick(self, i: int, permutation: List[int]) -> bool:
        picks = set()
        while len(picks) < self.limit:
            pick = random.choice(permutation)
            if pick in picks:
                continue
            if pick == i:
                return True
            picks.add(pick)
        return False


class SequencePicker(AbstractPicker):
    # each pick is made by following the sequence:
    # - get the value j at index i
    # - if j is not equal to i, get the value at index j, and repeat
    def _pick(self, i: int, permutation: List[int]) -> bool:
        picks = []
        current_pick = i
        while len(picks) < self.limit:
            pick = permutation[current_pick]
            if pick == i:
                return True
            picks.append(pick)
            current_pick = pick
        return False


def main():
    nb_runs = 1000
    for picker in (RandomPicker, SequencePicker):
        group_success, individual_success = picker().run_multiple(nb_runs)
        print(f"{picker.__name__} with {nb_runs} runs:")
        print(f"* group success average: {group_success * 100:.2f}%")
        print(f"* individual success average: {individual_success * 100:.2f}%")


if __name__ == '__main__':
    main()