pythonize this!

[superpollo]

goal (from e.c.m.): evaluate
1^2+2^2+3^2-4^2-5^2+6^2+7^2+8^2-9^2-10^2+...-2010^2, where each three
consecutive + must be followed by two - (^ meaning ** in this context)

my solution:

>>> s = 0
>>> for i in range(1, 2011):
... s += i**2
... if not (i+1)%5:
... s -= 2*i**2
... if not i%5:
... s -= 2*i**2
...
>>> print s
536926141
>>>

bye

[Ulrich Eckhardt]

superpollo wrote:
> ... s += i**2
> ... if not (i+1)%5:
> ... s -= 2*i**2
> ... if not i%5:
> ... s -= 2*i**2

if not (i % 5) in [1, 2]:
s += i**2
else:
s -= i**2

Untested code.

Uli

--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932

[Alain Ketterlin]

superpollo <ute...@esempio.net> writes:

> goal (from e.c.m.): evaluate
> 1^2+2^2+3^2-4^2-5^2+6^2+7^2+8^2-9^2-10^2+...-2010^2, where each three
> consecutive + must be followed by two - (^ meaning ** in this context)
>
> my solution:
>
>>>> s = 0
>>>> for i in range(1, 2011):
> ... s += i**2
> ... if not (i+1)%5:
> ... s -= 2*i**2
> ... if not i%5:
> ... s -= 2*i**2

You compute i**2 too many times (7/5 times more than necessary) and
twice too many modulos. I suggest:

c = { 0:1, 1:1, 2:1, 3:-1, 4:-1 }
#or, why not: c = lambda i : +1 if (i%5) < 3 else -1

s = 0
for i in range(1,2011):

s += c[(i-1)%5]*(i**2)
print s

Or, as a one liner using a list comprehension:

print sum( ( c[(i-1)%5]*i**2 for i in xrange(1,2011) ) )

I don't know which one is the fastest (between dict+loop, dict+compr,
lambda+loop and lambda+compr).

-- Alain.

[superpollo]

Ulrich Eckhardt ha scritto:

> superpollo wrote:
>> ... s += i**2
>> ... if not (i+1)%5:
>> ... s -= 2*i**2
>> ... if not i%5:
>> ... s -= 2*i**2
>
> if not (i % 5) in [1, 2]:
> s += i**2
> else:
> s -= i**2
>
> Untested code.

does not work:

>>> s = 0
>>> for i in range(1, 2011):

... if not (i % 5) in [1, 2]:
... s += i**2
... else:
... s -= i**2
...
>>> print s
546627205
>>>

but this does:

>>> s = 0
>>> for i in range(1, 2011):

... if i % 5 in [1, 2, 3]:
... s += i**2
... else:
... s -= i**2

[Stefan Behnel]

superpollo, 15.06.2010 13:49:

> goal (from e.c.m.): evaluate
> 1^2+2^2+3^2-4^2-5^2+6^2+7^2+8^2-9^2-10^2+...-2010^2, where each three
> consecutive + must be followed by two - (^ meaning ** in this context)
>
> my solution:
>
> >>> s = 0
> >>> for i in range(1, 2011):
> ... s += i**2
> ... if not (i+1)%5:
> ... s -= 2*i**2
> ... if not i%5:
> ... s -= 2*i**2

Pretty ugly, if you ask me. What about this:

s = 0
for i in range(1, 2011):

if i%5 in (1,2,3):

s += i**2
else:
s -= i**2

Here's the obvious one-liner:

s = sum(i**2 if i%5 in (1,2,3) else -i**2
for i in range(1, 2011))

Runs in ~600 usecs for me according to timeit - pretty fast.

Stefan

[Jussi Piitulainen]

superpollo writes:

Me two:

s = 0
for k in range(1, 2010, 5):
s += k**2 + (k + 1)**2 + (k + 2)**2 - (k + 3)**2 - (k + 4)**2

s = 0
for k in range(1, 2011):
s += k**2 * (-1 if k % 5 in {4,0} else +1)

[Peter Otten]

superpollo wrote:

> goal (from e.c.m.): evaluate
> 1^2+2^2+3^2-4^2-5^2+6^2+7^2+8^2-9^2-10^2+...-2010^2, where each three
> consecutive + must be followed by two - (^ meaning ** in this context)

>>> from itertools import cycle, izip
>>> sum(sign*i*i for sign, i in izip(cycle([1]*3+[-1]*2), range(1, 2011)))
536926141

[superpollo]

Peter Otten ha scritto:

don't understand it bit i like this a lot!

[superpollo]

superpollo ha scritto:

^^^

*but*

[Stefan Behnel]

Stefan Behnel, 15.06.2010 14:23:
> superpollo, 15.06.2010 13:49:

>> goal (from e.c.m.): evaluate
>> 1^2+2^2+3^2-4^2-5^2+6^2+7^2+8^2-9^2-10^2+...-2010^2, where each three
>> consecutive + must be followed by two - (^ meaning ** in this context)
>>
>> my solution:
>>
>> >>> s = 0
>> >>> for i in range(1, 2011):
>> ... s += i**2
>> ... if not (i+1)%5:
>> ... s -= 2*i**2
>> ... if not i%5:
>> ... s -= 2*i**2
>

> Pretty ugly, if you ask me. What about this:
>

> s = 0
> for i in range(1, 2011):

> if i%5 in (1,2,3):
> s += i**2
> else:
> s -= i**2
>
> Here's the obvious one-liner:
>
> s = sum(i**2 if i%5 in (1,2,3) else -i**2
> for i in range(1, 2011))
>
> Runs in ~600 usecs for me according to timeit - pretty fast.

Just for the record, this Cython code runs in ~15 usecs for me:

def makesum():
return <int>sum(i**2 if i%5 in (1,2,3) else -i**2

for i in range(1, 2011))

using the latest Cython 0.13pre. The "<int>" cast is required to drop the
sum() into efficient C code. Without it, the code runs in 55 usecs.

Stefan

[Andre Alexander Bell]

On 06/15/2010 01:49 PM, superpollo wrote:
> my solution:
>
> [...]
> >>> print s
> 536926141

Or, if you would like to use numpy:

>>> import numpy
>>> squares = numpy.arange(1, 2011, dtype=numpy.int)**2
>>> signs = numpy.ones(len(squares), dtype=numpy.int)
>>> signs[3::5] = -1
>>> signs[4::5] = -1
>>> numpy.sum(signs*squares)
536926141

Cheers

Andre

[Jean-Michel Pichavant]

Works for women as well, we don't understand them, yet we love them ;)

JM

[Stefan Behnel]

superpollo, 15.06.2010 14:55:

Didn't you want to get it "pythonized"? If it's not understandable, it
can't be pythonic.

Stefan

[superpollo]

Stefan Behnel ha scritto:

maybe i must study itertools then ;-)

thanks

bye

[Peter Otten]

Stefan Behnel wrote:

I'm glad I didn't have to say that mayself ;)

OP: You can work it out step by step:

First build a list of signs:

>>> [1]*3+[-1]*2
[1, 1, 1, -1, -1]

Then repeat them infinitely:

>>> c = cycle("xy")
>>> c.next()
'x'
>>> c.next()
'y'
>>> c.next()
'x'
>>> c.next()
'y'
>>> c.next()
'x'

Combine with the bases using izip:

>>> signs = cycle([1]*3+[-1]*2)
>>> [sign*i for sign, i in izip(signs, range(10))]
[0, 1, 2, -3, -4, 5, 6, 7, -8, -9]

Finally calculate the sum:
>>> signs = cycle([1]*3+[-1]*2)
>>> sum(sign*i for sign, i in izip(signs, range(10)))
-3

Peter

[Ian Kelly]

On Tue, Jun 15, 2010 at 6:21 AM, Alain Ketterlin
<al...@dpt-info.u-strasbg.fr> wrote:
> You compute i**2 too many times (7/5 times more than necessary) and
> twice too many modulos. I suggest:
>
> c = { 0:1, 1:1, 2:1, 3:-1, 4:-1 }
> #or, why not: c = lambda i : +1 if (i%5) < 3 else -1
>
> s = 0
> for i in range(1,2011):
>    s += c[(i-1)%5]*(i**2)
> print s

In fact, most of them are unnecessary:

from itertools import izip, cycle

def squares(start, stop):
square = start * start
step = start * 2 + 1
for root in xrange(start, stop):
yield square
square += step
step += 2

print sum(sign * square for sign, square in izip(cycle([1,1,1,-1,-1]),
squares(1, 2011)))

Now, anybody know how to make that version a one-liner without making
it go quadratic in run-time?

Cheers,
Ian

[Paul Rubin]

superpollo <ute...@esempio.net> writes:
> goal (from e.c.m.): evaluate
> 1^2+2^2+3^2-4^2-5^2+6^2+7^2+8^2-9^2-10^2+...-2010^2, where each three
> consecutive + must be followed by two - (^ meaning ** in this context)

print sum([-1,1,1,1,-1][i%5]*i**2 for i in xrange(1,2011))

[superpollo]

Paul Rubin ha scritto:

beautiful.

thx

[Ignacio Mondino]

I think This one is pretty, clean, using the standard library.
pretty pythonic.

def sign_and_sqr(n):
""" return a numbers square a change the sign accordingly
if n % 5 == 0 or (n + 1) % 5 == 0:
return (n ** 2) * -1
else:
return n ** 2

result = sum([sign_and_sqr(x) for x in range(0,2011)])
print result

ok, the function has two exits, but im lazy at the moment :)

--
---------------------------------------------------------------------------

Ignacio Mondino
Don't Panic

[Alessandro [AkiRoss] Re]

On Jun 15, 1:49 pm, superpollo <ute...@esempio.net> wrote:
> goal (from e.c.m.): evaluate
> 1^2+2^2+3^2-4^2-5^2+6^2+7^2+8^2-9^2-10^2+...-2010^2, where each three
> consecutive + must be followed by two - (^ meaning ** in this context)

My functional approach :)

from operator import add
from functools import reduce

def square(l):
return (v**2 for v in l)

def sign(l, s):
i = 0
for v in l:
yield s[i % len(s)] * v
i += 1

print reduce(add, sign(square(xrange(1, 2011)), [1, 1, 1, -1, -1]))

(536926141)

~Aki

[Alessandro [AkiRoss] Re]

On Jun 15, 2:37 pm, Peter Otten <__pete...@web.de> wrote:
> >>> from itertools import cycle, izip
> >>> sum(sign*i*i for sign, i in izip(cycle([1]*3+[-1]*2), range(1, 2011)))

Wow!! :D
I didn't knew cycle, great! With that i can reduce my solution (which
isn't still elegant as your) to:

print reduce(add,imap(mul, cycle([1, 1, 1, -1, -1]), (v**2 for v in
xrange(1, 2011))))

(536926141)
~Aki

[Lie Ryan]

On 06/15/10 21:49, superpollo wrote:
> goal (from e.c.m.): evaluate
> 1^2+2^2+3^2-4^2-5^2+6^2+7^2+8^2-9^2-10^2+...-2010^2, where each three
> consecutive + must be followed by two - (^ meaning ** in this context)
>
> my solution:
>
>>>> s = 0
>>>> for i in range(1, 2011):

> .... s += i**2
> .... if not (i+1)%5:
> .... s -= 2*i**2
> .... if not i%5:
> .... s -= 2*i**2
> ....
>>>> print s
> 536926141

Probably bending the rules a little bit:

>>> sum(x**2 - 8*x - 20 for x in range(1, 2010, 5))
536926141

another variation:

>>> sum((x - 10) * (x + 2) for x in range(1, 2010, 5))
536926141

[Jussi Piitulainen]

Lie Ryan writes:

> On 06/15/10 21:49, superpollo wrote:
> > goal (from e.c.m.): evaluate
> > 1^2+2^2+3^2-4^2-5^2+6^2+7^2+8^2-9^2-10^2+...-2010^2, where each
> > three consecutive + must be followed by two - (^ meaning ** in
> > this context)

[...]

> Probably bending the rules a little bit:
>
> >>> sum(x**2 - 8*x - 20 for x in range(1, 2010, 5))
> 536926141
>
> another variation:
>
> >>> sum((x - 10) * (x + 2) for x in range(1, 2010, 5))
> 536926141

Gleefully bending the rules all the way:

>>> 536926141
536926141

Cheers!

[Stefan Behnel]

Jussi Piitulainen, 16.06.2010 13:10:

Timeit:

100000000 loops, best of 3: 0.0148 usec per loop

Certainly the fastest solution so far.

Stefan

[Richard Brodie]

"Lie Ryan" <lie....@gmail.com> wrote in message news:4c18...@dnews.tpgi.com.au...

> Probably bending the rules a little bit:
>
>>>> sum(x**2 - 8*x - 20 for x in range(1, 2010, 5))
> 536926141

Or, letting Python do the algera for you:

>>> from sympy import var, sum
>>> dummy = var('j k')
>>> k = (5 * j) + 1
>>> t = (k)**2 + (k + 1)**2 + (k + 2)**2 - (k + 3)**2 - (k + 4)**2
>>> sum(t, (j, 0, 401))
536926141

[Boris Borcic]

Ignacio Mondino wrote:
> On Tue, Jun 15, 2010 at 8:49 AM, superpollo<ute...@esempio.net> wrote:

> I think This one is pretty, clean, using the standard library.
> pretty pythonic.
>
> def sign_and_sqr(n):
> """ return a numbers square a change the sign accordingly
> if n % 5 == 0 or (n + 1) % 5 == 0:

