Euler 71

I finished Euler 71. It was a relatively painless problem which, for my approach at least, involved reducing a search space through a little analysis to get a performant solution. I haven’t read the discussion yet, so there may well be better approaches than mine, but I’m solving it in a few seconds.

One noteworthy result of this problem was the difference between using range and xrange in python. The basic difference between the two, of course, is that range returns a list and xrange returns a generator. The documentation for xrange says:

For looping, this is slightly faster than range() and more memory efficient.

At least in the case of this problem, there was no “slightly” about it; a rough eyeballs-and-wristwatch calculation shows xrange with a 50x improvement. My solution involves, at the core, looping over a growing sequence of numbers 1 million times, but I never need any more than one element of a sequence in memory at a time. Hence, this is a perfect fit for a generator and, in the end, really demonstrates the utility the generator concept.

Advertisements

,

  1. Leave a comment

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: