In the conference season, developers face the perennial problem of getting from one hotel to another to meet colleagues. How good is your ability to write procedures to find shortest distance in a city block setting. Let's look at how the team at International Storm Door & Software set out the problem of Taxicab Geometry.
If you've not already met experienced developer Melvin Frammis and his junior programmer sidekick, Bugsy Cottman you'll find they were initially introduced in the Elevator Puzzle, the first in the series of Sharpen Your Coding Skills and they have posed us further challenges ever since.
Bugsy Cottman, junior programmer at International Storm door and Software, was looking at a map on his screen when his team leader Melvin Frammis came to his cubicle.
“How is our trip planning coming?” asked Melvin.
“Not too bad. The downtown conference area is a square grid, so even Fred will not be able to get lost. We can walk or take a taxi to get to where we need to be for trade show.” replied Bugsy without looking up. “We are going to be all over the place! When KludgeCon is in town, you get a hotel room wherever you can. Here is the map I made of our hotels.”
Bugsy rolled up from his screen so the rest of the guys could see his map.
“I named each hotel a letter and turned the streets into an standard Cartesian grid, to make the math easier than street names.” said Bugsy.
“Math?” asked Fred. “To figure out trips or what?”
“Oh yeah!” said Alice Jones. “Every KludgeCon we have to figure out how to accommodate a list of demands. I have a few of them collected together”
“Fred, how good is your geometry?” said Melvin, smiling.
“We need someone to do that math for all the stupid requests from our attendees. It is not enough to tell them what you discovered, you have to prove it. But you cannot use good old Euclidean geometry; you have to use taxicab geometry!”
Fred looked puzzled, so Melvin continued:
“Imagine that you are in a taxi and want to get from point (x1 , y1) to (x2, y2), how would you compute the distance?”
“Easy, high school math:
d = √ ((x1 - x2)2+(y1- y2)2).”
Melvin smiled and said:
“Not in a taxi! Assume you start at the center of town (0,0) and want to get to the Chez Vermin Hotel up her at (3,4), how far do you have to travel? Your Euclidean formula gives us five blocks; but look at the map. You go three block east then four blocks north for a total of seven blocks in the taxi. He cannot fly, so he has to drive through the streets. The shortest distance is seven blocks in Taxicab geometry.”
“But that means there are many ways to walk between two points. I could walk three block east then four blocks north; four blocks north then three block east; there are all kinds of zig-zags, but as long as the total number of blocks north is three and the total number of blocks east is four.” Fred caught on pretty fast!
Before you get your list of problems, let's invent some notations that we can turn into programs. Use uppercase letters for point (hotel) names
A= (x1, y1), B=(x2, y2)
De (A, B) = Euclidean Distance = d = √ ((x1 - x2)2+(y1- y2)2)