PyEuler

[bearophileHUGS]

This is the first time I write something that looks like a little
rant Surely I'll be wrong in many points, but I presume this isn't
going to damage people, so...

Here there are some functional Python solutions to some Euler
problems:
http://pyeuler.wikidot.com/

Some pieces of that code:

def takenth(n, iterable):
"Returns the nth item"
return list(islice(iterable, n, n+1))[0]

def euler1(end, nums):
isanymultiple = lambda x: any((x % y == 0) for y in nums)
return sum(filter(isanymultiple, xrange(end)))

euler1(1000, [3,5])

#Find the sum of all the even-valued terms in the Fibonacci sequence
which do not exceed one million.

def fibonacci(n):
"""Return nth element of the fibonacci serie"""
if n == 0 or n == 1:
return n
return fibonacci(n-1) + fibonacci(n-2)

def euler2(end):
genfib = imap(fibonacci, count())
candidates = takewhile(lambda n: n<end, genfib)
return sum(ifilter(lambda n: n%2, candidates))


def least_common_multiple(nums):
"""Return least common multiples of nums"""
factorized = dict((n, dict(factorize(n))) for n in nums)
union = lambda lst: reduce(set.union, map(set, lst))
all_factors = union(factorized.values())
getexponent = lambda factor: (factorized[n].get(factor, 0) for n
in nums)
return mul(factor**(max(getexponent(factor))) for factor in
all_factors)

What I think about such code:
- It's not much readable (but usually it can be read).
- it's not much Pythonic. Python is only partially functional, if you
try to use it in a very functional way you go against the language,
its coding practices, and the net result may be slow/little readable.
If you want to write almost fully functional code it's better to use a
fitter language, like Haskell.
- In some situations it seems to just show lack of knowledge of
Python.
- In various points it's not much efficient in speed and/or space.
- It's not even short, there are many ways to shorten that code, often
keeping or even increasing its readability; one of the most common
ways is to use generators and list comps more often.
- It lacks tests, like doctests.
- It has small pedagogical value too, because this is a bad way to
learn Python, and programming in general too.
- It has shown me when to use takewhile(), and some of the
mathematical insights it contains are interesting

Bye,
bearophile

 

[Mark Dickinson]

This is the first time I write something that looks like a little
rant Surely I'll be wrong in many points, but I presume this isn't
going to damage people, so...

Agreed on all points. This looks a lot like someone trying to
write
Haskell in Python. And that's a truly horrible way of finding a least
common multiple: much better to do lcm(a, b) = a*(b//gcd(a, b)), with
gcd computed using the usual algorithm (written *iteratively*, not
recursively).

Mark

 

[Paul Rubin]

def takenth(n, iterable):
"Returns the nth item"
return list(islice(iterable, n, n+1))[0]

return islice(iterable, n).next()

isanymultiple = lambda x: any((x % y == 0) for y in nums)
return sum(filter(isanymultiple, xrange(end)))

This isn't so good, you really want to apply the filters recursively.

def fibonacci(n):
"""Return nth element of the fibonacci serie"""
if n == 0 or n == 1:
return n
return fibonacci(n-1) + fibonacci(n-2)

uggh!!!! exponential blowup!

def euler2(end):
genfib = imap(fibonacci, count())

Are you kidding?
def ggenfib():
a,b = 1,2
while True:
yield a
a,b = b, a=b

What I think about such code:
- It's not much readable (but usually it can be read). ...

Your observations are generally good; I'd say it was done
without enough attention to the math too.

There is a full set of solutions on the haskell wiki, if anyone cares.

 

[Arnaud Delobelle]

Are you kidding?
    def ggenfib():
      a,b = 1,2
      while True:
         yield a
         a,b = b, a=b

Or:

def genfib(a=0, b=1):
for a, b in iter(lambdab, a+b), None):
yield a

;-)

Ahem. I admit that somehow, I am proud of this.

 

[Mark Dickinson]

def genfib(a=0, b=1):
    for a, b in iter(lambdab, a+b), None):
        yield a

;-)

Ahem.  I admit that somehow, I am proud of this.

You're one sick puppy dog.
(P.S. Your mother was a hamster, and your father smelt of
elderberries.)

Gratuitous insulting'ly yours,

Mark

 

[bearophileHUGS]

Paul Rubin:

def ggenfib():
a,b = 1,2
while True:
yield a
a,b = b, a=b

Your version is the nice basic generator version (the last line
contains a +, I presume), but I like this other version too:

def xfibonacci():
a = b = 1
yield a
yield b
while True:
a = a + b
yield a
b = b + a
yield b

It's a bit faster, longer, and I find it a bit more readable.

There is a full set of solutions on the haskell wiki, if anyone cares.

Thank you for the suggestion, I have found it:
http://www.haskell.org/haskellwiki/Euler_problems
In the last months lot of people are suddenly talking about Haskell
(and sometimes even F#!). I think the Haskell language is too much
complex for me for bigger programs, but for such small mathematical
programs it looks very nice and almost readable.

This is a curious comment from that Wiki about a solution to the
Problem 2:

The first two solutions work because 10^6 is small. The following solution also works for much larger numbers (up to at least 10^1000000 on my computer):<

What I like of the Haskell community is how much they keep things tidy
and ordered. And every function used on the Wiki points to the
documentation! They create a spotless wiki about Shootout benchmarks,
Euler problems, and so on, they discuss al lot and they try to find
fast & correct solutions. They even *improve* their language when they
find some benchmarks of the Shootout run too much slow with Haskell,
because they have understood that despite being most little (silly)
programs, the benchmarks of the Shootout site are rather well thought
out. Both the Python and D communities that I know (and I appreciate)
aren't like that. I presume the Haskell language itself appeals to
people that like tidy and well ordered things, and when you use that
language a lot it may encourage your mind to think even more in that
way. Computer languages too make the man

Bye,
bearophile

 

[Arnaud Delobelle]

Paul Rubin:


Your version is the nice basic generator version (the last line
contains a +, I presume), but I like this other version too:

def xfibonacci():
    a = b = 1
    yield a
    yield b
    while True:
        a = a + b
        yield a
        b = b + a
        yield b

It's a bit faster, longer, and I find it a bit more readable.

In this case why not:

def xfib(a=1, b=1):
while True:
yield a
a += b
yield b
b += a

 

[bearophileHUGS]

Arnaud Delobelle:

In this case why not:

def xfib(a=1, b=1):
while True:
yield a
a += b
yield b
b += a

That's a bit less easy to understand than my version, for me.
In my version is easy to see the values of the variables. And using a
longer function name is better.

Bye,
bearophile

 

[Arnaud Delobelle]

Arnaud Delobelle:



That's a bit less easy to understand than my version, for me.
In my version is easy to see the values of the variables.

I disagree; the generator function has no right to keep a and b to
itself. a and b cry out to be function parameters. The user may want
to start a fibonacci sequence with any two initial values. IMHO one
of the great qualities of Python is that it makes this very easy in
most cases.

And using a
longer function name is better.

Up to a certain length

 

[bearophileHUGS]

Arnaud Delobelle:

I disagree; the generator function has no right to keep a and b to
itself. a and b cry out to be function parameters.

I see. Then that's a generator for a generalized Fibonacci
sequence
Your version too is useful.

Bye,
bearophile