LEVEL 2

I’ve now done 51 problems on Project Euler. That means I am now level 2. Hurrah. That’s problems 1-50 and 67. 67 is a harder version of another problem, hence why I’ve done it. I am pleased that so far I’ve not had to skip any. Some have been frustrating but I’ve got there in the end.

The challenge with the problems is not just to get the right answer, but also to get it in a reasonable amount of time. There is often a brute force approach, but as the questions go on, the search space is getting bigger and brute force takes much longer. There is a one-minute rule, that a ‘good’ solution should run in less than 60 seconds. And in this respect, I have to say that Python and its generators are a life-saver.

Software structure can be a pain. It’s neater to pre-generate a list than it is to keep fiddling around with it at each iteration. But that means that you might have some elements in it which you don’t need to worry about yet. And that means your code is slow, particularly if the length of this list is central to an inner loop. In Python when you use a generator, there’s only a minor difference between a pre-generated list and one which is filled in as you request it, and so you can have your lazily growing lists and keep the code all neat and short.

When you finish a problem you get to see the forum page for it, and there’s always someone who has shared their 5-page long Java solution. My average solution is about 20 lines.

Here’s a good one, it sums the digits in 100!:

import math
print sum([int(x) for x in str(math.factorial(100))])

try doing that in Java.

Oh alright then. Let’s see…

class Solution {
  public static void main(String[] args) {
    long int product = 1;
    for (int i = 2; i <= 100; i++) product *= i;
    int sum = 0;
    while (product > 1) {
      sum += product % 10;
      product /= 10;
    }
    System.out.println("" + product);    
  }
}

something like that?

oh wait that wouldn’t work because the integer would overflow. I’d have to use BigInteger and then the operators wouldn’t work and the code would be a hideous mess.
WELL I TRIED.

Advertisements

I like blogging

Posted in Uncategorized

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: