Project Euler, Problem 2

I've got problem #2 in the bag.

Problem #2 goes like this:
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

And my code goes as follows:
Haskell:

  1. --fibinaci :: (Num a) => a -> a -> [a]
  2. fibinaci a b
  3. | sum' > 4000000 = []
  4. | otherwise = sum' : fibinaci b sum'
  5. where sum' = a + b
  6.  
  7. problem2 = sum $ filter (even) (fibinaci 0 1)

Python:
  1. #!/usr/bin/python
  2.  
  3. def fibinaci_list( in_list, input1, input2):
  4. flip = True
  5. while ( input1 + input2 < 4000000):
  6. if( flip == True):
  7. input1 = input1 + input2
  8. in_list.append(input1)
  9. flip = False
  10. else:
  11. input2 = input1 + input2
  12. in_list.append(input2)
  13. flip = True
  14.  
  15. def even(n):
  16. if n % 2 == 0:
  17. return True
  18. else:
  19. return False
  20.  
  21.  
  22. def main():
  23. first_list = []
  24. fibinaci_list(first_list, 0, 1)
  25. second_list = filter(even, first_list)
  26. print "%s" % (sum(second_list))
  27.  
  28. if __name__ == "__main__":
  29. main()

And finally, Perl:
  1. #!/usr/bin/perl
  2.  
  3. my $total = 0;
  4. my $count1 = 0;
  5. my $count2 = 1;
  6. my $flip = 1;
  7.  
  8. while( $count2 + $count1 < 4000000)
  9. {
  10. if ( $flip == 1)
  11. {
  12. $count1 += $count2;
  13. if ( $count1 % 2 == 0)
  14. {
  15. $total += $count1;
  16. }
  17. $flip = 0;
  18. }
  19. else
  20. {
  21. $count2 += $count1;
  22. if ( $count2 % 2 == 0)
  23. {
  24. $total += $count2;
  25. }
  26. $flip = 1;
  27. }
  28. }
  29.  
  30. print $total;

Originally, I tried to copy the Python algorithm to Perl, using an array instead of a list. That didn't work. The program would always fail due to out of memory errors. To solve this problem I changed the program to work without using arrays and just took the whole fibinaci function out and put it into main.

As always, constructive comments for the code are welcomed.

my python version

This is what I used to solve. Idk how fast it is

  1. a, b = 0, 1
  2. c = 0
  3. while b < 4000000:
  4. b, a = a, a + b
  5. if b % 2 == 0:
  6. c = c + b
  7. print c

Bad Python

No offense, but I think the Python and Perl versions of this code are really bad, and I'm not sure storing the entire sequence is the best way to do it in Haskell, either.

In any case, enough people have posted better Perl, so here is a better Python version:

  1. even_sum, a, b, c = 0, 0, 1, 1
  2. while c<4000000:
  3. if c&1 == 0: even_sum += c
  4. a,b,c = b, a+b, b+c
  5.  
  6. print(even_sum)

How's about this?

  1. fibs = 1 : 2 : zipWith (+) fibs (tail fibs)
  2. problem2 = sum . takeWhile (<4000000) . filter even $ fibs

fibo is a closure

  1. #! /usr/bin/perl
  2. use 5.10.0;
  3. use strict;
  4. use warnings;
  5. use List::Util qw/ sum /;
  6.  
  7. my $fib = do {
  8. my @f = ( 1, 2 );
  9. sub {
  10. push @f, sum @f;
  11. shift @f;
  12. }
  13. };
  14.  
  15. my $count = 0;
  16. while ( my $_ = &$fib ) {
  17. next if $_ % 2;
  18. my $c = $count + $_;
  19. if ( $c < 4_000_000 ) { $count = $c }
  20. else { say $count; exit }
  21. }

Solomon Foster wrote it in Perl6:

say [+] (1, 1, *+* ... 4000000).grep(* !% 2)

You write wrong in Perl

Your Perl code looks like ugly PHP, it's wrong and your Perl code (good Perl code) can't be the same like Python code, it's different languages, that uses different paradigms of programming. Try read some good books about Perl like "Intermediate Perl" + "High order Perl" in that order, and you'll discover incredible heights of Perl programming.

Despite your harsh language;

Despite your harsh language; I appreciate your input. I will purchase those book in the near future and soon after that I will start to write "prettier" Perl code.

I speak English not so well,

I speak English not so well, and I do not want to offend you in any way.

The second book that i pointed is the best book on how to use recursion and closures, and this knowledge can be useful not only for Perl.

Hey ZloyRusskiy, Would you

Hey ZloyRusskiy,

Would you use the Contact link above and send me an email with a way to contact you? I have problem 3 figured out, but I'm having serious problems with translating my Python algorithm to Perl.

Thanks.

No offense taken and thank

No offense taken and thank you for saying that. Also I really do appreciate the book recommendations. The High Order Perl book has gotten some great reviews on Amazon, and I really look forward to going through it.

Also, thanks for the comments after this on with the code in them. Its much easier to learn efficient Perl when you already have an idea of what your trying to accomplish.

Another one-liner: perl -E

Another one-liner:

perl -E 'for ($a=1,$b=2;$s < 4_000_000; ($a,$b) = ($b,$a+$b)) { $s += $a unless $a % 2 }; say $a'

sorry, i have misprinted:

sorry, i have misprinted: "say $s" must be in the end of code

of full variant

use 5.012;
my $sum;
for ( my ($a,$b) = (1,2) ; $sum < 4_000_000 ; ($a,$b) = ($b,$a+$b) ) {
$sum += $a unless $a % 2;
};
say $sum;

why not use a shorter version

why not use a shorter version :-)

#!/usr/bin/perl
use List::Util qw(sum);

@f = (0,1);
push @f, sum @f[-1,-2] while ($f[-1] < 4_000_000);
print sum grep {$_ % 2 == 0} @f;

If you made it this far down into the article, hopefully you liked it enough to share it with your friends. Thanks if you do, I appreciate it.

Bookmark and Share