import random

# array of candidates arriving in random order. candidate 1 is the best candidate
candidates = [6, 9, 2, 1, 5, 4, 10, 7, 3, 8]


# Write a function that will enable us choose the best candidate.
# - The optimal solution is to reject the first n/e applicants.
# - Choose the first candidate who is better than the best candidate from the rejected candidates.
# - If there is no candidate who is better then choose the last candidate.
def best_candidate(arr: list):
    """
    1. For N candidates, reject the first N/e candidates. e==2.7
    2. Choose the first candidate who is better than the best candidate from the rejected candidates.
    3. If there is no candidate who is better then choose the last candidate.
    """
    # assumes that the best candidate the one whose index is lowest
    random.shuffle(arr)
    e = 2.7
    reject_at = round(len(arr) / e)  # reject first 36%
    best_from_rejected = min(candidates[:reject_at])
    rest = candidates[reject_at:]
    for i in rest:
        if i < best_from_rejected:
            return i
    return rest[-1]


best_candidate(candidates)


# We can prove that this func works.
# The following loop should print a number close to 1(the best candidate) the majority of time.
for i in range(0, 7):
    random.shuffle(candidates)
    print(best_candidate(candidates))


# doc: https://danluu.com/sattolo/
# This is same algo used in pythons `random.shuffle`
def fisher_yates_shuffle(arr: list):
    n = len(arr)
    for i in range(n - 1):
        j = random.randrange(i, n)
        arr[i], arr[j] = arr[j], arr[i]