v2ex655102.rs

fn find_collatz(number: u64, cache: &mut Vec<i32>) -> i32 {
    let n = cache.len() as u64;
    let index = number as usize;

    if number < n && cache[index] != 0 {
        // cache hit
        cache[index]
    } else {
        // cache miss
        let result = match number {
            1 => 0,
            2 => 1,
            _ => {
                let next = match number & 1 == 0 {
                    true => number / 2,
                    false => 3 * number + 1,
                };
                find_collatz(next, cache) + 1
            }
        };
        if number < n {
            // cache
            cache[index] = result;
        }
        result
    }
}

fn main() {
    const CACHE_SIZE: usize = 200_000_000;
    const MAX_NUMBER: u64 = 100_000_000;

    let mut cache = vec![0; CACHE_SIZE];
    let number = (1..MAX_NUMBER)
        .max_by_key(|&x| find_collatz(x, &mut cache))
        .unwrap();
    let max_loop = find_collatz(number, &mut cache);
    println!("Number = {}, loop times = {}", number, max_loop);
}

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

    #[test]
    fn test_collatz() {
        let mut cache = vec![0; 255];
        for i in 1..255 {
            find_collatz(i as u64, &mut cache);
        }
        assert_eq!(
            cache,
            vec![
                0, 0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15,
                10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16,
                16, 16, 104, 11, 24, 24, 24, 11, 11, 112, 112, 19, 32, 19, 32, 19, 19, 107, 107, 6,
                27, 27, 27, 14, 14, 14, 102, 22, 115, 22, 14, 22, 22, 35, 35, 9, 22, 110, 110, 9,
                9, 30, 30, 17, 30, 17, 92, 17, 17, 105, 105, 12, 118, 25, 25, 25, 25, 25, 87, 12,
                38, 12, 100, 113, 113, 113, 69, 20, 12, 33, 33, 20, 20, 33, 33, 20, 95, 20, 46,
                108, 108, 108, 46, 7, 121, 28, 28, 28, 28, 28, 41, 15, 90, 15, 41, 15, 15, 103,
                103, 23, 116, 116, 116, 23, 23, 15, 15, 23, 36, 23, 85, 36, 36, 36, 54, 10, 98, 23,
                23, 111, 111, 111, 67, 10, 49, 10, 124, 31, 31, 31, 80, 18, 31, 31, 31, 18, 18, 93,
                93, 18, 44, 18, 44, 106, 106, 106, 44, 13, 119, 119, 119, 26, 26, 26, 119, 26, 18,
                26, 39, 26, 26, 88, 88, 13, 39, 39, 39, 13, 13, 101, 101, 114, 26, 114, 52, 114,
                114, 70, 70, 21, 52, 13, 13, 34, 34, 34, 127, 21, 83, 21, 127, 34, 34, 34, 52, 21,
                21, 96, 96, 21, 21, 47, 47, 109, 47, 109, 65, 109, 109, 47
            ]
        );

        assert_eq!(find_collatz(63728127, &mut cache), 949);
        assert_eq!(find_collatz(98110761, &mut cache), 748);
        assert_eq!(find_collatz(168432165432, &mut cache), 177);
    }
}