Instantly share code, notes, and snippets.

# JacksonGariety/euler_74.rs

Created April 10, 2016 21:07
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 extern crate fnv; use std::collections::HashSet; use std::hash::{BuildHasherDefault}; use self::fnv::FnvHasher; type Fnv = BuildHasherDefault; struct FactorialDigitChain { n: u32, // this is the current link in the chain v: HashSet, // the vector stores the lifetime of the chain } impl FactorialDigitChain { fn new(start: u32, terms: usize) -> FactorialDigitChain { FactorialDigitChain { n: start, v: HashSet::with_capacity_and_hasher(terms, Fnv::default()) } } } fn sum_digit_factorials(mut n: u32) -> u32 { let mut sum = 0; while n > 0 { sum += [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880][(n % 10) as usize]; // use pre-computed factorials 0 through 9 n /= 10; // remove one digit from the number } return sum } impl Iterator for FactorialDigitChain { type Item = u32; fn next(&mut self) -> Option { self.v.insert(self.n); // update lifetime self.n = sum_digit_factorials(self.n); // calculate n if self.v.contains(&self.n) { None } // check the lifetime vector for a duplicate else { Some(self.n) } // return n } } pub fn solve(max:u32, terms:usize) -> usize { (0..max) // make a range of each number below that of the problem statement .filter(|&i| FactorialDigitChain::new(i, terms).count() + 1 == terms) // filter that range by the length of i's factorial digit chain .count() // count the number of items remaining in the range }