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]

Re: Python Programming Contest

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]

Re: Python Programming Contest



Brian Quinlan wrote:[color=blue]
> 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[/color]

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]

Re: Python Programming Contest

James wrote:[color=blue]
> 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.[/color]

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]

Re: Python Programming Contest

Brian Quinlan enlightened us with:[color=blue]
> Also, it is easiest to protect my system against malicious code if
> it is being run on an OS without a writeable filesystem.[/color]

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]

Re: Python Programming Contest

Brian Quinlan wrote:
[color=blue]
> I've decided that it would be be fun to host a weekly Python programming
> contest.[/color]

I like the idea, and doing the first problem was fun indeed
:o)
[color=blue]
> I'm always looking for feedback, so let me know what you think or if you
> have any ideas for future problems.[/color]

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]

Re: Python Programming Contest

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

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(123 4567891)
params = []
for i in xrange(100):
schedule = fly_test.genera te_schedule()
from_, to = fly_test.pick_c ities(schedule)
params.append( (from_, to, schedule) )
"""

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

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

[Brian Quinlan]

Re: Python Programming Contest

Raymond Hettinger wrote:[color=blue]
> 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?[/color]

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]

Python Programming Contest: First results

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ä]

Re: Python Programming Contest: First results

Brian Quinlan wrote:[color=blue]
> 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[/color]

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]

Re: Python Programming Contest: First results

Tomi Kyöstilä wrote:[color=blue]
> 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.[/color]

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.
[color=blue]
> 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.[/color]

This is the time required to do several thousand trials.

Cheers,
Brian

[Brian Quinlan]

Re: Python Programming Contest: First results

Brian Quinlan wrote:[color=blue]
> 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.[/color]

Your solution is now included. See:

http://www.sweetapp.com/pycontest/contest1/results.html

Good job!

Cheers,
Brian

[Tomi Kyöstilä]

Re: Python Programming Contest: First results

Brian Quinlan wrote:[color=blue]
> Brian Quinlan wrote:
>[color=green]
>> 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.[/color]
>
>
> Your solution is now included. See:
> http://www.sweetapp.com/pycontest/contest1/results.html
>
> Good job!
>
> Cheers,
> Brian[/color]

Thanks! :)

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

--
dOb

[Brian Quinlan]

Re: Python Programming Contest: First results

Tomi Kyöstilä wrote:[color=blue]
> Any idea when the next competition is coming? (it hasn't been quite
> weekly as you hoped, eh? ;)[/color]

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