<commit_before><commit_msg>Add problem #119<commit_after>#[crate_type = "rlib"];

extern mod extra;
extern mod math;

use std::iter::{AdditiveIterator, Filter, SkipWhile};
use extra::priority_queue::PriorityQueue;
use math::{arith, numconv};

pub static EXPECTED_ANSWER: &'static str = "248155780267521";

struct Power(uint, uint, uint);

impl Ord for Power {
    #[inline]
    fn lt(&self, other: &Power) -> bool {
        let Power(sn, sb, _) = *self;
        let Power(on, ob, _) = *other;
        sn > on || (sn == on && sb > ob)
    }
}

struct Powers {
    queue: PriorityQueue<Power>
}

impl Powers {
    #[inline]
    fn new() -> Powers {
        let mut queue = PriorityQueue::new();
        queue.push(Power(4, 2, 2));
        Powers { queue: queue }
    }
}

impl Iterator<(uint, uint, uint)> for Powers {
    #[inline]
    fn next(&mut self) -> Option<(uint, uint, uint)> {
        let Power(n, b, e) = self.queue.pop();
        if b == 2 { self.queue.push(Power(n * b, b, e + 1)); }
        self.queue.push(Power(arith::pow(b + 1, e), b + 1, e));
        Some((n, b, e))
    }
}

#[inline]
fn a<'a>() -> Filter<'a, (uint, uint, uint), SkipWhile<'a, (uint, uint, uint), Powers>> {
    Powers::new()
        .skip_while(|&(n, _b, _e)| n < 10)
        .filter(|&(n, b, _e)| numconv::to_digits(n, 10).sum() == b)
}

pub fn solve() -> ~str {
    let (n, _b, _e) = a().nth(29).unwrap();
    n.to_str()
}

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

    #[test]
    fn powers() {
        let mut it = Powers::new();
        assert_eq!(Some((4, 2, 2)), it.next());
        assert_eq!(Some((8, 2, 3)), it.next());
        assert_eq!(Some((9, 3, 2)), it.next());
        assert_eq!(Some((16, 2, 4)), it.next());
        assert_eq!(Some((16, 4, 2)), it.next());
        assert_eq!(Some((25, 5, 2)), it.next());
        assert_eq!(Some((27, 3, 3)), it.next());
        assert_eq!(Some((32, 2, 5)), it.next());
        assert_eq!(Some((36, 6, 2)), it.next());
        assert_eq!(Some((49, 7, 2)), it.next());
        assert_eq!(Some((64, 2, 6)), it.next());
        assert_eq!(Some((64, 4, 3)), it.next());
        assert_eq!(Some((64, 8, 2)), it.next());
        assert_eq!(Some((81, 3, 4)), it.next());
        assert_eq!(Some((81, 9, 2)), it.next());
        assert_eq!(Some((100, 10, 2)), it.next());
    }

    #[test]
    fn a() {
        let mut it = super::a();
        assert_eq!(Some((512, 8, 3)), it.nth(1));
        assert_eq!(Some((614656, 28, 4)), it.nth(8 - 1));
    }
}

{'fraction_non_alphanumeric': 0.2285140562248996, 'fraction_numerical': 0.04457831325301205, 'mean_word_length': 2.674041297935103, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5852181', 'n_tokens_mistral': 1024, 'n_tokens_neox': 946, 'n_words': 234}