#![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() | |
}) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment