use std::collections::HashSet;
use std::env;
use std::fs;
use std::process::ExitCode;

const MAX_N: usize = 200_000_000;

fn fail(message: impl AsRef<str>) -> ExitCode {
    eprintln!("FAIL: {}", message.as_ref());
    ExitCode::FAILURE
}

/// Euler's sieve: after prime p is encountered, multiply every affected value
/// by (p-1)/p using exact integer subtraction.
fn totients_through(n: usize) -> Vec<usize> {
    let mut phi: Vec<usize> = (0..=n).collect();
    if n >= 1 {
        phi[1] = 1;
    }
    for p in 2..=n {
        if phi[p] == p {
            for multiple in (p..=n).step_by(p) {
                phi[multiple] -= phi[multiple] / p;
            }
        }
    }
    phi
}

/// Return the rank-at-each-position encoding of a strict ordering pattern.
/// Rank zero means the smallest value. A block with a tie has no strict pattern.
fn strict_pattern(values: &[usize]) -> Option<Vec<usize>> {
    let mut positions: Vec<usize> = (0..values.len()).collect();
    positions.sort_unstable_by_key(|&i| values[i]);
    if positions
        .windows(2)
        .any(|w| values[w[0]] == values[w[1]])
    {
        return None;
    }
    let mut ranks = vec![0; values.len()];
    for (rank, &position) in positions.iter().enumerate() {
        ranks[position] = rank;
    }
    Some(ranks)
}

/// k! if it is at most `bound`; None as soon as it is known to exceed bound.
fn factorial_if_at_most(k: usize, bound: usize) -> Option<usize> {
    let mut value = 1usize;
    for factor in 2..=k {
        if value > bound / factor {
            return None;
        }
        value *= factor;
    }
    Some(value)
}

/// Decide whether all k! strict patterns have occurred among blocks ending by n.
/// Returns (answer, number of distinct patterns observed, k! when small enough).
fn all_patterns(phi: &[usize], n: usize, k: usize) -> (bool, usize, Option<usize>) {
    if k == 0 {
        return (true, 1, Some(1));
    }
    if k > n {
        return (false, 0, None);
    }
    let starts = n - k + 1; // m = 0,...,n-k
    let factorial = factorial_if_at_most(k, starts);
    if factorial.is_none() {
        // There are fewer blocks than patterns, so surjectivity is impossible.
        return (false, 0, None);
    }

    let target = factorial.unwrap();
    let mut observed: HashSet<Vec<usize>> = HashSet::with_capacity(target);
    for m in 0..starts {
        if let Some(pattern) = strict_pattern(&phi[m + 1..m + k + 1]) {
            observed.insert(pattern);
            if observed.len() == target {
                return (true, target, Some(target));
            }
        }
    }
    (false, observed.len(), Some(target))
}

/// The first failed length determines F because occurrence of every pattern at
/// length k+1 implies occurrence of every pattern at length k: extend a desired
/// k-pattern by appending a new largest rank, then restrict an occurrence to its
/// first k positions.
fn compute_f(phi: &[usize], n: usize) -> (usize, usize, Option<usize>) {
    for k in 1..=n {
        let (all, seen, total) = all_patterns(phi, n, k);
        if !all {
            return (k - 1, seen, total);
        }
    }
    (n, 0, None)
}

fn parse_candidate(path: &str) -> Result<(usize, usize, usize), String> {
    let text = fs::read_to_string(path).map_err(|e| format!("cannot read candidate: {e}"))?;
    let tokens: Vec<&str> = text.split_whitespace().collect();
    if tokens.len() != 3 {
        return Err(format!(
            "expected exactly 3 whitespace-separated integers (n, claimed F(n), decreasing start m), got {} tokens",
            tokens.len()
        ));
    }
    let parse = |name: &str, token: &str| {
        token
            .parse::<usize>()
            .map_err(|_| format!("{name} is not a nonnegative machine-size integer: {token:?}"))
    };
    Ok((
        parse("n", tokens[0])?,
        parse("claimed F(n)", tokens[1])?,
        parse("m", tokens[2])?,
    ))
}

fn verify(path: &str) -> Result<String, String> {
    let (n, claimed_f, m) = parse_candidate(path)?;
    if n > MAX_N {
        return Err(format!("n={n} exceeds the documented resource limit {MAX_N}"));
    }
    let phi = totients_through(n);
    let (actual_f, seen_at_failure, total_at_failure) = compute_f(&phi, n);
    if claimed_f != actual_f {
        return Err(format!(
            "claimed F({n})={claimed_f}, but exhaustive enumeration gives {actual_f}"
        ));
    }

    let k = actual_f
        .checked_add(1)
        .ok_or_else(|| "overflow forming F(n)+1".to_string())?;
    let end = m
        .checked_add(k)
        .ok_or_else(|| "overflow forming m+k".to_string())?;
    if end > n {
        return Err(format!("witness block ends at m+k={end}, beyond n={n}"));
    }
    for offset in 1..k {
        let left_index = m + offset;
        let right_index = left_index + 1;
        if phi[left_index] <= phi[right_index] {
            return Err(format!(
                "block is not strictly decreasing at phi({left_index})={} and phi({right_index})={} ",
                phi[left_index], phi[right_index]
            ));
        }
    }

    let failure_detail = match total_at_failure {
        Some(total) => format!("{seen_at_failure} of {total} strict patterns observed"),
        None => format!("fewer available starts than (F+1)! patterns"),
    };
    Ok(format!(
        "PASS: exhaustive strict-pattern census gives F({n})={actual_f}; length {k} fails ({failure_detail}), while m={m} realizes the strictly decreasing length-{k} pattern"
    ))
}

fn main() -> ExitCode {
    let args: Vec<String> = env::args().collect();
    if args.len() != 2 {
        return fail(format!("usage: {} CANDIDATE.txt", args[0]));
    }
    match verify(&args[1]) {
        Ok(message) => {
            println!("{message}");
            ExitCode::SUCCESS
        }
        Err(message) => fail(message),
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn totient_by_gcd(n: usize) -> usize {
        fn gcd(mut a: usize, mut b: usize) -> usize {
            while b != 0 {
                (a, b) = (b, a % b);
            }
            a
        }
        (1..=n).filter(|&a| gcd(a, n) == 1).count()
    }

    #[test]
    fn sieve_agrees_with_definition_through_1000() {
        let phi = totients_through(1000);
        for n in 1..=1000 {
            assert_eq!(phi[n], totient_by_gcd(n), "n={n}");
        }
    }

    #[test]
    fn pattern_encoding_and_ties() {
        assert_eq!(strict_pattern(&[30, 10, 20]), Some(vec![2, 0, 1]));
        assert_eq!(strict_pattern(&[10, 10]), None);
        assert_eq!(strict_pattern(&[]), Some(vec![]));
    }

    #[test]
    fn tiny_f_values() {
        let phi = totients_through(20);
        assert_eq!(compute_f(&phi[..=0], 0).0, 0);
        assert_eq!(compute_f(&phi[..=1], 1).0, 1);
        // By n=3 only the increasing length-two order has occurred:
        // (phi(1),phi(2)) ties, (phi(2),phi(3)) increases; decreasing has not.
        assert_eq!(compute_f(&phi[..=3], 3).0, 1);
    }
}