imho this fails DRY too much to be wholly pythonic,
write rather

if n%5 in (0,4) :

[Andre Alexander Bell]

On 06/16/2010 12:47 PM, Lie Ryan wrote:
> Probably bending the rules a little bit:
>
>>>> sum(x**2 - 8*x - 20 for x in range(1, 2010, 5))
> 536926141

Bending them even further, the sum of the squares from 1 to N is given by

(1) N*(N+1)*(2*N+1)/6.

The given problem can be divided into five sums of every fifth square
starting from 1,2,3,4,5 respectively. This is given by

(2) S(a,k) = sum_{i=1}^k (5*i-4+a)^2

for a in range(5) and we are finally interested in

(3) S(k) = S(0,k) + S(1,k) + S(2,k) - S(3,k) - S(4,k)

Substituting (2) and (1) in (3) gives (in python code)

>>> S = lambda k: (50*k**3 - 165*k**2 - 47*k) / 6
>>> S(2010/5)
536926141

However, this only works for full cycles of (1,1,1,-1,-1) and you would
have to add/subtract the modulus parts yourself. (e.g. if you are
interested in your sum from 1..2011...

Cheers

Andre

[Stefan Behnel]

Andre Alexander Bell, 18.06.2010 11:23:

> On 06/16/2010 12:47 PM, Lie Ryan wrote:

>> Probably bending the rules a little bit:
>>
>>>>> sum(x**2 - 8*x - 20 for x in range(1, 2010, 5))
>> 536926141
>

> Bending them even further, the sum of the squares from 1 to N is given by
>
> (1) N*(N+1)*(2*N+1)/6.
>
> The given problem can be divided into five sums of every fifth square
> starting from 1,2,3,4,5 respectively. This is given by
>
> (2) S(a,k) = sum_{i=1}^k (5*i-4+a)^2
>
> for a in range(5) and we are finally interested in
>
> (3) S(k) = S(0,k) + S(1,k) + S(2,k) - S(3,k) - S(4,k)
>
> Substituting (2) and (1) in (3) gives (in python code)
>
>>>> S = lambda k: (50*k**3 - 165*k**2 - 47*k) / 6
>>>> S(2010/5)
> 536926141
>
> However, this only works for full cycles of (1,1,1,-1,-1) and you would
> have to add/subtract the modulus parts yourself. (e.g. if you are
> interested in your sum from 1..2011...

The thing is, if you can't do the math in the time that your processor
needs to run the brute force loop, it's often not worth doing the math at all.

Stefan

[Peter Otten]

Stefan Behnel wrote:

By that standard using Cython for the problem doesn't pay either;)

Peter

[Stefan Behnel]

Peter Otten, 18.06.2010 12:14:

True. Running the C compiler certainly takes a lot longer than starting up
Python and running the loop.

Stefan

[Mark Lawrence]

On 18/06/2010 10:23, Andre Alexander Bell wrote:
> On 06/16/2010 12:47 PM, Lie Ryan wrote:

>> Probably bending the rules a little bit:
>>
>>>>> sum(x**2 - 8*x - 20 for x in range(1, 2010, 5))
>> 536926141
>

> Bending them even further, the sum of the squares from 1 to N is given by
>
> (1) N*(N+1)*(2*N+1)/6.
>
> The given problem can be divided into five sums of every fifth square
> starting from 1,2,3,4,5 respectively. This is given by
>
> (2) S(a,k) = sum_{i=1}^k (5*i-4+a)^2
>
> for a in range(5) and we are finally interested in
>
> (3) S(k) = S(0,k) + S(1,k) + S(2,k) - S(3,k) - S(4,k)
>
> Substituting (2) and (1) in (3) gives (in python code)
>
>>>> S = lambda k: (50*k**3 - 165*k**2 - 47*k) / 6
>>>> S(2010/5)
> 536926141
>
> However, this only works for full cycles of (1,1,1,-1,-1) and you would
> have to add/subtract the modulus parts yourself. (e.g. if you are
> interested in your sum from 1..2011...
>

> Cheers
>
>
> Andre

The good news is that this is easily the fastest piece of code that I've
seen yet. The bad news is that first prize in the speed competition is
a night out with me. :)

Cheers.

Mark Lawrence.

[Steven D'Aprano]

On Fri, 18 Jun 2010 14:32:30 +0100, Mark Lawrence wrote:

> The good news is that this is easily the fastest piece of code that I've
> seen yet. The bad news is that first prize in the speed competition is
> a night out with me.

I suppose second prize is two nights out with you?

--
Steven

[Mark Lawrence]

Stephen, you are absolutely correct. I never realised from your posting
history just how astute you are. :)

Kindest regards.

Mark Lawrence.

[Andre Alexander Bell]

On 06/18/2010 03:32 PM, Mark Lawrence wrote:
> The good news is that this is easily the fastest piece of code that I've
> seen yet. The bad news is that first prize in the speed competition is

> a night out with me. :)

Well, that actually means that Stefan Behnel will run my solution
through cython. As Steven D'Aprano already pointed out this then will
make me receive the second price of two nights out?

Cheers

Andre

[Mark Lawrence]

Andre, looks like a really bad day for you then, *TWO* nights out with
me *AND* (looking at your email address) Germany loosing in the world
cup. :(

Kindest regards.

Mark Lawrence.

[Andre Alexander Bell]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 06/18/2010 05:53 PM, Mark Lawrence wrote:
> Andre, looks like a really bad day for you then, *TWO* nights out with
> me *AND* (looking at your email address) Germany loosing in the world
> cup. :(

There are days one looses and there are days the others win... ;)

Andre

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkwckGYACgkQnuHMhboRh6QvDACfSAzSKvE90a9YY51ab2nksYd7
gOkAoNV5YvXLddtgeYBqqWFqGsB5fXlL
=w4uA
-----END PGP SIGNATURE-----

[Stefan Behnel]

Mark Lawrence, 18.06.2010 17:53:
> ... *AND* (looking at your email address) Germany loosing in the world
> cup. :(

Yep, we always do that once at the early stages of a world cup. Pretty good
camouflage, still works most of the time.

Stefan

[Mark Lawrence]

Yes, but trying to be fair the Spanish referee for your game was crap.
England had no excuses what so ever for their pathetic performance last
night, unless they were trying to emulate your camouflage. The only
good thing about it is that I have an excuse to go out and drown my
sorrows. :)

Mark.