PERL

Project Euler: Problem 12

It’s time once again for a favorite blog theme, The Project Euler post. This time around I am answering problem twelve. The website states the problem as:
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

o spice things up I decided to use a language I haven't used for these in a while, Perl. I also included the usual suspects: Python and Haskell. So, here's the Perl code:

  1. #!/usr/bin/perl
  2.  
  3. use strict;
  4. use warnings;
  5.  
  6. my $index = 7;
  7. my $total = 28;
  8. my $divisors = 0;
  9.  
  10. sub divisors
  11. {
  12. my ($number) = @_;
  13. my $sq_n = sqrt($number);
  14. my $i = 1;
  15. my $t = 0;
  16.  
  17. while ($i <= $sq_n)
  18. {
  19. $t += 2 unless ($number % $i);
  20.  
  21. $i += 1;
  22. }
  23.  
  24. return $t;
  25. }
  26.  
  27. while( divisors($total) <= 500)
  28. {
  29. $index += 1;
  30. $total += $index;
  31. }
  32.  
  33. print "$total\n";

Nothing really new or interesting to mention in this code. Here is the Python code:
  1. #!/usr/bin/python
  2.  
  3. """
  4. solution for problem 12 in python.
  5. """
  6. import math
  7.  
  8. def get_divisors(number):
  9. tlist = []
  10. for x in xrange(2, int(math.sqrt(number))):
  11. d,r = divmod(number,x)
  12. if r == 0:
  13. tlist.append(x)
  14. tlist.append(d)
  15.  
  16. return len([1, number] + tlist)
  17.  
  18. def triangle_nums():
  19. iterator = 7
  20. num = 28
  21.  
  22. while True:
  23. yield num
  24. iterator += 1
  25. num += iterator
  26.  
  27. if __name__ == "__main__":
  28. tn = triangle_nums()
  29. for t in tn:
  30. tl = get_divisors(t)
  31. if tl > 500:
  32. print "num: %d\ncount: %d" % (t,tl)
  33. break

Pretty standard stuff for the most part. I think the only non-standard thing worth mentioning is the infinite triangle number generator. This took a little finangling, but I got it to work in the end.

Here is the Haskell code:

  1. module Main where
  2.  
  3. get_div_len number = foldl1 (+) [2 | x <- [1..x], number `mod` x == 0]
  4. where x = round . sqrt $ fromInteger number
  5.  
  6. main :: IO()
  7. main = do
  8. print . head $ dropWhile (\x -> fst x <= 499) (map (\x -> (get_div_len x ,x)) xs)
  9. where xs = map (\y -> sum [1..y]) [7..]

After creating these solutions, I did my usual, highly accurate, testing method to determine the speed of the computation. I was surprised by my results:

Perl: 12.462s
Python: 17.783s
Haskell (compiled): 13.877s

Normally the Haskell solution would be significantly faster, and I have a theory as to why the Haskell times are so close. In Perl and Python I’m doing two additions – one for the increase of the index number and another to increase the total number. In Haskell I’m doing 1 + n additions; the first is to increase the index, and the remaining additions (n) are those used to calculate the sum of all the numbers between (and including) 1 and the index. As the index variable gets larger, that calculation takes more and more time to perform. I would write this up as suboptimal. After spending some time traveling “the tubes,” I discovered the State Monad, which is the reason why this blog post took me so long. I had to spend a week going through random blogs, skimming books, and beating my head against a wall (more than usual) to figure this out.

Quick diversion, for those of you who do not know what the State Monad is, let me take a moment to to try and explain what it is and why it’s important in this context. Those of us that come from an imperative language (I am one of you in this regard) are used to being able to do a simple addition such as (in pseudo code):

Variable = 2
Variable = variable + 3 or Variable += 3

