Re: Python Programming Contest: First results
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest: First results
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest: First results
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest: First results
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest: First results
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
ThanhNam Nguyen wrote: Since my NNTP server doesnt allow posting, I'll ask you directly instead. Must I start from the first day? No. For example: 1st day: A -- B 100 bucks 2nd day: A -- B 60 bucks 3rd day: A -- B 40 bucks What would the solution be? And for how much in total? There are two correct solutions: [A, B] # spend one night in A, then fly to B on day two (cost 80) [A, A, B] # spend two nights in A, then fly to B on day two (cost 80) Cheers, Brian -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
ThanhNam Nguyen wrote: 1st day: A -- B 100 bucks 2nd day: A -- B 60 bucks 3rd day: A -- B 40 bucks What would the solution be? And for how much in total? There are two correct solutions: [A, B] # spend one night in A, then fly to B on day two (cost 80) [A, A, B] # spend two nights in A, then fly to B on day two (cost 80) They all mean I must start from the first day. The best solution would be, I fly from A to B for 40 bucks on day 3, assuming I live in the current city A. Then you should assume that you don't live in city A, because the actual cost in this case is 80. Cheers, Brian -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
[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)) -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
* Brian Quinlan [EMAIL PROTECTED] [2005-07-15 02:08]: You can find the first problem here: http://www.sweetapp.com/pycontest/contest1 I have one question about the problem. Is the cost we are to minimize the cost of arriving in the target city at all, or the cost of arriving at the target city at the end of the final day of the schedule? (If you were traveling to a conference, for example, you'd have a specific arrival time, and a cost to stay in the destination city until that time. But, if you were going to sight-see, then you could arrive at any time, and begin your itinerary upon arrival.) Say I can find a combination of flights that gets me to the target at the end of day 3 for 390 units, and a combination that gets me there at the end of day 4 for 400. If you count the hostel cost from day 3 to day 4, the first combination costs 410. So, which is preferred? -John P.S. I just realized this may be answered be the test suite, but I'm still at the thinking stage. -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
John Hazen wrote: * Brian Quinlan [EMAIL PROTECTED] [2005-07-15 02:08]: You can find the first problem here: http://www.sweetapp.com/pycontest/contest1 I have one question about the problem. Is the cost we are to minimize the cost of arriving in the target city at all, or the cost of arriving at the target city at the end of the final day of the schedule? (If you were traveling to a conference, for example, you'd have a specific arrival time, and a cost to stay in the destination city until that time. But, if you were going to sight-see, then you could arrive at any time, and begin your itinerary upon arrival.) Say I can find a combination of flights that gets me to the target at the end of day 3 for 390 units, and a combination that gets me there at the end of day 4 for 400. If you count the hostel cost from day 3 to day 4, the first combination costs 410. So, which is preferred? -John P.S. I just realized this may be answered be the test suite, but I'm still at the thinking stage. What we really need is a problem *specification* contest. -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
Someone correct me if I'm wrong -- but isn't this the Shortest Path problem? I don't foresee anyone getting a more efficient solution than what they can find in hundreds of algorithms textbooks. If this is indeed the case it should just come down to whoever can pull the narliest tricks to create a fast python implementation of the algorithm. 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
On Sat, 16 Jul 2005, Joseph Garvin wrote: Someone correct me if I'm wrong -- but isn't this the Shortest Path problem? Dang! I was just about to point that out. I don't foresee anyone getting a more efficient solution than what they can find in hundreds of algorithms textbooks. If this is indeed the case it should just come down to whoever can pull the narliest tricks to create a fast python implementation of the algorithm. I guess part of the challenge is seeing through the description to the underlying problem - in this case, seeing that this can be cast as shortest-path. Not everyone would necessarily realise that! In particular, the fact that the available flights, and their prices, can be different on different days could well throw people. But yes, this is basically about who can write the fastest implementation of Dijkstra's algorithm. I've got one somewhere - i have a half-finished journey planner for the London Underground! - so maybe i should enter ... Hmm. Actually, Dijkstra's algorithm isn't always the fastest way to find the shortest path. The thing is, it's fully general, so it works on absolutely any graph; if the graph you're traversing has particular properties, you might be able to leverage those to find a solution faster. For instance, if your graph is a road network, you can put a lower bound on the distance from any vertex to the goal (being the straight-line distance between them - no path over actual roads can be any shorter than that), which allows you to do an A* search, which is a lot faster than Dijkstra. My own journey planner is also a case of this - i exploit various obvious properties of tube trains to avoid examining a large number of possible but daft travel plans. I can't immediately see any properties of this network that could be exploited, but that doesn't mean there aren't any. tom -- taxidermy, high tide marks, sabotage, markets, folklore, subverting, . -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
Tom Anderson [EMAIL PROTECTED] wrote: On Sat, 16 Jul 2005, Joseph Garvin wrote: Someone correct me if I'm wrong -- but isn't this the Shortest Path problem? Dang! I was just about to point that out. [snipped] But yes, this is basically about who can write the fastest implementation of Dijkstra's algorithm. I've got one somewhere - i have a half-finished journey planner for the London Underground! - so maybe i should enter ... Hmm. Actually, Dijkstra's algorithm isn't always the fastest way to find the shortest path. The thing is, it's fully general, so it works on absolutely any graph; if the graph you're traversing has particular properties, you might be able to leverage those to find a solution faster. [snipped] Yes, that's right. Moreover, Dijkstra's computes the shortest path from a given start to *all* nodes in the network, which is usually an overkill if all you want is the shortest path to one (or a few) node(s). I can't immediately see any properties of this network that could be exploited, but that doesn't mean there aren't any. Hints: - You have to take exactly one decision (flight or stop) every single day until you reach the destination; no more, no less. - There is no time machine; days pass in one direction only, one at a time. George -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
Terry Reedy [EMAIL PROTECTED] wrote: Tom Anderson [EMAIL PROTECTED] wrote: I can't immediately see any properties of this network that could be exploited, but that doesn't mean there aren't any. No it doesn't. The challenge is to find a property that saves more time, across trials, that it takes to compute. There could have been one if the schedule was fixed across trials. However, if you look into the test script, this is not the case; a new schedule is randomly generated every time. So any heavy preprocessing on the schedule is rather unlikely to pay off. George -- http://mail.python.org/mailman/listinfo/python-list
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
Brian I've decided that it would be be fun to host a weekly Python Brian programming contest. The focus will be on algorithms that require Brian a bit of thought to design but not much code to implement. For some of us that's what we do day-in, day-out at work. It's just not called a contest. To make it more challenging, we sometimes leave out the bit of thought part. ;-) Skip -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
[EMAIL PROTECTED] wrote: Brian I've decided that it would be be fun to host a weekly Python Brian programming contest. The focus will be on algorithms that require Brian a bit of thought to design but not much code to implement. For some of us that's what we do day-in, day-out at work. It's just not called a contest. To make it more challenging, we sometimes leave out the bit of thought part. ;-) Hmmm...I find that I am rarely faced with challenging algorithmic problems in my day-to-day work. I continuously face difficult design decisions but that is a difficult sort of beast all together. This contest is for people who like thinking about algorithms. Cheers, Brian -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
On 7/15/05, Brian Quinlan [EMAIL PROTECTED] wrote: [EMAIL PROTECTED] wrote: Brian I've decided that it would be be fun to host a weekly Python Brian programming contest. The focus will be on algorithms that require Brian a bit of thought to design but not much code to implement. For some of us that's what we do day-in, day-out at work. It's just not called a contest. To make it more challenging, we sometimes leave out the bit of thought part. ;-) Hmmm...I find that I am rarely faced with challenging algorithmic problems in my day-to-day work. I continuously face difficult design decisions but that is a difficult sort of beast all together. This contest is for people who like thinking about algorithms. Cheers, Brian -- http://mail.python.org/mailman/listinfo/python-list Questions: Will that random test generator (included in the download) be used to perform the actual testing? How many tests will be run on each program? What is the penalty for a wrong answer? Peace Bill Mill PS - check out http://www.sleepinginairports.net/ before you say you can't sleep in the airport :) -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
Bill Mill wrote: On 7/15/05, Brian Quinlan [EMAIL PROTECTED] wrote: [EMAIL PROTECTED] wrote: Brian I've decided that it would be be fun to host a weekly Python Brian programming contest. The focus will be on algorithms that require Brian a bit of thought to design but not much code to implement. For some of us that's what we do day-in, day-out at work. It's just not called a contest. To make it more challenging, we sometimes leave out the bit of thought part. ;-) Hmmm...I find that I am rarely faced with challenging algorithmic problems in my day-to-day work. I continuously face difficult design decisions but that is a difficult sort of beast all together. This contest is for people who like thinking about algorithms. Cheers, Brian -- http://mail.python.org/mailman/listinfo/python-list Questions: Will that random test generator (included in the download) be used to perform the actual testing? Yes. With two caveats: 1. I will pick the seed ahead of time so everyone gets the same problem set 2. I will use a local copy of the verification code (for performance reasons) How many tests will be run on each program? Probably a few thousand. If I need more to discriminate between two very similar solutions, then I will do so. What is the penalty for a wrong answer? Infinite. Only correct solutions will be judged on performance. PS - check out http://www.sleepinginairports.net/ before you say you can't sleep in the airport :) Nice :-) Cheers, Brian -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
Brian This contest is for people who like thinking about algorithms. Surely you must have missed the smiley... S -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
[EMAIL PROTECTED] wrote: Brian This contest is for people who like thinking about algorithms. Surely you must have missed the smiley... No, I saw it but it just confused me as I have no sense of humor. Cheers, Brian -- http://mail.python.org/mailman/listinfo/python-list
Re: Python Programming Contest
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 -- http://mail.python.org/mailman/listinfo/python-list
