Python Programming Contest

[Brian Quinlan]

I've decided that it would be be fun to host a weekly Python programming
contest. The focus will be on algorithms that require a bit of thought
to design but not much code to implement.

I'm doing to judge the solutions based on execution speed. It sucks but
that is the easiest important consideration to objectively measure. I'll
also indicated which solutions I think are good examples of Python
design. Hopefully, people's solutions can provide a resource for people
looking for best practice examples and also for people looking for
performance ideas.

You can find the first problem here:
http://www.sweetapp.com/pycontest/contest1

I'm always looking for feedback, so let me know what you think or if you
have any ideas for future problems.

Cheers,
Brian

[Simon Dahlbacka]

Are you aware of http://mathschallenge.net/index.php?section=project ?

The "The focus will be on algorithms that require a bit of thought
to design but not much code to implement." part seems common, although
your problem domain probably is larger.

/Simon

[James]

Brian Quinlan wrote:

I've decided that it would be be fun to host a weekly Python programming
contest. The focus will be on algorithms that require a bit of thought
to design but not much code to implement.

I'm doing to judge the solutions based on execution speed. It sucks but
that is the easiest important consideration to objectively measure. I'll
also indicated which solutions I think are good examples of Python
design. Hopefully, people's solutions can provide a resource for people
looking for best practice examples and also for people looking for
performance ideas.

You can find the first problem here:
http://www.sweetapp.com/pycontest/contest1

I'm always looking for feedback, so let me know what you think or if you
have any ideas for future problems.

Cheers,
Brian

I am not sure if it is a good idea to use a LiveCD for OS when you are
testing for speed. CD access speeds fluctuate and may even impact
performance even if you start measuring after the module loading is
complete.

[Brian Quinlan]

James wrote:

I am not sure if it is a good idea to use a LiveCD for OS when you are
testing for speed. CD access speeds fluctuate and may even impact
performance even if you start measuring after the module loading is
complete.

It didn't seem to matter in my testing. Module loading is done before
the test is run. Also, it is easiest to protect my system against
malicious code if it is being run on an OS without a writeable filesystem.

Cheers,
Brian

[Sybren Stuvel]

Brian Quinlan enlightened us with:

Also, it is easiest to protect my system against malicious code if
it is being run on an OS without a writeable filesystem.

Even easier with User Mode Linux and a COW (copy on write) filesystem.

Sybren
--
The problem with the world is stupidity. Not saying there should be a
capital punishment for stupidity, but why don't we just take the
safety labels off of everything and let the problem solve itself?
Frank Zappa

[Thomas Lotze]

Brian Quinlan wrote:

I've decided that it would be be fun to host a weekly Python programming
contest.
I like the idea, and doing the first problem was fun indeed
:o)
I'm always looking for feedback, so let me know what you think or if you
have any ideas for future problems.

It would be nice if you could put up a suite of test data with oracle
solutions for download. For those sitting behind a modem line (like me),
it would be a great help and speed up of the testing cycle.

Thanks for your effort, in any case!

--
Thomas

[Raymond Hettinger]

[Brian Quinlan]

I'm doing to judge the solutions based on execution speed. It sucks but
that is the easiest important consideration to objectively measure. . . . I'm always looking for feedback, so let me know what you think or if you
have any ideas for future problems.

I'm curious about the stability of your timing setup. If you run your
own version of fly.py several times with the same starting seed, how
much variation do you see between runs?

When I tried the provided setup, it was highly variable. To get useful
measurements, I needed another timing framework:

import timeit

setup = """
import fly_test
import random

from fly import fly
random.seed(1234567891)
params = []
for i in xrange(100):
schedule = fly_test.generate_schedule()
from_, to = fly_test.pick_cities(schedule)
params.append( (from_, to, schedule) )
"""

stmt = """
for p in params:
fly(*p)
"""

print min(timeit.Timer(stmt, setup).repeat(5, 3))

[Brian Quinlan]

Raymond Hettinger wrote:

I'm curious about the stability of your timing setup. If you run your
own version of fly.py several times with the same starting seed, how
much variation do you see between runs?

There is very little variation (about 0.1%) but my solution is over an
order of magnitude slower than some of the submissions that I've gotten.
It is likely that the overhead of my timing code is significant when
running your solution.

I may have to *slightly* revise my test code to get better results. I
think that I can do so without changing the distribution of the random
schedule so as not to be biased against some solutions.

Cheers,
Brian

[Brian Quinlan]

Here are the results for the first problem in the Python Programming
Contest.

I haven't been able to find as much time as I excepted, so my analysis
is not very in depth.

You can find the results here:
http://www.sweetapp.com/pycontest/contest1/results.html

And the problem definition here:
http://www.sweetapp.com/pycontest/contest1/

Kudos to everyone who participated but especially to Raymond Hettinger
and Thomas Lotze, whose solutions were nearly 50 times faster than mine.

I'd also like to point out that Thomas Guettler's solution, which is the
slowest, was completed in less than 3 hours after the contest was
announced. That's impresive for a correct solution.

Cheers,
Brian

[Tomi Kyöstilä]

Brian Quinlan wrote:

Here are the results for the first problem in the Python Programming
Contest.

I haven't been able to find as much time as I excepted, so my analysis
is not very in depth.

You can find the results here:
http://www.sweetapp.com/pycontest/contest1/results.html

And the problem definition here:
http://www.sweetapp.com/pycontest/contest1/

Kudos to everyone who participated but especially to Raymond Hettinger
and Thomas Lotze, whose solutions were nearly 50 times faster than mine.

I'd also like to point out that Thomas Guettler's solution, which is the
slowest, was completed in less than 3 hours after the contest was
announced. That's impresive for a correct solution.

Cheers,
Brian

Why don't I see my solution (__author__ = "dOb") in the results? I'm
sure that you got it as you replied to my mail.

Where do the timing results come from? Is it the number that
fly_test.main(['fly']) outputs? I don't think it is that because with my
solution that would be ~0.06 seconds.

Great competition anyway, I want to see more of these :)

--
dOb

[Brian Quinlan]

Tomi Kyöstilä wrote:

Why don't I see my solution (__author__ = "dOb") in the results? I'm
sure that you got it as you replied to my mail.
Ahhh...sorry. I have your solution and I timed it but I don't have the
results here so I can't add it to the website. I'll do it tomorrow.
Where do the timing results come from? Is it the number that
fly_test.main(['fly']) outputs? I don't think it is that because with my
solution that would be ~0.06 seconds.

This is the time required to do several thousand trials.

Cheers,
Brian

[Brian Quinlan]

Brian Quinlan wrote:

Tomi Kyöstilä wrote:

Why don't I see my solution (__author__ = "dOb") in the results? I'm
sure that you got it as you replied to my mail.

Your solution is now included. See:
http://www.sweetapp.com/pycontest/contest1/results.html

Good job!

Cheers,
Brian

[Tomi Kyöstilä]

Brian Quinlan wrote:

Brian Quinlan wrote:

Tomi Kyöstilä wrote:

Why don't I see my solution (__author__ = "dOb") in the results? I'm
sure that you got it as you replied to my mail.

Your solution is now included. See:
http://www.sweetapp.com/pycontest/contest1/results.html

Good job!

Cheers,
Brian

Thanks! :)

Any idea when the next competition is coming? (it hasn't been quite
weekly as you hoped, eh? ;)

--
dOb

[Brian Quinlan]

Tomi Kyöstilä wrote:

Any idea when the next competition is coming? (it hasn't been quite
weekly as you hoped, eh? ;)

Uh no. It turns out that I have less time than I thought, though a big
chunk of it should be freed-up after this weekend. I do have an idea... :-)

Cheers,
Brian