import math
import random
import time


def generate_candidates(num_candidates):
    """Generates candidates with unique random score ranks from 1 to N."""
    candidates = list(range(1, num_candidates + 1))
    random.shuffle(candidates)
    return candidates


# 1. MONTE CARLO SIMULATION (Secretary Problem / 1/e Rule)
def hire_monte_carlo(candidates):
    """Fixed-time randomized algorithm.
    Rejects the first k = n/e candidates to set a benchmark, 
    then hires the first candidate who outperforms the benchmark.
    
    Guarantees ~37% success rate of picking the absolute best candidate.
    """
    n = len(candidates)
    k = int(n / math.e)  # Optimal sample size (~37% of N)

    # Phase 1: Observe first k candidates to set benchmark score
    benchmark = max(candidates[:k]) if k > 0 else 0

    # Phase 2: Hire the first candidate strictly better than benchmark
    for candidate in candidates[k:]:
        if candidate > benchmark:
            return candidate  # Hired candidate

    # Fallback: if no one was better, hire the very last candidate
    return candidates[-1]


def run_monte_carlo_experiment(num_candidates=100, trials=10000):
    """Runs multiple Monte Carlo trials to observe the theoretical ~37% success probability."""
    best_hired_count = 0
    total_score = 0

    for _ in range(trials):
        candidates = generate_candidates(num_candidates)
        hired = hire_monte_carlo(candidates)

        if hired == num_candidates:  # Max rank is num_candidates
            best_hired_count += 1
        total_score += hired

    success_rate = (best_hired_count / trials) * 100
    avg_score = total_score / trials
    return success_rate, avg_score


# 2. LAS VEGAS ALGORITHM
def hire_las_vegas(num_candidates):
    """Randomized runtime algorithm.
    Guarantees finding the BEST candidate by repeating random shuffles
    until the 1/e stopping rule successfully lands on the best candidate.
    
    Runtime varies; result is 100% correct.
    """
    attempts = 0
    target_best = num_candidates

    while True:
        attempts += 1
        candidates = generate_candidates(num_candidates)
        hired = hire_monte_carlo(candidates)

        # Success condition: guaranteed correct answer required by Las Vegas design
        if hired == target_best:
            return hired, attempts


if __name__ == "__main__":
    N = 100  # Total candidates
    TRIALS = 10000

    print("=" * 55)
    print(f" HIRING PROBLEM SIMULATION (N = {N} candidates)")
    print("=" * 55)

    # --- Run Monte Carlo Simulation ---
    print("\n[1] Running Monte Carlo Simulation...")
    start_time = time.perf_counter()
    success_rate, avg_score = run_monte_carlo_experiment(N, TRIALS)
    mc_time = time.perf_counter() - start_time

    print(f"    - Total Trials: {TRIALS}")
    print(f"    - Success Rate (Hired Absolute Best): {success_rate:.2f}% (Expected ~36.8%)")
    print(f"    - Average Hired Candidate Rank: {avg_score:.2f} / {N}")
    print(f"    - Total Execution Time: {mc_time:.4f} seconds")

    # --- Run Las Vegas Algorithm ---
    print("\n[2] Running Las Vegas Algorithm...")
    start_time = time.perf_counter()
    best_candidate, attempts_needed = hire_las_vegas(N)
    lv_time = time.perf_counter() - start_time

    print(f"    - Hired Candidate Rank: {best_candidate} (Guaranteed Best)")
    print(f"    - Number of Shuffle Attempts Needed: {attempts_needed}")
    print(f"    - Total Execution Time: {lv_time:.6f} seconds")