Remember the bridge of the four programmers? An interesting technical interview problem, with an unexpected answer. It turns out there is more complexity in this problem than I had thought. Yay! Here's the problem again, to refresh your memory...
I received an interesting email from Ben Webman (now
I like it! In the original solution, there was an assumption that the beam did not carry at all, and hence each programmer had to go all the way to the other side with the flashlight. In Ben's version, the flashlight's beam carries all the way, and there's no need to go back with it. Intermediate versions are possible, for additional complexity. For example, let's assume the flashlight beam Let's first see what this does to our original solution. Here it is (changes in red):
So the total time is reduced from 15 minutes to 12½ minutes. That's pretty good. However, I'm not sure this is really optimal. I'm troubled by the fact that the Francis + Pat trip is not shortened at all by consideration of the beam carry, because this is the longest single component of the whole operation. Perhaps there is a way to optimize further? Anyone have any good ideas? [ |
Home Greatest Hits |