July 31, 2003
And a little more Graham...

Furthermore: If you're bored with the daily grind of your object oriented programming job, there's also a fun read on what it takes to solve problems that are actually interesting.

The problem is airline route optimisation, not for the airline but for you, the lowly customer:

If you want to do a simple round-trip from BOS to LAX in two weeks, coming back in three, willing to entertain a 24 hour departure window for both parts, then limiting to "reasonable" routes (at most 3 flights and at most 10 hours or so) you have about 5,000 ways to get there and 5,000 ways to get back. Listing them is a mostly trivial graph-search [...] The real challenge is that a single fixed itinerary (a fixed set of flights from BOS to LAX and a fixed set back) with only two flights in each direction may have more than 10,000 possible combinations of applicable "fares", each fare with complex restrictions that must be checked against the flights and the other fares. That means that the search space for this simple trip is of the order 5000 x 5000 x 10000, and a naive program would need to do a _lot_ of computation just to validate each of these possibilities.

That is SO cool...

What's even cooler is that the company that makes this stuff only accepts programmer job applications in the form of actual running code to solve famous algorithmic problems. No "Must know Java, must have 20 years experience, must be 25 years old" there.

Some more company info

Posted by Claus at July 31, 2003 03:32 AM | TrackBack (0)
Comments (post your own)
Help the campaign to stomp out Warnock's Dilemma. Post a comment.

Email Address:


Type the characters you see in the picture above.

(note to spammers: Comments are audited as well. Your spam will never make it onto my weblog, no need to automate against this form)


Remember info?