| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1430.1 | | BUSY::SLAB | As you wish | Mon Jan 27 1997 13:54 | 5 |
|
Max is 17 blocks.
|
| 1430.2 | Senic route in .1? | CHEFS::STRANGEWAYS | Andy Strangeways@REO DTN 830-3216 | Tue Jan 28 1997 04:35 | 16 |
| Re .1:
Why 17? Another suggestion follows form feed.
I'd say go left on Apple. Walk 1 block. If you've reached Baker, you've
guessed right. If not, walk back to the subway station and carry on.
You'll reach Baker after 1 block. Total walked: 3 blocks so far. Now go
left on Baker, walk 1 block. If you're at Charlie, carry on. Otherwise
go back, across Apple, and carry on another block. You'll be at
Charlie. Total walked: 6 blocks so far. Go left on Charlie, walk 1
block. If you've arrived, good. Otherwise go back, across Baker, and
carry on another block. You'll be there.
Total walked (worst case): 9 blocks.
Andy.
|
| 1430.3 | | BUSY::SLAB | As you wish | Tue Jan 28 1997 11:35 | 21 |
|
RE: .2
Well, I think you're assuming a bit too much about the layout of
the streets.
If you're on Apple St., there are 4 different directions that you
could walk in order to find Baker. 3 wrong guesses at 2 blocks
each [1 block going, 1 block returning] and it could take you 7
blocks to find Baker.
From Baker you only have 3 choices, so 2 wrong guesses at 2 blocks
each and 1 right guess is 5 blocks.
From Charles you only have 3 choices, so 2 wrong guesses at 2 blocks
each and 1 right guess is 5 blocks.
7+5+5 = 17
|
| 1430.4 | New York or London? | CHEFS::STRANGEWAYS | Andy Strangeways@REO DTN 830-3216 | Wed Jan 29 1997 05:17 | 20 |
| Re .3:
Shaun,
Right. I see what you're saying.
I am assuming that the streets are labeled at each intersection
(otherwise how do you know when you've reached Charles and Dale?) and
that there are at most two directions of a given street from each
intersection (i.e. each named street is a single line or curve, with no
branches)
You, on the other hand, are assuming a square grid of streets. If you
follow your approach and it is possible for (say) six streets to meet
at an intersection, then the maximum distance is a lot higher!
I guess we have to ask Eric to clarify these assumptions.
Andy.
|
| 1430.5 | | BUSY::SLAB | As you wish | Wed Jan 29 1997 10:50 | 28 |
|
RE: .4
Good point about the max number of streets crossing ... I'd ob-
viously assumed 2, allowing for 4 possibilities at each corner.
However, in response to your 1st point, you still might have to
explore every possibility in order to find the 1 correct way,
since you're not sure where the next street crosses the current
1:
Spoiler:
|
|
-----A-----
|
|
-----B-----
|
|
-----C-----
|
|
D
|
| 1430.6 | Sticking to my original answer | CHEFS::STRANGEWAYS | Andy Strangeways@REO DTN 830-3216 | Thu Jan 30 1997 03:36 | 19 |
| Spoilers:
Ah! So you're allowing for the possibility that streets change names
as you go along them in a straight line? e.g.
| | | |
Able | Able | Baker | Charles | Dale
------S---------+---------+------------+--------
| | | |
| | | |
But (leaving aside the view that "Charles and Dale" implies a
perpendicular intersection) my algorithm still works just as long as
the streets are not branched. You still have at most two choices of
which way to go "on Baker", "on Charles" etc.
Andy.
|
| 1430.7 | maybe quicker | 22603::BUCHANAN | the rolling stone catches the worm | Thu Jan 30 1997 06:12 | 12 |
| Simplest set of assumptions:
* we're talking about a square grid,
* the streets are all labeled at every junction,
* the streets don't change names as you walk along them
Then the answer would be 7, not 9. The reason is that right at the
beginning, we can see whether we're already on Dale or not. If not,
then we know that after reaching Cable that there's only one direction
that Dale could be.
Cheers,
Andrew.
|
| 1430.8 | | BUSY::SLAB | As you wish | Thu Jan 30 1997 13:53 | 4 |
|
I was assuming that an intersection could consist of 4 streets
meeting at that point, not 2 streets crossing at that point.
|
| 1430.9 | | BUSY::SLAB | As you wish | Thu Jan 30 1997 18:29 | 8 |
|
Assuming that an intersection is 2 streets crossing and not 4
streets meeting, then I agree with .7.
From BC, you have no choice as to which way to go to get to CD.
|
| 1430.10 | tardy getting off the bus | 22603::BUCHANAN | the rolling stone catches the worm | Fri Jan 31 1997 05:06 | 23 |
| Taking the .7 model, imagine that we travel to the starting point
by bus (but that it's traveling too fast for us to read the street
signs). If we get out of the bus one block after the official starting
point, then we *reduce* the maximum amount of walking that we have to do, no
matter which direction the bus took us in!
This non-intuitive result is similar to a cookie-finding puzzle in
RUSURE::MATH where a cookie has been hidden somewhere on the real line,
(with normal probability density function). You can start somewhere on
the real line, and then hunt up and down until you locate the cookie.
The goal of the (I believe analytically insoluble) puzzle is to
minimise the expected distance until the cookie is located.
The point is that it's not optimal to start at the middle, where
the cookie is most likely to be. It's best to start on one side of the
bell distribution, and then walk towards the mode.
Returning to Apple, etc: what's the worst case walking distance if
we can choose to get off the bus at some location other than the
official starting point?
Cheers,
Andrew.
|
| 1430.11 | 5 - if I get off the bus late after it turns! | 22603::BUCHANAN | the rolling stone catches the worm | Sat Feb 01 1997 03:56 | 14 |
| If you get off the bus 1 block from the official start, you need to
walk a maximum of 6 blocks.
If you get off the bus 2 blocks from the official start (not two blocks
in a straight line, but diagonally), you need to walk a maximum of 5
blocks!
[This is with the assumptions as in .7. Also, when you get off the
bus, assume that you know the position of the official starting point.]
I think 5 is the best possible.
Cheers,
Andrew.
|
| 1430.12 | More assumptions | CHEFS::STRANGEWAYS | Andy Strangeways@REO DTN 830-3216 | Mon Feb 03 1997 04:37 | 18 |
| Re .11:
>I think 5 is the best possible.
A rash statement. All we need to do is follow the lead of your earlier
note and tighten the assumptions: assume the subway is on the corner of
the (rectangular) city. Then the maximum is 3!
(Note that in this case the directions given are unambiguous, despite
first appearances. Of course, assuming competence and good will on the
part of the friend who gave the directions, we can deduce the answer of
"3" directly without refrence to topography.)
Alternatively, we could seek the maximum across all possible city
layouts. This is bounded only by the number of streets it is physically
possible to fit into one junction.
Andy.
|
| 1430.13 | | CSC32::MACGREGOR | Colorado: the TRUE mid-west | Mon Feb 03 1997 15:10 | 16 |
|
Just to throw more wood on the fire...
Who says that a given street name will travel in a straight line. One
of the places I lived in Boston resulted in my giving the following
directions to get to my house.
... now you are on Tremont street. When you get to the light, take a
left onto Tremont street. After three lights, take a right onto
Tremont street...
8^)
Marc
|
| 1430.14 | | RHETT::MOORE | | Mon Feb 03 1997 15:34 | 14 |
| re .13 --
The same thing is true in Atlanta. Streets change name with
bewildering frequency, sometimes change back, and turn corners
at intersections. For example, near my house you can travel on
Pleasantdale Rd till you get to a certain red light. There you
can turn right on Pleasantdale, left on Tucker-Norcross, or go
straight on Tucker-Norcross. If you go straight two more lights,
you can either turn right on Chamblee-Tucker, or go straight on
Chamblee-Tucker.
Of course, with Atlanta traffic, you can't get anywhere anyways. :)
Martin
|
| 1430.15 | | DYPSS1::s_coghill.dyo.dec.com::CoghillS | Steve Coghill, NSIS Solution Architect | Mon Feb 03 1997 16:03 | 13 |
| It is also common in Ohio to see country roads that do the following:
|
|
|
-----------------------------
|
|
|
Where the jog to the right is about 80 feet.
|