| Taxicab Geometry Problems |
| Written by Joe Celko |
|
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. If you want to send in solutions either use the Comments section or email editor@i-programmer.info.
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: “Easy, high school math: d = √ ((x1 - x2)2+(y1- y2)2).” said Fred. 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) Dt (A, B) = Taxicab Distance = (|x1 - x2| + |y1 – y2|). You might want to convince yourself that Dt (A, A) = 0 Dt (A, B) = Dt (B, A)
Problem One:Albert needs to walk up to Bert's hotel each day of the conference. How many different shortest paths are there for him to use? We want a general formula so we do not have to do this again next year.
Problem Two:The Marketing team wants to be on the perimeter of a circle centered on the Pink Pony strip joint at P= (a,b) so they can all have the same travel distance to it. The definition of a circle in Taxicab geometry is that all points (hotels) in the set are the same distance from the center. Just like a Euclidean circle, but with a finite number of points! circle = { X: Dt (X, P) = k } k is the radius, P is the center For set of n marketing guys, what is the radius? Hint: if we send one salesman, he can stay at the Pink Pony the whole conference, if we send eight guys, they can stay two blocks away. Problem Three:A taxicab square is defined like a Euclidean square. Given four points,{P, Q, R, S} we can draw lines of the same length to make the four sides of the square: Dt (P, Q) = Dt (Q, R) = Dt (R, S) = Dt (S, P). But a square is hollow inside; no crossed lines! Write a procedure to find all of the squares in a set of points. Hint: {P =(0,0), Q =(0,6), R =(3,3), S =(0,6)} is a square, but it does not look like it on the grid! Bonus Problem:Given a set of points, draw a Euclidean polygon on the grid using them as corners. Points can be inside the polygon, outside the polygon or on the boundary. What is the area enclosed by this polygon?
Joe Celko is best known as the database expert who writes books on SQL, data and databases. But before that, he was an honest developer obsessed with finding good algorithms and clean code. More Joe Celko puzzles tackled by Melvin, Bugsy & CoSharpen your Coding Skills - Elevator Puzzle Programmer Puzzle - Hermit Boxes Jigsaw Puzzles and The MacMahon Squares Vertex Coverings And The Cool Kids Problem To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
Comments
or email your comment to: comments@i-programmer.info
|
