In a certain region, there are a number of hospitals that are situated in a close range from one another. The competition between these hospitals is lethal, and that is to be taken literally. Patients that are transported by ambulance, are not always brought to the nearest hospital. Consequentially, valuable time is lost, sometimes with lethal consequences. The local authorities want to put an end to this, and have put out a new rule that obliges the paramedics to bring their patients to the nearest hospital. In order to do so, a map must be constructed dividing the region in zones with one hospital per zone.

The authorities are asking you to make a division of a region, so that the nearest hospital on every point of a zone is always the only hospital situated in that zone. The individual hospitals, however, want to keep their sphere of influence as large as possible, and therefore, there is a lot of discussion about the way in which the distance between two points must be calculated. The table below contains a number of possible definitions the hospitals propose in order to calculate the distance between two points $$(x_1, y_1)$$ en $$(x_2, y_2)$$.

Assignment

Consider a rectangular region in which a number of hospitals are situated. We have divided this region in square cells that form a grid, so that each cell contains one hospital at the most. The rows and columns of the grid are respectively numbered from tow to bottom and from left to right, starting from 0. The cells of teh grid in which the hospital is situated, is marked with a (unique) uppercase letter and the remainder is marked with a full stop. The positions of the hospital can no be represented by a map of the following format:

......B..
.........
...A.....
.........
.......D.
.........
.C.......
.....E...
.........

The position of a cell in the grid is represented by a tuple $$(r, k)$$. Here, $$r$$ is the row number and $$k$$ is the column number for a cell in the grid. Asked: 

• Write three functions euclideanDistance, manhattanDistance and chessboardDistance that correspond with the concepts of the same name for the word distance as it is defined in the above table. To each of these functions, two mandatory arguments must be passed. Every argument is a tuple of 2 integers that represent the $$x$$ and $$y$$ co-ordinate of a point in the surface. As a result, these function must print the distance between the two given points as an integer, corresponding to the definitions of distance in the above table.

• Write a function positions to which the name of a text file must be passed. This text file must represent the positions of the hospitals in a certain region, in accordance with the format that was described above. The function must print a tuple of three elements, the first two of which respectively indicate the number of rows an columns of the rectangle grid in which the region was divided. The position of a hospital here corresponds with the position of a cell in the grid in which the hospital is situated.

• Write a function nearest with which the nearest hospital can be determined from a given point to this function, two arguments must be passed to this function: the position of the cell in which the given point is situated and a dictionary that contains the positions of the hospitals in the regions. This dictionary must have the same format as the dictionaries that are printed by the function positions (as third element of the tuple). In order to determine the distance between a given point and a hospital, a distance function should be used to which two cell positions in the grid must be given an that prints an integer that represents the distance between these two cells. The function euclideanDistance must be used as a standard, but the function nearest also has a third optional parameter distance to which an alternative distance function can be given. The function must print the uppercase letter that is used to mark the hospital that is closest to the given point. If the given point is on an equal distance from two or more hospitals, the upper case letter that alphabetically comes firs, must be printed.

• Write a function zones to which the name of a text file must be given. This text file must represent the position of the hospitals in a certain region, according to the format that is described above. For every cell in the grid that is marked with a full stop, the function must determine the uppercase letter of the nearest hospital (cf. function nearest) and print the corresponding lowercase letter in the position of the full stop. By default, the result must be printed by the function. However, is a second file name is given to the function, the function must pass the result to a file with the given name. The function also has a third, optional parameter distance, that is used in the same way as the parameter with the same name in the function nearest.

Example

In the example session below, we assume that the file hospitals.txt¹ is situated in the current directory.

>>> euclideanDistance((0, 0), (3, 4))
5.0
>>> manhattanDistance((0, 0), (3, 4))
7.0
>>> chessboardDistance((0, 0), (3, 4))
4.0

>>> positions('hospitals.txt')
(9, 9, {(0, 6): 'B', (4, 7): 'D', (7, 5): 'E', (2, 3): 'A', (6, 1): 'C'})

>>> nearest((0, 0), {(0, 6): 'B', (4, 7): 'D', (7, 5): 'E', (2, 3): 'A', (6, 1): 'C'})
'A'
>>> nearest((8, 8), {(0, 6): 'B', (4, 7): 'D', (7, 5): 'E', (2, 3): 'A', (6, 1): 'C'}, distance=manhattanDistance)
'E'

>>> zones('hospitals.txt')
aaaabbBbb
aaaaabbbb
aaaAaabdd
aaaaaaddd
ccaaaddDd
cccceeddd
cCcceeedd
ccceeEeee
ccceeeeee
>>> zones('hospitals.txt', distance=manhattanDistance)
aaaabbBbb
aaaaabbbb
aaaAaabdd
aaaaaaddd
ccaaaddDd
cccaeeddd
cCcceeedd
ccceeEeee
ccceeeeee
>>> zones('hospitals.txt', distance=chessboardDistance)
aaaaabBbb
aaaaabbbb
aaaAaabbb
aaaaaaddd
caaaaadDd
ccccedddd
cCcceeedd
cccceEeed
cccceeeee
>>> zones('hospitals.txt', 'zones.txt')