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.



  1. Leave a comment

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: