palindromes.rs

palindromes.rs

fn is_palindrome(n: u64) -> bool {
    if n < 10 {
        return true; // Single-digit numbers are palindromes
    }
    let s = n.to_string();
    s == s.chars().rev().collect::<String>()
}

fn generate_palindromes_up_to(limit: u64) -> Vec<u64> {
    let mut palindromes = Vec::new();

    // Add single-digit palindromes
    for i in 0..10 {
        if i <= limit {
            palindromes.push(i);
        } else {
            break;
        }
    }

    // Generate palindromes by constructing them
    let mut half_num = 1;
    loop {
        // Construct even-length palindrome
        let s_half = half_num.to_string();
        let reversed_s_half: String = s_half.chars().rev().collect();
        let even_palindrome_str = format!("{}{}", s_half, reversed_s_half);
        if let Ok(even_palindrome) = even_palindrome_str.parse::<u64>() {
            if even_palindrome <= limit {
                palindromes.push(even_palindrome);
            } else if half_num > limit {
                // Optimization: if half_num is already over limit, even and odd will be too.
                break;
            }
        } else {
            // Handle potential overflow if palindrome string is too long for u64
            break;
        }

        // Construct odd-length palindrome
        // Example: half_num = 123, reversed_s_half = 321
        // s_half_prefix = 12, reversed_s_half_suffix = 21 (from 321, removing the first digit)
        let s_half_prefix: String = s_half.chars().take(s_half.len() - 1).collect();
        let odd_palindrome_str = format!(
            "{}{}",
            s_half,
            reversed_s_half.chars().skip(1).collect::<String>()
        );

        if let Ok(odd_palindrome) = odd_palindrome_str.parse::<u64>() {
            if odd_palindrome <= limit {
                palindromes.push(odd_palindrome);
            } else if half_num > limit {
                break;
            }
        } else {
            // Handle potential overflow
            break;
        }

        // Break condition: If the smallest possible palindrome generated from the next half_num
        // (which would be 10...01 for even or 10...001 for odd depending on length)
        // exceeds the limit, we can stop.
        // A simpler but less precise check is to see if `half_num` itself exceeds `limit`.
        // For larger limits, `half_num` will eventually grow very large.
        if half_num > u64::MAX / 1000 {
            // Arbitrary large number to prevent overflow in half_num * 10
            break;
        }
        half_num += 1;
    }

    palindromes.sort_unstable(); // Sort to ensure ascending order
    palindromes.dedup(); // Remove duplicates (e.g., single digit palindromes might be generated)
    palindromes
}

fn main() {
    let limit = 10000;
    let palindromes = generate_palindromes_up_to(limit);
    println!("Palindromes up to {}:", limit);
    for pal in palindromes {
        println!("{}", pal);
    }
}