# 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:

`#!/usr/bin/perl use strict;use warnings; my \$index = 7;my \$total = 28;my \$divisors = 0; sub divisors{    my (\$number) = @_;    my \$sq_n = sqrt(\$number);    my \$i = 1;    my \$t = 0;     while (\$i <= \$sq_n)    {        \$t += 2 unless (\$number % \$i);         \$i += 1;    }     return \$t;} while( divisors(\$total) <= 500){    \$index += 1;    \$total += \$index;} print "\$total\n";`

Nothing really new or interesting to mention in this code. Here is the Python code:
`#!/usr/bin/python """solution for problem 12 in python."""import math def get_divisors(number):    tlist = []    for x in xrange(2, int(math.sqrt(number))):        d,r = divmod(number,x)        if r == 0:            tlist.append(x)            tlist.append(d)     return len([1, number] + tlist) def triangle_nums():    iterator = 7    num = 28     while True:        yield num        iterator += 1        num += iterator if __name__ == "__main__":    tn = triangle_nums()    for t in tn:        tl = get_divisors(t)        if tl > 500:            print "num: %d\ncount: %d" % (t,tl)            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.

`module Main where get_div_len number = foldl1 (+) [2 | x <- [1..x], number `mod` x == 0]    where x = round . sqrt \$ fromInteger number main :: IO()main = do  print . head \$ dropWhile (\x -> fst x <= 499) (map (\x -> (get_div_len x ,x)) xs)  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

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:

`{-# LANGUAGE BangPatterns, UnboxedTuples #-}module Main where import Control.Monadimport Control.Monad.State type MyState = (Int, Int)s0 = (7, 28) tick = do    (n,o) <- get    let divs = getDivLen (n,o)    if divs <= 500        then do            let n' = n + 1            let o' = o + n'            put (n', o')            tick        else            return o getDivLen :: MyState -> IntgetDivLen (!n, !o) = foldl1 (+) [2 | x <- [1..x], o `mod` x == 0]    where x = round . sqrt \$ fromIntegral o main :: IO ()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:

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.```

`module Main where main :: IO ()main = do       let x = [1..100]       let sum2 = sum \$ map (^2) x       let sum1 = (sum x) ^2       print (sum1 - sum2)`

Python:
`#!/usr/bin/python3"""Project Euler solution using generators.""" sum1 = 0sum2 = 0 for i in ((x,x ** 2) for x in range(1,100+1)):    sum1 += i[0]    sum2 += i[-1] print(sum1 ** 2 - sum2)`

PERL:
`#!/usr/bin/perl my \$sum1 = 0;my \$sum2 = 0; for (1..100){  \$sum1 += \$_;  \$sum2 += \$_ **2;} print (\$sum1 **2 - \$sum2);`

Java:
`public class problem6{    public static void main( String[] args)    {      int sum1 = 0;      int sum2 = 0;       for( int i = 0; i < 100; i++)      {        sum1 += i;        sum2 += i ^ 2;      }       System.out.println(sum1 ^ 2 - sum2);    }}`

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

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

`module Main where import Data.List divisible_11_to_20 number = 10 == (length \$ unfoldr(\x -> if (snd \$ quotRem number x) /= 0 || x < 11  then Nothing  else Just(x,x - 1)) 20) -- solved this by the help on this URL:-- (http)basildoncoder.com/blog/2008/06/10/project-euler-problem-5/-- by increaing the loop from 2 to 2520, problem solves in secondsmain :: IO ()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:

`#!/usr/bin/python def div_11_to_20(divided):  return all([not bool(divided % x) for x in xrange(11,20+1)]) if __name__ == "__main__":  count = 2520  while div_11_to_20(count) == False:    count += 2520   print "%s" % count`

And finally my Perl solution:

`#!/usr/bin/perl sub divide_11_to_20{  my ( \$divided ) = @_;   foreach (11..20)  {     return 0 if (\$divided % \$_);  }   return 1;} my \$main_count = 2520;while ( !divide_11_to_20(\$main_count) ){	\$main_count += 2520;} print \$main_count;`

Run Times:
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:

`module Main where import Data.List --Stole numberToList code from:--http://www.rhinocerus.net/forum/lang-functional/95473-converting-number-list-haskell.htmlnumberToList = 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
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!

`module Main where import Data.List --Stole numberToList code from:--http://www.rhinocerus.net/forum/lang-functional/95473-converting-number-list-haskell.htmlnumberToList = 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]`
`#!/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)])`
`#!/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);`