6

I am trying to solve a question in Project Euler, which is creating a fibonacci series until 4 million, and add the even numbers that come in the series, this is obviously very easy task and I answer it in 2 mins, 

int result=2;
int first=1;
int second=2;
int i=2;

while (i < 4000000)
{
    i = first + second;

    if (i % 2 == 0)
    {
       result += i;
    }

    first = second;
    second = i;
 }

 Console.WriteLine(result);

but I want to do it using a lambda expression

My effort is going like

DelType del = (oldVal, newVal) =>((oldVal==0?1:newVal  + newVal==1?2:oldVal+newVal) % 2 == 0) ? oldVal + newVal : 0;

int a=del(0, 1);

Kindly suggest how to get this done

Improve this question
1
  • I would suggest to first try doing it in a Linq statement. That's a little more readable and after that you can easily convert it to lambda syntax. Commented Dec 25, 2011 at 7:44

10 Answers 10

Reset to default
17

My first answer was having misread the question completely, but now I've reread it (thanks MagnatLU!) I'd suggest that this isn't a good fit for lambda expressions. However, it's a brilliant fit for a combination of iterator blocks and LINQ:

// Using long just to avoid having to change if we want a higher limit :)
public static IEnumerable<long> Fibonacci()
{
    long current = 0;
    long next = 1;
    while (true)
    {
        yield return current;
        long temp = next;
        next = current + next;
        current = temp;
    }
}

...

long evenSum = Fibonacci().TakeWhile(x => x < 4000000L)
                          .Where(x => x % 2L == 0L)
                          .Sum();
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

+1 for yield return, shame compiler returns The yield statement cannot be used inside an anonymous method or lambda expression when you try to use iterator inside lambda returning IEnumerable<T>.
@MegaMind: I'm looking for a one line code/statement for Fibonacci series. Can you help??
I like this answer, but I think lines 2-4 of the while loop could be simplified into a single line with next = current + (current = next); Is there any reason not to do so?
@JLRishe: Yes - it's much more confusing, in my view. It may well work, but extra side effects like that confused the heck out of me. I'd much rather have three statements, each of which is really simple to read.
public static IEnumerable<BigInteger> FibonacciSequence() { BigInteger a = 0, b = 1; while (true) { yield return a; a += b; yield return b; b += a; } }
8

Use this recursive function

Func<int, int> fib = null;
fib = (x) => x > 1 ? fib(x-1) + fib(x-2) : x;

Example Usage:

Console.WriteLine(fib(10));
Improve this answer

5 Comments

I'm not sure if it will compile. I mean, having the lambda referencing itself before it's assigned...
@ivowiblo the lambda can reference itself as long as the variable is assigned before the statement in the code example. Example: Func<int, int> fib = null; fib = x => x > 1 ? fib(x - 1) + fib(x - 2) : x;
@phoog: Please Can you help me in complete solution for the above query since i'm not getting how to see the same on OCnsole window or printing the same on console window after running the above LINQ query.
@sukumar what exactly are you having trouble with? What have you tried? Perhaps you should post a new question.
@phoog: I written a for loop as for (int i = 0; i < 10; i++) Console.WriteLine(fib(i)); Then got the output as 0 1 1 2 3 5 8 13 21 34
7

Here's oneliner as a lambda expression:

Func<int, int, int, int, int> fib = null;
fib = (n, a, b, res) => n == 0 ? res : fib(n - 1, b, a + b, n % 2 == 0 ? res : res + a + b);
// usage: fib(n, 1, 0, 0)

It uses O(n) stack space and O(n) time on x86 and O(1) stack space on x64 (due to tail recursion optimisation on x64 JIT), so it will fail for n=400000 on 32-bit system.

Edit: it is counting even elements of series from the end, not the beginning, but you should get the idea how to do it as λ with tailrec.

Improve this answer

1 Comment

I'm not getting Fibonacci Series with the above linq query/expression. Getting abuse/odd output not a fibonacci. I tried with fib(6,1,0,0)
3

Similar to the Func two-liner, now with local functions it can be done like this:

int Fibonacci(int i) => i <= 1 ? i : Fibonacci(i - 1) + Fibonacci(i - 2);
Improve this answer

Comments

