For this 12-point project, you will help me out with an authentic trip-planning problem. As the weather has turned cooler, my wife and I have recalled how much we enjoyed a trip to Austin, Texas, a few years ago, and have talked about going back. Last time we flew, but this time the idea of driving has come up. The only problem is that we don't drive anywhere near that far in a day, so we need to pick some spots for overnight stays. That's where you come in. You can write a program to pick hotels so as to minimize the total cost, subject to a limit on how many miles we drive in a day.
Using the web site of a national hotel chain, I put together a list of hotels along the route. For each one, I've got the name, distance from our starting point, and advertised room rate (price). This is real data from the web but reflects just a snapshot; your algorithm ought to survive if the data changes. I rounded both the distances and the room rates to integers. Here's how the list starts:
hotels=[('Super 8 Mankato', 10, 47),
('Days Inn Mankato', 10, 49),
('Microtel Inn & Suites Mankato', 10, 65),
...]
You might laugh at my having included Mankato hotels in the list; even my wife and I normally drive further than that in a day. In part, this just reflects my having produced the list in a systematic, computerized fashion. But in fact, depending on how the list continues, the Super 8 in Mankato might be part of an optimal solution, even if our driving allowance per day is more than 10 miles. You ought to be able to construct examples showing that just about any "greedy" strategy sometimes fails:
Sometimes it makes sense to pass by an inexpensive hotel.
Sometimes it makes sense to stop for the night even if further hotels exist within your daily mileage allowance.
Sometimes it makes sense to include more hotel stops than the minimum.
There is at least one heuristic that could safely be used to prune obviously bad options. It never makes sense to stop at a hotel if the hotel's cost is nonnegative and another one further along, but still within your day's limit, has at least as low of a room rate. As it turns out, for the data I gathered, this is a very powerful heuristic. It eliminates enough choices that the remaining ones can be searched using a brute force algorithm. However, I don't want you using this approach, because if the hotels change their prices, the heuristic might become much less effective. You ought to be able to construct an example where no pruning at all would be achieved. And without pruning, you sure don't want to use brute force. There are 83 hotels on my list, which leads to 283 possibilities for stopping or not stopping at each one.
You'll notice I mentioned nonnegativity of cost in the prior paragraph. Naturally enough, all of the hotels listed on the web site did indeed list nonnegative room rates. Nonetheless, it would be best if your code avoided assuming this constraint. That way, if there are places that Stefanie and I particularly are interested in staying, we can tweak the cost of those hotels downward, even to the point of a negative cost if we really want to stay there.
Your goal is to write a trip procedure in Python that produces an optimal plan for the trip. The optimal plan is a pair of two things: a total price and a list of hotels. Each of the hotels is one of the triples taken from the list I provide. Here's the heading for your procedure:
def trip(hotels, allowance):
"""Return a trip plan, staying within an allowance of miles per day.
A plan is a pair of a total cost (sum of room rates) and a list of hotels.
Each hotel is a triple of name, distance from the start, and room rate.
The given list of hotels must be listed in nondecreasing distance.
The last 'hotel' on the list is actually the ultimate trip destination
and must be included in any plan; its room rate might be 0.
All mileages must be integers: hotel distances and the allowance.
If no plan is feasible, the procedure raises a ValueError."""
I've linked to this assignment a hotels.py file that contains this procedure header and the full version of the hotels list. To receive full credit, you need to create a correct version of the trip procedure using either the memoized top-down approach or the bottom-up dynamic programming approach. You don't have to wring every last bit of efficiency out of your procedure, but it should scale up polynomially in the length of the hotels list and the number of miles in my allowance. Exponential growth is bad. You should quickly get answers for the full hotels list and any allowance, whether 80 miles, 1000 miles, or anything in between. (The 80 mile figure is just barely large enough to make the trip feasible, given the spacing of the hotels.)
If you are having trouble getting started, I can offer you various shortcuts, each of which cuts into the numbers of points you can earn. Each of these shortcuts starts with me providing you a recursive top-down version that gives correct answers for smaller lists of hotels, but takes unreasonably long for the full trip to Austin.
If you take the recursive version from me and then write a correct bottom-up version, you'll earn 11 of the 12 points.
If you take the recursive version from me and are stuck writing a bottom-up version, you can ask me for a template for that version, in which I create the necessary table, provide a comment explaining what each slot in the table ought to contain, and return the appropriate slot from the table at the end. Your code would fill in the table. If you do that much, you'll earn 10 of the 12 points.
If even the template isn't enough to get the bottom-up approach working, you can fall back on the memoized top-down approach, which is closer to the recursive version I provide. However, then you'll only earn 9 of the 12 points.
Note in particular that if you don't take the recursive version from me, you'll be able to earn the full 12 points even with a memoized top-down approach.