We can’t do this in Haskell; instead we have to create a new variable name for each new variable assignment. We could also create a function that recursively goes forward, generating the next number in the sequence and bringing our needed variables with us before going deeper down the recursion rabbit hole. With the State Monad, however, we can write our function in such a way that the necessary variables are implicitly passed. Take a look at the new solution to see what I mean:

  1. {-# LANGUAGE BangPatterns, UnboxedTuples #-}
  2. module Main where
  3.  
  4. import Control.Monad
  5. import Control.Monad.State
  6.  
  7. type MyState = (Int, Int)
  8. s0 = (7, 28)
  9.  
  10. tick = do
  11. (n,o) <- get
  12. let divs = getDivLen (n,o)
  13. if divs <= 500
  14. then do
  15. let n' = n + 1
  16. let o' = o + n'
  17. put (n', o')
  18. tick
  19. else
  20.  
  21. getDivLen :: MyState -> Int
  22. getDivLen (!n, !o) = foldl1 (+) [2 | x <- [1..x], o `mod` x == 0]
  23. where x = round . sqrt $ fromIntegral o
  24.  
  25. main :: IO ()
  26. main = print $ evalState tick s0

The tick function does not have any input parameters. All the information that the function needs comes from the “get” function call, which grabs the current state from the State Monad. If the tick function does not find a number of divisors greater than five hundred, it inserts new values back into the State Monad, and goes down to the next level of recursion.

It took me a long time to figure this out, mostly because of the lack of examples on the internet concerning the State Monad. If I wanted to create a random number generator I would have been set, but sadly I just wanted to create something that would hold a tuple of numbers and increment them accordingly. So I highly modified one of the “random number generator” examples.

My “highly accurate” speed test results for the new version is:
Haskell (compiled): 2.664s

which is a vast improvement (> 11s) over the previous implementation.

While a Project Euler problem may not have been the best way to learn about using the State Monad, I'm glad I stumbled upon it. I hope that it can be used as an example for others if they want to learn how to use the this particular monad to create things other than pseudo-random number generators.

One last thing – some of the brighter crayons in the box (which is most of you, based on the level of comments that I receive) might have noticed that I skipped problem 11. There is a simple response to that. I still haven’t solved it.

Project Euler: Problem 6

After a nice vacation, the obsession continues.

The sum of the squares of the first ten natural numbers is,
12 + 22 + ... + 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Haskell:

  1. module Main where
  2.  
  3. main :: IO ()
  4. main = do
  5. let x = [1..100]
  6. let sum2 = sum $ map (^2) x
  7. let sum1 = (sum x) ^2
  8. print (sum1 - sum2)

Python:
  1. #!/usr/bin/python3
  2. """Project Euler solution using generators."""
  3.  
  4. sum1 = 0
  5. sum2 = 0
  6.  
  7. for i in ((x,x ** 2) for x in range(1,100+1)):
  8. sum1 += i[0]
  9. sum2 += i[-1]
  10.  
  11. print(sum1 ** 2 - sum2)

PERL:
  1. #!/usr/bin/perl
  2.  
  3. my $sum1 = 0;
  4. my $sum2 = 0;
  5.  
  6. for (1..100)
  7. {
  8. $sum1 += $_;
  9. $sum2 += $_ **2;
  10. }
  11.  
  12. print ($sum1 **2 - $sum2);

Java:
  1. public class problem6
  2. {
  3. public static void main( String[] args)
  4. {
  5. int sum1 = 0;
  6. int sum2 = 0;
  7.  
  8. for( int i = 0; i < 100; i++)
  9. {
  10. sum1 += i;
  11. sum2 += i ^ 2;
  12. }
  13.  
  14. System.out.println(sum1 ^ 2 - sum2);
  15. }
  16. }

I admit writing a solution for Java is kind of a cheat. It's exactly the same as the PERL solution, minus some language differences. But since I started playing around with Android, I've started to spend more time working with Java and it has just bled into this project.

Run time comparison:

Because Java has to be compiled, I'm now using posting the time for the compiled version of the Haskell solution.
Haskell: 0.004s
Python: 0.285s
Perl: 0.005s
Java: 0.625s

I'll refrain from insulting the speed of Java if you do. ;)

Discussion:

Because of the simplicity of the solution, I tried to play around with the answers between Haskell and Python. Originally my Python solution looked more like my Haskell one, but after learning about generators I decided I would use one for the Python solution. All in all I think it would out rather well.

Questions, comments, insults?? (And not about me, about the code... I know what you people are thinking!)

Project Euler: Problem 5

It's that time again. ;)

Question five reads:
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

And here are my solutions (which I hope are correct this time).

Haskell:

  1. module Main where
  2.  
  3. import Data.List
  4.  
  5. divisible_11_to_20 number = 10 == (length $ unfoldr(\x -> if (snd $ quotRem number x) /= 0 || x < 11
  6. then Nothing
  7. else Just(x,x - 1)) 20)
  8.  
  9. -- solved this by the help on this URL:
  10. -- (http)basildoncoder.com/blog/2008/06/10/project-euler-problem-5/
  11. -- by increaing the loop from 2 to 2520, problem solves in seconds
  12. main :: IO ()
  13. main = print $ until (divisible_11_to_20) (+2520) 2520

As a quick note, yes I know that I could do this much quicker and cleaner with a list comprehension. I decided to use unfoldr because I wanted the experience of working with it. If it wasn't for this little desire my answer would have looked a lot more like my Python answer.

Python:

  1. #!/usr/bin/python
  2.  
  3. def div_11_to_20(divided):
  4. return all([not bool(divided % x) for x in xrange(11,20+1)])
  5.  
  6. if __name__ == "__main__":
  7. count = 2520
  8. while div_11_to_20(count) == False:
  9. count += 2520
  10.  
  11. print "%s" % count

And finally my Perl solution:

  1. #!/usr/bin/perl
  2.  
  3. sub divide_11_to_20
  4. {
  5. my ( $divided ) = @_;
  6.  
  7. foreach (11..20)
  8. {
  9. return 0 if ($divided % $_);
  10. }
  11.  
  12. return 1;
  13. }
  14.  
  15. my $main_count = 2520;
  16. while ( !divide_11_to_20($main_count) )
  17. {
  18. $main_count += 2520;
  19. }
  20.  
  21. print $main_count;

Run Times:
Haskell: 0m1.302s
Python: 0m0.769s
Perl: 0m0.223s

Observations:
It doesn't surprise me that the Perl solution ends up being the fastest on these run times. I say this because per iteration the Perl solutions has less calculations. Both the Haskell and Python solutions perform 10 divisions per iteration, where as the Perl solution only performs 10 divisions when the correct number is is being divided. Its one of those things where the difference is very small, but will become larger as the number of iterations increases.

Project Euler: Problem 4

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:

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

Python:

  1. #!/usr/bin/python
  2.  
  3. def int_to_list(number):
  4. return map(int, str(number))
  5.  
  6. def is_palindrome(number):
  7. local_list = int_to_list(number)
  8. return local_list == list(reversed(local_list))
  9.  
  10. if __name__ == "__main__":
  11. second_list = first_list = list(reversed(range(100,1000+1)))
  12. prod_set = map(lambda i,j: i*j, first_list, second_list)
  13.  
  14. print "%s" % max(filter(is_palindrome,prod_set))

And finally, Perl:

  1. #!/usr/bin/perl
  2.  
  3. use strict;
  4. use warnings;
  5. use List::MoreUtils qw(pairwise);
  6.  
  7. sub is_palimdrone
  8. {
  9. my ($number) = @_;
  10.  
  11. my @digits = split(//, $number);
  12. my @reversed_digits = reverse(@digits);
  13.  
  14. for (my $i = 0; $i < @digits; $i++)
  15. {
  16. return 0 if $digits[$i] != $reversed_digits[$i];
  17. }
  18.  
  19. return 1;
  20. }
  21.  
  22. my @two = my @one = reverse((1..1000));
  23.  
  24. my @join = pairwise { $a * $b } @one, @two;
  25.  
  26. foreach(@join)
  27. {
  28. if ( is_palimdrone($_))
  29. {
  30. print "$_\n";
  31. last;
  32. }
  33. }

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:

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

Python:
  1. #!/usr/bin/python
  2.  
  3. def int_to_list(number):
  4. return map(int, str(number))
  5.  
  6. def is_palindrome(number):
  7. local_list = int_to_list(number)
  8. return local_list == list(reversed(local_list))
  9.  
  10. if __name__ == "__main__":
  11. print "%s" % max([x * y for x in range(1000,100, -1) \
  12. for y in range(1000,100,-1) \
  13. if is_palindrome(x * y)])

Perl:
  1. #!/usr/bin/perl
  2.  
  3. use strict;
  4. use warnings;
  5. use List::Util qw(max);
  6.  
  7. sub is_palimdrone
  8. {
  9. my ($number) = @_;
  10.  
  11. my @digits = split(//, $number);
  12. my @reversed_digits = reverse(@digits);
  13.  
  14. for (my $i = 0; $i < @digits; $i++)
  15. {
  16. return 0 if $digits[$i] != $reversed_digits[$i];
  17. }
  18.  
  19. return 1;
  20. }
  21.  
  22. my @two = my @one = reverse((100..999));
  23. my @three;
  24.  
  25. for my $one (@one)
  26. {
  27. for my $two (@two)
  28. {
  29. my $three = $two * $one;
  30. next unless is_palimdrone($three);
  31. push @three, $three;
  32. }
  33. }
  34.  
  35. print max(@three);

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

Syndicate content