Project Euler #2 in Rust

Question

I'm learning Rust, so I'm doing the Project Euler problems, as they are good exercises imho. But I'm already stuck on the second problem. The idea is to find the sum of all the even numbers that are less than 4000000 in the Fibonacci sequence. So I tried to do it a bit the functional way, and using a custom iterator :

use std::mem;
static LIMIT: uint = 4000000u;
struct Fibonacci {
    current: uint,
    next: uint,
    limit: uint,
}
fn fibo(lim: uint) -> Fibonacci {
    Fibonacci {
        current: 1u, next: 1u, limit: lim
    }
}

impl Iterator<uint> for Fibonacci {
    fn next(&mut self) -> Option<uint> {
        let nex = self.current + self.next;
        let cur = mem::replace(&mut self.next, nex);
        if cur >= self.limit { return None; }
        Some(mem::replace(&mut self.current, cur))
    }
}

fn main() {
    let sum = fibo(LIMIT).filter(|&x| x%2 == 0).fold(0, |sum, x| sum + x);
    println!("Sum of fibs : {}", sum);
}

It looks good, and it gives the correct Fibonacci sequence (I verified with println!s). The problem is that it doesn't give the correct sum : it outputs 1089154 whereas it should output 4613732. To me it seems that the fold misses the last number, but I can't see why !

I'm a total beginner with Rust, so any help would be greatly appreciated, thanks !

Answer 1

What you should be testing in your exit branch is the value of self.current; instead, you're testing the value of self.next. In other words, you're failing to output the last number in the sequence (as Matthieu suggested).

I verified that if the iterator is implemented correctly, it should produce the correct result with this (using grabbag_macros = "0.0.1" as a Cargo dependency):

#![feature(phase)]
#[phase(plugin, link)] extern crate grabbag_macros;

static LIMIT: u64 = 4000000;

fn main() {
    let sum = recurrence![f[n]: u64 = 1, 1... f[n-1] + f[n-2]]
        .take_while(|&n| n <= LIMIT)
        .filter(|&n| n % 2 == 0)
        .fold(0, |a, b| a + b);
    println!("Sum of fibs: {}", sum);
}

A few other random notes: I'd avoid uint for this, since it's platform-dependent. You don't need the u suffix unless you need to be specific about the type. You can use take_while or plain old take instead of hard-coding a limit into your iterator.