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:

--fibinaci :: (Num a) => a -> a -> [a]
fibinaci a b
  | sum' > 4000000 = []
  | otherwise = sum' : fibinaci b sum'
  where sum' = a + b
 
problem2 = sum $ filter (even) (fibinaci 0 1)

#!/usr/bin/python
 
def fibinaci_list( in_list, input1, input2):
  flip = True
  while ( input1 + input2 < 4000000):
    if( flip == True):
      input1 = input1 + input2
      in_list.append(input1)
      flip = False
    else:
      input2 = input1 + input2
      in_list.append(input2)
      flip = True 
 
def even(n):
  if n % 2 == 0:
    return True
  else:
    return False
 
 
def main():
  first_list = []
  fibinaci_list(first_list, 0, 1)
  second_list = filter(even, first_list)
  print "%s" % (sum(second_list))
 
if __name__ == "__main__":
  main()

#!/usr/bin/perl
 
my $total = 0;
my $count1 = 0;
my $count2 = 1;
my $flip = 1;
 
while( $count2 + $count1 < 4000000)
{
  if ( $flip == 1)
  {
    $count1 += $count2;
    if ( $count1 % 2 == 0)
    {
      $total += $count1;
    }
    $flip = 0;
  }
  else
  {
    $count2 += $count1;
    if ( $count2 % 2 == 0)
    {
      $total += $count2;
    }
    $flip = 1;
  }
}
 
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.

So I'll admit it, I'm more than acceptably late to this party. OJ started working on these problems years ago, while I was still coding away on other stuff at school. Now that I'm not in school and needing a challenge I'm doing the best I can to tackle the problems at Project Euler. Since I'm also trying to pick up Haskell, this makes for a good way to learn the language. This isn't my first time using a Functional Programming language. But the last time I tried, it was forced upon me at school with inadequate assistance and the whole experience left a bad taste in my mouth. I'm glad that getting over the bad experience and learning something new at the same time.

I've started keeping a github repo with my solutions for the various problems. If anyone is interested in commenting on my code please do so. I welcome all constructive criticism.

To start this thing off; problem one reads,
“If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.”

Being this one was simple. I coded it up in Haskell, Python, and Perl.
Haskell:

problem1 = sum $ filter (\x -> mod x 3 == 0 || mod x 5 == 0) [1..1000]
problem1' = sum $ filter (\x -> mod x 3 == 0 || mod x 5 == 0) [1..999]

#!/usr/bin/python
 
def threeorfive(n):
  if ( n % 3 == 0 or n % 5 == 0):
    return True
  else:
    return False
 
def main():
  first_list = range(1,1000)
  second_list = filter(threeorfive, first_list)
  print "%s" % (sum(second_list))
 
if __name__ == "__main__":
  main()

#!/usr/bin/perl
 
my $count = 0;
my $total = 0;
 
while ( $count < 1000)
{
  if ( $count % 3 == 0 or $count % 5 == 0)
  {
    $total += $count;
  }
 
  $count++;
}
 
print $total;

One thing that is nice about doing this in different languages, is that you get to become aware of the differences between some of those languages. For instance in Python the range function works a little differently than I expected. I was expecting an inclusive range function, one in which the 10 is included in the list. But that is now how Python's range works. It gives me 10 numbers, starting with 1, the end result is a list ending in 9. It's not a big deal and easily fixable, but just not something I was expecting. That is why the Haskell code has to functions in it. Just to verify that the Python code was correct.

I'll be posting more answers as I complete them. So expect to see some random posts with Euler solutions in them.

Even though Poisonbit's solution to the original problem is the fastest (Thanks again PoisenBit!) I decided to use the original code as an excuse to learn multi-threading programming in PERL and see if it might improve the performance of the original code. One of those "for shits and giggles" moments.

First off, here is the new and improved code:

#!/usr/bin/perl
#######################################################################
#	Created By: Bryce Verdier
#	on 4/14/10
# 
#	Function: grab all installed packages, using threads
#           find their exact versions, and display them
#	NOTE: FOR USE ON DEBIAN BASED MACHINES
#######################################################################
 
use threads;
 
my $temp_pack;
my $temp_ver;
my $returned_version;
my %pack_hash :shared;
my $thread_count = 0;
my $pack_count;
my @return = `dpkg --get-selections`;
 
sub get_package_ver
{
  my %args = @_;
  my $temp_ver;
  my $returned_ver = `dpkg -s $args{package}`;
 
  $returned_ver =~ m/^Version: (.+)$/m;
 
  $temp_ver = $1;
 
  lock($args{hash});
  $args{hash}{$args{package}} = $temp_ver;
}
 
