extern crate num;
use num::FromPrimitive;
use num::bigint::BigInt;

use std::collections::HashSet;

/// Reverse a number then add it to the original.
fn rev_add(num: &BigInt) -> BigInt {
    let rev_string: String = num.to_string().chars().rev().collect();
    // should be safe, our string is guaranteed to be a number
    let rev_val: BigInt = rev_string.parse().unwrap();
    num + rev_val
}

/// Check if a number is a palindrome when written in base 10.
fn is_palindrome(num: &BigInt) -> bool {
    let num_string = num.to_string();
    let rev_string: String = num_string.chars().rev().collect();
    let comp_len = num_string.len() / 2;
    num_string[0..comp_len] == rev_string[0..comp_len]
}

/// Perform a lychrel test on a number, stopping after max_tests
/// Returns the sequence of numbers if this number is a lychrel, None otherwise.
fn test_lychrel(num: &BigInt, max_tests: usize) -> Option<Vec<BigInt>> {
    let mut sequence = Vec::<BigInt>::new();

    let is_lychrel = (0..max_tests)
        .scan(num.clone(), |current, _| {
            *current = rev_add(current);
            Some(current.clone())
        })
        .inspect(|current| sequence.push(current.clone()))
        .filter(|curent| is_palindrome(curent))
        .next()
        .is_none();

    if is_lychrel {
        Some(sequence)
    }
    else {
        None
    }
}

/// Determine if the sequence for a lychrel number is related to a previously seen sequence
fn is_related(seq: &Vec<BigInt>, lychrel_seq_numbers: &HashSet<BigInt>) -> bool {
    seq.iter().filter(|num| lychrel_seq_numbers.contains(num)).next().is_some()
}

/// Find the lychrel numbers up to max_num (inclusive).
/// Returns a tuple (lychrel numbers, related numbers, palindrome lychrel/related numbers)
fn find_lychrels(max_num: u64, max_tests: usize) -> (Vec<BigInt>, Vec<BigInt>, Vec<BigInt>) {
    // storage for various outputs
    let mut lychrels = Vec::<BigInt>::new();
    let mut relateds = Vec::<BigInt>::new();
    let mut palindrome_lychrels = Vec::<BigInt>::new();

    let mut lychrel_seq_numbers: HashSet<BigInt> = HashSet::new();

    for i in (1..(max_num + 1)) {
        let num = FromPrimitive::from_u64(i).unwrap();
        let maybe_lychrel = test_lychrel(&num, max_tests);

        if let Some(lychrel_seq) = maybe_lychrel {
            // it's a lychrel - check if it's a related number
            let related = is_related(&lychrel_seq, &lychrel_seq_numbers);

            // update our sequences
            for seq_num in lychrel_seq.into_iter() {
                lychrel_seq_numbers.insert(seq_num);
            }

            if !related {
                // the number has a new lychrel sequence, store it
                lychrels.push(num.clone());
            }
            else {
                // just count it as a related number
                relateds.push(num.clone());
            }

            if is_palindrome(&num) {
                // doesn't matter if palindromes are related or not
                palindrome_lychrels.push(num.clone());
            }
        }
    }

    (lychrels, relateds, palindrome_lychrels)
}

fn print_nums(before: &str, numbers: &Vec<BigInt>) {
    print!("{}", before);
    for (i, current) in numbers.iter().enumerate() {
        print!("{}", current);
        if i + 1 < numbers.len() {
            print!(", ");
        }
    }
    println!("");
}

fn main() {
    let max_num: u64 = 10_000;
    let max_tests: usize = 500;

    println!("Calculations using n = 1..{} and limiting each search to {} reverse-digits-and-adds",
        max_num, max_tests);

    let (lychrels, relateds, palindrome_lychrels) = find_lychrels(max_num, max_tests);

    println!("Number of Lychrel numbers: {}", lychrels.len());
    print_nums("Lychrel numbers: ", &lychrels);
    println!("Number of Lychrel related: {}", relateds.len());
    println!("Number of Lychrel palindromes: {}", palindrome_lychrels.len());
    print_nums("Lychrel palindromes: ", &palindrome_lychrels);
}