A couple months back, I got to interview Georgia Tech mathematician William Cook – an expert on the venerable Traveling Salesman Problem. He looks at the problem from an interesting angle: Instead of trying to find the shortest tour, he tries to calculate the probability that a generated tour is, say, within 5 percent of optimal. And by playing with the numbers, he knows how you should pick up tennis balls on a court or plan your route between fifteen errands.
Basically, if you always go to the nearest point (and continue until you've hit them all), you'll always be within 25 percent of the shortest tour. And if you then "uncross" any places where your route intersects itself, you'll be within 10 percent of optimal. There's some serious computational firepower behind that, and you certainly don't want to see it here.
Santa would do well to heed good Mr. Cook's words for the jolly old elf's stops are many and his time is tight.
For the purposes of this week's puzzle, not only did you have to find the shortest tour, but you had to guide Santa along this shortest path using the Logo language. This required getting intimate with Pythagoras (and maybe a little bit o' basic Trig).
So, mad props to this week's winner of the $50 ThinkGeek gift certificate (and all the correct entrants!), Otto, who actually turned the turtle to travel across the hypotenuse of each needed triangle instead of just driving the turtle at 90-degree angles along the lines. The rest of you can use the code GEEKDAD21FK to get $10 off an order of $50.
Tune in on Monday, when Dave G drops another installment of the puzzle – and your last chance to score $50 at ThinkGeek before the holiday.