foreach (@return)
{
  $_ =~ m/^(\S+)[ \t].*/;
 
  $_ = $1;
}
 
 
$pack_count = @return;
while ( $pack_count - $thread_count >= 1)
{
    my $th1 = threads->create(\&get_package_ver, hash => \%pack_hash, 
                              package => $return[$thread_count]);
    my $th2 = threads->create(\&get_package_ver, hash => \%pack_hash, 
                              package => $return[$thread_count+1]);
 
    $th1->join();
    $th2->join();
 
    $thread_count = $thread_count + 2;
}
 
# Get the odd package, if there is one
if ($pack_count - $thread_count == 1)
{
    my $th1 = threads->create(\&get_package_ver, hash => \%pack_hash, 
                              package => $return[$thread_count]);
 
    $th1->join();
 
    $thread_count++;
}
 
while((my $key, my $value) = each(%pack_hash))
{
  print "$key : $value\n";
}

For all the number crunchers out there, putting things into two threads reduced the program execution time by more than 1 minute. For a program that took two and a half seconds to complete, a reduction to one and a half seconds is pretty significant.Well, in my book anyway.

After first following the suggestions of Sam for the regexes, (Thanks again Sam!) I pulled out the version checking code into its own function so that each thread would have a very specific thing to do. After that I realized I needed to clean up the package names that were being sent to the threads, creating the foreach loop on line 35. Within the foreach loop I tried something that I didn't expect to work - the line:

$_ = $1;

There isn't a reason for the line above to not work, but in the PERL code I've seen "$_" is not being used as a pointer to write data to, only to retrieve data from. And I guess that is why I did not expect it to work. But then, that's why I'm doing this - to learn things. :-D

After these changes and adding the threads code, I was almost done. For some reason the data from each thread wasn't getting stored into the hash. It wasn't until I looked a little deeper at the examples on perldoc that I saw what I needed to do. In the section "Shared And Unshared Data" I noticed I needed to mark %pack_hash as shared, so all the threads could access it. Which I did like so:

my %pack_hash :shared;

All in all, my first multi-threading coding expirence in perl wasn't bad. Granted the program isn't complicated, but this was truely new territory for me. I haven't tried doing any kind of multi-process/multi-threading programming since my operating systems class almost 3 years ago, so there were some battles to fight in my head on how to modify things to work with multiple threads. But again, it was a good experience. And I'm going to reiterate this so everyone remembers: don't use this code in production. Poisonbit's solution is MUCH faster than mine. Like me, use this code for learning.

AAAHHH work! Everyone has those horror stories where your boss, or the client, comes and asks for some horrible feature that will require an entire rewrite of the program. Fortunately, that hasn't happened to me (yet) and that is not what this blog entry is about. It's about the even more (what I believe to be) unlikely scenario when someone wants a feature that they think will be difficult to create and after some research you implement that feature in a small amount of time. It's a rare event and great confidence booster when it does happen though.

A co-worker wanted a feature added to a project. He thought that it might take a while to complete so he talked to me first about it to “plant the seed” and get my brain started on figuring out a solution, not expecting a quick turnaround. Of course, as the title hints at, the problem was to find out all the packages installed on our Debian boxes as well as their version numbers. So after a little bit of googleing and man page reading I had a basic algorithm to build on. Twenty minutes of coding and testing later, I had this script:

#!/usr/bin/perl
#######################################################################
#	Created By: Bryce Verdier
#	on 4/14/10
# 
#	Function: grab all installed packages, find their exact
#           versions, and display them
#	NOTE: FOR USE ON DEBIAN BASED MACHINES
#######################################################################
 
my $temp_pack;
my $temp_ver;
my $returned_version;
my %pack_hash;
my @return = `dpkg --get-selections`;
 
foreach (@return)
{
  $_ =~ m/(\S*)[ \t].*/i;
 
  $temp_pack = $1;
 
  $returned_version = `dpkg -s $temp_pack`;
 
  $returned_version =~ m/Version: (.*)/i;
 
  $temp_ver = $1;
 
  $pack_hash{$temp_pack} = $temp_ver;
 
}
 
while((my $key, my $value) = each(%pack_hash))
{
  print "$key : $value\n";
}

I will admit that is a little slow (on my desktop it takes around two and a half minutes to complete) and could probably benefit from some parallelization. However, that might be over-engineering for such a simple task. I'll code that feature up next, grab a stopwatch, and test it just to find out. Anybody gonna place bets one way or another? In the meantime, I'm proud of my use of regex's in this script, the "\S" removes the trailing whitespace from the package names, instead of just using ".*", which should speed things up a bit because I don't have to call chomp on each package name. Also using a hash for storage simplifies the data management and should allow for an easier time porting the code into a larger script later.