//! Independent exact checker for a claimed first cutoff at which all strict
//! patterns of a fixed length have occurred.

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

const MAX_N: usize = 200_000_000;
const MAX_K: usize = 10;

fn totient_sieve(n: usize) -> Vec<u32> {
    let mut result: Vec<u32> = (0..=n).map(|x| x as u32).collect();
    if n > 0 {
        result[1] = 1;
    }
    for p in 2..=n {
        if result[p] == p as u32 {
            for q in (p..=n).step_by(p) {
                result[q] = result[q] / p as u32 * (p as u32 - 1);
            }
        }
    }
    result
}

fn rank_pattern(block: &[u32]) -> Option<Vec<u8>> {
    let mut answer = Vec::with_capacity(block.len());
    for (i, &x) in block.iter().enumerate() {
        let mut rank = 0u8;
        for (j, &y) in block.iter().enumerate() {
            if i != j && x == y {
                return None;
            }
            if y < x {
                rank += 1;
            }
        }
        answer.push(rank);
    }
    Some(answer)
}

fn factorial(k: usize) -> Option<usize> {
    (2..=k).try_fold(1usize, |a, b| a.checked_mul(b))
}

fn parse(path: &str) -> Result<(usize, usize), String> {
    let input = fs::read_to_string(path).map_err(|e| format!("cannot read candidate: {e}"))?;
    let words: Vec<_> = input.split_whitespace().collect();
    if words.len() != 2 {
        return Err(format!("expected exactly `k cutoff`, got {} tokens", words.len()));
    }
    let k = words[0]
        .parse::<usize>()
        .map_err(|_| "k is not a nonnegative integer".to_string())?;
    let n = words[1]
        .parse::<usize>()
        .map_err(|_| "cutoff is not a nonnegative integer".to_string())?;
    Ok((k, n))
}

fn verify(path: &str) -> Result<String, String> {
    let (k, n) = parse(path)?;
    if !(1..=MAX_K).contains(&k) {
        return Err(format!("k must lie in 1..={MAX_K}"));
    }
    if n > MAX_N {
        return Err(format!("cutoff {n} exceeds resource limit {MAX_N}"));
    }
    if n < k {
        return Err("no length-k block ends by the claimed cutoff".to_string());
    }
    let target = factorial(k).ok_or_else(|| "factorial overflow".to_string())?;
    let phi = totient_sieve(n);
    let mut seen: HashSet<Vec<u8>> = HashSet::with_capacity(target);
    let mut newly_at_n = Vec::new();
    let mut count_before_n = 0usize;

    for endpoint in k..=n {
        let start_index = endpoint - k + 1;
        if let Some(pattern) = rank_pattern(&phi[start_index..=endpoint]) {
            let was_new = seen.insert(pattern.clone());
            if endpoint < n {
                count_before_n = seen.len();
            } else if was_new {
                newly_at_n.push(pattern);
            }
        }
    }

    if seen.len() != target {
        return Err(format!(
            "only {} of {target} strict patterns have occurred by {n}",
            seen.len()
        ));
    }
    if count_before_n == target {
        return Err(format!(
            "all {target} patterns had already occurred by {}, so {n} is not the first cutoff",
            n - 1
        ));
    }
    if newly_at_n.is_empty() {
        return Err("internal inconsistency: no new pattern at claimed first cutoff".to_string());
    }

    Ok(format!(
        "PASS: exhaustive census proves the first cutoff for all {target} strict length-{k} patterns is {n}; new final pattern(s) {newly_at_n:?}"
    ))
}

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

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

    fn gcd(mut x: usize, mut y: usize) -> usize {
        while y != 0 {
            let r = x % y;
            x = y;
            y = r;
        }
        x
    }

    #[test]
    fn sieve_matches_gcd_definition() {
        let phi = totient_sieve(1000);
        for n in 1..=1000 {
            let direct = (1..=n).filter(|&a| gcd(a, n) == 1).count();
            assert_eq!(phi[n] as usize, direct, "n={n}");
        }
    }

    #[test]
    fn ranks_and_ties() {
        assert_eq!(rank_pattern(&[4, 1, 3, 2]), Some(vec![3, 0, 2, 1]));
        assert_eq!(rank_pattern(&[1, 2, 2]), None);
    }
}