1 
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class Fibonacci : IEnumerable<int>{
    delegate Tuple<int,int> update(Tuple<int,int> x);
    update func = ( x ) => Tuple.Create(x.Item2, x.Item1 + x.Item2);

    public IEnumerator<int> GetEnumerator(){
        var x = Tuple.Create<int,int>(0,1);
        while (true){
            yield return x.Item1;
            x = func(x);
        }
    }
    IEnumerator IEnumerable.GetEnumerator() {
        return GetEnumerator();
    }
}

class Sample {
    static public void Main(){
        int result= (new Fibonacci()).TakeWhile(x => x < 4000000).Where(x => x % 2 == 0).Sum();
        Console.WriteLine(result);//4613732
   }
}

OTHER

public static class Seq<T>{
    public delegate Tuple<T,T> update(Tuple<T,T> x);

    static public IEnumerable<T> unfold(update func, Tuple<T,T> initValue){
        var value = initValue;
        while (true){
            yield return value.Item1;
            value = func(value);
        }
    }
}

class Sample {
    static public void Main(){
        var fib = Seq<int>.unfold( x => Tuple.Create<int,int>(x.Item2, x.Item1 + x.Item2), Tuple.Create<int,int>(0,1));
        int result= fib.TakeWhile(x => x < 4000000).Where(x => x % 2 == 0).Sum();
        Console.WriteLine(result);
   }
}
Improve this answer

4 Comments

That result is surely wrong! if fib(30) => 832040, there is no way sum of fib(0) to fib(4000000) => 4613732 can be true
@leppie Make sure you see it again? fib series add sum when even. fib(x!=4000000), fib(?) < 4000000
See my answer for a somewhat simpler iterator block to create the Fibonacci sequence.
@Jon Skeet Your answer is always helpful. However, this may be it for question. It might seem strange...
0

Just in case you wanted a pure recursive lambda solution, take a look at this answer for a couple of links to articles showing how it's done.

However, that uber stuff is too mad for me, so I'd better follow another answer that is already here.

Improve this answer

Comments

0

You know you can do:

Func<int,int,int> func = (first, second) => {  
                                          var result=2;
                                          int i=2;
                                          while (i < 4000000)
                                          {
                                              i = first + second;
                                              if (i % 2 == 0)
                                              {
                                                  result += i;
                                              }
                                              first = second;
                                              second = i;
                                          }
                                          return result;
                                        };
Improve this answer

4 Comments

Thanks for your response, but i want to make it a one liner,
I'm just curious... why do you need it in one single line? I don't know if it's even possible.
@ivowiblo: Sadly, this wont compile either... (fix your own code before pointing out the same fault in other's ;p)
You could have use that time in fixing it instead of complaining :)
0

I know this is an old question, but I was working on the same problem today and arrived at this concise functional-style solution with O(n) running time:

static int FibTotal(int limit, Func<int, bool> include, int last = 0, int current = 1)
{
    if (current < limit)
        return FibTotal(limit, include, current, last + current) + 
                               (include(current) ? current : 0);
    else
        return 0;
}

You can also get a nice one-line solution if you first define this convenience class (maybe something like this already exists in the .NET framework, but I was unable to find it):

public static class Sequence
{
    public static IEnumerable<T> Generate<T>(T seed, Func<T, T> next)
    {
        while (true)
        {
            yield return seed;
            seed = next(seed);
        }
    }
}

The solution then becomes:

var result = Sequence.Generate(Tuple.Create(1, 1), 
                               t => Tuple.Create(t.Item2, t.Item1 + t.Item2))
                     .Select(t => t.Item1)
                     .TakeWhile(i => i < 4000000)
                     .Where(i=> i % 2 == 0)
                     .Sum();
Improve this answer

Comments

0 
public static void fibSeriesEx3()
{
    List<int> lst = new List<int> { 0, 1 };
    for (int i = 0; i <= 10; i++)
    {
        int num = lst.Skip(i).Sum();
        lst.Add(num);

        foreach (int number in lst)
            Console.Write(number + " ");
            Console.WriteLine();
    }
}
Improve this answer

Comments

0

One liner that works:

Func<int, int, int, int, int> fib = null;
fib = (a, b, counter, n) => counter < n ? fib(b, a + b, counter+1, n) : a;
        //print the 9th fib num
        Console.WriteLine(fib(0,1,1,9));

output: 21

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.