Skip to content

Instantly share code, notes, and snippets.

@TheNeikos TheNeikos/main.rs
Created May 19, 2019

Embed
What would you like to do?
#![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
You can’t perform that action at this time.