The Reminiscences of Dr. Watson
During the first week or so we had no callers, and I had begun to think that my companion was as friendless a man as I was myself.Presently, however, I found that he had many acquaintances, and those in the most different classes of society.
There was one little sallow rat-faced, dark-eyed fellow who was introduced to me as Mr. Lestrade, and who came three or four times in a single week.
One morning a young girl called, fashionably dressed, and stayed for half an hour or more.
The same afternoon brought a grey-headed, seedy visitor, who appeared to me to be much excited, and who was closely followed by a slipshod elderly woman.
On another occasion an old white-haired gentleman had an interview with my companion; and on another a railway porter in his velveteen uniform.
When any of these nondescript individuals put in an appearance, Sherlock Holmes used to beg for the use of the sitting-room, and I would retire to my bed-room.
He always apologized to me for putting me to this inconvenience. "I have to use this room as a place of business," he said, "and these people are my clients."
Again I had an opportunity of asking him a point blank question, and again my delicacy prevented me from forcing another man to confide in me.
I imagined at the time that he had some strong reason for not alluding to it, but he soon dispelled the idea by coming round to the subject of his own accord.
It was upon the 4th of March, as I have good reason to remember, that I rose somewhat earlier than usual, and found that Sherlock Holmes had not yet finished his breakfast.
The landlady had become so accustomed to my late habits that my place had not been laid nor my coffee prepared.
With the unreasonable petulance of mankind I rang the bell and gave a curt intimation that I was ready. Then I picked up a magazine from the table and attempted to while away the time with it, while my companion munched silently at his toast.
Suddenly several strong knocks on the door arose me from my stupor. My companion sprang up quickly and opened the door. A very old gentleman stood at the entrance.
Mr. Sherlock Holmes motioned the visitor to the sitting-room and turning to me said "Watson would you be so kind as to follow us?".
A bit intrigued, I inspected the old man carefully; despite his age, he moved confidently and still looked as if he was at the top of his faculties. There was, however, a sadness in his gaze.
"This is Mr. Radnoor" introduced my companion, "and this is Dr. Watson." "If am not mistaken Mr. Radnoor's story is of the particularly unusual sort". Sherlock pointed the visitor to one of the chairs, and we all sat. "Thank you Mr. Holmes." After a short pause and a sigh the old man started his story.
"It all started many many years ago when I was a small boy growing up in Stadford.
I did small jobs for Dr. Cavetar that often carried me all across town.
During one of these assignments I came across a candy shop with the most unusual assortment of candy I had ever seen.
Behind the counter was the prettiest girl I had ever seen as well. Timidly at first, then growing in confidence I ordered this and that candy and soon I had enough for a month. The young lady neatly packed my order and handed it to me with the most beautiful of smiles.
Stuttering, I thanked her and walked away.
In the next few days whenever I ate one of the candies I couldn't dispel the memory of the girl's smile.
I returned often to the store and in due time the beautiful lady became Mrs. Radnoor.
We moved across country, then to India and lived a wonderful life together."
At this point, the old man pulled his handkerchief and wiped away a tear.
"Mrs. Radnoor died a week ago." he explained.
"I have not had a night's sleep since then. I would like to return to the candy shop of my youth were it all started. It has been many years though and my memory is not what it used to be. I do not remember where exactly the shop is located and I thought you could help me."
Sherlock Holmes bent forward and prompted the gentleman "Please do tell us everything you still remember about that shop."
Mr. Radnoor looked pensive before saying "These are the facts I remember:"
- "I do remember that from any given point (x,y) in the city of Statford I could move to the four neighboring (x-1,y), (x,y-1), (x+1,y),(x,y+1) points in a quarter hour.
- I also recall that the ith time I went to the candy shop I went from point (x[i],y[i]) and drove for not more than a quarter hour * L[i].
- The candy shop was located at a point with integer coordinates.
- I never walked more than 5 hours-this happened on the day I asked Mrs. Radnoor to marry me- (i.e. L[i] was at most 20).
- The coordinates (x[i],y[i]) are within the rectangle (-20, 20), i.e. -20<=x[i], y[i]<= 20).
- Dr. Cavetar's office was at (0,0).
Sherlock Holmes rose and guaranteed to Mr. Radnoor that he would have a solution with the number of possible locations as well as corresponding paths from the starting position to those candy shop locations by next day. The gentleman's eyes glinted with gratitude and he thanked my companion profusely.
"What do you make of it, Watson?".
"Well, lets say he did one visit to the candy shop and walked for at most a quarter hour. We know that he either didn't move, in which case the candy shop would be at Dr. Cavetar's office or he moved once in which case the candy shop could be at (1,0),(0,1),(-1,0),(0,-1). I.e. the candy shop could be at 5 different locations.
If he walked for at most half an hour, then besides these 5 locations he could have from each of the one step locations reached 8 more making it 13 locations. That is an awful lot of locations. How do you think we can help him?".
 |
| Dr. Watson second example: 13 locations for the candy shop. The paths in red take half an hour to reach from (0,0). The paths in black take only a quarter of an hour. |
"Do not be so pessimistic Watson. The case can be less complicated. Lets imagine Mr. Radnoor starts at point (2,1) in his first visit and walks at most half an hour. Then we have 13 possible locations as you pointed out. In his second visit lets say he starts at (3,-1) and also walks at most half an hour. Then among the 13 possible locations from (2,1) only those that are reachable from (3,-1) are possible locations for the shop. There are only 4 locations like that: (2,-1), (3,0), (3,1) and (2,0)."
 |
