Computational Thinking Project: Where should we put the Pokestops?
Niantic is paying you big bucks to come up with an algorithm that helps them dynamically determine where Poke-stops should be located on a map. The information available will be the population density at each cell on the map, and the number of stops that should be on that map. The objective is to place the stops at cells where they are as near to as many people as possible so that it is convenient for them to visit the stops.
Problem statement:
Inputs to your algorithm:
- Map showing population density at each cell
- Number of stops that Niantic wants on this map
Output.
- Your algorithm is expected to make recommendations as to where the stops should be placed on the map, and return the coordinates of these cells. The "quality" of your recommended stops will be scored (details about scoring later).
Here is an example of a 15-celled map with population density indicated in each cell. We shall call this small map map0:
|
|
0
|
1
|
2
|
3
|
4
|
|
0
|
2
|
5
|
5
|
1
|
3
|
|
1
|
8
|
4
|
4
|
0
|
2
|
|
2
|
1
|
5
|
2
|
0
|
6
|
All maps will be rectangular (i.e. each row has the same number of columns), and the upper-leftmost cell of the map is always the origin (0, 0). We will also use (y, x) instead of the traditional (x, y) to indicate the position of a particular cell on the map;the population densities at cells (1, 2) and (2, 1) in map0are 4 and 5 respectively.
Your task:
Your challenge is to come up with a get_pokestops method that returns selected stops that produce a low score (the lower the better) for different maps and number of stops.
Attachment:- Project.zip