The Amazing Race: Optimization

So the thing that’s been keeping me busy is Dragon Age: Origins math. Well, okay, Dragon Age too; these past two weeks I must have spent around 60 hours or so with it, and that’s more than I usually play in a month, regularly. It’s really quite something, even for a game that’s two years old (thank you, bargain pick-ups). But really, that’s for another time. Today it was mostly math.

Problem sets, eh? What’s up with thaaat? /seinfeld

(By the way, there is literally no reason you darned whippersnappers in attendance should know what that references)

I spent about four hours working on my problem set today. Not a lot of time, maybe, but considering that’s an entire week’s worth of work for me (on the good weeks), that’s quite a large chunk. Only to realize at the end I’d basically wrote a lot of unnecessary, incorrect things on my sheets of paper, which is really quite frustrating. So it took me another two hours to do a rewrite, which I just finished.

So I figure, hey, I spent all that time on it. Might as well talk about it, hm?

The Problem, basically, is finding… let’s say the cheapest flight from here (the Philippines) to, I don’t know, the USA (let’s say Oklahoma City). So you can go the direct flight, sure, but that’s not always the cheapest way to go. Maybe it’s cheaper to go by Guam first, or Hawaii, right? Each flight’s cost is given, and at most, it’s going to be ten flights (or nine stops) you can take. Think about it, though; that’s a lot of flights.

Solving that in itself isn’t really that hard, if you know how to do so. Just start with the destination and work your way backward. For example, from Oklahoma City to, say, Chicago, there’s only one flight. Then from Oklahoma city to California, you can either stop by Chicago first and then head to California, or go straight to California from OKC; just pick whichever’s cheaper. Then just work your way to the Philippines one stop at a time. On the whole, if you’re doing it right, you should only be considering 55 flights at most. The real Problem is this: what if you’ve got a couple of coupons at your disposal?

If you answered “Why, just take whatever you found without the coupons, then use them at the most expensive flights!”, you’d be wrong. Discounts let you “cheat” the method by taking some of the more expensive, yet quicker, flights. So given any path you just need to apply the larger discount to the most expensive flight, and the other to the second most expensive flight.

But that’s, in practice, quite a bit of work. To solve this, you actually need to concoct two preliminary scenarios: one where you only have one coupon, and another where you only have, well, the other one. Then, with that data in hand, you can solve the case where you have both. In the case with ten flights, two coupons actually has you looking at 220 flights (for a complete system). Again, that’s a lot of flights. But that’s still less than what you get when you list down all your options: for any single case, there are 512 flight paths from the Philippines to OKC.

Quick aside, here: there’s actually a really simple way to obtain the number of possible flights. If you have ten flights, you have at most nine stops in between your origin and your destination. For each stop, you either stop there, or you don’t. So that’s just 2^9 = 512.

Math at work, people. Math at work.

Moving forward, there are four cases (no coupons, only the larger, only the smaller, and both), so that’s 512 x 4 = 2048 options. Now, aren’t you glad you didn’t write them all down? That would take all day!

Actually, thinking about it now, I’m pretty glad there wasn’t an exorbitant amount of flights and coupons. If you add just one more coupon and one more flight, which doesn’t really sound like much, you’re looking at 528 flights; a 140% increase in workload. So in the end I guess I got off pretty easy there.

Yeah, let’s go with that. Move along folks, nothing to see here. I got me some salesmen to assign.