ScrollingText

Project Euler: Problem 4

Submitted by Bryce on Thu, 07/08/2010 - 10:19

If you been following me the last three times I've done this, then you really don't need any introductions.

Problem four is as follows:
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

And my results in the usual three languages are:
Hasekell:

module Main where
 
import Data.List
 
--Stole numberToList code from:
--http://www.rhinocerus.net/forum/lang-functional/95473-converting-number-list-haskell.html
numberToList = reverse . unfoldr (\x -> if x == 0 then Nothing else let (a,b) = x `quotRem` 10 in Just (b,a))
 
is_palimdrome number = num_list == reverse num_list
  where
    num_list = numberToList number
 
main :: IO ()
main = print . maximum . filter is_palimdrome $ zipWith (*) y z
  where y = [1000,999..100]
        z = [1000,999..100]

Python:

#!/usr/bin/python
 
def int_to_list(number):
  return map(int, str(number))
 
def is_palindrome(number):
  local_list = int_to_list(number)
  return local_list == list(reversed(local_list))
 
if __name__ == "__main__":
  second_list = first_list = list(reversed(range(100,1000+1)))
  prod_set = map(lambda i,j: i*j, first_list, second_list)
 
  print "%s" % max(filter(is_palindrome,prod_set))

And finally, Perl:

#!/usr/bin/perl
 
use strict;
use warnings;
use List::MoreUtils qw(pairwise);
 
sub is_palimdrone
{
  my ($number) = @_;
 
  my @digits = split(//, $number);
  my @reversed_digits = reverse(@digits);
 
  for (my $i = 0; $i < @digits; $i++)
  {
    return 0 if $digits[$i] != $reversed_digits[$i];
  }
 
  return 1;
}
 
my @two = my @one = reverse((1..1000));
 
my @join = pairwise { $a * $b } @one, @two;
 
foreach(@join)
{
  if ( is_palimdrone($_))
  {
    print "$_\n";
    last;
  }
}

Run Times
Haskell: 0m0.034s
Python: 0m0.060s
Perl: 0m0.166s

For anyone that is not aware, haskell should win this statistic every time. Out of the three languages its the only one that is compiled. If anyone knows of a way to run haskell interpretively, and without using ghci, please let me know. I've tried looking on the internets for this piece of information, but have come up short.

I am still open to code suggestions or improvements. I have found these to be very helpful and useful. So thank you to everyone that has said something before.

UPDATE
So here is the new code that fixes the problem of my algo before. I'm leaving the old up just to future readers aren't confused.

Thanks goes out to Jeremiah, Tom.B, Juster, and Guillaume for the code ideas used to fix the mistakes in the code above. Thanks guys!

Haskell:

module Main where
 
import Data.List
 
--Stole numberToList code from:
--http://www.rhinocerus.net/forum/lang-functional/95473-converting-number-list-haskell.html
numberToList = reverse . unfoldr (\x -> if x == 0 then Nothing else let (a,b) = x `quotRem` 10 in Just (b,a))
 
is_palimdrome number = num_list == reverse num_list
  where
    num_list = numberToList number
 
main :: IO ()
main = print . maximum $ [ x * y | x <- nums, y <- nums, is_palimdrome (x * y)] 
  where nums = [1000,999..100]

Python:

#!/usr/bin/python
 
def int_to_list(number):
  return map(int, str(number))
 
def is_palindrome(number):
  local_list = int_to_list(number)
  return local_list == list(reversed(local_list))
 
if __name__ == "__main__":
  print "%s" % max([x * y for x in range(1000,100, -1) \
                          for  y  in range(1000,100,-1) \
                          if is_palindrome(x * y)])

Perl:

#!/usr/bin/perl
 
use strict;
use warnings;
use List::Util qw(max);
 
sub is_palimdrone
{
  my ($number) = @_;
 
  my @digits = split(//, $number);
  my @reversed_digits = reverse(@digits);
 
  for (my $i = 0; $i < @digits; $i++)
  {
    return 0 if $digits[$i] != $reversed_digits[$i];
  }
 
  return 1;
}
 
my @two = my @one = reverse((100..999));
my @three;
 
for my $one (@one)
{
  for my $two (@two)
  {
    my $three = $two * $one;
    next unless is_palimdrone($three);
    push @three, $three;
  }
}
 
print max(@three);

Project Euler: Problem 3

Submitted by Bryce on Thu, 07/01/2010 - 23:09

OK, next installment of this. :)

The problem is stated as such:
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Haskell:

module Main where
 
factors count top_number
  | count >= top_number = []
  | zero_mod count = count : new_top: factors (count + 2) new_top
  | otherwise = factors (count + 2) top_number
  where new_top = round . fromIntegral $ top_number `div` count
 
zero_mod divisor
  | divide == 0 = True 
  | otherwise = False
  where divide = mod 600851475143 divisor
 
--prime :: Integer -> Integral -> Bool
prime divisor divided
  | divided == 1 = True
  | divisor >= sqrt_divided = True
  | mod divided divisor == 0 = False
  | otherwise = next_prime
  where next_prime = prime (divisor + 2) divided
        sqrt_divided = round . sqrt . fromIntegral $ divided
 
is_prime :: Integer -> Bool
is_prime input = prime 3 input
 
main :: IO ()
main = do
       let x = factors 3 600851475143
       let y = map is_prime x
       putStrLn $ show $ snd $  maximum ( zip y x)

Getting that sqrt function to work took me longer to figure out than I want to admit. I was having the hardest time getting the numeric types to play nice. I finally broke down and asked the haskell-beginners email list to get the answer.

Python:

#!/usr/bin/python
 
import math
 
top_number = 600851475143
 
def zero_mod(divisor):
  if top_number % divisor == 0:
    return True
  else:
    return False
 
def is_prime(divided):
  divisor = 3
  sqrt_divided = math.sqrt(divided)
  if divided == 1:
    return True
  else:
    while divisor <= sqrt_divided:
      if divided == divisor:
        return True
      elif divided % divisor == 0:
        return False
      else:
        divisor += 2
    return True
 
def main():
  count = 3
  go_to = top_number
 
  first_list =[]
 
  while count <= go_to:
    if zero_mod(count):
      first_list.append(count)
      go_to = top_number / count
      first_list.append(go_to)
 
    count += 2
 
  second_list = map(is_prime, first_list)
  print "%s" % max(zip(second_list, first_list))[-1] 
 
 
if __name__ == "__main__":
  main()

And finally Perl:

#!/usr/bin/perl
 
use strict;
use warnings;
 
my $top_number = 600851475143;
 
sub is_prime
{
  my ($divided) = @_;
  return 1 if ($divided == 1);
 
  my $divisor = 3;
  my $sqrt_divided = sqrt($divided);
 
  while($divisor <= $sqrt_divided)
  {
    return 0 unless ($divided % $divisor);
    $divisor += 2;
  }
 
  1;
}
 
my @f;
my $new_top = $top_number;
 
for(my $i = 3; $i <= $new_top; $i += 2)
{
  unless ($top_number % $i)
  {
    if (is_prime($i))
    {
      push @f, $i;
    }
  }
    $new_top = $top_number / $i;
}
 
print $f[-1];

Props goes out to zloyrusski who helped me figure out a major hang up with Perl on this one. The for loop idea was his,though I really diverted from his answer. Goes to show you how much two people really can think differently. Hey Zloyrusski, is this Perl code looking better? ;) As always, I'm open to constructive criticism.

--UPDATES--
1) Code has been redone to fix the error talked about by agf. I find it a little amusing that I still get the same answer though.
2) I gotta start using less languages to do this in. If I make a mistake I've gotta change & test three different versions.
3) Times ( as requested by Caleb):
Haskell: 0.004s
Python: 0.205s
Perl : 0.136s
4) More props for zloyrusski for the division algorithm.

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:

--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)

Python:

#!/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()

And finally, Perl:

#!/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.

Project Euler: Problem 1

Submitted by Bryce on Thu, 06/17/2010 - 20:39

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]

Python:

#!/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()

Perl:

#!/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.

Subscribe to my RSS feed

icon provided by FastIcon.com

Project Euler: Problem 4

Project Euler: Problem 3

Project Euler, Problem 2

Project Euler: Problem 1

Subscribe to my RSS feed

Top 5 most viewed posts

All time:

Last viewed: