I've decided to try hosting a weekly Python programming contest.
For now, I'll be judging solutions first by correctness and then by speed. I'd prefer to judge on some other criterion, such as elegance, but it is hard to do so objectively. But I will provide my unofficial, non-objective judgement of the best design too.
At the end of the contest, I'll run benchmarks and post the results, along with all the submitted solutions, on my website. I'll also write a summary for the Python list
I'm going to start small and any feedback would be very welcome (Brian Quinlan <brian@sweetapp.com>)! Now onto the first problem...
This problem is an adaptation of the real-life problem: how to fly from A to B with the minimum possible cost. Since I am incredibly cheap, I am willing to take several flights to get to my final destination. I'm more far more concerned with money than with prompt arrival, so the complete trip can take an arbitrary amount of time.
Your task is to write a scheduling module that generates the cheapest possible route from A to B.
The solution requires a bit of thinking but not much code (my solution is 40 lines of code, including comments).
>>> from fly import fly
>>> schedule = [
... # (from, to) : cost
... {('A', 'B') : 100.00, ('A', 'C') : 10.00, ('C', 'B') : 20}, # Day 1
... {('A', 'B') : 100.00, ('A', 'C') : 10.00, ('C', 'B') : 20}] # Day 2
>>> # Calculate the optimal route to fly from A to B. The route should be:
>>> # Day 1: A => C (cost 20)
>>> # Day 2: C => B (cost 20)
>>> fly('A', 'B', schedule)
['C', 'B']
>>> schedule = [
... # From # To # Cost
... {('Athens', 'Berlin') : 55.25, # Day 1 flights
... ('Berlin', 'Athens') : 73.00,
... ('Dresden', 'Athens') : 85.50,
... ('Dresden', 'Berlin') : 12.50},
... {('Berlin', 'Athens') : 23.55, # Day 2 flights
... ('Berlin', 'Cairo') : 125.15,
... ('Berlin', 'Dresden') : 18.25,
... ('Dresden', 'Athens') : 85.50,
... ('Dresden', 'Berlin') : 13.50},
... {('Athens', 'Cairo') : 65.55, # Day 3 flights
... ('Berlin', 'Athens') : 23.55,
... ('Berlin', 'Cairo') : 125.15,
... ('Dresden', 'Athens') : 85.50},
... {('Athens', 'Cairo') : 7.25, # Day 4 flights
... ('Berlin', 'Athens') : 23.55,
... ('Dresden', 'Athens') : 85.50}]
>>> # Calculate the optimal route to fly from Dresden to Cairo.
>>> # The route should be:
>>> # Day 1: Dresden => Berlin (cost 12.50)
>>> # Day 2: Berlin => Athens (cost 23.55)
>>> # Day 3: Athens (stay the day: fixed cost of 20)
>>> # Day 4: Athens => Cairo (cost 7.25)
>>> # If you think that this route is absurd, let me assure
>>> # you that I am actually flying it (including the night in
>>> # Athens) in October
>>> fly('Dresden', 'Cairo', schedule)
['Berlin', 'Athens', 'Athens', 'Cairo']
>>> # There is now way to get from Cairo to Dresden
>>> fly('Cairo', 'Dresden', schedule)
Traceback (most recent call last):
...
ValueError
You can download a stub version of the fly module along with a simple test suite here.
The solution deadline is July 24, 2005. When you are done your implementation, please send it to me at Brian Quinlan <brian@sweetapp.com>.
I'm going to test all of the submissions using the test suite that you can find as part of test framework. I will pick a random seed so everyone's tests are identical (I'm a very fair person).
The exact test environment will be: