Programming exercises/challenges

[skip at pobox.com]

    Ben> I'm learning Python by teaching myself, ...  I'm working on the
    Ben> project Euler problems, but I find that they don't really help my
    Ben> programming skills; they are more math focused.

I've found quite the opposite to be the case.  I've been programming in
Python for quite awhile and I find Project Euler helps me explore both the
math side of the problems (reminding me of all I've forgotten) but also
forces me to exercise various Python programming techniques and data
structures in ways I typically wouldn't in my day-to-day programming
existence.  Some of the problems while conceptually simple to solve are
intractable computationally with naive algorithms.

Here are four of the five (I think) basic ways to solve Problem 1 (find the
sum of all numbers below 1000 which are multiples of 3 or 5).  If you run it
notice the wide range of runtimes.  Which ones degrade badly as N increases?

    #!/usr/bin/env python

    import time

    N = 1000

    t = time.time()
    print sum([(n % 3 == 0 or n % 5 == 0) and n or 0 for n in xrange(N)]),
    print "%.6f" % (time.time() - t)

    t = time.time()
    print (sum(xrange(3, N, 3))
           + sum(xrange(5, N, 5))
           - sum(xrange(15, N, 15))),
    print "%.6f" % (time.time() - t)

    t = time.time()
    print sum([n for n in xrange(N) if n % 3 == 0 or n % 5 == 0]),
    print "%.6f" % (time.time() - t)

    t = time.time()
    print reduce(lambda x,y: x+y,
                 filter(lambda n: n%3==0 or n%5==0, xrange(N))),
    print "%.6f" % (time.time() - t)

    t = time.time()
    print sum(set(xrange(3, N, 3)) | set(xrange(5, N, 5))),
    print "%.6f" % (time.time() - t)

-- 
Skip Montanaro - skip at pobox.com - http://smontanaro.dyndns.org/