Home

Project Euler, Problem 2

Submitted by Bryce on Thu, 06/24/2010 - 00:51

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.
#1Submitted by mccomasd (not verified) on Fri, 12/10/2010 - 16:32.

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
#2Submitted by Jeremiah (not verified) on Fri, 07/02/2010 - 09:10.

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)
#3Submitted by OJ (not verified) on Fri, 07/02/2010 - 03:43.

How's about this?

  1. fibs = 1 : 2 : zipWith (+) fibs (tail fibs)
  2. problem2 = sum . takeWhile (<4000000) . filter even $ fibs
#4Submitted by eiro (not verified) on Thu, 06/24/2010 - 15:59.

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. }
#5Submitted by Anonymous (not verified) on Thu, 06/24/2010 - 08:06.

Solomon Foster wrote it in Perl6:

say [+] (1, 1, *+* ... 4000000).grep(* !% 2)
#6Submitted by zloyrusskiy (not verified) on Thu, 06/24/2010 - 02:18.

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.
#7Submitted by Bryce on Thu, 06/24/2010 - 22:14.

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.
#8Submitted by zloyrusskiy (not verified) on Thu, 06/24/2010 - 22:34.

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.
#9Submitted by Bryce on Tue, 06/29/2010 - 17:09.

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.
#10Submitted by Bryce on Thu, 06/24/2010 - 23:04.

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.
#11Submitted by zloyrusskiy (not verified) on Thu, 06/24/2010 - 02:10.

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'
#12Submitted by zloyrusskiy (not verified) on Thu, 06/24/2010 - 02:35.

sorry, i have misprinted:

sorry, i have misprinted: "say $s" must be in the end of code
#13Submitted by zloyrusskiy (not verified) on Thu, 06/24/2010 - 02:34.

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;
#14Submitted by Anonymous (not verified) on Thu, 06/24/2010 - 01:47.

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