| Sherlock example: There are only 4 possible locations for the candy shop. (3,1) and (2,0) takes a quarter of an hour to reach from (2,1) but half an hour from (3,-1). On the contrary (2,-1) and (3,0) takes a quarter of an hour to reach from (3,-1) but half an hour from (2,1). |
"Exactly my dear Watson. How to solve the problem in general you may ask. To find the number of possible locations of the candy shop is elementary. Here it is the thought process:
- Let (csx, csy) be the location of the candy shop (these are integers!). The maximum values of csx and csy are (x[i],y[i]) + L[i] since at most the gentleman moves L[i] units. Since x[i],y[i] and L[i] can at most be 20, this comes to a maximum value of 40.
- Similarly the minimum value of csx,csy will be -40 (when x[i]= -20 or/and y[i]=-20 and L[i]=20 and we move 20 steps in the negative direction).
- So we can consider every single point inside or on the boundary of the rectangle -40, 40 as a candidate for the candy shop location.
- For each such point (csx,csy) in the rectangle, lets define the distance between the candy shop and (x[i],y[i]) as abs(x[i]-csx)+abs(y[i]-csy). This is really the number of quarter hours Mr. Radnoor walks from (x[i],y[i]). We know this number is at most L[i].
- (csx,csy) will only be a valid location if this distance (which is called the Manhattan distance) is smaller or equal than L[i] for every i."
def countPossibleLocations(self, P, L):
count = 0
candy_shop_locations = []
for csx in range(-41,41):
for csy in range(-41, 41):
possible = True
# For each possible (csx,csy) compute the Manhattan distance to
# each point (x[i],y[i]). If that distance is <= than L[i]
# for every (x[[i],y[i]) then (csx,csy) is a possible location
for i in range(0, len(P)):
manhattan = abs(P[i][0] - csx) + abs(P[i][1] - csy)
possible = possible and (manhattan <= L[i])
if possible:
count += 1
candy_shop_locations.append((csx,csy))
return count,candy_shop_locations
Notice how we store the coordinates of the possible candy shop locations in a list that is also returned by this method.
To find the paths that lead from each starting point (x[i],y[i]) to each (csx,csy) candy shop possible location in at most L[i] number of steps is also elementary: The Manhattan distance between (csx,csy) and a starting point is the shortest distance between those two points. We know from the discussion above that this distance is always <=L[i].
A possible path from (x[i],y[i]) with this length is to move along say the x direction until the x coordinate matches csx and then move along the y direction until the y coordinate matches csy.
The only other detail we need to pay attention is that if csx is to the left of x[i] we need to move left otherwise we move right. Similarly for csy and y[i] (up or down).
In Python
def findPaths(self,Cs,P):
paths = []
for i in range(0,len(P)):
for j in range(0,len(Cs)):
path = []
# move left
if Cs[j][0]< P[i][0]:
stepx = -1
# move right
else:
stepx = 1
stepsx = 0
path.append([P[i][0],P[i][1]])
#go along the x axis until Cs[j][0] and P[i][0] match
for x in range(0,abs(Cs[j][0]-P[i][0])):
stepsx += stepx
path.append([P[i][0]+stepsx,P[i][1]])
# move down
if Cs[j][1]< P[i][1]:
stepy = -1
# move up
else:
stepy = 1
stepsy = 0
#go along the y axis until Cs[j][1] and P[i][1] match
for y in range(0,abs(Cs[j][1]-P[i][1])):
stepsy += stepy
path.append([P[i][0] + stepsx,P[i][1]+stepsy])
paths.append(path)
return paths
For example for the example that you talked about before Watson where the starting locations (x[[i],y[i]) and the maximum number of steps L[i] are [(2, 1), (3, -1), (5, 0)] num of steps [2, 2, 3]The possible candy shop locations are
Locations [(2, 0), (3, 0), (3, 1)]And the possible shortest paths as computed by the method above will be
Possible paths [[2, 1], [2, 0]] [[2, 1], [3, 1], [3, 0]] [[2, 1], [3, 1]] [[3, -1], [2, -1], [2, 0]] [[3, -1], [3, 0]] [[3, -1], [3, 0], [3, 1]] [[5, 0], [4, 0], [3, 0], [2, 0]] [[5, 0], [4, 0], [3, 0]] [[5, 0], [4, 0], [3, 0], [3, 1]]The first, third and fifth paths takes only a quarter hour (one step).
The second, fourth, sixth and eighth paths take half an hour (2 steps).
The seventh and ninth paths take three quarters of an hour (3 steps).
One final point is that these paths are not the only possible shortest paths.
They always follow first along the x axis then along the y axis.
Another possibility would be to always start along the y axis and once the y coordinates match start moving along the x axis.
And many other shortests paths exist that result from moving sometimes along the x axis sometimes along the y axis in a non predictable way (Mr. Radnoor could move in a random direction each step as long as he goes from (x[i],y[i]) to (csx,csy).
Gathering all the pieces we have the following Python code
No comments:
Post a Comment