Monday, October 30, 2006

What makes a good work environment? It's being part of a larger event...for an architect, putting your mark on inspiring spaces. Not big, not finely detailed, but a space that matches the present day, in both needs and in relevancy. I cringe when some brilliant programmer comes up with a puzzle to help weed out the competition. If one had the time to do this, they would probably be using their spare time on a paying side project, or consulting. It says nothing about the ability to function in the appropriate environment.

Computer Scientist/Programmer
Join a team of extraordinary engineers ....

Most applicants solve one of these puzzles. Unless otherwise specified, you may use any language you like. Aim for clarity and efficiency. Please include your program's final answer in the body of your email, and please send code that actually compiles and runs so we can test it -- no pseudo-code please!

Tour the T

Given a T timetable, write a program to compute the quickest route that passes through every station on the Red, Blue, Green, and Orange Lines, ending at Kendall Square.


Your program should compute a route that visits all T stations at least once. A station has been visited if you stop there (to change to a different line) or pass through on a train. You may start at any station.

The supplied T timetable contains the definitive list of all T stations and the travel time between them. All trains in the timetable should be assumed to run in both directions. Assume that the expected wait time for a train at a given station is fixed:

* Red Line - 5 minutes
* Blue Line - 4 minutes
* Green Line - 3 minutes
* Orange Line - 2 minutes

For example, if part of your route includes changing from the Green Line to the Red Line at Park Street, you should assume that you will wait 5 minutes for the Red Line train to show up. You should also assume that the wait time is the same for all trains (e.g. you will wait 5 minutes for the Red Line to Braintree, Ashmont, or Alewife).

At the end of the line, you must get off the train and wait the appropriate amount of time for a train going in the opposite direction.

Include in your answer the total time to visit all stations, plus enough information to verify your solution. Sample output for a (suboptimal) route starting at Kendall Square might look like:

0:00:00: Arrive Kendall/MIT
0:05:00: Board Red Line Braintree
0:07:00: Arrive Charles/MGH
0:09:00: Arrive Park St
0:12:00: Board Green Line B
0:14:00: Arrive Government Center
0:17:00: Board Green Line B

Of course, your code should not be in any way specific to the Boston subway topology, but generalize easily to other data files, representing, say, the New York subway.

So, if one must go to the big G - what's wrong with being in management, or in administration? Nothing that I can tell.