The Manhattan peninsula is one of the five boroughs of New York City. The borough is famous for its skyscrapers, broad avenues, the financial center Wall Street and the many yellow taxis that drive around the district. The streets of Manhattan are laid out in a rectangular grid by the Commissioners' Plan of 1811. The area is intersected by avenues (running north and south) and streets (running east and west).

Consider a rectangular $$s \times a$$ grid that represent part of Manhattan covering $$s$$ streets and $$a$$ avenues. Taxis can refuel at a number of petrol stations located at various intersections. Whenever a taxi is close to running out of gasoline, its driver can read the coordinates of the closest petrol station from his GPS. Due to bad programming, however, there is a bug in the GPS devices of the taxis. If there are multiple "closest" petrol stations at a given intersection, the GPS gets lost, which panics the driver who then causes a car crash. Such intersections are therefore called critical points.

Assignment

In Manhattan, an intersection on a rectangular $$s \times a$$ grid is always represented as a tuple $$(x, y)$$, where $$x, y \in \mathbb{N}$$, $$0 \leq x < s$$ and $$0 \leq y < a$$. The intersection at the top left corner of the grid therefore is at position $$(0, 0)$$, and the intersection at the bottom right corner is at position $$(s-1, a-1)$$. This is also the representation of the intersections as they are used in this exercise.

• In Manhattan, the distance between two intersections $$(x_1, y_1)$$ and $$(x_2, y_2)$$ is computed as \[|x_1 - x_2| + |y_1 - y_2|\,,\] where $$|x|$$ represents the absolute value of $$x$$. This distance is called Manhattan distance (or city block distance) in literature. Write a function manhattanDistance that returns the Manhattan distance between two given intersections. The coordinates of both intersections must be passed as arguments to the function.

• Use the function manhattanDistance to write a function critical that returns a Boolean value indicating whether or not a given intersection is at a critical point. Two arguments must be passed to this function: the coordinates of the intersection that must be evaluated, and a list of intersections at which the petrol stations are located on the $$s \times a$$ grid.

• Write a function manhattan that takes three arguments: i) the number of streets $$s$$, ii) the number of avenues $$a$$, and iii) a list of intersections at which the petrol stations are located on the $$s \times a$$ grid. The function must print a representation of the rectangular grid, in which all intersections are by default represented with an asterisk (*). Intersections having a petrol station are represented with the letter P, and intersections that are at critical points are represented with the letter D.

Example

In the example $$10\times 10$$ grid that is represented in the following interactive Python session, the intersection at position $$(5,0)$$ is an example of a critical point, since there are two petrol stations at Fourth Avenue that are both at distance 4 from the intersection $$(5,0)$$.

>>> manhattanDistance((3, 5), (7, 9))
8
>>> manhattanDistance((12, 5), (3, 16))
20

>>> critical((4, 3), [(1, 8), (4, 3), (6, 3), (6, 5)])
False
>>> critical((7, 4), [(1, 8), (4, 3), (6, 3), (6, 5)])
True

>>> manhattan(10, 10, [(1, 8), (4, 3), (6, 3), (6, 5)])
****D*****
****D***P*
*****D****
*****DD***
***P*DDD**
DDDDD***DD
***PDP****
****D*****
****D*****
****D*****