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

Practice Makes Perfect

I recently came across a blog post that is probably old enough to not be called a “blog post”. It’s called the Python Paradox. And the first paragraph starts like this, “In a recent talk I said something that upset a lot of people: that you could get smarter programmers to work on a Python project than you could to work on a Java project.” While I encourage everyone to read the rest of the short essay for yourselves, my interpretation of this essay is simply that programmers who in their spare time learn esoteric languages are generally better programmers and the ones you want to hire. If I haven’t already lost you, I really do have a reason for thinking this: practice.

As ZenHabits puts it, “It takes anywhere from 6-10 years to get great at something, depending on how often and how much you do it. Some estimate that it takes 10,000 hours to master something, but I think it varies from person to person and depends on the skill and other factors.”

I would count time spent coding at work to be practice. It’s certainly possible to learn new things about writing code from one’s coworkers, even if they happen to be bad coders, (just don’t do what they do) but you still have to be advanced enough to be aware of their mistakes. And that time learning and doing goes towards the ambiguous tipping point of around 10,000 hours. But it’s the programmer who goes home and fusses with something outside of his or her job that matters. The programmer who goes home and answers stack overflow questions for an extra couple of hours a week, writes open source code in her spare time, or keeps a tech blog where he documents and discusses with the world all of his little projects. That extra time spent doing these activities adds up, and allows someone to become a more proficient programmer quicker than just doing a job alone. I feel that type of programmer is what Paul Graham was talking about when he said “smarter programmers”. It’s not that these Python programmers back in 2004 had more brain power than non-Python programmers, they probably just wrote better or smarter code because they had more practice.

On a side note, I can’t help but feel there is a correlation with Python back in 2004 and functional programming languages today. People spending their free time working on projects that interest them, adding more time to the great skill clock. I feel safe in going out on a limb to paraphrase the quote above and state that, “You could get smarter programmers to work on a FP project than you could to work on a .NET or Java project.”

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.

A year in the life of this blogger

A little over a month and a half ago there was a personal reason to raise a beer in celebration. This blog reached its first birthday!

Most popular posts:

Getting the eeepc synaptic pad to work with Fedora 12: this recently became the “best seller” on the site. I guess there are a lot of fedora netbook users out there that really want the full functionality of their touch pad. And I don't blame a single one of them. ;)

pxe-network boot virtualbox -pt 2:I can't take all the credit for this one. I was working on some PXE stuff for work and wanted to see if I could use VirtualBox as a testing tool. And when I read the blog I saw that there were some steps that were assumed that the reader knew about. So I just took it upon me as a good techie to fill in the perceived void.

Getting all installed software, and their versions, on Debian/Ubuntu pt 2: Now with Threads!: Like the syaptic pad post, this one hasn't been up there very long. But it's had a fair amount of viewers to it. I guess singing up for the Perl Ironman
challenge paid off a little bit.

Flash Turtorial: Hello World: OK Really?!?! This should not have been viewed as much as it was. I shouldn't have been the first person to blog about using a button in flash for extreme beginners. Flash is very graphically oriented, having a text "Hello World" just seemed stupid to me.

Some lessons I've learned over the year:
t's amazing how much setting up SEO “stuff” can really draw traffic to one's site. I wish I learned that lesson much sooner than I did. Oh well, better late than never. And it really does seem to me that people prefer blogs that have been properly edited. Or at least I would like to think that I'm keeping readers longer because my grammar isn't as bad as when I started writing.

Some unexpected things:
No I didn't earn any money, mostly because I didn't try. But what did happen is that I got contacted for a job interview. Ironically enough it was the post “how NOT to get a job interview”
that the recruiter saw and got interested in me. Even though this happened months ago, I still chuckle a little every time I think about it.

The email from John telling me that my code for PS3 trophies no longer worked. Granted it's not the best reason to receive an email, but all things considered it was nice of him to let me know that it no longer worked. John, if you're reading this, thanks!

PoisenBit's 4 comments. I appreciate all the information that he left, and I can't help but be in awe at the enthusiasm with which he did it.

And no accomplishment post would be complete without the most important part, the “Thank You's".

OJ – for motivating me to start this journey. Thanks Bro!
Kelsey – for having the patience to help me become a better writer, even if it's just for a blog. Thanks Goofy Girl!

Syndicate content