main.rs

#![cfg_attr(test, feature(test))]

use rayon::prelude::*;
use std::hash::Hash;
use std::hash::Hasher;
use smallvec::{SmallVec, smallvec};

#[derive(Debug, Copy, Clone, PartialEq, Hash, Eq)]
pub struct Integer([u8; 10]);

impl Integer {
    pub fn new() -> Integer {
        Integer([0; 10])
    }

    fn merge<I: Into<Integer>>(&mut self, other: I) {
        let other = other.into();

        for i in 0..=9 {
            self.0[i] += other.0[i];
        }
    }

    fn next_term(&self) -> Integer {
        let mut ret = Integer([0; 10]);

        for i in 0..=9 {
            if self.0[i] == 0 { continue; }
            ret.0[i] += 1;
            match self.0[i] {
                0..=9 => ret.0[self.0[i] as usize] += 1,
                10 => {
                    ret.0[1] += 1;
                    ret.0[0] += 1;
                }
                _ => unreachable!(),
            }
        }

        ret
    }
}

impl std::fmt::Display for Integer {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
        for (i, &val) in self.0.iter().enumerate() {
            if val > 0 {
                write!(f, "{}{}", val, i)?;
            }
        }
        Ok(())
    }
}

impl From<u64> for Integer {
    fn from(mut f: u64) -> Integer {
        let mut ret = [0; 10];

        while f > 0 {
            let digit = f % 10;
            ret[digit as usize] += 1;
            f /= 10;

            if f == 0 { break }
        }

        Integer(ret)
    }
}

impl From<&u64> for Integer {
    fn from(f: &u64) -> Integer {
        (*f).into()
    }
}
#[derive(Debug, Clone)]
pub struct IntegerIter(SmallVec<[Integer; 24]>);

impl IntegerIter {
    pub fn from_u64(from: u64) -> IntegerIter {
        let next: Integer = from.into();
        IntegerIter(smallvec![next])
    }

    pub fn from_integer(from: Integer) -> IntegerIter {
        IntegerIter(smallvec![from])
    }
}

impl Iterator for IntegerIter {
    type Item = Integer;
    fn next(&mut self) -> Option<Integer> {
        let next = self.0.last()?.next_term();

        if self.0.contains(&next) {
            None
        } else {
            self.0.push(next);
            Some(next)
        }
    }
}


fn main() {
    // let iter = IntegerIter::from_u64(9900);
    // println!("9900");
    // println!("{}", Integer::from(9900));
    // for i in iter {
    //     println!("{}", i);
    // }
    // return;

    let max = (1..100_000_000u64).into_par_iter().map(|i| {
        (i, IntegerIter::from_integer(Integer::from(i)).count() + 2)
    }).max_by(|(_, val), (_, oval)| val.cmp(oval)).unwrap();

    println!("{} with {} is the longest", max.0, max.1);
}

#[cfg(test)]
mod tests {
    extern crate test;

    use super::*;
    use test::{black_box, Bencher};

    #[bench]
    fn bench_9900(b: &mut test::Bencher) {
        let n = test::black_box(IntegerIter::from_u64(9900));

        b.iter(|| {
            n.clone().count() + 2
        })
    }

    #[bench]
    fn bench_next(b: &mut test::Bencher) {
        let n = test::black_box(Integer::from(9900));

        b.iter(|| {
            n.next_term()
        })
    }
}