import math
import random
import time


# Time: O(n). Space: O(n).
def generate_candidates(n):
    candidates = list(range(1, n + 1))
    random.shuffle(candidates)
    return candidates


# 1. MONTE CARLO SIMULATION (Secretary Problem / 1/e Rule)
# Hiring one candidate list: O(n) time and O(1) extra space.
def hire_monte_carlo(candidates):
    if not candidates:
        raise ValueError("At least one candidate is required.")

    k = int(len(candidates) / math.e)
    benchmark = max(candidates[:k]) if k else 0

    for candidate in candidates[k:]:
        if candidate > benchmark:
            return candidate

    return candidates[-1]


# Time: O(trials * n). Space: O(n) for each shuffled candidate list.
def run_monte_carlo_experiment(n=100, trials=10000):
    if n < 1 or trials < 1:
        raise ValueError("Candidate and trial counts must be positive.")

    best_count = 0
    total_score = 0

    for _ in range(trials):
        hired = hire_monte_carlo(generate_candidates(n))
        if hired == n:
            best_count += 1
        total_score += hired

    return best_count / trials * 100, total_score / trials


# 2. LAS VEGAS ALGORITHM
# Expected time: O(n); worst-case time is unbounded. Space: O(n).
def hire_las_vegas(n):
    if n < 1:
        raise ValueError("At least one candidate is required.")

    attempts = 0
    while True:
        attempts += 1
        hired = hire_monte_carlo(generate_candidates(n))
        if hired == n:
            return hired, attempts


if __name__ == "__main__":
    n, trials = 100, 10000

    start = time.perf_counter()
    success_rate, average_score = run_monte_carlo_experiment(n, trials)
    monte_carlo_time = time.perf_counter() - start

    print(f"Success rate: {success_rate:.2f}%")
    print(f"Average hired rank: {average_score:.2f} / {n}")
    print(f"Monte Carlo time: {monte_carlo_time:.4f} seconds")

    start = time.perf_counter()
    best, attempts = hire_las_vegas(n)
    las_vegas_time = time.perf_counter() - start

    print(f"Best candidate rank: {best}")
    print(f"Shuffle attempts: {attempts}")
    print(f"Las Vegas time: {las_vegas_time:.6f} seconds")
